A minimax problem seeks to minimize the maximum value of a number of decision variables. It is sometimes applied to minimize the possible loss for a worst case (maximum loss) scenario. For example, suppose that we want to minimize the maximum of 3 variables and the sum of those variables must add up to 15. This problem is posed as:
min max(x1,x2,x3) s.t. x1 + x2 + x3 = 15
This tutorial covers a method to reformulate a minimax (or maximin) problem for gradient-based optimization solvers that require continuous first and second derivatives. Posing the problem in this way allows rapid convergence to a solution with large-scale linear or nonlinear programming solvers. From the example above, the minimax problem can be alternatively expressed by maximizing an additional variable Z that is an upper bound for each of the individual variables (x1, x2, and x3).
min Z s.t. x1 + x2 + x3 = 15 Z >= x1 Z >= x2 Z >= x3
The solution to this problem can be determined by expressing the optimization problem in the APMonitor Modeling Language. To solve this simple example problem, select the link below:
The solution is shown above with all variables being equal to a value of 5. This solution is the minimum possible solution out of the maximum of all variable (x1, x2, x3) combinations. The additional slack variables are automatically added to the model to transform the inequality constraints (e.g. Z >= x1) into equality constraints (e.g. Z = x1 + slk, slk >= 0).
Integer Solution to Minimax Problem
Suppose that the variables in the above example problem are required to be integer (1, 2, 3, etc) values instead of continuous values. In this case, the solution would be the same because the continuous problem has an integer solution. However, if the sum of the variables (x1 + x2 + x3) were set equal to 16 instead of 15, the solution would be different. In order to require that the variables have an integer value, the prefix int is added.
Solving the problem with the modified variable names gives a numerical solution of x1 = 5, x2 = 6, x3 = 5. There are three potential solutions with one of the variables being equal to 6 while the others are equal to 5.
Mixed Integer Nonlinear Programming (MINLP) Solvers
Selecting a solver that does not handle integer variables (such as IPOPT) results in a relaxed continuous variable solution because the integer variable requirements are ignored. Selecting a mixed integer nonlinear programming (MINLP) solver such as APOPT will attempt to find an integer solution.
Maximin Optimization Problem
The maximin problem is similar to the minimax problem but it seeks to maximize the minimum of all available options.
max min (x1,x2,x3) s.t. x1 + x2 + x3 = 17
The minimax problem can be alternatively posed by maximizing an additional variable Z that is a lower bound for each of the individual variables.
max Z s.t. x1 + x2 + x3 = 17 Z <= x1 Z <= x2 Z <= x3
Solving the maximin problem with integer variables gives a numerical solution of x1 = 6, x2 = 6, x3 = 5. There are three potential solutions with one of the variables being equal to 5 while the others are equal to 6.
comments powered by Disqus