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

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 }\}$. Подвійне спряження корисне, коли потрібно показати, що виконується сильна або слабка двоїстість (за допомогою Шаблон:Не перекладено).

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

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

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

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

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

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

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

Загалом, якщо дано Шаблон:Не перекладено відокремлюваних локально опуклих просторів $(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$ — Шаблон:Не перекладено. Нехай тепер $F:X\times Y\to ℝ\cup \{+\mathrm{\infty }\}$ (для іншої двоїстої пари $(Y,Y^{*})$) — Шаблон:Не перекладено, така що $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 — Шаблон:Не перекладено для прямої та двоїстої задач, а 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 г.). Шаблон:М.: МГУ.
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга