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

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

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

Выпуклые множестваПравить

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

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

$\mathrm{\lambda <!--\; \lambda \; -->}x+(1-<!--\; -\; -->\mathrm{\lambda <!--\; \lambda \; -->})y\in <!--\; \in \; -->C$$\lambda x+(1-\lambda )y\in C$ .

Выпуклая функцияПравить

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

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

$f(\mathrm{\lambda <!--\; \lambda \; -->}x+(1-<!--\; -\; -->\mathrm{\lambda <!--\; \lambda \; -->})y)⩽<!--\; ⩽\; -->\mathrm{\lambda <!--\; \lambda \; -->}f(x)+(1-<!--\; -\; -->\mathrm{\lambda <!--\; \lambda \; -->})f(y)$$f(\lambda x+(1-\lambda )y)\leqslant \lambda f(x)+(1-\lambda )f(y)$ .

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

$\left\{(x,r)\in <!--\; \in \; -->X\times <!--\; \times \; -->\mathbf{R}:f(x)⩽<!--\; ⩽\; -->r\right\}$$\left\{(x,r)\in X\times \mathbf {R} :f(x)\leqslant r\right\}$ 

является выпуклым множеством.

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

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

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

$f^{\ast <!--\; \ast \; -->}(x^{\ast <!--\; \ast \; -->})=\underset{x\in <!--\; \in \; -->X}{sup}\left\{⟨<!--\; ⟨\; -->x^{\ast <!--\; \ast \; -->},x⟩<!--\; ⟩\; -->-<!--\; -\; -->f(x)\right\}.$$f^{*}(x^{*})=\sup _{x\in X}\left\{\langle x^{*},x\rangle -f(x)\right\}.$ 

Двойное сопряжениеПравить

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

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

Выпуклая минимизацияПравить

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

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

$\underset{x\in <!--\; \in \; -->M}{inf}f(x)$$\inf _{x\in M}f(x)$ 

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

Двойственная задачаПравить

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

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

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

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

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

$\underset{y^{\ast <!--\; \ast \; -->}\in <!--\; \in \; -->Y^{\ast <!--\; \ast \; -->}}{sup}-<!--\; -\; -->F^{\ast <!--\; \ast \; -->}(0,y^{\ast <!--\; \ast \; -->})$$\sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})$ 

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

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

$\underset{y^{\ast <!--\; \ast \; -->}\in <!--\; \in \; -->Y^{\ast <!--\; \ast \; -->}}{sup}-<!--\; -\; -->F^{\ast <!--\; \ast \; -->}(0,y^{\ast <!--\; \ast \; -->})⩽<!--\; ⩽\; -->\underset{x\in <!--\; \in \; -->X}{inf}F(x,0),$$\sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leqslant \inf _{x\in X}F(x,0),\,$ 

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

$\underset{y^{\ast <!--\; \ast \; -->}\in <!--\; \in \; -->Y^{\ast <!--\; \ast \; -->}}{sup}-<!--\; -\; -->F^{\ast <!--\; \ast \; -->}(0,y^{\ast <!--\; \ast \; -->})⩽<!--\; ⩽\; -->\underset{x\in <!--\; \in \; -->X}{inf}F(x,0).$$\sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leqslant \inf _{x\in X}F(x,0).$ 

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

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

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

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

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

$\underset{x}{min}f(x)$$\min _{x}f(x)$  при условиях $g_i(x)⩽<!--\; ⩽\; -->0$$g_{i}(x)\leqslant 0$  для i = 1, …, m.

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

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

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

$L(x,u)=f(x)+\underset{j=1}{\overset{m}{\sum <!--\; \sum \; -->}}{u}_j{g}_j(x)$$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 г.). М.: МГУ.
• Jonathan Borwein, Adrian Lewis. Convex Analysis and Nonlinear Optimization: Theory and Examples. — 2. — Springer, 2006. — ISBN 978-0-387-29570-1.
• Stephen Boyd, Lieven Vandenberghe. Convex Optimization. — Cambridge University Press, 2004. — ISBN 978-0-521-83378-3.
• R. Tyrrell Rockafellar. Convex Analysis. — Princeton, NJ: Princeton University Press, 1997. — ISBN 978-0-691-01586-6.
• Radu Ioan Boţ, Gert Wanka, Sorin-Mihai Grad. Duality in Vector Optimization. — Springer, 2009. — ISBN 978-3-642-02885-4.
• Constantin Zălinescu. Convex analysis in general vector spaces. — River Edge, NJ: World Scientific Publishing Co., Inc., 2002. — С. 106–113. — ISBN 981-238-067-1.
• Ernö Robert Csetnek. Overcoming the failure of the classical generalized interior-point regularity conditions in convex optimization. Applications of the duality theory to enlargements of maximal monotone operators. — Logos Verlag Berlin GmbH, 2010. — ISBN 978-3-8325-2503-3.
• Jonathan Borwein, Adrian Lewis. Convex Analysis and Nonlinear Optimization: Theory and Examples. — 2. — Springer, 2006. — ISBN 978-0-387-29570-1.
• Hiriart-Urruty J.-B., Lemaréchal C. Fundamentals of convex analysis. — Berlin: Springer-Verlag, 2001. — ISBN 978-3-540-42205-1.
• Ivan Singer. Abstract convex analysis. — New York: John Wiley & Sons, Inc., 1997. — С. xxii+491. — (Canadian Mathematical Society series of monographs and advanced texts). — ISBN 0-471-16015-6.
• Stoer J., Witzgall C. Convexity and optimization in finite dimensions. — Berlin: Springer, 1970. — Т. 1. — ISBN 978-0-387-04835-2.
• Kusraev A.G., Kutateladze S.S. Subdifferentials: Theory and Applications. — Dordrecht: Kluwer Academic Publishers, 1995. — ISBN 978-94-011-0265-0.
• Кусраев А. Г., Кутателадзе С. С. Субдифференциалы. Теория и приложения. Ч. 2. — 2-е, перераб.. — Новосибирск: Изд-во Ин-та математики, 2003. — ISBN 5–86134–116–8.