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

Обобщение преобразования Лежандра

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

Определение

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

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

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

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

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

значение которого определяется как супремум : ${\displaystyle x^{*}\in X^{*}}$

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

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

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

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

Примеры

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

• Выпуклое сопряжение аффинной функции — это ${\displaystyle f(x)=\left\langle a,x\right\rangle -b}$ $${\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 ,{\text{where}}{\tfrac {1}{p}}+{\tfrac {1}{q}}=1.}$$
• Выпуклая сопряженная функция абсолютного значения имеет вид ${\displaystyle f(x)=\left|x\right|}$ $${\displaystyle f^{*}\left(x^{*}\right)={\begin{cases}0,&\left|x^{*}\right|\leq 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].}$$

Заказ

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

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

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

Реверсирование заказа

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

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

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

и из неравенства максимума и минимума, что

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

Биконъюгата

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

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

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

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

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

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

Выпуклость

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

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

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

Инфинимальная извилина

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

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

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

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

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

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

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

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

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

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

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

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

и более того

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

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

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

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

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

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

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

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

где

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

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

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

${\displaystyle f(Ax)=f(x)}$для всех и каждого ${\displaystyle x}$ ${\displaystyle A\in G}$

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

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

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

Смотрите также

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

Ссылки

1. "Legendre Transform" . Получено 14 апреля 2019 г. .
2. Фелпс, Роберт (1993). Выпуклые функции, монотонные операторы и дифференцируемость (2-е изд.). Springer. стр. 42. ISBN 0-387-56715-1.
3. Bauschke, Heinz H.; Goebel, Rafal; Lucet, Yves; Wang, Xianfu (2008). "The Proximal Average: Basic Theory". SIAM Journal on Optimization . 19 (2): 766. CiteSeerX 10.1.1.546.4270 . doi :10.1137/070687542. 
4. Иоффе А.Д. и Тихомиров В.М. (1979), Теория экстремальных условий . Deutscher Verlag der Wissenschaften . Сац 3.4.3
5. Борвейн, Джонатан ; Льюис, Адриан (2006). Выпуклый анализ и нелинейная оптимизация: теория и примеры (2-е изд.). Springer. стр. 50–51. ISBN 978-0-387-29570-1.

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

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

• Тушетт, Гюго (16.10.2014). "Legendre-Fenchel трансформируется в двух словах" (PDF) . Архивировано из оригинала (PDF) 2017-04-07 . Получено 2017-01-09 .

• Тушетт, Гюго (21.11.2006). "Элементы выпуклого анализа" (PDF) . Архивировано из оригинала (PDF) 2015-05-26 . Получено 2008-03-26 .

• "Преобразования Лежандра и Лежандра-Фенхеля в пошаговом объяснении" . Получено 18.05.2013 .

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

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