23
$\begingroup$

I can't understand why max min of a function is less than equal to min max of that function i.e
Why $$\underset{x}{\text{max}}\:\underset{y}{\text{min}} f(x,y) \leq \underset{y}{\text{min}}\:\underset{x}{\text{max}}f(x,y)$$
Here $x,y \in \mathbb{R}$ and $f(x,y)\in \mathbb{R}$
Moreover, I don't understand intuitively what is the effect of just changing the order of max and min.
Suppose $(\hat{x},\hat{y})$ is the solution of $\underset{x}{\text{max}}\:\underset{y}{\text{min}} f(x,y)$, then why this is not the same solution for $\underset{y}{\text{min}}\:\underset{x}{\text{max}}f(x,y)$.
One more thing I want to know is do we evaluate inner optimization first or outer ? i.e in $\underset{x}{\text{max}}\:\underset{y}{\text{min}} f(x,y)$, do we evaluate $\underset{y}{\text{min}}$ first or $\underset{x}{\text{max}}$ first ?

$\endgroup$
  • 1
    $\begingroup$ It's a difficult matter. John Forbes Nash has won a Nobel prize for a general theorem about min-max-problems. $\endgroup$ – Christian Blatter Aug 25 '12 at 14:18
  • 1
    $\begingroup$ $\max_x \min_y f(x,y) = \max_x \left( \min_y f(x,y) \right)$, i.e. the maximum (with respect to $x$) of the minimum (with respect to $y$) of $f(x,y)$. It's usually kind of hard to evaluate the outer optimization without first evaluating the inner, since you need to evaluate the inner one just to know what the outer one is supposed to be optimizing. Of course, sometimes one can find clever ways to skip or delay the inner optimization, but those cases are the exception, not the rule. $\endgroup$ – Ilmari Karonen Aug 26 '12 at 17:00
  • 4
    $\begingroup$ An intuitive explanation: Think about this as a two-player game. The goal for player $x$ is to make $f(x,y)$ as small as possible and player $y$ to make it big. The left-hand side is the case where $x$ gets to move first, the right-hand side is where $y$ moves first. The inequality shows that it is sometimes advantageous to move first in a two player game, depending on the nature of $f(x,y)$. I imagine this interpretation is what gave rise to the minimax theorem, which gives some conditions for the interchange of $\min$ and $\max$ with equality. $\endgroup$ – Tim Vieira Jan 4 '15 at 1:42
  • 1
    $\begingroup$ The above explanation is backward. Max-min inequality shows that is better to play second, not first. On the left, $y$ plays second, in reaction to any possible $x$. On RHS, $x$ plays second, in reaction to any possible $y$. Max-min inequality shows that it's better to wait until your opponent plays first. Intuitively, once your opponent (the x-player) reveals their strategy $x \in X$, you can choose your best response $\min_y f(x,y)$. If you choose first (RHS), any choice that you make (even the best one, $\min_{y\in Y}$) is going to be worse for you (higher $f(x,y)$) against an adversary x. $\endgroup$ – eqzx Jun 16 '18 at 20:28
23
$\begingroup$

Perhaps a simple example will help. Let $f(x,y) = \sin(x+y)$. Then

$\underset{y}{\text{min}} f(x,y) = -1$ for all $x$; and

$\underset{x}{\text{max}} f(x,y) = +1$ for all $y$.

So $\underset{x}{\text{max}}\:\underset{y}{\text{min}} f(x,y) = \underset{x}{\text{max}} (-1) = -1$; but $\underset{y}{\text{min}}\:\underset{x}{\text{max}} f(x,y) = \underset{y}{\text{min}} (+1) = +1\,$.

$\endgroup$
41
$\begingroup$

One asks that $$ \max\limits_x\left(\min\limits_sf(x,s)\right)\leqslant\min\limits_y\left(\max\limits_tf(t,y)\right). $$ The assertion is equivalent to the fact that, for every $x$ and $y$, $$ \min\limits_sf(x,s)\leqslant\max\limits_tf(t,y). $$ Since $\min\limits_sf(x,s)\leqslant f(x,y)\leqslant\max\limits_tf(t,y)$ by definition, this holds.

$\endgroup$
  • $\begingroup$ what is $\lim_y$? $\endgroup$ – Seyhmus Güngören Aug 25 '12 at 12:09
  • $\begingroup$ @Seyhmus: A typo. As you guessed, one should read $\min\limits_y$. $\endgroup$ – Did Aug 25 '12 at 13:53
9
$\begingroup$

I personally found this question in ML class of mine and went down to solve it myself at home as the teacher did not give any proof. Here it is:
Let $ f(x_{0}, y_{0}) = \max_x\min_y f(x, y)$ and $f(x_{1}, y_{1}) = \min_y\max_x f(x, y)$.

By this definition the problem is to prove that $f(x_{0}, y_{0}) \leq f(x_{1}, y_{1})$ provided that they exist.

By definition of min and max function we have:

$\min_yf(x, y) = f(x, y_{0}) \leq f(x, y) \forall y$. Here $\min_yf(x, y)$ would be a function only of x.

$\max_xf(x, y_{0})=f(x_{0}, y_{0}) \geq f(x, y_{0})\forall x$. Here $\max_xf(x, y_{0})$ is a scalar.

$\max_xf(x, y)=f(x_{1}, y) \geq f(x,y) \forall x$. Here $\max_xf(x_{1}, y)$ is a function of y.

$\min_yf(x_{1}, y)=f(x_{1},y_{1}) \leq f(x_{1}, y) \forall y$. Here $\min_yf(x_{1}, y)$ is a scalar.

From all this equation you get the following inequalities:

$f(x, y_{0}) \leq f(x_{0},y_{0}) \leq f(x,y) \leq f(x_{1}, y_{1}) \leq f(x_{1}, y)$

$\min_yf(x,y) \leq \max_x\min_yf(x,y) \leq f(x,y) \leq \min_y\max_xf(x,y) \leq \max_xf(x,y)$ $g(x) \leq Scalar \leq f(x,y) \leq Scalar \leq h(y)$

Hope the last thing as visualization helps you understand the problem.

$\endgroup$
  • $\begingroup$ Well just to add a comment that might on the other hand looks really confusing, but the left part of the inequalities are varying on X and the right ones are varying on y... I just hope it helps cause now I realize it might actually confuse you even more. $\endgroup$ – Alex Botev Sep 3 '12 at 15:28
  • $\begingroup$ This is excellent thanks a lot - I have edited your formatting as I feel this answer would gain a lot from being seen more $\endgroup$ – Xavier Bourret Sicotte Jun 27 '18 at 15:37
6
$\begingroup$

Let $\hat x,\hat y$ be the arguments responsible for the value $\underset{x}{\text{max}}\:\underset{y}{\text{min}} f(x,y)$. Then $f(\hat x,y)\ge f(\hat x,\hat y)$ for all $y$. For every $y$, the maximization $\underset{x}{\text{max}}f(x,y)$ extends over one of these values, and thus $\underset{x}{\text{max}}f(x,y)\ge f(\hat x,\hat y)$ for all $y$, and thus also $\underset{y}{\text{min}}\:\underset{x}{\text{max}}f(x,y)\ge f(\hat x,\hat y)=\underset{x}{\text{max}}\:\underset{y}{\text{min}} f(x,y)$.

$\endgroup$
  • $\begingroup$ Provided that $\hat{x}$ and $\hat{y}$ exist, of course. $\endgroup$ – Siminore Aug 25 '12 at 10:23
  • 1
    $\begingroup$ As Juan and Siminore rightly point out, this only works if the minima and maxima actually exist; else they need to be replaced by infima and suprema, respectively. $\endgroup$ – joriki Aug 25 '12 at 10:25
  • $\begingroup$ @Joriki I understood first line, but in starting of third line, you wrote $\underset{x}{\text{max}}f(x,y) \geq f(\hat{x},\hat{y})$, isn't $\underset{x}{\text{max}}f(x,y)$ same as $f(\hat{x},y)$ ? $\endgroup$ – Happy Mittal Aug 25 '12 at 10:50
  • $\begingroup$ @Happy: No, why should it be? $\hat x$ is the value of $x$ that maximizes $\underset{y}{\text{min}} f(x,y)$. I don't see why the same value of $x$ should maximize $f(x,y)$ for every $y$. In fact, since the values of $f$ for different values of $y$ can be chosen entirely independently of each other, it would be weird if it did. $\endgroup$ – joriki Aug 25 '12 at 11:26
  • $\begingroup$ joriki: Sorry but I do not understand the definition of $\hat y$. Shouldn't this depend on $x$? $\endgroup$ – Did Aug 25 '12 at 11:42
4
$\begingroup$

The inequality should be $\sup_x\inf_yf(x,y)\leq \inf_y\sup_x f(x,y)$. Consider $f(x,y)= x^2y^2$.

$\endgroup$
  • $\begingroup$ I downvoted here, because the inequality wasn't reversed. $\endgroup$ – davidlowryduda Aug 26 '12 at 4:53
  • $\begingroup$ It's not reversed, I was just (a bit pedantically) pointing out the inequality is in terms of supremums and infimums instead of maxima and minima, the original phrasing implicitly assumed that the minima and maxima actualy exists. $\endgroup$ – jkn Aug 26 '12 at 13:25
  • $\begingroup$ Oh you're right. I'm sorry. $\endgroup$ – davidlowryduda Aug 26 '12 at 15:22
  • $\begingroup$ That's ok, no worries ^^. $\endgroup$ – jkn Aug 27 '12 at 15:29
3
$\begingroup$

I had to prove this for an assignment the other day and I came up with a fairly clean proof that I thought I should share:

We define a' and b' as follows:

$$a'\triangleq\underset{a\in A}{argmin}\left\{ \underset{b\in B}{\max}f(a,b)\right\} \\ b'\triangleq\underset{b\in B}{argmax}\left\{ \underset{a\in A}{\min}f(a,b)\right\} $$

a' is the point in A where the MinMax is reached, whereas b' is the point in B where the MaxMin is reached.

Consider f(a',b'). We can bound it from above and below as follows:

$$\underset{a\in A}{\min}f(a,b')\leq f(a',b')\leq\underset{b\in B}{\max}f(a',b)$$

Now we can plug in a' and b' according to their definitions and get:

$$\underset{b\in B}{max}\left\{ \underset{a\in A}{\min}f(a,b)\right\} =\underset{a\in A}{\min}f(a,b')\leq f(a',b')\leq\underset{b\in B}{\max}f(a',b)=\underset{a\in A}{min}\left\{ \underset{b\in B}{\max}f(a,b)\right\} $$

Q.E.D

Note that this proof works for discrete A,B and as well as for infinite yet compact A,B (with continuous f).

$\endgroup$
0
$\begingroup$

The inequality should be using the infimum and supremum:

$$ \sup_{x} \inf_{y} f \left( x, y \right) \leq \inf_{y} \sup_{x} f \left( x, y \right) $$

Defining $ m \left( x \right) = \inf_{y} f \left( x, y \right) $ and $ M \left( y \right) = \sup_{x} f \left( x, y \right) $.

By using the definition of infimum and supremum:

$$ \exists \hat{x}, \hat{y} \epsilon >0 : \sup_{x} m \left( x \right) - \epsilon \leq m \left( \hat{x} \right), \; M \left( \hat{y} \right) \leq \inf_{y} M \left( y \right) + \epsilon $$

Now:

$$ \sup_{x} m \left( x \right) - \epsilon \leq m \left( \hat{x} \right) \leq f \left( \hat{x}, \hat{y} \right) \leq M \left( \hat{y} \right) \leq \inf_{y} M \left( y \right) + \epsilon $$

Hence clearly $ \sup_{x} m \left( x \right) \leq \inf_{y} M \left( y \right) $ which means:

$$ \sup_{x} \inf_{y} f \left( x, y \right) \leq \inf_{y} \sup_{x} f \left( x, y \right) $$

As requested.

Intuition? Well, think of two forces. The one want to minimize its degree of freedom. The other one want to maximize its degree of freedom.
It seems there is much more incentive to the force for minimization to work first. It guarantees the end result will be lower than the other way around (It is symmetrical from the point of view of the maximizing force).

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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