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

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

Определение

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

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

Для функции

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

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

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

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

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

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

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

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

Примеры

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

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

равно

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

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

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

равно

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

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

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

$f(x)=\left|x\right|$

равно

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

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

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

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

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

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

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

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

$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].$

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

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

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

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

Свойства

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

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

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

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

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

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

и из max–min неравенства

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

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

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

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

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

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

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

Выпуклость

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

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

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

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

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

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

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

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

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

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

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

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

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

откуда

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где

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

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

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

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

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

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

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

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

См. также

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

Литература

• 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.