Max–min inequality

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

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

$\underset{z\in Z}{\sup }\underset{w\in W}{\inf }f(z,w)\le \underset{w\in W}{\inf }\underset{z\in Z}{\sup }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 \underset{w\in W}{\inf }f(z,w).$ For all $z\in Z$, we get $g(z)\le 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)\le \underset{z\in Z}{\sup }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)\le f(z,w)\le \underset{z\in Z}{\sup }f(z,w)$ making $h(w)\triangleq \underset{z\in Z}{\sup }f(z,w)$ an upper bound on $g(z)$ for any choice of $w\in W$. Because the supremum is the least upper bound, $\underset{z\in Z}{\sup }g(z)\le h(w)$ holds for all $w\in W$. From this inequality, we also see that $\underset{z\in Z}{\sup }g(z)$ is a lower bound on $h(w)$. By the greatest lower bound property of infimum, $\underset{z\in Z}{\sup }g(z)\le \underset{w\in W}{\inf }h(w)$. Putting all the pieces together, we get

$\underset{z\in Z}{\sup }\underset{w\in W}{\inf }f(z,w)=\underset{z\in Z}{\sup }g(z)\le \underset{w\in W}{\inf }h(w)=\underset{w\in W}{\inf }\underset{z\in Z}{\sup }f(z,w)$

which proves the desired inequality. $◼$

References

• Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge University Press. https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf. 

See also

• Minimax theorem