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

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

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

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

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

Визначення

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

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

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

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

Стандартна форма

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

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

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

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

Властивості

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

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

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

Приклади

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

Ієрархія задач опуклої оптимізації. (LP: лінійна програма, QP: квадратична програма, програма конусів SOCP другого порядку, SDP: напіввизначена програма, CP: програма конуса.)

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

Множники Лагранжа

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

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

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

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

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

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

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

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

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

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

Алгоритми

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

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

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

Розширення

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

Див. також

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

Список літератури

• 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
• Брайан Борчерс, Огляд програмного забезпечення для опуклої оптимізації