What does min max in optimization problems mean?

Question

With $A$ and $B$ being different decision variables, does $$\min_{A} \max_{B}$$ in front of an objective function specify a specific order of optimization? In other words, is it saying "minimize $A$ while maximizing $B$", or "minimize $A$ while holding the maximized $B$ fixed", or something else?

What if the places are swapped, or some other combination?

$$\max_B \min_A$$

Finally, can the min-max prefix appear for any sort of optimization problem, i.e. quadratic programming (convex optimization), linear programming, dynamic programming? How does it differ from "minimax"?

score 7 · Accepted Answer · answered Sep 11 '20 at 01:12

7

The notation $\min\limits_A \max\limits_B f(A,B)$ does not mean to minimize $A$ or maximize $B$. It means that, for each fixed value of $A$, you find a $B$ value that maximizes $f(A,B)$, and you find a value of $A$ that minimizes that maximum value. If it helps, you can think of the "inner problem" as $g(A) = \max\limits_B f(A,B)$, and then the "outer" problem is $\min\limits_A g(A)$. It is also called a minimax problem. Yes, you can interchange the roles to obtain a maximin problem. More generally, you can have an arbitrary combination of any number of $\min$ and $\max$ operators.

answered Sep 11 '20 at 01:12

RobPratt

45,619

can the min-max prefix appear for any sort of optimization problem, i.e. quadratic programming (convex optimization), linear programming, dynamic programming? – develarist Sep 11 '20 at 01:15
Yes, see Constrained maximin models in the same Wikipedia article. – RobPratt Sep 11 '20 at 01:20

What does min max in optimization problems mean?

1 Answers1