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

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

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

Визначення

Проблема оптимізації опуклості — це проблема оптимізації, в якій цільова функція є опуклою функцією, а допустимою множиною є опукла множина. Функція ${\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}$. Якщо така точка існує, вона називається оптимальною точкою ; множина всіх оптимальних точок називається оптимальною множиною. Якщо ${\displaystyle f}$ є необмеженою внизу над ${\displaystyle C}$ або мінімум не досягнуто, тоді, як кажуть, проблема оптимізації є необмеженою. Інакше, якщо ${\displaystyle C}$ є порожньою множиною, тоді проблема, як кажуть, невирішувана.

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

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

${\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}}$ є афінними. У цьому позначенні функція ${\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}$. Ця множина є опуклою, оскільки підмножини опуклих функцій опуклі, афінні множини опуклі, а перетин опуклих множин — опуклий.

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

Властивості

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

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

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

Приклади

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

Ієрархія задач опуклої оптимізації. (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}$.

Алгоритми

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

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

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

Розширення

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

Див. також

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

Примітки

1. Nesterov та Nemirovskii, 1994
2. Murty, Katta; Kabadi, Santosh (1987). Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming. 39 (2): 117—129. doi:10.1007/BF02592948.
3. Sahni, S. "Computationally related problems, " in SIAM Journal on Computing, 3, 262—279, 1974.
4. Quadratic programming with one negative eigenvalue is NP-hard, Panos M. Pardalos and Stephen A. Vavasis in Journal of Global Optimization, Volume 1, Number 1, 1991, pg.15-22.
5. Boyd та Vandenberghe, 2004
6. Chritensen/Klarbring, chpt. 4.
7. Schmit, L.A.; Fleury, C. 1980: Structural synthesis by combining approximation concepts and dual methods.
8. Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1996). Convex analysis and minimization algorithms: Fundamentals. с. 291. ISBN .
9. Ben-Tal, Aharon; Nemirovskiĭ, Arkadiĭ Semenovich (2001). Lectures on modern convex optimization: analysis, algorithms, and engineering applications. с. 335—336. ISBN .
10. Rockafellar, R. Tyrrell (1993). Lagrange multipliers and optimality (PDF). SIAM Review. 35 (2): 183—238. CiteSeerX 10.1.1.161.7209. doi:10.1137/1035044.
11. Agrawal, Akshay; Verschueren, Robin; Diamond, Steven; Boyd, Stephen (2018). A rewriting system for convex optimization problems (PDF). Control and Decision. 5 (1): 42—60. arXiv:1709.04494. doi:10.1080/23307706.2017.1397554.
12. Для методів для опуклої мінімізації див. книги від Hiriart-Urruty і Lemaréchal, а також підручники від Ruszczyński і Bertsekas і від Boyd і Vandenberghe (внутрішня точка).
13. Nesterov, Yurii; Arkadii, Nemirovskii (1995). Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics. ISBN .
14. Peng, Jiming; Roos, Cornelis; Terlaky, Tamás (2002). Self-regular functions and new search directions for linear and semidefinite optimization. Mathematical Programming. 93 (1): 129—171. doi:10.1007/s101070200296. ISSN 0025-5610.
15. Bertsekas

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

• Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). Convex Analysis and Optimization. Belmont, MA.: Athena Scientific. ISBN .
• (2009). Convex Optimization Theory. Belmont, MA.: Athena Scientific. ISBN .
• (2015). Convex Optimization Algorithms. Belmont, MA.: Athena Scientific. ISBN .
• Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (PDF). Cambridge University Press. ISBN . Процитовано 15 жовтня 2011.
• Борвейн, Джонатан та Льюїс, Адріан. (2000). Аналіз опуклості та нелінійна оптимізація. Спрингер.
• Christensen, Peter W.; Anders Klarbring (2008). An introduction to structural optimization. Т. 153. Springer Science & Businees Media. ISBN . Christensen, Peter W.; Anders Klarbring (2008). An introduction to structural optimization. Т. 153. Springer Science & Businees Media. ISBN . Christensen, Peter W.; Anders Klarbring (2008). An introduction to structural optimization. Т. 153. Springer Science & Businees Media. ISBN .
• Хіріарт-Урруті, Жан-Батист і Лемарешал, Клод. (2004). Основи опуклого аналізу. Берлін: Спрінгер.
• Hiriart-Urruty, Jean-Baptiste; (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 . MR 1261420. Hiriart-Urruty, Jean-Baptiste; (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 . MR 1261420. Hiriart-Urruty, Jean-Baptiste; (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 . MR 1261420.
• Hiriart-Urruty, Jean-Baptiste; (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 . MR 1295240. Hiriart-Urruty, Jean-Baptiste; (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 . MR 1295240. Hiriart-Urruty, Jean-Baptiste; (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 . MR 1295240.
• Kiwiel, Krzysztof C. (1985). Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Mathematics. New York: Springer-Verlag. ISBN . Kiwiel, Krzysztof C. (1985). Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Mathematics. New York: Springer-Verlag. ISBN . Kiwiel, Krzysztof C. (1985). Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Mathematics. New York: Springer-Verlag. ISBN .
• (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 . MR 1900016. (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 . MR 1900016. (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 . MR 1900016.
• Nesterov, Yurii; Nemirovskii, Arkadii (1994). Interior Point Polynomial Methods in Convex Programming. SIAM.
• Нестеров, Юрій. (2004). Вступні лекції з опуклої оптимізації, наукові видавці Kluwer
• (1970). Convex analysis. Princeton: Princeton University Press.
• (2006). Nonlinear Optimization. Princeton University Press.
• Шміт, Л.А.; Флері, C. 1980: Структурний синтез шляхом поєднання концепцій наближення та подвійних методів. Дж. Амер. Інст. Аеронавт. Астронавт 18, 1252—1260

Посилання

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