Max–min inequality

In mathematics, the max–min inequality is as follows: for any function ${\displaystyle f:Z\times W\to \mathbb {R} }$,

${\displaystyle \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 f, W and Z satisfies a strong max–min property (or a saddle-point property). As the function f(z,w)=sin(z+w) illustrates, this equality does not always hold. A theorem giving conditions on f, W and Z in order to guarantee the saddle point property is called a minimax theorem.

Proof

Define ${\displaystyle g(z)\triangleq \inf _{w\in W}f(z,w)}$.

${\displaystyle \forall w\in W,\forall z\in Z,g(z)\leq f(z,w)}$

${\displaystyle \Longrightarrow \forall w\in W,\sup _{z\in Z}g(z)\leq \sup _{z\in Z}f(z,w)}$

${\displaystyle \Longrightarrow \sup _{z\in Z}g(z)\leq \inf _{w\in W}\sup _{z\in Z}f(z,w)}$

${\displaystyle \Longrightarrow \sup _{z\in Z}\inf _{w\in W}f(z,w)\leq \inf _{w\in W}\sup _{z\in Z}f(z,w)\qquad \square }$

References

• Boyd, Stephen; Vandenberghe, Lieven (2004), Convex Optimization (PDF), Cambridge University Press

See also

• Minimax theorem