Опукле спряження

Опукле спряження функції — це узагальнення перетворення Лежандра, яке застосовується до неопуклих функцій. Воно відоме також як перетворення Лежандра — Фенхеля або перетворення Фенхеля (за іменами Адрієна-Марі Лежандра та Шаблон:Нп). Спряження використовується для перетворення задачі оптимізації у відповідну двоїсту задачу, яку, можливо, простіше розв'язати.

Визначення

Нехай $X$ — дійсний топологічний векторний простір і нехай $X^{*}$ — двоїстий простір для $X$. Позначимо Шаблон:Не перекладено через

$⟨\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$ не спадає.

Властивості

Опукле спряження замкнутої опуклої функції також є замкнутою опуклою функцією. Опукле спряження поліедральної опуклої функції (опуклої функції з многогранним надграфіком) також є поліедральною опуклою функцією.

Обернення порядку

Опукле спряження обертає порядок — якщо $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^{*}),$

та з Шаблон:Не перекладено

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

Подвійне спряження

Опукле спряження функції завжди напівнеперервне знизу. Подвійне спряження $f^{**}$ (опукле спряження опуклого спряження) є також замкненою опуклою оболонкою, тобто найбільшою напівнеперервною знизу опуклою функцією з $f^{**}⩽f$ . Для Шаблон:Не перекладено $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