Main.MiniMax History

Hide minor edits - Show changes to output

November 22, 2013, at 10:47 AM 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 [[http://en.wikipedia.org/wiki/APMonitor | APMonitor Modeling Language]]. To solve this simple example problem, select the link below:
November 22, 2013, at 10:43 AM 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 10:41 AM 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 10:36 AM 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

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

[[http://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 10:22 AM by 69.169.137.17 -
Changed lines 22-23 from:
[[http://apmonitor.com/online/view_pass.php?f=minimax.apm | Example #1: Solve minimax Optimization Problem]]
to:
[[http://apmonitor.com/online/view_pass.php?f=minimax.apm | Example #1: Click to Solve minimax Optimization Problem]]
Changed line 32 from:
[[http://apmonitor.com/online/view_pass.php?f=minimax_integer.apm | Example #2: Solve minimax Problem with Integer Variables]]
to:
[[http://apmonitor.com/online/view_pass.php?f=minimax_integer.apm | Example #2: Click to Solve minimax Problem with Integer Variables]]
November 22, 2013, at 10:21 AM 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 10:19 AM by 69.169.137.17 -
Changed lines 22-23 from:
[[http://apmonitor.com/online/view_pass.php?f=minimax.apm | Solve minimax Optimization Problem]]
to:
[[http://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:
[[http://apmonitor.com/online/view_pass.php?f=minimax.apm | Attach:minimax_solution.png]]
Changed lines 34-35 from:
[[http://apmonitor.com/online/view_pass.php?f=minimax.apm | Solve minimax Optimization Problem]]
to:
[[http://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:
[[http://apmonitor.com/online/view_pass.php?f=minimax_integer.apm | Attach:minimax_integer_solution.png]]
November 22, 2013, at 10:16 AM 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.

[[http://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 09:26 AM 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:

[[http://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 09:15 AM 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 = 'http://' + 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="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
    <a href="http://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>
(:htmlend:)
GlossyBlue theme adapted by David Gilbert
Powered by PmWiki