Max–min inequality
In mathematics, the max–min inequality is as follows:
- For any function [math]\displaystyle{ \ f : Z \times W \to \mathbb{R}\ , }[/math]
- [math]\displaystyle{ \sup_{z \in Z} \inf_{w \in W} f(z, w) \leq \inf_{w \in W} \sup_{z \in Z} f(z, w)\ . }[/math]
When equality holds one says that f, W, and Z satisfies a strong max–min property (or a saddle-point property). The example function [math]\displaystyle{ \ f(z,w) = \sin( z + w )\ }[/math] 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 [math]\displaystyle{ g(z) \triangleq \inf_{w \in W} f(z, w)\ . }[/math] For all [math]\displaystyle{ z \in Z }[/math], we get [math]\displaystyle{ g(z) \leq f(z, w) }[/math] for all [math]\displaystyle{ w \in W }[/math] by definition of the infimum being a lower bound. Next, for all [math]\displaystyle{ w \in W }[/math], [math]\displaystyle{ f(z, w) \leq \sup_{z \in Z} f(z, w) }[/math] for all [math]\displaystyle{ z \in Z }[/math] by definition of the supremum being an upper bound. Thus, for all [math]\displaystyle{ z \in Z }[/math] and [math]\displaystyle{ w \in W }[/math], [math]\displaystyle{ g(z) \leq f(z, w) \leq \sup_{z \in Z} f(z, w) }[/math] making [math]\displaystyle{ h(w) \triangleq \sup_{z \in Z} f(z, w) }[/math] an upper bound on [math]\displaystyle{ g(z) }[/math] for any choice of [math]\displaystyle{ w \in W }[/math]. Because the supremum is the least upper bound, [math]\displaystyle{ \sup_{z \in Z} g(z) \leq h(w) }[/math] holds for all [math]\displaystyle{ w \in W }[/math]. From this inequality, we also see that [math]\displaystyle{ \sup_{z \in Z} g(z) }[/math] is a lower bound on [math]\displaystyle{ h(w) }[/math]. By the greatest lower bound property of infimum, [math]\displaystyle{ \sup_{z \in Z} g(z) \leq \inf_{w \in W} h(w) }[/math]. Putting all the pieces together, we get
[math]\displaystyle{ \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) }[/math]
which proves the desired inequality. [math]\displaystyle{ \blacksquare }[/math]
References
- Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge University Press. https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf.
See also
 |  |
