Max–min inequality

In mathematics, the max–min inequality is as follows: for any function ${\displaystyle f:Z\times W\to \mathbb {R} }$,

${\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). As the function f(z,w)=sin(z+w) illustrates, this equality does not always hold. A theorem giving conditions on f, W and Z in order to guarantee the saddle point property is called a minimax theorem.

Trivial Proof

This is essentially the same proof used below.

Suppose you have a plot of land, which need not be rectangular; two different directions that you consider horizontal and vertical, which need not be orthogonal, and where either ${\displaystyle z}$ or ${\displaystyle w}$ can be the horizontal or vertical direction; and where ${\displaystyle f(z,w)}$ is the elevation of the plot of land at ${\displaystyle z}$ and ${\displaystyle w}$ as measured by our horizontal and vertical directions. Now suppose you cut up this plot of land into tiny horizontal strips. Each strip that the plot of land is cut into will have some lowest elevation such that there is nowhere on that strip that has a lower elevation, but at least one point will have that same elevation. Now let's suppose that we put one red pebble on each strip of land at a point that is equal to that elevation. No matter where we go in our plot of land, the red pebble to the left or the right of the strip that we are on (or perhaps even under our feet) will be either lower than us or at the same elevation as us.

We must now do the same thing with blue pebbles, but with vertical strips and with points that are at a highest elevation on each strip. Are there any red pebbles which are higher than blue pebbles? Suppose we have one red pebble higher than a blue pebble. That would mean that the lowest piece of the horizontal strip of land the red pebble is on is higher than the vertical strip of land the blue pebble is on. Now think about walking from the blue pebble to one of the points where the two pieces of land intersect. Because the blue pebble is at a highest point, this means that we must have gone down in elevation. Because we are on the horizontal piece of land that the red pebble is on, and the red pebble has a higher elevation than the blue pebble, and we have gone down in elevation since we were on the blue pebble, that means we must be well below the red pebble. However, the red pebble was supposed to be at the lowest point on the horizontal strip of land that we are standing on. We have thus proven by contradiction that there is no red pebble higher than any blue pebble. If our land is completely flat, and so there is the same elevation everywhere, that means that we can have a situation where there is a red pebble at the same elevation as a blue pebble. That means that the highest of the red pebbles is no higher, but can be as high as, the lowest of the blue pebbles.

If we put that more succinctly, that means that we have proven that the highest of the lowest of the horizontal strip's points is no higher than the lowest of the highest of the vertical strip's points. If we cut the strips into narrower and narrower strips, we can see that this intuitive proof holds for continuums. We can see that this proof holds for any coordinate system as well by imagining twisting the strip of land into various rough shapes where ${\displaystyle f(z,w)}$ is the "elevation" at that point from the "ideal" shape.

In fact, we can show intuitively that this holds for discrete sets as well. Suppose that ${\displaystyle W}$ is the set ${\displaystyle \{{\text{plate}},{\text{bowl}}\}}$, and ${\displaystyle Z}$ is the set ${\displaystyle \{{\text{cat}},{\text{dog}},{\text{mouse}}\}}$, and we define ${\displaystyle f(z,w)}$ completely as follows:

${\displaystyle f({\text{cat}},{\text{plate}})=1}$

${\displaystyle f({\text{cat}},{\text{bowl}})=3}$

${\displaystyle f({\text{dog}},{\text{plate}})=6}$

${\displaystyle f({\text{dog}},{\text{bowl}})=2}$

${\displaystyle f({\text{mouse}},{\text{plate}})=4}$

We can see that:

${\displaystyle \inf _{z\in Z}f(z,{\text{plate}})=1}$

${\displaystyle \inf _{z\in Z}f(z,{\text{bowl}})=2}$

Which means that their supremum is:

${\displaystyle \sup _{w\in W}\inf _{z\in Z}f(z,w)=2}$

We can also see that:

${\displaystyle \sup _{w\in W}f({\text{cat}},w)=3}$

${\displaystyle \sup _{w\in W}f({\text{dog}},w)=6}$

${\displaystyle \sup _{w\in W}f({\text{mouse}},w)=4}$

Which means that their infimum is:

${\displaystyle \inf _{z\in Z}\sup _{w\in W}f(z,w)=3}$

And so since ${\displaystyle 2\leq 3}$,

${\displaystyle \sup _{w\in W}\inf _{z\in Z}f(z,w)\leq \inf _{z\in Z}\sup _{w\in W}f(z,w)}$

And one can play around with different numbers and discrete sets to convince oneself of this fact. Another, perhaps more geometric, way of imagining discrete sets is to imagine the plot of land with the red and blue pebbles again, but cut into a grid with some of the squares potentially missing, and we just ignore those squares (they are not negative infinity). A more rigorous symbolic proof is given in the next section.

Symbolic Proof

Define ${\displaystyle g(z)\triangleq \inf _{w\in W}f(z,w)}$.

${\displaystyle \forall w,\forall z,g(z)\leq f(z,w)}$

${\displaystyle \Longrightarrow \forall w,\sup _{z}g(z)\leq \sup _{z}f(z,w)}$

${\displaystyle \Longrightarrow \sup _{z}g(z)\leq \inf _{w}\sup _{z}f(z,w)}$

${\displaystyle \Longrightarrow \sup _{z}\inf _{w}f(z,w)\leq \inf _{w}\sup _{z}f(z,w)\qquad \square }$

References

• Boyd, Stephen; Vandenberghe, Lieven (2004), Convex Optimization (PDF), Cambridge University Press

See also

• Minimax theorem