Max–min inequality explained

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

For any function

f : Z x W \to R , \sup _{z} inf _{w} f(z, w) \leq inf _{w} \sup _{z} f(z, w) .

When equality holds one says that,, and 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,, and which guarantee the saddle point property is called a minimax theorem.

Proof

Define

g(z) \triangleq inf _{w} f(z, w) . For all z \in Z , we get $g(z)\; \backslash leq\; f(z,\; w)$ for all w \in W by definition of the infimum being a lower bound. Next, for all $w\; \backslash in\; W$, f(z, w) \leq \sup _{z} f(z, w) for all $z\; \backslash 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} f(z, w) making h(w) \triangleq \sup _{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} g(z) \leq h(w) holds for all w \in W . From this inequality, we also see that \sup _{z} g(z) is a lower bound on h(w) . By the greatest lower bound property of infimum, \sup _{z} g(z) \leq inf _{w} h(w) . Putting all the pieces together, we get\sup _{z} inf _{w} f(z, w) = \sup _{z} g(z) \leq inf _{w} h(w) = inf _{w} \sup _{z} f(z, w)

which proves the desired inequality.

\blacksquare

References

• Book: Stephen . Boyd . Lieven . Vandenberghe . 2004 . Convex Optimization . .

See also

• Minimax theorem