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

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