Minimax and Maximin Optimization

Main.MiniMax History

Hide minor edits - Show changes to output

October 28, 2020, at 02:32 PM by 136.36.211.159 -
Changed lines 102-104 from:


To require that the variables have an integer value, the prefix
''int'' is added to APMonitor.
to:
In [[https://gekko.readthedocs.io/en/latest/|Python Gekko]] an integer solution can be obtained with ''integer=True'' and by switching to the APOPT solver with ''m.options.solver=1''.

(:source lang=python:)
from gekko import GEKKO
m = GEKKO(remote=False)
x1,x2,x3,Z = m.Array(m.Var,4,integer=True)
m.Minimize(Z)
m.Equation(x1+x2+x3==16)
m.Equations([Z>=x1,Z>=x2,Z>=x3])
m.options.solver=1
m.solve()
print('x1: ',x1.value[0])
print('x2: ',x2.value[0])
print('x3: ',x3.value[0])
print('Z:  ',Z.value[0])
(:sourceend:)

Valid solutions are any combination of 15,15,16. To require that the variables have an integer value in APMonitor, the prefix ''int'' is added
.
October 28, 2020, at 01:45 PM by 136.36.211.159 -
Added line 29:
m.Equation(x1+x2+x3==15)
Changed lines 100-104 from:
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.
to:
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.



To require that the variables have an integer
value, the prefix ''int'' is added to APMonitor.
October 28, 2020, at 01:19 PM by 136.36.211.159 -
Changed lines 61-63 from:
The maximin optimization solution is now a maximization problem with additional inequality constraints with Z.

[[https://gekko.readthedocs.io/en/latest/|Python Gekko]] solves the minimax problem.
to:
The maximin optimization solution is now a maximization problem with additional inequality constraints with Z. [[https://gekko.readthedocs.io/en/latest/|Python Gekko]] also solves the maximin problem.
October 28, 2020, at 01:18 PM by 136.36.211.159 -
Changed lines 12-13 from:
 s.t.   x1 + x2 + x3 = 15
to:
 s.t. x1 + x2 + x3 = 15
Changed lines 44-45 from:
The value of Z is not exactly equal to 5. This is because of small numerical errors from the optimizer. The optimizer reports a successful solution when a precision tolerance is met.
to:
The value of Z is not exactly equal to 5. This is because of small numerical errors from the IPOPT optimizer. The optimizer reports a successful solution when a precision tolerance is met.
Deleted lines 50-54:
 s.t.    x1 + x2 + x3 = 15

The maximin problem is likewise transformed with an additional variable ''Z'' but that is a lower bound for each of the individual variables (x1, x2, and x3).

 max Z
Added lines 52-56:

The maximin problem is likewise transformed with an additional variable ''Z''. However, ''Z'' is now a lower bound for each of the individual variables (x1, x2, and x3).

 max Z
 s.t. x1 + x2 + x3 = 15
Changed lines 61-63 from:
The maximin optimization solution is now a minimization with additional inequality constraints with Z.

to:
The maximin optimization solution is now a maximization problem with additional inequality constraints with Z.

[[https://gekko.readthedocs.io/en/latest/|Python Gekko]] solves the minimax problem.

(:source lang=python:)
from gekko import GEKKO
m = GEKKO(remote=False)
m.options.SOLVER = 1
x1,x2,x3,Z = m.Array(m.Var,4)
m.Maximize(Z)
m.Equation(x1+x2+x3==15)
m.Equations([Z<=x1,Z<=x2,Z<=x3])
m.solve()
print('x1: ',x1.value[0])
print('x2: ',x2.value[0])
print('x3: ',x3.value[0])
print('Z:  ',Z.value[0])
(:sourceend:)

The solution is that all of the variables are equal to 5 to maximize the minimum value. The sum of the variables must equal 15 so this is same optimal solution as the minimax problem.

  x1:  5.0
  x2:  5.0
  x3:  5.0
  Z:  5.0

The value of Z is now exactly equal to 5. This is because of the switch to the ''APOPT'' optimizer ''(m.options.SOLVER=1)'' that is an active-set SQP optimizer as opposed to the [[Main/InteriorPointMethod|interior point]] IPOPT optimizer that uses a barrier function.
October 28, 2020, at 01:10 PM by 136.36.211.159 -
Changed line 85 from:
!!!! Mixed Integer Nonlinear Programming (MINLP) Solvers
to:
!!!! Mixed Integer Nonlinear Programming (MINLP)
October 28, 2020, at 01:10 PM by 136.36.211.159 -
Changed lines 5-6 from:
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:
to:
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. A maximin problem maximizes the minimum value. It is used to maximize the minimum objective (such as profit or revenue) for all potential scenarios.

!!!! Minimax

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:
Changed lines 14-15 from:
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).
to:
The minimax problem is transformed for efficient solution by gradient-based optimization solvers that require continuous first and second derivatives. Posing the problem in this way allows rapid convergence to a solution. The minimax problem can be alternatively expressed by minimizing an additional variable ''Z'' that is an upper bound for each of the individual variables (x1, x2, and x3).
Changed lines 22-67 from:
The solution to this problem can be determined by expressing the optimization problem in the [[https://en.wikipedia.org/wiki/APMonitor | APMonitor Modeling Language]]. To solve this simple example problem, select the link below:
to:
The minimax optimization solution is now a minimization with additional inequality constraints with Z. [[https://gekko.readthedocs.io/en/latest/|Python Gekko]] solves the minimax problem.

(:source lang=python:)
from gekko import GEKKO
m = GEKKO(remote=False)
x1,x2,x3,Z = m.Array(m.Var,4)
m.Minimize(Z)
m.Equations([Z>=x1,Z>=x2,Z>=x3])
m.solve()
print('x1: ',x1.value[0])
print('x2: ',x2.value[0])
print('x3: ',x3.value[0])
print('Z:  ',Z.value[0])
(:sourceend:)

The solution is that all of the variables are equal to 5 to minimize the maximum value. The sum of the variables must equal 15 so this is optimal solution.

  x1:  5.0
  x2:  5.0
  x3:  5.0
  Z:  4.9999999901

The value of Z is not exactly equal to 5. This is because of small numerical errors from the optimizer. The optimizer reports a successful solution when a precision tolerance is met.

!!!! Maximin

Suppose that we instead want to maximize the minimum of 3 variables and the sum of those variables must add up to 15. This problem is posed as:

 max min(x1,x2,x3)
 s.t.    x1 + x2 + x3 = 15

The maximin problem is likewise transformed with an additional variable ''Z'' but that is a lower bound for each of the individual variables (x1, x2, and x3).

 max Z
 s.t. x1 + x2 + x3 = 15
      Z <= x1
      Z <= x2
      Z <= x3

The maximin optimization solution is now a minimization with additional inequality constraints with Z.



!!!! Solve Minimax Problem Online

The solution to Minimax problem can be determined by expressing the optimization problem in the [[https://en.wikipedia.org/wiki/APMonitor | APMonitor Modeling Language]] and solved through a web browser. To solve this simple example problem, select the link below:
June 21, 2020, at 04:44 AM by 136.36.211.159 -
Deleted lines 59-77:

----

(:html:)
 <div id="disqus_thread"></div>
    <script type="text/javascript">
        /* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */
        var disqus_shortname = 'apmonitor'; // required: replace example with your forum shortname

        /* * * DON'T EDIT BELOW THIS LINE * * */
        (function() {
            var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
            dsq.src = 'https://' + disqus_shortname + '.disqus.com/embed.js';
            (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
        })();
    </script>
    <noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
    <a href="https://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>
(:htmlend:)
April 12, 2017, at 03:25 PM by 10.5.113.121 -
Changed line 44 from:
 max min (x1 + x2 + x3)
to:
 max min (x1,x2,x3)
March 17, 2017, at 02:10 PM by 86.91.137.35 -
Changed line 7 from:
 min max (x1 + x2 + x3)
to:
 min max(x1,x2,x3)
November 22, 2013, at 05:47 PM by 69.169.137.17 -
Changed lines 5-6 from:
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 could be posed as:
to:
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:
Changed lines 10-11 from:
This tutorial covers a method to pose 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 posed by maximizing an additional variable ''Z'' that is an upper bound for each of the individual variables.
to:
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).
Changed line 18 from:
The solution to this problem can be determined by posing the optimization problem as this minimax problem in the APMonitor Modeling Language. To solve this simple example problem, select the link below:
to:
The solution to this problem can be determined by expressing the optimization problem in the [[https://en.wikipedia.org/wiki/APMonitor | APMonitor Modeling Language]]. To solve this simple example problem, select the link below:
November 22, 2013, at 05:43 PM by 69.169.137.17 -
Changed lines 26-27 from:
!!! Integer Solution to Minimax Problem
to:
!! Integer Solution to Minimax Problem
Changed lines 36-40 from:
!!! Maximin Optimization Problem
to:
!!!! 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
November 22, 2013, at 05:41 PM by 69.169.137.17 -
Deleted lines 4-5:
!!!! Minimax Optimization Tutorial
Changed lines 10-11 from:
This tutorial covers a method to pose 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 posed as:
to:
This tutorial covers a method to pose 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 posed by maximizing an additional variable ''Z'' that is an upper bound for each of the individual variables.
Changed lines 26-27 from:
!!!! Integer Solution to Minimax Problem
to:
!!! Integer Solution to Minimax Problem
Changed lines 36-37 from:
!!!! Maximin Optimization Problem
to:
!!! Maximin Optimization Problem
Changed lines 43-44 from:
The minimax problem can be alternatively posed as:
to:
The minimax problem can be alternatively posed by maximizing an additional variable ''Z'' that is a lower bound for each of the individual variables.
Changed line 55 from:
Solving the maximin problem 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.
to:
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.
November 22, 2013, at 05:36 PM by 69.169.137.17 -
Added lines 37-57:

!!!! 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 as:

 max Z
 s.t. x1 + x2 + x3 = 17
      Z <= x1
      Z <= x2
      Z <= x3

[[https://apmonitor.com/online/view_pass.php?f=maximin_integer.apm | Example #3: Click to Solve maximin Problem with Integer Variables]]

[[https://apmonitor.com/online/view_pass.php?f=maximin_integer.apm | Attach:maximin_integer_solution.png]]

Solving the maximin problem 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.
November 22, 2013, at 05:22 PM by 69.169.137.17 -
Changed lines 22-23 from:
[[https://apmonitor.com/online/view_pass.php?f=minimax.apm | Example #1: Solve minimax Optimization Problem]]
to:
[[https://apmonitor.com/online/view_pass.php?f=minimax.apm | Example #1: Click to Solve minimax Optimization Problem]]
Changed line 32 from:
[[https://apmonitor.com/online/view_pass.php?f=minimax_integer.apm | Example #2: Solve minimax Problem with Integer Variables]]
to:
[[https://apmonitor.com/online/view_pass.php?f=minimax_integer.apm | Example #2: Click to Solve minimax Problem with Integer Variables]]
November 22, 2013, at 05:21 PM by 69.169.137.17 -
Deleted lines 23-24:
Alternatively, the solution is shown below and results in all variables being equal to a value of 5. This solution is the minimum possible solution out of the maximum of all variables x1, x2, and x3.
Changed lines 26-27 from:
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).
to:
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).
Deleted lines 33-34:
Solving the problem with the modified variable names gives a numerical solution of x1 = 5, x2 = 6, x3 = 5. There are actually three potential solutions with one of the variables being equal to 6 while the others are equal to 5.
Added lines 35-36:

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.
November 22, 2013, at 05:19 PM by 69.169.137.17 -
Changed lines 22-23 from:
[[https://apmonitor.com/online/view_pass.php?f=minimax.apm | Solve minimax Optimization Problem]]
to:
[[https://apmonitor.com/online/view_pass.php?f=minimax.apm | Example #1: Solve minimax Optimization Problem]]
Changed lines 26-27 from:
Attach:minimax_solution.png
to:
[[https://apmonitor.com/online/view_pass.php?f=minimax.apm | Attach:minimax_solution.png]]
Changed lines 34-35 from:
[[https://apmonitor.com/online/view_pass.php?f=minimax.apm | Solve minimax Optimization Problem]]
to:
[[https://apmonitor.com/online/view_pass.php?f=minimax_integer.apm | Example #2: Solve minimax Problem with Integer Variables]]
Changed line 38 from:
Attach:minimax_integer_solution.png
to:
[[https://apmonitor.com/online/view_pass.php?f=minimax_integer.apm | Attach:minimax_integer_solution.png]]
November 22, 2013, at 05:16 PM by 69.169.137.17 -
Added lines 29-38:

!!!! 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.

[[https://apmonitor.com/online/view_pass.php?f=minimax.apm | Solve minimax Optimization Problem]]

Solving the problem with the modified variable names gives a numerical solution of x1 = 5, x2 = 6, x3 = 5. There are actually three potential solutions with one of the variables being equal to 6 while the others are equal to 5.

Attach:minimax_integer_solution.png
November 22, 2013, at 04:26 PM by 69.169.137.17 -
Changed lines 20-24 from:
The solution to this problem is:

* x1 = 5
* x2 = 5
* x3 = 5
to:
The solution to this problem can be determined by posing the optimization problem as this minimax problem in the APMonitor Modeling Language. To solve this simple example problem, select the link below:

[[https://apmonitor.com/online/view_pass.php?f=minimax.apm | Solve minimax Optimization Problem]]

Alternatively, the solution is shown below and results in all variables being equal to a value of 5. This solution is the minimum possible solution out of the maximum of all variables x1, x2, and x3.

Attach:minimax_solution.png

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).
November 22, 2013, at 04:15 PM by 69.169.137.17 -
Added lines 1-43:
(:title Minimax and Maximin Optimization:)
(:keywords minimax, min-max, maximin, max-min, maximum, minimum, optimization:)
(:description Tutorial on minimizing the maximum as a minimax (min-max) problem. This also applies to maximizing the minimum as a maximin (max-min) optimization problem.:)

!!!! Minimax Optimization Tutorial

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 could be posed as:

 min max (x1 + x2 + x3)
 s.t.    x1 + x2 + x3 = 15

This tutorial covers a method to pose 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 posed as:

 min Z
 s.t. x1 + x2 + x3 = 15
      Z >= x1
      Z >= x2
      Z >= x3

The solution to this problem is:

* x1 = 5
* x2 = 5
* x3 = 5

----

(:html:)
 <div id="disqus_thread"></div>
    <script type="text/javascript">
        /* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */
        var disqus_shortname = 'apmonitor'; // required: replace example with your forum shortname

        /* * * DON'T EDIT BELOW THIS LINE * * */
        (function() {
            var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
            dsq.src = 'https://' + disqus_shortname + '.disqus.com/embed.js';
            (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
        })();
    </script>
    <noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
    <a href="https://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>
(:htmlend:)