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

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

Определение

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

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

Для функции

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

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

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

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

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

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

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

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

Примеры

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

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

равно

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

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

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

равно

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

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

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

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

равно

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

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

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

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

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

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

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

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

$f^{\ast }(p)={\int }_0^p{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-{\int }_0^{1}max\{t-f(u),0\}\mathrm{d}u,$

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

Свойства

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

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

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

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

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

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

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

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

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

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

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

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

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

Доказательство следует немедленно из определения выпуклого сопряжения: $f^{\ast }(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)}^{\ast }⩽(1-\lambda )f_0^{\ast }+\lambda f_1^{\ast }$.

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

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

Инфимальная конволюция двух функций 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)}^{\ast }=f_1^{\ast }+\cdots +f_m^{\ast }.$

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

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

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

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

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

откуда

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где

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

См. также

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

Литература

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

Ссылки

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