Saddle point property proof, min max

1.7k Views Asked by At

The max-min inequality proof shows that for a function $f: Z \times W \to \mathbb{R}$, we can algebraicly show the following:

$$ \sup_{z\in Z} \inf_{w\in W} f(z,w) \leq \inf_{w\in W} \sup_{z\in Z} f(z,w) $$

Can we use a similar method to prove the following: $$ \sup_{z\in Z} \inf_{w\in W} f(z,w) = \inf_{w\in W} \sup_{z\in Z} f(z,w) $$

if we know there exists a saddle point $(\tilde{z},\tilde{w})$, and that $f(\tilde{z},\tilde{w}) = \sup_{w \in W} f(\tilde{z},w) = \inf_{z\in Z} f(z,\tilde{w}) $

1

There are 1 best solutions below

6
On BEST ANSWER

It is better to consider the max-min inequality in this form: $$\sup_{w\in W}\inf_{z\in Z}f(z,w)\leq \inf_{z\in Z}\sup_{w\in W} f(z,w),$$ which is true because of the same arguments.

Next we have (omitting $Z$ and $W$ in $\inf$ and $\sup$) \begin{align} f(\tilde z, \tilde w) & = \inf_z f(z, \tilde w)\leq \sup_w \inf_z f(z,w)\\ f(\tilde z, \tilde w) & = \sup_w f(\tilde z, w)\geq \inf_z \sup_w f(z,w). \end{align} These two inequalities gives one the opposite inequality to the first one.