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

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

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

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

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

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

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

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

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

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

${\displaystyle f(\lambda x+(1-\lambda )y)\leqslant \lambda f(x)+(1-\lambda )f(y)}$^[1].

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

${\displaystyle \left\{(x,r)\in X\times \mathbf {R} :f(x)\leqslant r\right\}}$

является выпуклым множеством^[1].

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

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

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

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

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

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

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

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

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

(Прямая) задача выпуклого программирования, это задача вида

${\displaystyle \inf _{x\in M}f(x)}$

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

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

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

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

общем случае, если дана двойственная пара^{[англ.][4]} отделимых локально выпуклых пространств ${\displaystyle \left(X,X^{*}\right)}$ и функция ${\displaystyle f:X\to \mathbb {R} \cup \{+\infty \}}$, мы можем определить прямую задачу как нахождение такого ${\displaystyle {\hat {x}}}$, что ${\displaystyle f({\hat {x}})=\inf _{x\in X}f(x).\,}$ Другими словами, ${\displaystyle f({\hat {x}})}$ — это инфимум (точная нижняя граница) функции ${\displaystyle f}$.

Если имеются ограничения, они могут быть встроены в функцию ${\displaystyle f}$, если положить ${\displaystyle {\tilde {f}}=f+I_{\mathrm {constraints} }}$, где ${\displaystyle I}$ — индикаторная функция^[англ.]. Пусть теперь ${\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \}}$ (для другой двойственной пары ${\displaystyle \left(Y,Y^{*}\right)}$) будет функцией возмущений^[англ.], такой что ${\displaystyle F(x,0)={\tilde {f}}(x)}$^[5].

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

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

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

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

${\displaystyle \sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leqslant \inf _{x\in X}F(x,0),\,}$

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

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

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

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

• F = F**, где F является функцией возмущений^[англ.] для прямой и двойственной задач, а F** является двойным сопряжением функции F;
• прямая задача является задачей линейного программирования;
• Условие Слейтера для задач выпуклого программирования^[8][9].

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

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

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

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

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

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

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