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

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

Определение

Пусть [math]\displaystyle{ X }[/math] будет вещественным топологическим векторным пространством и пусть [math]\displaystyle{ X^{*} }[/math] будет двойственным пространством для [math]\displaystyle{ X }[/math]. Обозначим двойственную пару через

[math]\displaystyle{ \langle \cdot , \cdot \rangle : X^{*} \times X \to \mathbb{R}. }[/math]

Для функции

[math]\displaystyle{ f : X \to \mathbb{R} \cup \{ - \infty, + \infty \} }[/math],

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

[math]\displaystyle{ f^{*} : X^{*} \to \mathbb{R} \cup \{ - \infty, + \infty \} }[/math]

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

[math]\displaystyle{ f^{{*}} \left( x^{*} \right) := \sup \left \{ \left. \left\langle x^{*} , x \right\rangle - f \left( x \right) \right|x \in X \right\}, }[/math]

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

[math]\displaystyle{ f^{{*}} \left( x^{*} \right) := - \inf \left \{ \left. f \left( x \right) - \left\langle x^{*} , x \right\rangle \right|x \in X \right\}. }[/math]

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

Примеры

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

[math]\displaystyle{ f(x)=\left\langle a,x \right\rangle - b,\, a \in \mathbb{R}^n, b \in \mathbb{R} }[/math]

равно

[math]\displaystyle{ f^{*}\left(x^{*} \right)=\begin{cases} b, & x^{*} = a \\ +\infty, & x^{*} \ne a. \end{cases} }[/math]

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

[math]\displaystyle{ f(x)=\frac{1}{p}|x|^p,\,1\lt p\lt \infty }[/math]

равно

[math]\displaystyle{ f^{*}\left(x^{*} \right)=\frac{1}{q}|x^{*}|^q,\,1\lt q\lt \infty }[/math]

где [math]\displaystyle{ \tfrac{1}{p} + \tfrac{1}{q}=1. }[/math]

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

[math]\displaystyle{ f(x)=\left|x \right| }[/math]

равно

[math]\displaystyle{ f^{*}\left(x^{*} \right)=\begin{cases} 0, & \left|x^{*} \right|\leqslant 1 \\ \infty, & \left|x^{*} \right| \gt 1. \end{cases} }[/math]

Выпуклое сопряжение показательной функции [math]\displaystyle{ f(x)=\,\! e^x }[/math] равно

[math]\displaystyle{ f^{*}\left(x^{*} \right) = \begin{cases} x^{*} \ln x^{*} - x^{*} , & x^{*} \gt 0 \\ 0 , & x^{*} =0 \\ \infty , & x^{*} \lt 0. \end{cases} }[/math]

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

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

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

[math]\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] }[/math]

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

[math]\displaystyle{ f^{*}(p)=\int_0^p F^{-1}(q) \, dq=(p-1)F^{-1}(p)+\operatorname{E}\left[\min(F^{-1}(p),X)\right] =p F^{-1}(p)-\operatorname{E}\left[\max(0,F^{-1}(p)-X)\right]. }[/math]

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

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

[math]\displaystyle{ f^\text{inc}(x):= \arg \sup_t \,t\cdot x-\int_0^1 \max\{t-f(u),0\} \, \mathrm d u, }[/math]

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

Свойства

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

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

Выпуклое сопряжение обращает порядок — если [math]\displaystyle{ f \leqslant g }[/math], то [math]\displaystyle{ f^* \geqslant g^* }[/math]. Здесь

[math]\displaystyle{ (f \leqslant g ) :\iff (\forall x, f(x) \leqslant g(x)). }[/math]

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

[math]\displaystyle{ \left(\inf_\alpha f_\alpha\right)^*(x^*)= \sup_\alpha f_\alpha^*(x^*), }[/math]

и из max–min неравенства

[math]\displaystyle{ \left(\sup_\alpha f_\alpha\right)^*(x^*)\leqslant \inf_\alpha f_\alpha^*(x^*). }[/math]

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

Выпуклое сопряжение функции всегда полунепрерывно снизу. Двойное сопряжение [math]\displaystyle{ f^{**} }[/math] (выпуклое сопряжение выпуклого сопряжения) является также замкнутой выпуклой оболочкой, то есть наибольшей полунепрерывной снизу выпуклой функцией с [math]\displaystyle{ f^{**}\leqslant f }[/math]. Для выпуклых собственных функций [math]\displaystyle{ f=f^{**} }[/math] тогда и только тогда, когда f выпукла и полунепрерывна снизу по теореме Фенхеля — Моро.

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

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

[math]\displaystyle{ \left\langle p,x \right\rangle \leqslant f(x) + f^*(p). }[/math]

Доказательство следует немедленно из определения выпуклого сопряжения: [math]\displaystyle{ f^*(p)=\sup_{\tilde x} \{ \langle p,\tilde x \rangle - f(\tilde x) \} \geqslant \langle p,x \rangle - f(x) }[/math].

Выпуклость

Для двух функций [math]\displaystyle{ f_0 }[/math] и [math]\displaystyle{ f_1 }[/math] и числа [math]\displaystyle{ 0\leqslant \lambda\leqslant 1 }[/math] выполняется

[math]\displaystyle{ \left((1-\lambda)f_0+\lambda f_1\right)^{*}\leqslant (1-\lambda)f_0^{*}+ \lambda f_1^{*} }[/math].

Здесь операция [math]\displaystyle{ {*} }[/math] — это выпуклое отображение в себя.

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

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

[math]\displaystyle{ \left(f \Box g\right)(x)=\inf \left \{ f(x-y) + g(y) \,|\, y \in \mathbb{R}^n \right \}. }[/math]

Пусть f₁, …, f_m будут правильными выпуклыми полунепрерывными снизу функциями на [math]\displaystyle{ \R^n }[/math]. Тогда инфимальная конволюция выпукла и полунепрерывна снизу (но не обязательно будет правильной функцией) и удовлетворяет равенству

[math]\displaystyle{ \left( f_1 \Box \cdots \Box f_m \right)^{*}=f_1^{*} + \cdots + f_m^{*}. }[/math]

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

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

Если функция [math]\displaystyle{ f }[/math] дифференцируема, то её производная является максимизирующим аргументом при вычислении выпуклого сопряжения:

[math]\displaystyle{ f^\prime(x)=x^*(x):= \arg\sup_{x^{*}} {\langle x, x^{*}\rangle} -f^{*}(x^{*}) }[/math] и

[math]\displaystyle{ f^{{*}\prime}(x^{*})=x(x^{*}):= \arg\sup_x {\langle x, x^{*}\rangle}-f(x); }[/math]

откуда

[math]\displaystyle{ x= \nabla f^{{*}}(\nabla f(x)), }[/math]

[math]\displaystyle{ x^{*}= \nabla f(\nabla f^{{*}}(x^{*})), }[/math]

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

[math]\displaystyle{ f^{\prime\prime}(x) \cdot f^{{*}\prime\prime} (x^{*}(x))=1, }[/math]

[math]\displaystyle{ f^{{*}\prime\prime}(x^{*})\cdot f^{\prime\prime}(x(x^{*}))=1. }[/math]

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

Если для некоторого [math]\displaystyle{ \gamma\gt 0 }[/math] [math]\displaystyle{ \,g(x)=\alpha+ \beta x +\gamma \cdot f(\lambda x+\delta) }[/math], то

[math]\displaystyle{ g^{*}(x^{*})= -\alpha- \delta\frac{x^{*}-\beta}\lambda +\gamma \cdot f^{*} \left(\frac {x^{*}-\beta}{\lambda \gamma}\right). }[/math]

В случае дополнительного параметра (скажем, [math]\displaystyle{ \alpha }[/math]), более того,

[math]\displaystyle{ f_\alpha(x)=-f_\alpha(\tilde x), }[/math]

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

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

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

[math]\displaystyle{ \left(A f\right)^{*}=f^{*} A^{*} }[/math]

где

[math]\displaystyle{ (A f)(y)=\inf\{ f(x) : x \in X , A x=y \} }[/math]

является прообразом f для A, а A^* является сопряжённым оператором для A.

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

[math]\displaystyle{ f\left(A x\right)=f(x), \; \forall x, \; \forall A \in G }[/math]

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

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

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

[math]\displaystyle{ g(x) }[/math]	[math]\displaystyle{ \operatorname{dom}(g) }[/math]	[math]\displaystyle{ g^*(x^*) }[/math]	[math]\displaystyle{ \operatorname{dom}(g^*) }[/math]
[math]\displaystyle{ f(ax) }[/math] (где [math]\displaystyle{ a \neq 0 }[/math])	[math]\displaystyle{ X }[/math]	[math]\displaystyle{ f^*\left(\frac{x^*}{a}\right) }[/math]	[math]\displaystyle{ X^* }[/math]
[math]\displaystyle{ f(x + b) }[/math]	[math]\displaystyle{ X }[/math]	[math]\displaystyle{ f^*(x^*) - \langle b,x^* \rangle }[/math]	[math]\displaystyle{ X^* }[/math]
[math]\displaystyle{ a f(x) }[/math] (где [math]\displaystyle{ a \gt 0 }[/math])	[math]\displaystyle{ X }[/math]	[math]\displaystyle{ a f^*\left(\frac{x^*}{a}\right) }[/math]	[math]\displaystyle{ X^* }[/math]
[math]\displaystyle{ \alpha+ \beta x+ \gamma \cdot f(\lambda x+\delta) }[/math]	[math]\displaystyle{ X }[/math]	[math]\displaystyle{ -\alpha- \delta\frac{x^*-\beta}\lambda+ \gamma \cdot f^* \left(\frac {x^*-\beta}{\gamma \lambda}\right)\quad (\gamma\gt 0) }[/math]	[math]\displaystyle{ X^* }[/math]
[math]\displaystyle{ \frac{|x|^p}{p} }[/math] (где [math]\displaystyle{ p \gt 1 }[/math])	[math]\displaystyle{ \mathbb{R} }[/math]	[math]\displaystyle{ \frac{|x^*|^q}{q} }[/math] (где [math]\displaystyle{ \frac{1}{p} + \frac{1}{q}=1 }[/math])	[math]\displaystyle{ \mathbb{R} }[/math]
[math]\displaystyle{ \frac{-x^p}{p} }[/math] (где [math]\displaystyle{ 0 \lt p \lt 1 }[/math])	[math]\displaystyle{ \mathbb{R}_+ }[/math]	[math]\displaystyle{ \frac{-(-x^*)^q}q }[/math] (где [math]\displaystyle{ \frac 1 p + \frac 1 q=1 }[/math])	[math]\displaystyle{ \mathbb{R}_{-} }[/math]
[math]\displaystyle{ \sqrt{1 + x^2} }[/math]	[math]\displaystyle{ \mathbb{R} }[/math]	[math]\displaystyle{ -\sqrt{1 - (x^*)^2} }[/math]	[math]\displaystyle{ [-1,1] }[/math]
[math]\displaystyle{ -\log(x) }[/math]	[math]\displaystyle{ \mathbb{R}_{++} }[/math]	[math]\displaystyle{ -(1 + \log(-x^*)) }[/math]	[math]\displaystyle{ \mathbb{R}_{--} }[/math]
[math]\displaystyle{ e^x }[/math]	[math]\displaystyle{ \mathbb{R} }[/math]	[math]\displaystyle{ \begin{cases}x^* \log(x^*) - x^* & \text{if }x^* \gt 0\\ 0 & \text{if }x^*=0\end{cases} }[/math]	[math]\displaystyle{ \mathbb{R}_{+} }[/math]
[math]\displaystyle{ \log\left(1 + e^x\right) }[/math]	[math]\displaystyle{ \mathbb{R} }[/math]	[math]\displaystyle{ \begin{cases}x^* \log(x^*) + (1 - x^*) \log(1 - x^*) & \text{if }0 \lt x^* \lt 1\\ 0 & \text{if }x^*=0,1\end{cases} }[/math]	[math]\displaystyle{ [0,1] }[/math]
[math]\displaystyle{ -\log\left(1 - e^x\right) }[/math]	[math]\displaystyle{ \mathbb{R} }[/math]	[math]\displaystyle{ \begin{cases}x^* \log(x^*) - (1 + x^*) \log(1 + x^*) & \text{if }x^* \gt 0\\ 0 & \text{if }x^*=0\end{cases} }[/math]	[math]\displaystyle{ \mathbb{R}_+ }[/math]

См. также

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

Литература

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

Ссылки

• Touchette, Hugo Legendre-Fenchel transforms in a nutshell (неопр.) (PDF) (недоступная ссылка) (16 октября 2014). Дата обращения: 9 января 2017. Архивировано 7 апреля 2017 года.
• Touchette, Hugo Elements of convex analysis (неопр.) (PDF) (недоступная ссылка) (21 ноября 2006). Дата обращения: 26 марта 2008. Архивировано 26 мая 2015 года.
• Legendre and Legendre-Fenchel transforms in a step-by-step explanation (неопр.). Дата обращения: 18 мая 2013.