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

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

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

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

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

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

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

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

Розглянемо проблему мінімізації опуклої форми, задану в стандартній формі функцією витрат ${\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}$.

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

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

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

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

• Подвійність
• Умови Каруша — Куна — Такера
• Задача оптимізації
• Метод проксимального градієнта

• 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. 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. ISBN 978-3-540-42877-0. MR 1900016. doi:10.1007/3-540-45586-8_4. 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. ISBN 978-3-540-42877-0. MR 1900016. doi:10.1007/3-540-45586-8_4. 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. ISBN 978-3-540-42877-0. MR 1900016. doi:10.1007/3-540-45586-8_4.
• 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
• Брайан Борчерс, Огляд програмного забезпечення для опуклої оптимізації