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

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

Визначення

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

${\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\}.}$

Це визначення можна інтерпретувати як кодування опуклої оболонки (надграфіка) функції в термінах її (опорних гіперплощин) .

Приклади

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

${\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^{*}),}$

та з ^[en]

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

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

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

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

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

Максимізувальний аргумент

Якщо функція ${\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.

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

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

тоді й лише тоді, коли опукле спряження f^* симетричне для G.

Таблиця деяких опуклих спряжень

У таблиці наведено перетворення Лежандра для багатьох поширених функцій, а також для декількох корисних властивостей.

${\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} _{+}}$

Див. також

• Двоїста задача
• (Теорема двоїстості Фенхеля)
• (Перетворення Лежандра)
• (Нерівність Юнга)

Примітки

1. Legendre Transform. Процитовано 14 квітня 2019.
2. Frank Nielsen. Legendre transformation and information geometry (PDF).
3. Phelps, 1991, с. 42.
4. Bauschke, Goebel, Lucet, Wang, 2008, с. 766.
5. Иоффе, Тихомиров, 1974, с. утверждение 3.4.3.
6. Borwein, Lewis, 2006, с. 50–51.

Література

• Robert R. Phelps. Convex Functions, Monotone Operators and Differentiability. — Springer, 1991. — .
• 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. — .
• Владимир Игоревич Арнольд. Математические методы классической механики. — М. : «Наука», 1989.
• R. Tyrrell Rockafellar. Convex Analysis. — Princeton : Princeton University Press, 1970. — .

Посилання

• Touchette, Hugo (16 жовтня 2014). (PDF) (англійською) . Архів (PDF) за 7 квітня 2017. Процитовано 9 січня 2017.
• Touchette, Hugo (21 листопада 2006). (PDF) (англійською) . Архів оригіналу (PDF) за 26 травня 2015. Процитовано 26 березня 2008.
• Legendre and Legendre-Fenchel transforms in a step-by-step explanation (англійською) . Процитовано 18 травня 2013.