Max–min inequality

In mathematics, the max–min inequality is as follows:

:For any function $\ f : Z \times W \to \mathbb{R}\ ,$

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

When equality holds one says that {{mvar|f}}, {{mvar|W}}, and {{mvar|Z}} satisfies a strong max–min property (or a saddle-point property). The example function $\ f(z,w) = \sin( z + w )\$ illustrates that the equality does not hold for every function.

A theorem giving conditions on {{mvar|f}}, {{mvar|W}}, and {{mvar|Z}} which guarantee the saddle point property is called a minimax theorem.

Proof

Define $g(z) \triangleq \inf_{w \in W} f(z, w)\ .$ For all $z \in Z$ , we get $g(z) \leq f(z, w)$ for all $w \in W$ by definition of the infimum being a lower bound. Next, for all $w \in W$ , $f(z, w) \leq \sup_{z \in Z} f(z, w)$ for all $z \in Z$ by definition of the supremum being an upper bound. Thus, for all $z \in Z$ and $w \in W$ , $g(z) \leq f(z, w) \leq \sup_{z \in Z} f(z, w)$ making $h(w) \triangleq \sup_{z \in Z} f(z, w)$ an upper bound on $g(z)$ for any choice of $w \in W$ . Because the supremum is the least upper bound, $\sup_{z \in Z} g(z) \leq h(w)$ holds for all $w \in W$ . From this inequality, we also see that $\sup_{z \in Z} g(z)$ is a lower bound on $h(w)$ . By the greatest lower bound property of infimum, $\sup_{z \in Z} g(z) \leq \inf_{w \in W} h(w)$ . Putting all the pieces together, we get

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

which proves the desired inequality. $\blacksquare$

References

{{cite book

|first1=Stephen |last1=Boyd

|first2=Lieven |last2=Vandenberghe

|year=2004

|title=Convex Optimization

|publisher=Cambridge University Press

|url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

}}

Max–min inequality

Proof

References

See also