Опукла оптимізація

Опукла оптимізація

Опукла оптимізація у Вікісховищі

Опукла оптимізація — це підрозділ математичної оптимізації, котрий вивчає проблему мінімізації опуклих функцій над опуклими множинами. Багато класів задач з опуклою оптимізацією допускають поліноміальні алгоритми^[1] тоді як математична оптимізація в цілому NP-важка^[2][3][4].

Опукла оптимізація має застосування в широкому спектрі дисциплін, таких як автоматичні системи управління, оцінка та обробка сигналів, комунікації та мережі, проєктування електронних схем^[5], аналіз та моделювання даних, фінанси, статистика (оптимальний експериментальний дизайн),^[6] та структурна оптимізація, де концепція наближення виявилась ефективною.^[5][7] З недавніми досягненнями в галузі обчислювальних та оптимізаційних алгоритмів, опукле програмування майже настільки ж просте, як і лінійне програмування^[5].

Проблема оптимізації опуклості — це проблема оптимізації, в якій цільова функція є опуклою функцією, а допустимою множиною є опукла множина. Функція ${\displaystyle f}$ відображення деякої підмножини ${\displaystyle \mathbb {R} ^{n}}$ в ${\displaystyle \mathbb {R} \cup \{\pm \infty \}}$ опукла, якщо її домен опуклий і для всіх ${\displaystyle \theta \in [0,1]}$ і також для всіх ${\displaystyle x,y}$ у своєму домені виконується така умова: ${\displaystyle f(\theta x+(1-\theta )y)\leq \theta f(x)+(1-\theta )f(y)}$. Множина S опукла, якщо для всіх членів ${\displaystyle x,y\in S}$ і для всіх ${\displaystyle \theta \in [0,1]}$, у нас є, що ${\displaystyle \theta x+(1-\theta )y\in S}$.

Конкретно, проблема опуклої оптимізації — це проблема пошуку ${\displaystyle \mathbf {x^{\ast }} \in C}$ маючи

${\displaystyle \inf\{f(\mathbf {x} ):\mathbf {x} \in C\}}$,

де об'єктивна функція ${\displaystyle f}$ є опуклою, як і допустима множина ${\displaystyle C}$^[8][9]. Якщо така точка існує, вона називається оптимальною точкою ; множина всіх оптимальних точок називається оптимальною множиною. Якщо ${\displaystyle f}$ є необмеженою внизу над ${\displaystyle C}$ або мінімум не досягнуто, тоді, як кажуть, проблема оптимізації є необмеженою. Інакше, якщо ${\displaystyle C}$ є порожньою множиною, тоді проблема, як кажуть, невирішувана^[5].

Кажуть, що проблема опуклої оптимізації є в стандартній формі, якщо вона записана як

${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&f(\mathbf {x} )\\&\operatorname {subject\ to} &&g_{i}(\mathbf {x} )\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}}$

де ${\displaystyle x\in \mathbb {R} ^{n}}$ — змінна оптимізації, функції ${\displaystyle f,g_{1},\ldots ,g_{m}}$ є опуклими, і функції ${\displaystyle h_{1},\ldots ,h_{p}}$ є афінними^[5]. У цьому позначенні функція ${\displaystyle f}$ — це цільова функція задачі, і функції ${\displaystyle g_{i}}$ і ${\displaystyle h_{i}}$ називаються функціями обмеження. Можливим набором задачі оптимізації є множина, що складається з усіх точок ${\displaystyle x\in \mathbb {R} ^{n}}$ задовольняючи ${\displaystyle g_{1}(x)\leq 0,\ldots ,g_{m}(x)\leq 0}$ і ${\displaystyle h_{1}(x)=0,\ldots ,h_{p}(x)=0}$. Ця множина є опуклою, оскільки підмножини опуклих функцій опуклі, афінні множини опуклі, а перетин опуклих множин — опуклий^[5].

Багато проблем оптимізації можуть бути сформульовані в цій стандартній формі. Наприклад, проблема максимізації увігнутої функції ${\displaystyle f}$ може бути переформульовано як проблема мінімізації опуклої функції ${\displaystyle -f}$ ; така проблема максимізації увігнутої функції над опуклою множиною часто називається проблемою оптимізації опуклої форми.

Наступні корисні властивості задач опуклої оптимізації:^[5][10]

• кожен локальний мінімум — це глобальний мінімум;
• оптимальна множина опукла;
• якщо цільова функція строго опукла, то задача має щонайменше одну оптимальну точку.

Ці результати використовуються теорією опуклої мінімізації разом з геометричними поняттями функціонального аналізу (в просторах Гільберта), такими як теорема проєкції Гільберта, теорема розділення гіперплан та лема Фаркаса.

Перелічені класи задач — це все задачі опуклої оптимізації, або їх можна звести до задачі опуклої оптимізації за допомогою простих перетворень:^[5][11]

• Найменші квадрати
• Лінійне програмування
• Опукла квадратична мінімізація з лінійними обмеженнями
• Квадратна мінімізація з опуклими квадратичними обмеженнями
• Конічна оптимізація
• Геометричне програмування
• Програмування конуса другого порядку
• Напівскінченне програмування
• Максимізація ентропії з відповідними обмеженнями

Розглянемо проблему мінімізації опуклої форми, задану в стандартній формі функцією витрат ${\displaystyle f(x)}$ та обмеженням нерівності ${\displaystyle g_{i}(x)\leq 0}$ для ${\displaystyle 1\leq i\leq m}$. Домен ${\displaystyle {\mathcal {X}}}$ є:

${\displaystyle {\mathcal {X}}=\left\{x\in X\vert g_{1}(x),\ldots ,g_{m}(x)\leq 0\right\}.}$

Функцією Лагранжа для задачі є

${\displaystyle L(x,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})=\lambda _{0}f(x)+\lambda _{1}g_{1}(x)+\cdots +\lambda _{m}g_{m}(x).}$

Для кожної точки ${\displaystyle x}$ в ${\displaystyle X}$ що мінімізує ${\displaystyle f}$ над ${\displaystyle X}$, існують реальні числа ${\displaystyle \lambda _{0},\lambda _{1},\ldots ,\lambda _{m},}$ котрі називаються множниками Лагранжа, які одночасно задовольняють ці умови:

1. ${\displaystyle x}$ мінімізує ${\displaystyle L(y,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})}$ над усім ${\displaystyle y\in X,}$
2. ${\displaystyle \lambda _{0},\lambda _{1},\ldots ,\lambda _{m}\geq 0,}$ принаймні з одним ${\displaystyle \lambda _{k}>0,}$
3. ${\displaystyle \lambda _{1}g_{1}(x)=\cdots =\lambda _{m}g_{m}(x)=0}$ (додаткова млявість).

Якщо існує «строго допустима точка», тобто точка ${\displaystyle z}$, котра задовольняє

${\displaystyle g_{1}(z),\ldots ,g_{m}(z)<0,}$

тоді твердження вище може вимагати ${\displaystyle \lambda _{0}=1}$.

І навпаки, якщо якісь ${\displaystyle x}$ в ${\displaystyle X}$ задовольняють (1) — (3) для скалярів ${\displaystyle \lambda _{0},\ldots ,\lambda _{m}}$ з ${\displaystyle \lambda _{0}=1}$, то ${\displaystyle x}$ мінімізує ${\displaystyle f}$ над ${\displaystyle X}$.

Задачі опуклої оптимізації можуть бути розв'язані такими сучасними методами:^[12]

• Методи розшарування (Вулф, Лемарель, Ківіль) та
• Методи субградієнтної проєкції (Поляк),
• Методи внутрішніх точок^[1], в яких використовуються самокорегуючі бар'єрні функції^[13] та саморегулярні бар'єрні функції.^[14]
• Ріжучі площинні методи
• Еліпсоїдний метод
• Субградієнтний метод
• Подвійні субградієнти та метод дрейфу плюс-штраф

Субградієнтні методи можуть бути реалізовані просто і тому широко застосовуються.^[15] Подвійні субградієнтні методи — це субградієнтні методи, застосовані до подвійної задачі. Метод дрейфування плюс-штрафу схожий з методом подвійного субградієнта.

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

• Двоїстість (оптимізація)
• Умови Каруша — Куна — Такера
• Задача оптимізації
• Метод проксимального градієнта
• Алгоритм Франк — Вульфа

• Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). Convex Analysis and Optimization. Belmont, MA.: Athena Scientific. ISBN 978-1-886529-45-8.
• Bertsekas, Dimitri P. (2009). Convex Optimization Theory. Belmont, MA.: Athena Scientific. ISBN 978-1-886529-31-1.
• Bertsekas, Dimitri P. (2015). Convex Optimization Algorithms. Belmont, MA.: Athena Scientific. ISBN 978-1-886529-28-1.
• Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (PDF). Cambridge University Press. ISBN 978-0-521-83378-3. Процитовано 15 жовтня 2011.
• Борвейн, Джонатан та Льюїс, Адріан. (2000). Аналіз опуклості та нелінійна оптимізація. Спрингер.
• Christensen, Peter W.; Anders Klarbring (2008). An introduction to structural optimization. Т. 153. Springer Science & Businees Media. ISBN 9781402086663. Christensen, Peter W.; Anders Klarbring (2008). An introduction to structural optimization. Т. 153. Springer Science & Businees Media. ISBN 9781402086663. Christensen, Peter W.; Anders Klarbring (2008). An introduction to structural optimization. Т. 153. Springer Science & Businees Media. ISBN 9781402086663.
• Хіріарт-Урруті, Жан-Батист і Лемарешал, Клод. (2004). Основи опуклого аналізу. Берлін: Спрінгер.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Convex analysis and minimization algorithms, Volume I: Fundamentals. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Т. 305. Berlin: Springer-Verlag. с. xviii+417. ISBN 978-3-540-56850-6. MR 1261420. Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Convex analysis and minimization algorithms, Volume I: Fundamentals. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Т. 305. Berlin: Springer-Verlag. с. xviii+417. ISBN 978-3-540-56850-6. MR 1261420. Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Convex analysis and minimization algorithms, Volume I: Fundamentals. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Т. 305. Berlin: Springer-Verlag. с. xviii+417. ISBN 978-3-540-56850-6. MR 1261420.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Т. 306. Berlin: Springer-Verlag. с. xviii+346. ISBN 978-3-540-56852-0. MR 1295240. Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Т. 306. Berlin: Springer-Verlag. с. xviii+346. ISBN 978-3-540-56852-0. MR 1295240. Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Т. 306. Berlin: Springer-Verlag. с. xviii+346. ISBN 978-3-540-56852-0. MR 1295240.
• Kiwiel, Krzysztof C. (1985). Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Mathematics. New York: Springer-Verlag. ISBN 978-3-540-15642-0. Kiwiel, Krzysztof C. (1985). Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Mathematics. New York: Springer-Verlag. ISBN 978-3-540-15642-0. Kiwiel, Krzysztof C. (1985). Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Mathematics. New York: Springer-Verlag. ISBN 978-3-540-15642-0.
• Lemaréchal, Claude (2001). Lagrangian relaxation. У Michael Jünger and Denis Naddef (ред.). Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. Lecture Notes in Computer Science. Т. 2241. Berlin: Springer-Verlag. с. 112—156. doi:10.1007/3-540-45586-8_4. ISBN 978-3-540-42877-0. MR 1900016. Lemaréchal, Claude (2001). Lagrangian relaxation. У Michael Jünger and Denis Naddef (ред.). Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. Lecture Notes in Computer Science. Т. 2241. Berlin: Springer-Verlag. с. 112—156. doi:10.1007/3-540-45586-8_4. ISBN 978-3-540-42877-0. MR 1900016. Lemaréchal, Claude (2001). Lagrangian relaxation. У Michael Jünger and Denis Naddef (ред.). Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. Lecture Notes in Computer Science. Т. 2241. Berlin: Springer-Verlag. с. 112—156. doi:10.1007/3-540-45586-8_4. ISBN 978-3-540-42877-0. MR 1900016.
• Nesterov, Yurii; Nemirovskii, Arkadii (1994). Interior Point Polynomial Methods in Convex Programming. SIAM.
• Нестеров, Юрій. (2004). Вступні лекції з опуклої оптимізації, наукові видавці Kluwer
• Rockafellar, R. T. (1970). Convex analysis. Princeton: Princeton University Press.
• Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton University Press.
• Шміт, Л.А.; Флері, C. 1980: Структурний синтез шляхом поєднання концепцій наближення та подвійних методів. Дж. Амер. Інст. Аеронавт. Астронавт 18, 1252—1260

• Стівен Бойд та Лівен Ванденберге, опукла оптимізація (книга в pdf)
• EE364a: Опукла оптимізація I та EE364b: Опукла оптимізація II, домашні сторінки курсу «Стенфорд»
• 6.253: Опуклий аналіз та оптимізація, домашня сторінка курсу MIT OCW
• Брайан Борчерс, Огляд програмного забезпечення для опуклої оптимізації