Max–min inequality

In mathematics, the max–min inequality is as follows: for any function f: Z × W → ℝ,

$\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 $g(z)\triangleq \inf _{{w\in W}}f(z,w)$.

${\displaystyle \Longrightarrow g(z)\leq f(z,w),\forall z,w}$

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

${\displaystyle \Longrightarrow \sup _{z}\inf _{w}f(z,w)\leq \sup _{z}f(z,w),\forall w}$

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

References

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

See also

• Minimax theorem