Max–min inequality

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

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

$\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 Template:Mvar, Template:Mvar, and Template:Mvar 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 Template:Mvar, Template:Mvar, and Template:Mvar 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

• Template:Cite book

See also

• Minimax theorem