In mathematics, the max–min inequality is as follows:
For any function f : Z × W → R , {\displaystyle \ f:Z\times W\to \mathbb {R} \ ,}
sup z ∈ Z inf w ∈ W f ( z , w ) ≤ inf w ∈ W sup z ∈ Z f ( z , w ) . {\displaystyle \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 ) {\displaystyle \ 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 ) ≜ inf w ∈ W f ( z , w ) . {\displaystyle g(z)\triangleq \inf _{w\in W}f(z,w)\ .} For all z ∈ Z {\displaystyle z\in Z} , we get g ( z ) ≤ f ( z , w ) {\textstyle g(z)\leq f(z,w)} for all w ∈ W {\displaystyle w\in W} by definition of the infimum being a lower bound. Next, for all w ∈ W {\textstyle w\in W} , f ( z , w ) ≤ sup z ∈ Z f ( z , w ) {\displaystyle f(z,w)\leq \sup _{z\in Z}f(z,w)} for all z ∈ Z {\textstyle z\in Z} by definition of the supremum being an upper bound. Thus, for all z ∈ Z {\displaystyle z\in Z} and w ∈ W {\displaystyle w\in W} , g ( z ) ≤ f ( z , w ) ≤ sup z ∈ Z f ( z , w ) {\displaystyle g(z)\leq f(z,w)\leq \sup _{z\in Z}f(z,w)} making h ( w ) ≜ sup z ∈ Z f ( z , w ) {\displaystyle h(w)\triangleq \sup _{z\in Z}f(z,w)} an upper bound on g ( z ) {\displaystyle g(z)} for any choice of w ∈ W {\displaystyle w\in W} . Because the supremum is the least upper bound, sup z ∈ Z g ( z ) ≤ h ( w ) {\displaystyle \sup _{z\in Z}g(z)\leq h(w)} holds for all w ∈ W {\displaystyle w\in W} . From this inequality, we also see that sup z ∈ Z g ( z ) {\displaystyle \sup _{z\in Z}g(z)} is a lower bound on h ( w ) {\displaystyle h(w)} . By the greatest lower bound property of infimum, sup z ∈ Z g ( z ) ≤ inf w ∈ W h ( w ) {\displaystyle \sup _{z\in Z}g(z)\leq \inf _{w\in W}h(w)} . Putting all the pieces together, we get
sup z ∈ Z inf w ∈ W f ( z , w ) = sup z ∈ Z g ( z ) ≤ inf w ∈ W h ( w ) = inf w ∈ W sup z ∈ Z f ( z , w ) {\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)} which proves the desired inequality. ◼ {\displaystyle \blacksquare }
References Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization (PDF). Cambridge University Press.
See also Minimax theorem