Выпуклое сопряжение

Выпуклое сопряжение функции — это обобщение преобразования Лежандра, которое применяется к невыпуклым функциям. Оно известно также как преобразование Лежандра — Фенхеля или преобразование Фенхеля (по именам Адриена Мари Лежандра и Вернера Фенхеля). Сопряжение используется для преобразования задачи оптимизации в соответствующую двойственную задачу, которую, возможно, проще решить.

Определение

Пусть ${\displaystyle X}$ будет вещественным топологическим векторным пространством и пусть ${\displaystyle X^{*}}$ будет двойственным пространством для ${\displaystyle X}$. Обозначим двойственную пару^[англ.] через

${\displaystyle \langle \cdot ,\cdot \rangle :X^{*}\times X\to \mathbb {R} .}$

Для функции

${\displaystyle f:X\to \mathbb {R} \cup \{-\infty ,+\infty \}}$,

принимающей значения на расширенной числовой прямой, выпуклое сопряжение

${\displaystyle f^{*}:X^{*}\to \mathbb {R} \cup \{-\infty ,+\infty \}}$

определено в терминах супремума по формуле

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

или, эквивалентно, в терминах инфимума по формуле

${\displaystyle f^{*}\left(x^{*}\right):=-\inf \left\{\left.f\left(x\right)-\left\langle x^{*},x\right\rangle \right|x\in X\right\}.}$

Это определение можно интерпретировать как кодирование выпуклой оболочки надграфика функции в терминах её опорных гиперплоскостей^[1][2].

Примеры

Выпуклое сопряжение аффинной функции

${\displaystyle f(x)=\left\langle a,x\right\rangle -b,\,a\in \mathbb {R} ^{n},b\in \mathbb {R} }$

равно

${\displaystyle f^{*}\left(x^{*}\right)={\begin{cases}b,&x^{*}=a\\+\infty ,&x^{*}\neq a.\end{cases}}}$

Выпуклое сопряжение степенной функции

${\displaystyle f(x)={\frac {1}{p}}|x|^{p},\,1<p<\infty }$

равно

${\displaystyle f^{*}\left(x^{*}\right)={\frac {1}{q}}|x^{*}|^{q},\,1<q<\infty }$

где ${\displaystyle {\tfrac {1}{p}}+{\tfrac {1}{q}}=1.}$

Выпуклое сопряжение функции абсолютной величины

${\displaystyle f(x)=\left|x\right|}$

равно

${\displaystyle f^{*}\left(x^{*}\right)={\begin{cases}0,&\left|x^{*}\right|\leqslant 1\\\infty ,&\left|x^{*}\right|>1.\end{cases}}}$

Выпуклое сопряжение показательной функции ${\displaystyle f(x)=\,\!e^{x}}$ равно

${\displaystyle f^{*}\left(x^{*}\right)={\begin{cases}x^{*}\ln x^{*}-x^{*},&x^{*}>0\\0,&x^{*}=0\\\infty ,&x^{*}<0.\end{cases}}}$

Выпуклое сопряжение и преобразование Лежандра показательной функции совпадают за исключением того, что область определения выпуклого сопряжения строго шире, поскольку преобразование Лежандра определено лишь для положительных вещественных чисел.

Связь с ожидаемыми потерями (средняя цена риска)

Пусть F означает интегральную функцию распределения случайной величины X. Тогда (интегрируя по частям),

${\displaystyle f(x):=\int _{-\infty }^{x}F(u)\,du=\operatorname {E} \left[\max(0,x-X)\right]=x-\operatorname {E} \left[\min(x,X)\right]}$

имеет выпуклое сопряжение

${\displaystyle f^{*}(p)=\int _{0}^{p}F^{-1}(q)\,dq=(p-1)F^{-1}(p)+\operatorname {E} \left[\min(F^{-1}(p),X)\right]=pF^{-1}(p)-\operatorname {E} \left[\max(0,F^{-1}(p)-X)\right].}$

Упорядочение

Конкретная интерпретация имеет преобразование

${\displaystyle f^{\text{inc}}(x):=\arg \sup _{t}\,t\cdot x-\int _{0}^{1}\max\{t-f(u),0\}\,\mathrm {d} u,}$

как неубывающую перегруппировку начальной функции f. В частности, ${\displaystyle f^{\text{inc}}=f}$ для ${\displaystyle f}$ не убывает.

Свойства

Выпуклое сопряжение замкнутой выпуклой функции^[англ.] снова является замкнутой выпуклой функцией. Выпуклое сопряжение полиэдральной выпуклой функции (выпуклой функции с многогранным надграфиком) снова является полиэдральной выпуклой функцией.

Обращение порядка

Выпуклое сопряжение обращает порядок — если ${\displaystyle f\leqslant g}$, то ${\displaystyle f^{*}\geqslant g^{*}}$. Здесь

${\displaystyle (f\leqslant g):\iff (\forall x,f(x)\leqslant g(x)).}$

Для семейства функций ${\displaystyle \left(f_{\alpha }\right)_{\alpha }}$ это следует из факта, что супремумы могут быть переставлены местами

${\displaystyle \left(\inf _{\alpha }f_{\alpha }\right)^{*}(x^{*})=\sup _{\alpha }f_{\alpha }^{*}(x^{*}),}$

и из max–min неравенства^[англ.]

${\displaystyle \left(\sup _{\alpha }f_{\alpha }\right)^{*}(x^{*})\leqslant \inf _{\alpha }f_{\alpha }^{*}(x^{*}).}$

Двойное сопряжение

Выпуклое сопряжение функции всегда полунепрерывно снизу. Двойное сопряжение ${\displaystyle f^{**}}$ (выпуклое сопряжение выпуклого сопряжения) является также замкнутой выпуклой оболочкой, то есть наибольшей полунепрерывной снизу выпуклой функцией с ${\displaystyle f^{**}\leqslant f}$. Для выпуклых собственных функций^[англ.] ${\displaystyle f=f^{**}}$ тогда и только тогда, когда f выпукла и полунепрерывна снизу по теореме Фенхеля — Моро.

Неравенство Фенхеля

Для любой функции f и её выпуклого сопряжения ${\displaystyle f^{*}}$ неравенство Фенхеля (известное также как неравенство Фенхеля — Моро) выполняется для любого ${\displaystyle x\in X}$ и ${\displaystyle p\in X^{*}}$ :

${\displaystyle \left\langle p,x\right\rangle \leqslant f(x)+f^{*}(p).}$

Доказательство следует немедленно из определения выпуклого сопряжения: ${\displaystyle f^{*}(p)=\sup _{\tilde {x}}\{\langle p,{\tilde {x}}\rangle -f({\tilde {x}})\}\geqslant \langle p,x\rangle -f(x)}$.

Выпуклость

Для двух функций ${\displaystyle f_{0}}$ и ${\displaystyle f_{1}}$ и числа ${\displaystyle 0\leqslant \lambda \leqslant 1}$ выполняется

${\displaystyle \left((1-\lambda )f_{0}+\lambda f_{1}\right)^{*}\leqslant (1-\lambda )f_{0}^{*}+\lambda f_{1}^{*}}$.

Здесь операция ${\displaystyle {*}}$ — это выпуклое отображение в себя.

Инфимальная конволюция

Инфимальная конволюция двух функций f и g определяется как

${\displaystyle \left(f\Box g\right)(x)=\inf \left\{f(x-y)+g(y)\,|\,y\in \mathbb {R} ^{n}\right\}.}$

Пусть f₁, …, f_m будут правильными выпуклыми полунепрерывными снизу функциями на ${\displaystyle \mathbb {R} ^{n}}$. Тогда инфимальная конволюция выпукла и полунепрерывна снизу (но не обязательно будет правильной функцией)^[3] и удовлетворяет равенству

${\displaystyle \left(f_{1}\Box \cdots \Box f_{m}\right)^{*}=f_{1}^{*}+\cdots +f_{m}^{*}.}$

Инфимальная конволюция двух функций имеет геометрическую интерпретацию — (строгий) надграфик инфимальной конволюции двух функций равен сумме Минковского (строгих) надграфиков этих функций^[4].

Максимизирующий аргумент

Если функция ${\displaystyle f}$ дифференцируема, то её производная является максимизирующим аргументом при вычислении выпуклого сопряжения:

${\displaystyle f^{\prime }(x)=x^{*}(x):=\arg \sup _{x^{*}}{\langle x,x^{*}\rangle }-f^{*}(x^{*})}$ и

${\displaystyle f^{{*}\prime }(x^{*})=x(x^{*}):=\arg \sup _{x}{\langle x,x^{*}\rangle }-f(x);}$

откуда

${\displaystyle x=\nabla f^{*}(\nabla f(x)),}$

${\displaystyle x^{*}=\nabla f(\nabla f^{*}(x^{*})),}$

и, более того,

${\displaystyle f^{\prime \prime }(x)\cdot f^{{*}\prime \prime }(x^{*}(x))=1,}$

${\displaystyle f^{{*}\prime \prime }(x^{*})\cdot f^{\prime \prime }(x(x^{*}))=1.}$

Масштабирующие свойства

Если для некоторого ${\displaystyle \gamma >0}$ ${\displaystyle \,g(x)=\alpha +\beta x+\gamma \cdot f(\lambda x+\delta )}$, то

${\displaystyle g^{*}(x^{*})=-\alpha -\delta {\frac {x^{*}-\beta }{\lambda }}+\gamma \cdot f^{*}\left({\frac {x^{*}-\beta }{\lambda \gamma }}\right).}$

В случае дополнительного параметра (скажем, ${\displaystyle \alpha }$), более того,

${\displaystyle f_{\alpha }(x)=-f_{\alpha }({\tilde {x}}),}$

где ${\displaystyle {\tilde {x}}}$ где выбирается максимизирующим аргументом.

Поведение при линейных преобразованиях

Пусть A будет ограниченным линейным оператором из X в Y. Для любой выпуклой функции f на X, имеем

${\displaystyle \left(Af\right)^{*}=f^{*}A^{*}}$

где

${\displaystyle (Af)(y)=\inf\{f(x):x\in X,Ax=y\}}$

является прообразом f для A, а A^* является сопряжённым оператором для A^[5].

Замкнутая выпуклая функция f симметрична для заданного множества G ортогональных линейных преобразований

${\displaystyle f\left(Ax\right)=f(x),\;\forall x,\;\forall A\in G}$

тогда и только тогда, когда выпуклое сопряжение f^* симметрично для G.

Таблица некоторых выпуклых сопряжений

Следующая таблица даёт преобразования Лежандра для многих часто употребимых функций, а также для нескольких полезных свойств^[6].

${\displaystyle g(x)}$	${\displaystyle \operatorname {dom} (g)}$	${\displaystyle g^{*}(x^{*})}$	${\displaystyle \operatorname {dom} (g^{*})}$
${\displaystyle f(ax)}$ (где ${\displaystyle a\neq 0}$)	${\displaystyle X}$	${\displaystyle f^{*}\left({\frac {x^{*}}{a}}\right)}$	${\displaystyle X^{*}}$
${\displaystyle f(x+b)}$	${\displaystyle X}$	${\displaystyle f^{*}(x^{*})-\langle b,x^{*}\rangle }$	${\displaystyle X^{*}}$
${\displaystyle af(x)}$ (где ${\displaystyle a>0}$)	${\displaystyle X}$	${\displaystyle af^{*}\left({\frac {x^{*}}{a}}\right)}$	${\displaystyle X^{*}}$
${\displaystyle \alpha +\beta x+\gamma \cdot f(\lambda x+\delta )}$	${\displaystyle X}$	${\displaystyle -\alpha -\delta {\frac {x^{*}-\beta }{\lambda }}+\gamma \cdot f^{*}\left({\frac {x^{*}-\beta }{\gamma \lambda }}\right)\quad (\gamma >0)}$	${\displaystyle X^{*}}$
${\displaystyle {\frac {|x|^{p}}{p}}}$ (где ${\displaystyle p>1}$)	${\displaystyle \mathbb {R} }$	${\displaystyle {\frac {|x^{*}|^{q}}{q}}}$ (где ${\displaystyle {\frac {1}{p}}+{\frac {1}{q}}=1}$)	${\displaystyle \mathbb {R} }$
${\displaystyle {\frac {-x^{p}}{p}}}$ (где ${\displaystyle 0<p<1}$)	${\displaystyle \mathbb {R} _{+}}$	${\displaystyle {\frac {-(-x^{*})^{q}}{q}}}$ (где ${\displaystyle {\frac {1}{p}}+{\frac {1}{q}}=1}$)	${\displaystyle \mathbb {R} _{-}}$
${\displaystyle {\sqrt {1+x^{2}}}}$	${\displaystyle \mathbb {R} }$	${\displaystyle -{\sqrt {1-(x^{*})^{2}}}}$	${\displaystyle [-1,1]}$
${\displaystyle -\log(x)}$	${\displaystyle \mathbb {R} _{++}}$	${\displaystyle -(1+\log(-x^{*}))}$	${\displaystyle \mathbb {R} _{--}}$
${\displaystyle e^{x}}$	${\displaystyle \mathbb {R} }$	${\displaystyle {\begin{cases}x^{*}\log(x^{*})-x^{*}&{\text{if }}x^{*}>0\\0&{\text{if }}x^{*}=0\end{cases}}}$	${\displaystyle \mathbb {R} _{+}}$
${\displaystyle \log \left(1+e^{x}\right)}$	${\displaystyle \mathbb {R} }$	${\displaystyle {\begin{cases}x^{*}\log(x^{*})+(1-x^{*})\log(1-x^{*})&{\text{if }}0<x^{*}<1\\0&{\text{if }}x^{*}=0,1\end{cases}}}$	${\displaystyle [0,1]}$
${\displaystyle -\log \left(1-e^{x}\right)}$	${\displaystyle \mathbb {R} }$	${\displaystyle {\begin{cases}x^{*}\log(x^{*})-(1+x^{*})\log(1+x^{*})&{\text{if }}x^{*}>0\\0&{\text{if }}x^{*}=0\end{cases}}}$	${\displaystyle \mathbb {R} _{+}}$

См. также

• Двойственная задача
• Теорема двойственности Фенхеля
• Преобразование Лежандра
• Неравенство Юнга

Примечания

1. Legendre Transform  (неопр.). Дата обращения: 14 апреля 2019. Архивировано 28 июля 2020 года.
2. Frank Nielsen. Legendre transformation and information geometry  (неопр.). Дата обращения: 19 апреля 2019. Архивировано 11 ноября 2013 года.
3. Phelps, 1991, с. 42.
4. Bauschke, Goebel, Lucet, Wang, 2008, с. 766.
5. Иоффе, Тихомиров, 1974, с. утверждение 3.4.3.
6. Borwein, Lewis, 2006, с. 50–51.

Литература

• Robert R. Phelps. Convex Functions, Monotone Operators and Differentiability. — Springer, 1991. — ISBN 0-387-56715-1.
• Heinz H. Bauschke, Rafal Goebel, Yves Lucet, Xianfu Wang. The Proximal Average: Basic Theory // SIAM Journal on Optimization. — 2008. — Т. 19, вып. 2. — doi:10.1137/070687542.
• Иоффе А. Д., Тихомиров В. М. Теория экстремальных задач. — М.: «Наука», 1974.
• Jonathan Borwein, Adrian Lewis. Convex Analysis and Nonlinear Optimization: Theory and Examples. — Springer, 2006. — ISBN 978-0-387-29570-1.
• Владимир Игоревич Арнольд. Математические методы классической механики. — М.: «Наука», 1989.
• R. Tyrrell Rockafellar. Convex Analysis. — Princeton: Princeton University Press, 1970. — ISBN 0-691-01586-4.

Ссылки

• Touchette, Hugo Legendre-Fenchel transforms in a nutshell  (неопр.) (PDF) (16 октября 2014). Дата обращения: 9 января 2017. Архивировано из оригинала 7 апреля 2017 года.
• Touchette, Hugo Elements of convex analysis  (неопр.) (PDF) (21 ноября 2006). Дата обращения: 26 марта 2008. Архивировано из оригинала 26 мая 2015 года.
• Legendre and Legendre-Fenchel transforms in a step-by-step explanation  (неопр.). Дата обращения: 18 мая 2013.