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

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

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

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

Шаблон:Основная статья Выпуклое множество является множеством $C\subseteq X$ для некоторого векторного пространства X, такое что для любых $x,y\in C$ и $\lambda \in [0,1]$Шаблон:Sfn

$\lambda x+(1-\lambda )y\in C$.

Выпуклая функция

Шаблон:Основная статья Выпуклая функция — любая расширенная вещественнозначная функция $f:X\to ℝ\cup \{\pm \mathrm{\infty }\}$, которая удовлетворяет неравенству Йенсена, то есть, для любых $x,y\in X$ и любой $\lambda \in [0,1]$

$f(\lambda x+(1-\lambda )y)⩽\lambda f(x)+(1-\lambda )f(y)$Шаблон:Sfn.

Эквивалентно, выпуклой функцией является любая (расширенная) вещественнозначная функция, такая что её надграфик

$\{(x,r)\in X\times 𝐑:f(x)⩽r\}$

является выпуклым множествомШаблон:Sfn.

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

Шаблон:Основная статья Выпуклое сопряжение расширенной вещественнозначной (не обязательно выпуклой) функции $f:X\to ℝ\cup \{\pm \mathrm{\infty }\}$ — это функция $f^{*}:X^{*}\to ℝ\cup \{\pm \mathrm{\infty }\}$, где X* является двойственным пространством пространства XШаблон:Sfn, такая что

$f^{*}(x^{*})=\underset{x\in X}{\sup }\{⟨x^{*},x⟩-f(x)\}.$

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

Двойное сопряжение функции $f:X\to ℝ\cup \{\pm \mathrm{\infty }\}$ — это сопряжение сопряжения, что обычно записывается как $f^{**}:X\to ℝ\cup \{\pm \mathrm{\infty }\}$. Двойное сопряжение полезно, когда нужно показать, что выполняется сильная или слабая двойственность (с помощью Шаблон:Не переведено 5).

Для любого $x\in X$ неравенство $f^{**}(x)⩽f(x)$ вытекает из неравенства Фенхеля. Для Шаблон:Не переведено 5 f = f** тогда и только тогда, когда f выпукла и полунепрерывна снизу по теореме Фенхеля — МороШаблон:SfnШаблон:Sfn.

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

Шаблон:Основная статья (Прямая) задача выпуклого программирования, это задача вида

$\underset{x\in M}{\inf }f(x)$

такая что $f:X\to ℝ\cup \{\pm \mathrm{\infty }\}$ является выпуклой функцией, а $M\subseteq X$ является выпуклым множеством.

Двойственная задача

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

общем случае, если дана Шаблон:Не переведено 5 отделимых локально выпуклых пространств $(X,X^{*})$ и функция $f:X\to ℝ\cup \{+\mathrm{\infty }\}$, мы можем определить прямую задачу как нахождение такого $\hat{x}$, что $f(\hat{x})=\underset{x\in X}{\inf }f(x).$ Другими словами, $f(\hat{x})$ — это инфимум (точная нижняя граница) функции $f$.

Если имеются ограничения, они могут быть встроены в функцию $f$, если положить $\tilde{f}=f+I_{\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{s}}$, где $I$ — Шаблон:Не переведено 5. Пусть теперь $F:X\times Y\to ℝ\cup \{+\mathrm{\infty }\}$ (для другой двойственной пары $(Y,Y^{*})$) будет Шаблон:Не переведено 5, такой что $F(x,0)=\tilde{f}(x)$Шаблон:Sfn.

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

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

где F* является выпуклым сопряжением по обоим переменным функции F.

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

$\underset{y^{*}\in Y^{*}}{\sup }-F^{*}(0,y^{*})⩽\underset{x\in X}{\inf }F(x,0),$

где $F^{*}$ — выпуклое сопряжение от обоих переменных, а $\sup$ означает супремум (точную верхнюю границу)Шаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn.

$\underset{y^{*}\in Y^{*}}{\sup }-F^{*}(0,y^{*})⩽\underset{x\in X}{\inf }F(x,0).$

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

Существует много условий для сильной двойственности, такие как:

• F = F**, где F является Шаблон:Не переведено 5 для прямой и двойственной задач, а F** является двойным сопряжением функции F;
• прямая задача является задачей линейного программирования;
• Условие Слейтера для задач выпуклого программированияШаблон:SfnШаблон:Sfn.

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

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

$\underset{x}{\min }f(x)$ при условиях $g_i(x)⩽0$ для i = 1, …, m.

двойственной задачей Лагранжа будет

$\underset{u}{\sup }\underset{x}{\inf }L(x,u)$ при условиях $u_i(x)⩾0$ для i = 1, …, m,

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

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

Литература

• Осипенко К.Ю. Оптимизация. Ч. 1. Выпуклый анализ (консп. лекций). М.: МГУ. 57 с.
• Осипенко К.Ю. Выпуклый анализ (программа курса и консп. лекций). М.: МГУ. 68 с.
• Петров Н.Н. Выпуклый анализ (консп. лекций). Ижевск: УдмГУ, 2009. 160 с.
• Жадан В. Г. Методы оптимизации. Часть I. Введение в выпуклый анализ и теорию оптимизации: учеб. пос. для студ. вузов по направл. ... "Прикладные математика и физика". Москва : МФТИ, 2014. ISBN 978-5-7417-0514-8. (Ч. I). 271 с. Выпуск 300 шт.
• Элементы выпуклого и сильно выпуклого анализа : учебное пособие для студентов высших учебных заведений, обучающихся по направлению "Прикладные математика и физика" и смежным направлениям и специальностям / Е. С. Половинкин, М. В. Балашов. - 2-е изд., испр. и доп. - Москва : Физматлит, 2007. - 438 с.; 22 см. - (Физтеховский учебник).; ISBN 978-5-9221-0896-6
• Протасов В.Ю. Выпуклый анализ (консп. лекций. Мехмат МГУ, экономич. поток, 2009 г.). М.: МГУ.
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга