Выпуклое программирование - NiNa.Az

Выпуклое программирование — это подобласть математической оптимизации, которая изучает задачу минимизации выпуклых функций на выпуклых множествах. В то время как многие классы задач выпуклого программирования допускают алгоритмы полиномиального времени, математическая оптимизация в общем случае 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)\leqslant \theta f(x)+(1-\theta )f(y)}$. Множество выпукло, если для всех его элементов ${\displaystyle x,y}$ и любого ${\displaystyle \theta \in [0,1]}$ также и ${\displaystyle \theta x+(1-\theta )y}$ принадлежит множеству.

В частности, задачей выпуклого программирования является задача нахождения некоторого ${\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 f(\mathbf {x} )}$

При условиях

${\displaystyle {\begin{aligned}&&g_{i}(\mathbf {x} )\leqslant 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)\leqslant 0,\ldots ,g_{m}(x)\leqslant 0}$ и ${\displaystyle h_{1}(x)=0,\ldots ,h_{p}(x)=0}$. Это множество выпукло, поскольку множества подуровня выпуклой функции выпуклы, аффинные множества также выпуклы, а пересечение выпуклых множеств является выпуклым множеством.

Многие задачи оптимизации можно привести к этой стандартной форме. Например, задача максимизации вогнутой функции ${\displaystyle f}$ может быть переформулирована эквивалентно как задача минимизации выпуклой функции ${\displaystyle -f}$, так что о задаче максимизации вогнутой функции на выпуклом множестве часто говорят как о задаче выпуклого программирования

Свойства

Полезные свойства задач выпуклого программирования:

• любой локальный минимум является глобальным минимумом;
• оптимальное множество выпукло;
• если целевая функция сильно выпукла, проблема имеет максимум одну оптимальную точку.

Эти результаты используются в теории выпуклой минимизации вместе с геометрическими понятиями из функционального анализа (на гильбертовых пространствах), такими как ^[англ.], теорема об опорной гиперплоскости и лемма Фаркаша.

Примеры

Иерархия задач выпуклого программирования.
(LP: линейное программирование,
QP: квадратичное программирование,
SOCP: коническое программирования на конусе второго порядка,
SDP: полуопределённое программирование,
CP: коническое программирование,
GFP: программирование графических форм.)

Следующие классы задач являются задачами выпуклого программирования или могут быть сведены к задачам выпуклого программирования путём простых преобразований:

• Метод наименьших квадратов
• Линейное программирование
• Выпуклая квадратичная оптимизация с линейными ограничениями
• ^[англ.]
• ^[англ.]
• Геометрическое программирование
• ^[англ.]
• Полуопределённое программирование
• Принцип максимума энтропии с подходящими ограничениями

Метод множителей Лагранжа

Рассмотрим задачу выпуклой минимизации, заданную в стандартной форме с функцией цены ${\displaystyle f(x)}$ и ограничениям-неравенствам ${\displaystyle g_{i}(x)\leqslant 0}$ для ${\displaystyle 1\leqslant i\leqslant m}$. Тогда область определения ${\displaystyle {\mathcal {X}}}$ равна:

${\displaystyle {\mathcal {X}}=\left\{x\in X\vert g_{1}(x),\ldots ,g_{m}(x)\leqslant 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}\geqslant 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, Kabadi, 1987, с. 117–129.
3. Sahni, 1974, с. 262—279.
4. Pardalos, Vavasis, 1991, с. 15—22.
5. Boyd, Vandenberghe, 2004, с. 17.
6. Christensen, Klarbring, 2008, с. chpt. 4.
7. Boyd, Vandenberghe, 2004.
8. Boyd, Vandenberghe, 2004, с. 8.
9. Hiriart-Urruty, Lemaréchal, 1996, с. 291.
10. Ben-Tal, Nemirovskiĭ, 2001, с. 335–336.
11. Boyd, Vandenberghe, 2004, с. chpt. 4.
12. Boyd, Vandenberghe, 2004, с. chpt. 2.
13. Rockafellar, 1993, с. 183–238.
14. Agrawal, Verschueren, Diamond, Boyd, 2018, с. 42–60.
15. О методах выпуклого программирования см. книги Ирриарта-Уррути и Лемерикала (несколько книг) и книги Рушчиньского, Берцекаса, а также Бойда и Вандерберге (методы внутренней точки).
16. Nesterov, Nemirovskii, 1995.
17. Peng, Roos, Terlaky, 2002, с. 129–171.
18. Bertsekas, 2009.
19. Bertsekas, 2015.

Литература

• Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal. Convex analysis and minimization algorithms: Fundamentals. — 1996. — ISBN 9783540568506.
• Aharon Ben-Tal, Arkadiĭ Semenovich Nemirovskiĭ. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. — 2001. — ISBN 9780898714913.
• Katta Murty, Santosh Kabadi. Some NP-complete problems in quadratic and nonlinear programming // Mathematical Programming. — 1987. — Т. 39, вып. 2. — С. 117–129. — doi:10.1007/BF02592948.
• Sahni S. Computationally related problems // SIAM Journal on Computing. — 1974. — Вып. 3.
• Panos M. Pardalos, Stephen A. Vavasis. Quadratic programming with one negative eigenvalue is NP-hard // Journal of Global Optimization. — 1991. — Т. 1, № 1.
• R. Tyrrell Rockafellar. Convex analysis. — Princeton: Princeton University Press, 1970.
• R. Tyrrell Rockafellar. Lagrange multipliers and optimality // SIAM Review. — 1993. — Т. 35, вып. 2. — doi:10.1137/1035044.
• Akshay Agrawal, Robin Verschueren, Steven Diamond, Stephen Boyd. A rewriting system for convex optimization problems // Control and Decision. — 2018. — Т. 5, вып. 1. — doi:10.1080/23307706.2017.1397554.
• Yurii Nesterov, Arkadii Nemirovskii. Interior-Point Polynomial Algorithms in Convex Programming. — Society for Industrial and Applied Mathematics, 1995. — ISBN 978-0898715156.
• Yurii Nesterov, Arkadii Nemirovskii. Interior Point Polynomial Methods in Convex Programming. — SIAM, 1994. — Т. 13. — (Studies in Applied and Numerical Mathematics). — ISBN 978-0-89871-319-0.
• Yurii Nesterov. Introductory Lectures on Convex Optimization. — Boston, Dordrecht, London: Kluwer Academic Publishers, 2004. — Т. 87. — (Applied Optimisation). — ISBN 1-4020-7553-7.
• Jiming Peng, Cornelis Roos, Tamás Terlaky. Self-regular functions and new search directions for linear and semidefinite optimization // Mathematical Programming. — 2002. — Т. 93, вып. 1. — ISSN 0025-5610. — doi:10.1007/s101070200296.
• Dimitri P. Bertsekas, Angelia Nedic, Asuman Ozdaglar. Convex Analysis and Optimization. — Athena Scientific, 2003. — ISBN 978-1-886529-45-8.
• Dimitri P. Bertsekas. Convex Optimization Theory. — Belmont, MA.: Athena Scientific, 2009. — ISBN 978-1-886529-31-1.
• Dimitri P. Bertsekas. Convex Optimization Algorithms. — Belmont, MA.: Athena Scientific, 2015. — ISBN 978-1-886529-28-1.
• Stephen P. Boyd, Lieven Vandenberghe. Convex Optimization. — Cambridge University Press, 2004. — ISBN 978-0-521-83378-3.
• Jonathan M. Borwein, Adrian Lewis. Convex Analysis and Nonlinear Optimization. — Springer, 2000. — (CMS Books in Mathematics). — ISBN 0-387-29570-4.
• Peter W. Christensen, Anders Klarbring. An introduction to structural optimization. — Springer Science & Businees Media, 2008. — Т. 153. — ISBN 9781402086663.
• Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal. Fundamentals of Convex analysis. — Berlin: Springer, 2004. — (Grundlehren text editions). — ISBN 978-3-540-42205-1.
• Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal. Convex analysis and minimization algorithms, Volume I: Fundamentals. — Berlin: Springer-Verlag, 1993. — Т. 305. — С. xviii+417. — ISBN 978-3-540-56850-6.
• Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal. Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods. — Berlin: Springer-Verlag, 1993. — Т. 306. — С. xviii+346. — ISBN 978-3-540-56852-0.
• Krzysztof C. Kiwiel. Methods of Descent for Nondifferentiable Optimization. — New York: Springer-Verlag, 1985. — (Lecture Notes in Mathematics). — ISBN 978-3-540-15642-0.
• Claude Lemaréchal. Lagrangian relaxation // Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. — Berlin: Springer-Verlag, 2001. — Т. 2241. — С. 112–156. — ISBN 978-3-540-42877-0. — doi:10.1007/3-540-45586-8_4.
• Andrzej Ruszczyński. Nonlinear Optimization. — Princeton University Press, 2006.
• Еремин И. И., Астафьев Н. Н. Введение в теорию линейного и выпуклого программирования. - М., Наука, 1976. - 189 c.
• Каменев Г. К. Оптимальные адаптивные методы полиэдральной аппроксимации выпуклых тел. М.: ВЦ РАН, 2007, 230 с. ISBN 5-201-09876-2.
• Каменев Г. К. Численное исследование эффективности методов полиэдральной аппроксимации выпуклых тел. М: Изд. ВЦ РАН, 2010, 118с. ISBN 978-5-91601-043-5.

Ссылки

• Stephen Boyd, Lieven Vandenberghe, Convex optimization (pdf)
• EE364a: Convex Optimization I, EE364b: Convex Optimization II, Страница курса оксфордского университета
• 6.253: Convex Analysis and Optimization, страница курса MIT OCW
• Brian Borchers, An overview of software for convex optimization