3
$\begingroup$

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"?

$\endgroup$

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ can the min-max prefix appear for any sort of optimization problem, i.e. quadratic programming (convex optimization), linear programming, dynamic programming? $\endgroup$
    – develarist
    Commented Sep 11, 2020 at 1:15
  • $\begingroup$ Yes, see Constrained maximin models in the same Wikipedia article. $\endgroup$
    – RobPratt
    Commented Sep 11, 2020 at 1:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .