Неравенство Макс-Мин

В математике неравенство max–min выглядит следующим образом:

Для любой функции $\ f:Z\times 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)\ .$

Когда равенство соблюдается, говорят, что f , W и Z удовлетворяют сильному свойству max–min (или свойству перевала ). Пример функции $\ f(z,w)=\sin(z+w)\$ показывает, что равенство справедливо не для каждой функции.

Теорема, задающая условия на f , W и Z , которые гарантируют свойство седловой точки, называется минимаксной теоремой .

Доказательство

Определять $g(z)\triangleq \inf _{w\in W}f(z,w)\ .$ Для всех $z\in Z$, мы получаем ${\textstyle g(z)\leq f(z,w)}$ для всех $w\in W$ по определению нижняя грань является нижней границей. Далее для всех ${\textstyle w\in W}$, $f(z,w)\leq \sup _{z\in Z}f(z,w)$ для всех ${\textstyle z\in Z}$ по определению супремум является верхней границей. Таким образом, для всех $z\in Z$ и $w\in W$, $g(z)\leq f(z,w)\leq \sup _{z\in Z}f(z,w)$ изготовление $h(w)\triangleq \sup _{z\in Z}f(z,w)$ верхняя граница $g(z)$ на любой выбор $w\in W$. Поскольку супремум является наименьшей верхней границей, $\sup _{z\in Z}g(z)\leq h(w)$ держится для всех $w\in W$. Из этого неравенства мы также видим, что $\sup _{z\in Z}g(z)$ является нижней границей $h(w)$. По свойству наибольшей нижней границы нижней границы $\sup _{z\in Z}g(z)\leq \inf _{w\in W}h(w)$. Сложив все части вместе, мы получим

$\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)$

что доказывает требуемое неравенство. $\blacksquare$

Ссылки

• Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация (PDF) . Издательство Кембриджского университета .

См. также

• Теорема о минимаксе