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

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

Определение

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

$⟨\cdot ,\cdot ⟩:X^{*}\times X\to ℝ.$

Для функции

$f:X\to ℝ\cup \{-\mathrm{\infty },+\mathrm{\infty }\}$,

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

$f^{*}:X^{*}\to ℝ\cup \{-\mathrm{\infty },+\mathrm{\infty }\}$

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

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

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

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

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

Примеры

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

$f(x)=⟨a,x⟩-b,a\in {ℝ}^n,b\in ℝ$

равно

$f^{*}\left(x^{*}\right)=\{\begin{array}{cc}b,& x^{*}=a\\ +\mathrm{\infty },& x^{*}\ne a.\end{array}$

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

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

равно

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

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

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

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

равно

$f^{*}\left(x^{*}\right)=\{\begin{array}{cc}0,& \left|x^{*}\right|⩽1\\ \mathrm{\infty },& \left|x^{*}\right|>1.\end{array}$

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

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

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

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

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

$f(x):=\underset{-\mathrm{\infty }}{\overset{x}{\int }}F(u)du=\mathrm{E}[\max (0,x-X)]=x-\mathrm{E}[\min (x,X)]$

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

$f^{*}(p)=\underset{0}{\overset{p}{\int }}{F}^{-1}(q)dq=(p-1)F^{-1}(p)+\mathrm{E}[\min (F^{-1}(p),X)]=p{F}^{-1}(p)-\mathrm{E}[\max (0,F^{-1}(p)-X)].$

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

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

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

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

Свойства

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

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

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

$(f⩽g):⟺(\mathrm{\forall }x,f(x)⩽g(x)).$

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

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

и из Шаблон:Не переведено 5

${\left(\underset{\alpha }{\sup }{f}_{\alpha }\right)}^{*}(x^{*})⩽\underset{\alpha }{\inf }{f}_{\alpha }^{*}(x^{*}).$

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

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

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

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

$⟨p,x⟩⩽f(x)+f^{*}(p).$

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

Выпуклость

Для двух функций $f_0$ и $f_1$ и числа $0⩽\lambda ⩽1$ выполняется

${((1-\lambda )f_0+\lambda f_1)}^{*}⩽(1-\lambda )f_0^{*}+\lambda f_1^{*}$.

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

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

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

$\left(f◻g\right)(x)=\inf \{f(x-y)+g(y)|y\in {ℝ}^n\}.$

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

${(f_1◻\cdots ◻f_m)}^{*}=f_1^{*}+\cdots +f_m^{*}.$

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

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

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

$f^{\prime }(x)=x^{*}(x):=\arg \underset{x^{*}}{\sup }⟨x,x^{*}⟩-f^{*}(x^{*})$ и

$f^{*\prime }(x^{*})=x(x^{*}):=\arg \underset{x}{\sup }⟨x,x^{*}⟩-f(x);$

откуда

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

$x^{*}=\mathrm{\nabla }f(\mathrm{\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Шаблон:Sfn.

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

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

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

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

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

$g(x)$	$\mathrm{dom}(g)$	$g^{*}(x^{*})$	$\mathrm{dom}(g^{*})$
$f(ax)$ (где $a\ne 0$)	$X$	$f^{*}\left(\frac{x^{*}}{a}\right)$	$X^{*}$
$f(x+b)$	$X$	$f^{*}(x^{*})-⟨b,x^{*}⟩$	$X^{*}$
$af(x)$ (где $a>0$)	$X$	$a{f}^{*}\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)(\gamma >0)$	$X^{*}$
$\frac{|x{|}^p}{p}$ (где $p>1$)	$ℝ$	$\frac{|x^{*}{|}^q}{q}$ (где $\frac{1}{p}+\frac{1}{q}=1$)	$ℝ$
$\frac{-x^p}{p}$ (где $0<p<1$)	${ℝ}_{+}$	$\frac{-(-x^{*}{)}^q}{q}$ (где $\frac{1}{p}+\frac{1}{q}=1$)	${ℝ}_{-}$
$\sqrt{1+x^2}$	$ℝ$	$-\sqrt{1-(x^{*}{)}^2}$	$[-1,1]$
$-\log (x)$	${ℝ}_{++}$	$-(1+\log (-x^{*}))$	${ℝ}_{--}$
$e^x$	$ℝ$	$\{\begin{array}{cc}{x}^{*}\log (x^{*})-x^{*}& \text{if }{x}^{*}>0\\ 0& \text{if }{x}^{*}=0\end{array}$	${ℝ}_{+}$
$\log (1+e^x)$	$ℝ$	$\{\begin{array}{cc}{x}^{*}\log (x^{*})+(1-x^{*})\log (1-x^{*})& \text{if }0<x^{*}<1\\ 0& \text{if }{x}^{*}=0,1\end{array}$	$[0,1]$
$-\log (1-e^x)$	$ℝ$	$\{\begin{array}{cc}{x}^{*}\log (x^{*})-(1+x^{*})\log (1+x^{*})& \text{if }{x}^{*}>0\\ 0& \text{if }{x}^{*}=0\end{array}$	${ℝ}_{+}$

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

Ссылки

• Шаблон:Cite web
• Шаблон:Cite web
• Шаблон:Cite web