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

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

Выпуклое множество является множеством ${\displaystyle C\subseteq X}$ для некоторого векторного пространства X , такое что для любых ${\displaystyle x,y\in C}$ и ${\displaystyle \lambda \in [0,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)}$ .

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

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

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

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

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

${\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 выпукла и полунепрерывна снизу по теореме Фенхеля — Моро .

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

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

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

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

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

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

общем случае, если дана отделимых локально выпуклых пространств ${\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)}$ .

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

${\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 }$ означает супремум (точную верхнюю границу) .

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

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

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

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

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

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

${\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)}$

Примечания

Литература

• Осипенко К.Ю. (консп. лекций). М.: МГУ. 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. . — 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.