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 ?
Max Min of function less than Min max of function
-
1The 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. – 2018-06-16
9 Answers
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).
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.
-
0@Seyhmus: A typo. As you guessed, one should read $\min\limits_y$. – 2012-08-25
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\,$.
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.
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)$.
-
0@joriki: Understood. Thanks. – 2012-08-25
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$.
-
0That's ok, no worries ^^. – 2012-08-27
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).