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

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

Определение

Пусть ${\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} _{+}}$

См. также

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