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 f, W, and 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 f, W, and 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 ${\textstyle g(z)\leq f(z,w)}$ for all $w\in W$ by definition of the infimum being a lower bound. Next, for all ${\textstyle w\in W}$, $f(z,w)\leq \sup _{z\in Z}f(z,w)$ for all ${\textstyle 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

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

See also

• Minimax theorem