Выпуклое программирование

Выпуклое программирование — это подобласть математической оптимизации, которая изучает задачу минимизации выпуклых функций на выпуклых множествах. В то время как многие классы задач выпуклого программирования допускают алгоритмы полиномиального времени, математическая оптимизация в общем случае 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. — .
• Aharon Ben-Tal, Arkadiĭ Semenovich Nemirovskiĭ. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. — 2001. — .
• 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. — .
• Yurii Nesterov, Arkadii Nemirovskii. Interior Point Polynomial Methods in Convex Programming. — SIAM, 1994. — Т. 13. — (Studies in Applied and Numerical Mathematics). — .
• Yurii Nesterov. Introductory Lectures on Convex Optimization. — Boston, Dordrecht, London: Kluwer Academic Publishers, 2004. — Т. 87. — (Applied Optimisation). — .
• 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. — .
• Dimitri P. Bertsekas. Convex Optimization Theory. — Belmont, MA.: Athena Scientific, 2009. — .
• Dimitri P. Bertsekas. Convex Optimization Algorithms. — Belmont, MA.: Athena Scientific, 2015. — .
• Stephen P. Boyd, Lieven Vandenberghe. Convex Optimization. — Cambridge University Press, 2004. — .
• Jonathan M. Borwein, Adrian Lewis. Convex Analysis and Nonlinear Optimization. — Springer, 2000. — (CMS Books in Mathematics). — .
• Peter W. Christensen, Anders Klarbring. An introduction to structural optimization. — Springer Science & Businees Media, 2008. — Т. 153. — .
• Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal. Fundamentals of Convex analysis. — Berlin: Springer, 2004. — (Grundlehren text editions). — .
• Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal. Convex analysis and minimization algorithms, Volume I: Fundamentals. — Berlin: Springer-Verlag, 1993. — Т. 305. — С. xviii+417. — .
• 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. — .
• Krzysztof C. Kiwiel. Methods of Descent for Nondifferentiable Optimization. — New York: Springer-Verlag, 1985. — (Lecture Notes in Mathematics). — .
• 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. — . — doi:10.1007/3-540-45586-8_4.
• Andrzej Ruszczyński. Nonlinear Optimization. — Princeton University Press, 2006.
• (Еремин И. И.), Астафьев Н. Н. Введение в теорию линейного и выпуклого программирования. - М., Наука, 1976. - 189 c.
• (Каменев Г. К.) Оптимальные адаптивные методы полиэдральной аппроксимации выпуклых тел. М.: ВЦ РАН, 2007, 230 с. .
• Каменев Г. К. Численное исследование эффективности методов полиэдральной аппроксимации выпуклых тел. М: Изд. ВЦ РАН, 2010, 118с. .

Ссылки

• 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,