2

I saw the following proof that max min of a function is $\leq$ than min max of a function on Max Min of function less than Min max of function, pasted below for your reference


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)$

My confusion is on the last line, where did the $f(x_{0},y_{0}) \leq f(x,y) \leq f(x_{1}, y_{1})$ come from? I don't see how this conclusion was made from the prior steps.

user5965026
  • 677

1 Answers1

1

$f(x_0, y_0) \leq f(x, y)$ because $f(x, y_0) \leq f(x, y)$ for all $x$ and $y$, and $f(x_0, y_0) \geq f(x, y_0)$ since $x_0$ is a maximizer. Similar logic applies to $f(x_1, y_1)$.

eyio
  • 11