Опуклий аналіз — Вікіпедія

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

Опуклі множини[ред. | ред. код]

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

Для будь-кого ${\displaystyle x\in X}$ нерівність ${\displaystyle f^{**}(x)\leqslant f(x)}$ випливає з нерівності Фенхеля. Для власної функції^[en] 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}$ є опуклою множиною.

Двоїста задача[ред. | ред. код]

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

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

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

${\displaystyle 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 = 1970. — 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.

Наука nLab Тематичні сайти Quora Нормативний контроль BNF: 18087923r · Freebase: /m/090dns

п о р Розділи математики огляд[en] переліки тем Галузі Алгебра елементарна лінійна полілінійна абстрактна Теорія груп геометрична комбінаторна обчислювальна Алгоритми Арифметика / Теорія чисел адитивна алгебрична аналітична Геометрія дискретна алгебрична біраціональна диференціальна синтетична скінченна Диференціальні рівняння / Динамічні системи Комбінаторика адитивна алгебрична арифметична геометрична многогранників нумераційна топологічна Математика та мистецтво Математична логіка Математична статистика Математична фізика Обчислення / Аналіз Оптимізація Опуклий аналіз Рекреаційна математика Статистика Теорія графів алгебрична екстремальна спектральна Теорія ігор Теорія інформації Теорія ймовірності Теорія категорій Теорія керування Теорія Лі Теорія множин Теорія порядку Теорія представлень Топологія загальна алгебрична диференціальна Тригонометрія Функціональний аналіз Чисельний аналіз Підрозділи Чиста Прикладна Дискретна Обчислювальна Експериментальна   Категорія   Портал