Теорема двойственности Фенхеля

Теорема двойственности Фенхеля — это результат в теории выпуклых функций, носящий имя немецкого математика Вернера Фенхеля.

Пусть ƒ — собственная выпуклая функция^[англ.] ${\displaystyle \mathbb {R} ^{n}}$, а g — собственная вогнутая функция на ${\displaystyle \mathbb {R} ^{n}}$. Тогда, если удовлетворены условия регулярности,

${\displaystyle \inf _{x}(f(x)-g(x))=\sup _{p}(g_{\star }(p)-f^{\star }(p)).}$

где ${\displaystyle f^{\star }}$ является выпуклым сопряжением функции ƒ (которое называется преобразованием Фенхеля — Лежандра), а ${\displaystyle g_{\star }}$ — вогнутым сопряжением функции g. То есть,

${\displaystyle f^{\star }\left(x^{*}\right):=\sup \left\{\left.\left\langle x^{*},x\right\rangle -f\left(x\right)\right|x\in \mathbb {R} ^{n}\right\}}$

${\displaystyle g_{\star }\left(x^{*}\right):=\inf \left\{\left.\left\langle x^{*},x\right\rangle -g\left(x\right)\right|x\in \mathbb {R} ^{n}\right\}}$

Пусть X и Y будут банаховыми пространствами, ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \}}$ и ${\displaystyle g:Y\to \mathbb {R} \cup \{+\infty \}}$ — выпуклыми функциями, а ${\displaystyle A:X\to Y}$ будет ограниченным линейным отображением. Тогда задачи Фенхеля

${\displaystyle p^{*}=\inf _{x\in X}\{f(x)+g(Ax)\}}$

${\displaystyle d^{*}=\sup _{y^{*}\in Y^{*}}\{-f^{*}(A^{*}y^{*})-g^{*}(-y^{*})\}}$

удовлетворяют слабой двойственности, то есть ${\displaystyle p^{*}\geqslant d^{*}}$. Заметим, что ${\displaystyle f^{\star },g^{\star }}$ являются выпуклыми сопряжениями функций f и g соответственно, а ${\displaystyle A^{*}}$ является сопряжённым оператором. Функция возмущений^[англ.] для этой двойственной задачи задаётся формулой ${\displaystyle F(x,y)=f(x)+g(Ax-y)}$.

Предположим, что f, g и A удовлетворяет либо

1. f и g полунепрерывны снизу и ${\displaystyle 0\in \operatorname {core} (\operatorname {dom} g-A\operatorname {dom} f)}$, где ${\displaystyle \operatorname {core} }$ — алгебраическая внутренность^[англ.], а ${\displaystyle \operatorname {dom} h}$, где h — некоторая функция, является множеством ${\displaystyle \{z:h(z)<+\infty \}}$, либо
2. ${\displaystyle A\operatorname {dom} f\cap \operatorname {cont} g\neq \emptyset }$, где ${\displaystyle \operatorname {cont} }$ — это точки, где функция непрерывна.

Тогда имеет место сильная двойственность, то есть ${\displaystyle p^{*}=d^{*}}$. Если ${\displaystyle d^{*}\in \mathbb {R} }$, то супремум достигается^[1].

На рисунке иллюстрируется задача минимизации в левой части равенства. Ищется значение переменной x, такой что вертикальное расстояние между выпуклой и вогнутой кривой в точке x настолько мало, насколько возможно. Положение вертикальной прямой на рисунке (примерно) оптимально.

Следующий рисунок иллюстрирует задачу максимизации на правой стороне равенства выше. Касательные, нарисованные для каждой кривой, имеют одинаковый наклон p. Задача заключается в уточнении значения p таким образом, чтобы две касательные были как можно дальше друг от друга (точнее так, что точки пересечения их с осью y были как можно дальше друг от друга). Механически, можно представить касательные как металлические стержни, соединённые вертикальными пружинами, которые их расталкивают, а параболы ограничивают положение стержней.

Теорема Фенхеля утверждает, что эти две задачи имеют одно и то же решение. Точки, имеющие минимальное вертикальное разделение также являются точками касания для максимально раздвинутых параллельных касательных.

• Преобразование Лежандра
• Выпуклое сопряжение
• Теорема Моро
• Двойственность Вольфа^[англ.]