Выпуклый анализ

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

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

Выпуклые множества

Основная статья: Выпуклое множество

Подмножество $C\subseteq X$ некоторого векторного пространства $X$ является выпуклым , если он удовлетворяет любому из следующих эквивалентных условий:

1. Если $0\leq r\leq 1$ реально и $x,y\in C$ затем $rx+(1-r)y\in C.$
2. Если $0<r<1$ реально и $x,y\in C$ с $x\neq y,$ затем $rx+(1-r)y\in C.$

Выпуклая функция на интервале.

Основная статья: Выпуклая функция

Через, $f:X\to [-\infty ,\infty ]$ будет картой, оцененной в расширенных действительных числах $[-\infty ,\infty ]=\mathbb {R} \cup \{\pm \infty \}$ с доменом $\operatorname {domain} f=X$ это выпуклое подмножество некоторого векторного пространства. Карта $f:X\to [-\infty ,\infty ]$ является выпуклой функцией, если

$f(rx+(1-r)y)\leq rf(x)+(1-r)f(y)$

( Выпуклость ≤ )

справедливо для любого реального $0<r<1$ и любой $x,y\in X$ с $x\neq y.$ Если это останется верным для $f$ когда определяющее неравенство ( Выпуклость ≤ ) заменяется строгим неравенством

$f(rx+(1-r)y)<rf(x)+(1-r)f(y)$

( Выпуклость < )

затем $f$ называется строго выпуклым .

Выпуклые функции связаны с выпуклыми множествами. В частности, функция $f$ выпукло тогда и только тогда, когда его надграфик

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

График двумерной выпуклой функции $x^{2}+xy+y^{2}.$

$\operatorname {epi} f:=\left\{(x,r)\in X\times \mathbb {R} ~:~f(x)\leq r\right\}$

( Эпиграф по определению )

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

Область определения функции $f:X\to [-\infty ,\infty ]$ обозначается $\operatorname {domain} f$ а его эффективной областью определения является множество

$\operatorname {dom} f:=\{x\in X~:~f(x)<\infty \}.$

( дом f по определению )

Функция $f:X\to [-\infty ,\infty ]$ называется правильным, если $\operatorname {dom} f\neq \varnothing$ и $f(x)>-\infty$ для всех $x\in \operatorname {domain} f.$ С другой стороны, это означает, что существует некоторый $x$ в области $f$ на котором $f(x)\in \mathbb {R}$ и $f$ также никогда не равен $-\infty .$ Другими словами, функция является правильной , если ее область определения не пуста, она никогда не принимает значение $-\infty ,$ и оно также не тождественно равно $+\infty .$ Если $f:\mathbb {R} ^{n}\to [-\infty ,\infty ]$ является собственной выпуклой функцией , то существует некоторый вектор $b\in \mathbb {R} ^{n}$ и некоторые $r\in \mathbb {R}$ такой, что

$f(x)\geq x\cdot b-r$     для каждого $x$

где $x\cdot b$ обозначает скалярное произведение этих векторов.

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

Основная статья: Выпуклое сопряжение

Выпуклое сопряжение расширенной действительной функции $f:X\to [-\infty ,\infty ]$ (не обязательно выпуклая) — функция $f^{*}:X^{*}\to [-\infty ,\infty ]$ из (непрерывного) дуального пространства $X^{*}$ из $X,$ и

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

где скобки $\left\langle \cdot ,\cdot \right\rangle$ обозначим каноническую двойственность $\left\langle x^{*},z\right\rangle :=x^{*}(z).$ Двусопряженное ​ ​ $f$ это карта $f^{**}=\left(f^{*}\right)^{*}:X\to [-\infty ,\infty ]$ определяется $f^{**}(x):=\sup _{z^{*}\in X^{*}}\left\{\left\langle x,z^{*}\right\rangle -f\left(z^{*}\right)\right\}$ для каждого $x\in X.$ Если $\operatorname {Func} (X;Y)$ обозначает набор $Y$-значные функции на $X,$ тогда карта $\operatorname {Func} (X;[-\infty ,\infty ])\to \operatorname {Func} \left(X^{*};[-\infty ,\infty ]\right)$ определяется $f\mapsto f^{*}$ называется преобразованием Лежандра-Фенхеля .

Фенхеля-Юнга

Если $f:X\to [-\infty ,\infty ]$ и $x\in X$ тогда субдифференциальное множество

${\begin{alignedat}{4}\partial f(x):&=\left\{x^{*}\in X^{*}~:~f(z)\geq f(x)+\left\langle x^{*},z-x\right\rangle {\text{ for all }}z\in X\right\}&&({\text{“}}z\in X{\text{''}}{\text{ can be replaced with: }}{\text{“}}z\in X{\text{ such that }}z\neq x{\text{''}})\\&=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle -f(x)\geq \left\langle x^{*},z\right\rangle -f(z){\text{ for all }}z\in X\right\}&&\\&=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle -f(x)\geq \sup _{z\in X}\left\langle x^{*},z\right\rangle -f(z)\right\}&&{\text{ The right hand side is }}f^{*}\left(x^{*}\right)\\&=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle -f(x)=f^{*}\left(x^{*}\right)\right\}&&{\text{ Taking }}z:=x{\text{ in the }}\sup {}{\text{ gives the inequality }}\leq .\\\end{alignedat}}$

Например, в важном частном случае, когда $f=\|\cdot \|$ это норма для $X$, это можно показать что если $0\neq x\in X$ тогда это определение сводится к:

$\partial f(x)=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle =\|x\|{\text{ and }}\left\|x^{*}\right\|=1\right\}$     и      $\partial f(0)=\left\{x^{*}\in X^{*}~:~\left\|x^{*}\right\|\leq 1\right\}.$

Для любого $x\in X$ и $x^{*}\in X^{*},$ $f(x)+f^{*}\left(x^{*}\right)\geq \left\langle x^{*},x\right\rangle ,$ которое называется неравенством Фенхеля-Юнга . Это неравенство представляет собой равенство (т.е. $f(x)+f^{*}\left(x^{*}\right)=\left\langle x^{*},x\right\rangle$) тогда и только тогда, когда $x^{*}\in \partial f(x).$ Таким образом, субдифференциальное множество $\partial f(x)$ напрямую связано с выпуклым сопряжением $f^{*}\left(x^{*}\right).$

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

Двусопряженная ​ функция $f:X\to [-\infty ,\infty ]$ является сопряженным конъюгатом, обычно записываемым как $f^{**}:X\to [-\infty ,\infty ].$ Двусопряжение полезно для демонстрации того, когда выполняется сильная или слабая двойственность (с помощью функции возмущения ).

Для любого $x\in X,$ неравенство $f^{**}(x)\leq f(x)$ следует из неравенства Фенхеля–Янга . Для правильных функций $f=f^{**}$ тогда и только тогда, когда $f$ выпукла и полунепрерывна снизу по теореме Фенхеля–Моро .

Выпуклая минимизация

Основная статья: Выпуклая оптимизация

Задача выпуклой минимизации ( основная ) имеет вид

находить $\inf _{x\in M}f(x)$ если задана выпуклая функция $f:X\to [-\infty ,\infty ]$ и выпуклое подмножество $M\subseteq X.$

Двойная задача

Основная статья: Двойственность (оптимизация)

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

В общем случае даны две двойственные пары, разделяющие локально выпуклые пространства. $\left(X,X^{*}\right)$ и $\left(Y,Y^{*}\right).$ Тогда, учитывая функцию $f:X\to [-\infty ,\infty ],$ мы можем определить основную проблему как поиск $x$ такой, что

$\inf _{x\in X}f(x).$

Если существуют условия ограничения, их можно встроить в функцию $f$ позволяя $f=f+I_{\mathrm {constraints} }$ где $I$ – индикаторная функция . Тогда пусть $F:X\times Y\to [-\infty ,\infty ]$ — функция возмущения такая, что $F(x,0)=f(x).$

Двойственная задача относительно выбранной функции возмущения имеет вид

$\sup _{y^{*}\in Y^{*}}-F^{*}\left(0,y^{*}\right)$

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

— Разрыв двойственности это разница правой и левой частей неравенства.

$\sup _{y^{*}\in Y^{*}}-F^{*}\left(0,y^{*}\right)\leq \inf _{x\in X}F(x,0).$

Этот принцип аналогичен слабой двойственности . Если две стороны равны друг другу, то говорят, что задача удовлетворяет сильной двойственности .

Существует множество условий для существования сильной дуальности, например:

• $F=F^{**}$ где $F$ — функция возмущения, связывающая основную и двойственную задачи, а $F^{**}$ является двусопряженным ​ $F$;
• основная проблема — это задача линейной оптимизации ;
• Условие Слейтера для задачи выпуклой оптимизации .

Двойственность Лагранжа

Для задачи выпуклой минимизации с ограничениями-неравенствами

$\min {}_{x}f(x)$ при условии $g_{i}(x)\leq 0$ для $i=1,\ldots ,m.$

лагранжева двойственная задача

$\sup {}_{u}\inf {}_{x}L(x,u)$ при условии $u_{i}(x)\geq 0$ для $i=1,\ldots ,m.$

где целевая функция $L(x,u)$ – двойственная функция Лагранжа, определенная следующим образом:

$L(x,u)=f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)$

См. также

• Выпуклость в экономике - важная тема в экономике.
  • Невыпуклость (экономика) - Нарушения предположений о выпуклости элементарной экономики.
• Список тем, посвященных выпуклости
• Вернер Фенхель - немецкий математик. Страницы, отображающие описания викиданных в качестве запасного варианта.

Ссылки

• Баушке, Хайнц Х .; Комбеттс, Патрик Л. (28 февраля 2017 г.). Выпуклый анализ и теория монотонных операторов в гильбертовых пространствах . Книги CMS по математике. Springer Science & Business Media . ISBN  978-3-319-48311-5 . OCLC   1037059594 .
• Бойд, Стивен ; Ванденберге, Ливен (8 марта 2004 г.). Выпуклая оптимизация . Кембриджская серия по статистической и вероятностной математике. Кембридж, Великобритания, Нью-Йорк: Издательство Кембриджского университета . ISBN  978-0-521-83378-3 . OCLC   53331084 .
• Хириарт-Уррути, Ж.-Б. ; Лемарешаль, К. (2001). Основы выпуклого анализа . Берлин: Springer-Verlag. ISBN  978-3-540-42205-1 .
• Кусраев, А.Г.; Кутателадзе, Семен Самсонович (1995). Субдифференциалы: теория и приложения . Дордрехт: Kluwer Academic Publishers. ISBN  978-94-011-0265-0 .
• Рокафеллар, Р. Тиррелл ; Уэтс, Роджер Ж.-Б. (26 июня 2009 г.). Вариационный анализ . Основные принципы математических наук. Том 317. Берлин, Нью-Йорк: Springer Science & Business Media . ISBN  9783642024313 . OCLC   883392544 .
• Рудин, Уолтер (1991). Функциональный анализ . Международная серия по чистой и прикладной математике. Том. 8 (Второе изд.). Нью-Йорк, штат Нью-Йорк: McGraw-Hill Science/Engineering/Math . ISBN  978-0-07-054236-5 . OCLC   21163277 .
• Певец Иван (1997). Абстрактный выпуклый анализ . Серия монографий и продвинутых текстов Канадского математического общества. Нью-Йорк: John Wiley & Sons, Inc., стр. xxii+491. ISBN  0-471-16015-6 . МР   1461544 .
• Стер, Дж.; Вицгалл, К. (1970). Выпуклость и оптимизация в конечных размерностях . Том. 1. Берлин: Шпрингер. ISBN  978-0-387-04835-2 .
• Залинеску, Константин (30 июля 2002 г.). Выпуклый анализ в общих векторных пространствах . Ривер Эдж, Нью-Джерси, Лондон: World Scientific Publishing . ISBN  978-981-4488-15-0 . МР   1921556 . OCLC   285163112 – через Интернет-архив .

Внешние ссылки

• СМИ, связанные с выпуклым анализом, на Викискладе?