Max–min ojämlikhet

I matematik är max–min ojämlikheten följande:

För alla funktioner $\ f:Z\ gånger W\to \mathbb {R} \ ,$

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

När likheten gäller säger man att f , W och Z uppfyller en stark max–min-egenskap (eller en sadelpunktsegenskap) . Exempelfunktionen $\ f(z,w)=\sin(z+w)\$ illustrerar att likheten inte gäller för varje funktion.

En sats som ger villkor för f , W och Z som garanterar sadelpunktsegenskapen kallas en minimaxsats .

Bevis

Definiera $g(z)\triangleq \inf _{w\in W}f(z,w)\ .$ För alla $z\in Z$ får vi ${\textstyle g(z)\leq f(z,w)}$ för alla $w\in W$ per definition av att infimum är en nedre gräns. Därefter, för alla ${\textstyle w\in W}$ , $f(z,w)\leq \sup _{z\ i Z}f(z,w)$ för alla ${\textstil z\in Z}$ per definition av att supremum är en övre gräns. Således, för alla $z\in Z$ och $w\in W$ , ${\displaystyle g(z)\leq f(z,w)\leq \sup _{z\in Z}f(z,w)} vilket$ gör ${ \displaystyle h(w)\triangleq \sup _{z\in Z}f(z,w)}$ en övre gräns på $g(z)$ för valfritt val av $w\in W$ . Eftersom supremum är den minsta övre gränsen, $\sup _{z\in Z}g(z)\leq h(w)$ för alla $w\in W$ . Från denna olikhet ser vi också att $\sup _{z\in Z}g(z)$ är en nedre gräns på $h(w)$ . Med den största nedre gränsegenskapen för infimum, $\sup _{z\in Z}g(z)\leq \inf _{w\ i W}h(w)$ . Vi får ihop alla bitar

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

vilket bevisar den önskade ojämlikheten. $\blacksquare$

• Boyd, Stephen; Vandenberghe, Lieven (2004). Konvex optimering (PDF) . Cambridge University Press .

Se även

• Minimaxsats