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

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

Определение

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

$\langle \cdot ,\cdot \rangle :X^{*}\times X\to \mathbb {R}$

каноническое двойственное спаривание , которое определяется формулой $\left(x^{*},x\right)\mapsto x^{*}(x).$

Для функции $f:X\to \mathbb {R} \cup \{-\infty ,+\infty \}$ принимающие значения на расширенной прямой вещественных чисел , ее выпуклой сопряженной является функция

$f^{*}:X^{*}\to \mathbb {R} \cup \{-\infty ,+\infty \}$

чья стоимость в $x^{*}\in X^{*}$ определяется как верхняя граница :

$f^{*}\left(x^{*}\right):=\sup \left\{\left\langle x^{*},x\right\rangle -f(x)~\colon ~x\in X\right\},$

или, что то же самое, через нижнюю грань :

$f^{*}\left(x^{*}\right):=-\inf \left\{f(x)-\left\langle x^{*},x\right\rangle ~\colon ~x\in X\right\}.$

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

Примеры

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

• Выпуклое сопряжение аффинной функции $f(x)=\left\langle a,x\right\rangle -b$ является $$f^{*}\left(x^{*}\right)={\begin{cases}b,&x^{*}=a\\+\infty ,&x^{*}\neq a.\end{cases}}$$
• Выпуклое сопряжение степенной функции $f(x)={\frac {1}{p}}|x|^{p},1<p<\infty$ является $$f^{*}\left(x^{*}\right)={\frac {1}{q}}|x^{*}|^{q},1<q<\infty ,{\text{where}}{\tfrac {1}{p}}+{\tfrac {1}{q}}=1.$$
• Выпуклое сопряжение абсолютного значения функции $f(x)=\left|x\right|$ является $$f^{*}\left(x^{*}\right)={\begin{cases}0,&\left|x^{*}\right|\leq 1\\\infty ,&\left|x^{*}\right|>1.\end{cases}}$$
• Выпуклое сопряжение показательной функции $f(x)=e^{x}$ является $$f^{*}\left(x^{*}\right)={\begin{cases}x^{*}\ln x^{*}-x^{*},&x^{*}>0\\0,&x^{*}=0\\\infty ,&x^{*}<0.\end{cases}}$$

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

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

См. , например, эту статью.

Обозначим через кумулятивную функцию распределения величины случайной   X. F Тогда (интегрируя по частям) $$f(x):=\int _{-\infty }^{x}F(u)\,du=\operatorname {E} \left[\max(0,x-X)\right]=x-\operatorname {E} \left[\min(x,X)\right]$$имеет выпуклое сопряжение $$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].$$

Заказ

Частная интерпретация имеет преобразование $$f^{\text{inc}}(x):=\arg \sup _{t}t\cdot x-\int _{0}^{1}\max\{t-f(u),0\}\,du,$$так как это неубывающая перестановка исходной функции f ; в частности, $f^{\text{inc}}=f$ для f неубывающей.

Характеристики

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

Реверс заказа

Заявите, что $f\leq g$ тогда и только тогда, когда $f(x)\leq g(x)$ для всех $x.$ Тогда выпуклое сопряжение меняет порядок , что по определению означает, что если $f\leq g$ затем $f^{*}\geq g^{*}.$

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

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

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

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

Двусопряженный

Выпуклая сопряженная функция всегда полунепрерывна снизу . Двусопряженное ​ $f^{**}$ (выпуклая сопряженная выпуклая сопряженная функция) также является замкнутой выпуклой оболочкой , т. е. наибольшей полунепрерывной снизу выпуклой функцией с $f^{**}\leq f.$ Для правильных функций $f,$

$f=f^{**}$ тогда и только тогда, когда $f$ является выпуклым и полунепрерывным снизу по теореме Фенхеля–Моро .

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

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

$\left\langle p,x\right\rangle \leq f(x)+f^{*}(p).$

Более того, равенство имеет место только тогда, когда $p\in \partial f(x)$.Доказательство следует из определения выпуклого сопряженного: $f^{*}(p)=\sup _{\tilde {x}}\left\{\langle p,{\tilde {x}}\rangle -f({\tilde {x}})\right\}\geq \langle p,x\rangle -f(x).$

Выпуклость

Для двух функций $f_{0}$ и $f_{1}$ и номер $0\leq \lambda \leq 1$ соотношение выпуклости

$\left((1-\lambda )f_{0}+\lambda f_{1}\right)^{*}\leq (1-\lambda )f_{0}^{*}+\lambda f_{1}^{*}$

держит. ${*}$ операция сама по себе является выпуклым отображением.

Инфимальная свертка

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

$\left(f\operatorname {\Box } g\right)(x)=\inf \left\{f(x-y)+g(y)\mid y\in \mathbb {R} ^{n}\right\}.$

Позволять $f_{1},\ldots ,f_{m}$ — собственные , выпуклые и полунепрерывные снизу функции на $\mathbb {R} ^{n}.$ Тогда нижняя свертка выпукла и полунепрерывна снизу (но не обязательно правильная): и удовлетворяет

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

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

Максимизация аргумента

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

$f^{\prime }(x)=x^{*}(x):=\arg \sup _{x^{*}}{\langle x,x^{*}\rangle }-f^{*}\left(x^{*}\right)$ и

$f^{{*}\prime }\left(x^{*}\right)=x\left(x^{*}\right):=\arg \sup _{x}{\langle x,x^{*}\rangle }-f(x);$

следовательно

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

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

и более того

$f^{\prime \prime }(x)\cdot f^{{*}\prime \prime }\left(x^{*}(x)\right)=1,$

$f^{{*}\prime \prime }\left(x^{*}\right)\cdot f^{\prime \prime }\left(x(x^{*})\right)=1.$

Масштабирование свойств

Если для некоторых $\gamma >0,$ $g(x)=\alpha +\beta x+\gamma \cdot f\left(\lambda x+\delta \right)$, затем

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

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

Позволять $A:X\to Y$ — ограниченный линейный оператор . Для любой выпуклой функции $f$ на $X,$

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

где

$(Af)(y)=\inf\{f(x):x\in X,Ax=y\}$

является прообразом $f$ относительно $A$ и $A^{*}$ является сопряженным оператором $A.$

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

$f(Ax)=f(x)$ для всех $x$ и все $A\in G$

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

Таблица избранных выпуклых конъюгатов

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

$g(x)$	$\operatorname {dom} (g)$	$g^{*}(x^{*})$	$\operatorname {dom} (g^{*})$
$f(ax)$ (где $a\neq 0$)	$X$	$f^{*}\left({\frac {x^{*}}{a}}\right)$	$X^{*}$
$f(x+b)$	$X$	$f^{*}(x^{*})-\langle b,x^{*}\rangle$	$X^{*}$
$af(x)$ (где $a>0$)	$X$	$af^{*}\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)\quad (\gamma >0)$	$X^{*}$
${\frac {|x|^{p}}{p}}$ (где $p>1$)	$\mathbb {R}$	${\frac {|x^{*}|^{q}}{q}}$ (где ${\frac {1}{p}}+{\frac {1}{q}}=1$)	$\mathbb {R}$
${\frac {-x^{p}}{p}}$ (где $0<p<1$)	$\mathbb {R} _{+}$	${\frac {-(-x^{*})^{q}}{q}}$ (где ${\frac {1}{p}}+{\frac {1}{q}}=1$)	$\mathbb {R} _{--}$
${\sqrt {1+x^{2}}}$	$\mathbb {R}$	$-{\sqrt {1-(x^{*})^{2}}}$	$[-1,1]$
$-\log(x)$	$\mathbb {R} _{++}$	$-(1+\log(-x^{*}))$	$\mathbb {R} _{--}$
$e^{x}$	$\mathbb {R}$	${\begin{cases}x^{*}\log(x^{*})-x^{*}&{\text{if }}x^{*}>0\\0&{\text{if }}x^{*}=0\end{cases}}$	$\mathbb {R} _{+}$
$\log \left(1+e^{x}\right)$	$\mathbb {R}$	${\begin{cases}x^{*}\log(x^{*})+(1-x^{*})\log(1-x^{*})&{\text{if }}0<x^{*}<1\\0&{\text{if }}x^{*}=0,1\end{cases}}$	$[0,1]$
$-\log \left(1-e^{x}\right)$	$\mathbb {R} _{--}$	${\begin{cases}x^{*}\log(x^{*})-(1+x^{*})\log(1+x^{*})&{\text{if }}x^{*}>0\\0&{\text{if }}x^{*}=0\end{cases}}$	$\mathbb {R} _{+}$

См. также

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

Ссылки

• Арнольд, Владимир Игоревич (1989). Математические методы классической механики (Второе изд.). Спрингер. ISBN  0-387-96890-3 . МР   0997295 .
• Рокафеллар, Р. Тиррелл ; Уэтс, Роджер Ж.-Б. (26 июня 2009 г.). Вариационный анализ . Основные принципы математических наук. Том 317. Берлин, Нью-Йорк: Springer Science & Business Media . ISBN  9783642024313 . OCLC   883392544 .
• Рокафеллар, Р. Тайрелл (1970). Выпуклый анализ . Принстон: Издательство Принстонского университета. ISBN  0-691-01586-4 . МР   0274683 .

Дальнейшее чтение

• Тушетт, Хьюго (16 октября 2014 г.). «Краткое описание трансформаций Лежандра-Фенхеля» (PDF) . Архивировано из оригинала (PDF) 7 апреля 2017 г. Проверено 9 января 2017 г.

• Тушетт, Хьюго (21 ноября 2006 г.). «Элементы выпуклого анализа» (PDF) . Архивировано из оригинала (PDF) 26 мая 2015 г. Проверено 26 марта 2008 г.

• «Преобразования Лежандра и Лежандра-Фенхеля в пошаговом объяснении» . Проверено 18 мая 2013 г.

• Эллерман, Дэвид Паттерсон (21 марта 1995 г.). «Глава 12: Параллельное сложение, последовательно-параллельная двойственность и финансовая математика» . Интеллектуальное посягательство как образ жизни: очерки философии, экономики и математики (PDF) . Мирская философия: исследования на стыке философии и экономики. Rowman & Littlefield Publishers, Inc., стр. 237–268. ISBN  0-8476-7932-2 . Архивировано (PDF) из оригинала 5 марта 2016 г. Проверено 9 августа 2019 г. Серия G – Серия справочных, информационных и междисциплинарных предметов [1] (271 страница)

• Эллерман, Дэвид Паттерсон (май 2004 г.) [21 марта 1995 г.]. «Введение в последовательно-параллельную двойственность» (PDF) . Калифорнийский университет в Риверсайде . CiteSeerX   10.1.1.90.3666 . Архивировано из оригинала 10 августа 2019 г. Проверено 9 августа 2019 г. [2] (24 страницы)