0
$\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
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\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 Sep 11 at 1:15
  • $\begingroup$ Yes, see Constrained maximin models in the same Wikipedia article. $\endgroup$ – RobPratt Sep 11 at 1:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.