Опуклий аналіз

Опуклий аналіз — це гілка математики, присвячена вивченню властивостей опуклих функцій і опуклих множин, часто застосовується в опуклому програмуванні, підгалузі теорії оптимізації.

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

Опуклі множини

Опукла множина — це множина ${\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 \}}$. Подвійне спряження корисне, коли потрібно показати, що виконується сильна або (слабка двоїстість) (за допомогою ^[en]).

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

Опукла мінімізація

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

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

така що ${\displaystyle f:X\to \mathbb {R} \cup \{\pm \infty \}}$ є опуклою функцією, а ${\displaystyle M\subseteq X}$ є опуклою множиною.

Двоїста задача

Принцип двоїстості в оптимізації стверджує, що задачу оптимізації можна розглядати з двох точок зору як пряму задачу або двоїсту задачу.

Загалом, якщо дано ^[en] відокремлюваних (локально опуклих просторів) ${\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}$ — ^[en]. Нехай тепер ${\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \}}$ (для іншої двоїстої пари ${\displaystyle \left(Y,Y^{*}\right)}$) — ^[en], така що ${\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 — ^[en] для прямої та двоїстої задач, а 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 ,

де цільова функція${\displaystyle L(x,u)}$ є двоїстою функцією Лагранжа, визначеною так:

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

Примітки

1. Rockafellar, 1997.
2. Zălinescu, 2002, с. 75–79.
3. Borwein, Lewis, 2006, с. 76–77.
4. Двоїста пара — це трійка ${\displaystyle \left(X,X^{*},\langle ,\rangle \right)}$, де ${\displaystyle X}$ — векторний простір над полем ${\displaystyle F}$, ${\displaystyle X^{*}}$ — множина всіх лінійних відображень ${\displaystyle \phi \colon X\to F}$, а третій елемент — білінійна форма ${\displaystyle X^{*}\times X\to F\colon (\phi ,x)\mapsto \phi (x)}$.
5. Boţ, Wanka, Grad, 2009.
6. Csetnek, 2010.
7. Zălinescu, 2002, с. 106–113.
8. Borwein, Lewis, 2006.
9. Boyd, Vandenberghe, 2004.

Література

• Осипенко К. Ю. Оптимизация. Ч. 1. Выпуклый анализ (консп. лекций). М.: МГУ. 57 с.
• Осипенко К. Ю. Выпуклый анализ (программа курса и консп. лекций). М.: МГУ. 68 с.
• Петров Н. Н. Выпуклый анализ (консп. лекций). Ижевск: УдмГУ, 2009. 160 с.
• Жадан В. Г. Методы оптимизации. Часть I. Введение в выпуклый анализ и теорию оптимизации: учеб. пос. для студ. вузов по направл. … «Прикладные математика и физика». Москва : МФТИ, 2014. . (Ч. I). 271 с. Выпуск 300 шт.
• Элементы выпуклого и сильно выпуклого анализа: учебное пособие для студентов высших учебных заведений, обучающихся по направлению «Прикладные математика и физика» и смежным направлениям и специальностям / Е. С. Половинкин, М. В. Балашов. — 2-е изд., испр. и доп. — М. : Физматлит, 2007. — 438 с.; 22 см — (Физтеховский учебник).;
• Выпуклый анализ (консп. лекций. Мехмат МГУ, экономич. поток, 2009 г.). М.: МГУ.
• Jonathan Borwein, Adrian Lewis. Convex Analysis and Nonlinear Optimization: Theory and Examples. — 2. — Springer, 2006. — .
• Stephen Boyd, Lieven Vandenberghe. Convex Optimization. — Cambridge University Press, 2004. — .
• R. Tyrrell Rockafellar. Convex Analysis = 1970. — Princeton, NJ : Princeton University Press, 1997. — .
• Radu Ioan Boţ, Gert Wanka, Sorin-Mihai Grad. Duality in Vector Optimization. — Springer, 2009. — .
• Constantin Zălinescu. Convex analysis in general vector spaces. — River Edge, NJ : World Scientific Publishing Co., Inc, 2002. — С. 106–113. — .
• 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. — .
• Jonathan Borwein, Adrian Lewis. Convex Analysis and Nonlinear Optimization: Theory and Examples. — 2. — Springer, 2006. — .
• Hiriart-Urruty J.-B., Lemaréchal C. Fundamentals of convex analysis. — Berlin : Springer-Verlag, 2001. — .
• Ivan Singer. Abstract convex analysis. — New York : John Wiley & Sons, Inc, 1997. — С. xxii+491. — (Canadian Mathematical Society series of monographs and advanced texts) — .
• Stoer J., Witzgall C. Convexity and optimization in finite dimensions. — Berlin : Springer, 1970. — Т. 1. — .
• Kusraev A.G., Kutateladze S.S. Subdifferentials: Theory and Applications. — Dordrecht : Kluwer Academic Publishers, 1995. — .
• Кусраев А. Г., Кутателадзе С. С. Субдифференциалы. Теория и приложения. Ч. 2. — 2-е, перераб. — Новосибирск : Изд-во Ин-та математики, 2003. — ISBN 5–86134–116–8.