Выпуклое программирование
Выпуклое программирование — это подобласть математической оптимизации, которая изучает задачу минимизации выпуклых функций на выпуклых множествах. В то время как многие классы задач выпуклого программирования допускают алгоритмы полиномиального времени[1], математическая оптимизация в общем случае NP-трудна[2][3][4].
Выпуклое программирование находит применение в целом ряде дисциплин, таких как автоматические системы управления, оценка и обработка сигналов, коммуникации и сети, схемотехника[5], анализ данных и моделирование, финансы, статистика (оптимальный план эксперимента )[6] и структурная оптимизация[7]. Развитие вычислительной техники и алгоритмов оптимизации сделало выпуклое программирование почти столь же простым как линейное программирование[8].
Определение
Задача выпуклого программирования — это задача оптимизации, в которой целевая функция является выпуклой функцией и область допустимых решений выпукла. Функция [math]\displaystyle{ f }[/math], отображающая некоторое подмножество [math]\displaystyle{ \mathbb{R}^n }[/math] в [math]\displaystyle{ \mathbb{R} \cup \{\pm \infty\} }[/math], является выпуклой, если область определения выпукла и для всех [math]\displaystyle{ \theta \in [0, 1] }[/math], и всех [math]\displaystyle{ x, y }[/math] в их области определения [math]\displaystyle{ f(\theta x + (1 - \theta)y) \leqslant \theta f(x) + (1 - \theta) f(y) }[/math]. Множество выпукло, если для всех его элементов [math]\displaystyle{ x, y }[/math] и любого [math]\displaystyle{ \theta \in [0, 1] }[/math] также и [math]\displaystyle{ \theta x + (1 - \theta) y }[/math] принадлежит множеству.
В частности, задачей выпуклого программирования является задача нахождения некоторого [math]\displaystyle{ \mathbf{x^\ast} \in C }[/math], на котором достигается
- [math]\displaystyle{ \inf \{ f(\mathbf{x}) : \mathbf{x} \in C \} }[/math],
где целевая функция [math]\displaystyle{ f }[/math] выпукла, как и множество допустимых решений [math]\displaystyle{ C }[/math][9][10]. Если такая точка существует, её называют оптимальной точкой. Множество всех оптимальных точек называется оптимальным множеством. Если [math]\displaystyle{ f }[/math] не ограничена на [math]\displaystyle{ C }[/math] или инфимум не достигается, говорят, что оптимизации не ограничена. Если же [math]\displaystyle{ C }[/math] пусто, говорят о недопустимой задаче[11].
Стандартная форма
Говорят, что задача выпуклого программирования представлена в стандартной форме, если она записана как
- Минимизировать [math]\displaystyle{ f(\mathbf{x}) }[/math]
- При условиях
- [math]\displaystyle{ \begin{align}&&g_i(\mathbf{x}) \leqslant 0, \quad i=1, \dots, m \\ &&h_i(\mathbf{x})=0, \quad i=1, \dots, p, \end{align} }[/math]
где [math]\displaystyle{ x \in \mathbb{R}^n }[/math] является переменной оптимизации, функции [math]\displaystyle{ f, g_1, \ldots, g_m }[/math] выпуклы, а функции [math]\displaystyle{ h_1, \ldots, h_p }[/math] аффинны [11].
В этих терминах функция [math]\displaystyle{ f }[/math] является целевой функцией задачи, а функции [math]\displaystyle{ g_i }[/math] и [math]\displaystyle{ h_i }[/math] именуются функциями ограничений. Допустимое множество решений задачи оптимизации — это множество, состоящее из всех точек [math]\displaystyle{ x \in \mathbb{R}^n }[/math], удовлетворяющих условиям [math]\displaystyle{ g_1(x) \leqslant 0, \ldots, g_m(x) \leqslant 0 }[/math] и [math]\displaystyle{ h_1(x)=0, \ldots, h_p(x)=0 }[/math]. Это множество выпукло, поскольку множества подуровня выпуклой функции выпуклы, аффинные множества также выпуклы, а пересечение выпуклых множеств является выпуклым множеством[12].
Многие задачи оптимизации можно привести к этой стандартной форме. Например, задача максимизации вогнутой функции [math]\displaystyle{ f }[/math] может быть переформулирована эквивалентно как задача минимизации выпуклой функции [math]\displaystyle{ -f }[/math], так что о задаче максимизации вогнутой функции на выпуклом множестве часто говорят как о задаче выпуклого программирования
Свойства
Полезные свойства задач выпуклого программирования[13][11]:
- любой локальный минимум является глобальным минимумом;
- оптимальное множество выпукло;
- если целевая функция сильно выпукла, проблема имеет максимум одну оптимальную точку.
Эти результаты используются в теории выпуклой минимизации вместе с геометрическими понятиями из функционального анализа (на гильбертовых пространствах), такими как теорема проектирование Гильберта , теорема об опорной гиперплоскости и лемма Фаркаша.
Примеры
Следующие классы задач являются задачами выпуклого программирования или могут быть сведены к задачам выпуклого программирования путём простых преобразований[11][14]:
- Метод наименьших квадратов
- Линейное программирование
- Выпуклая квадратичная оптимизация с линейными ограничениями
- Квадратичное программирование в квадратичных ограничениях
- Коническая оптимизация
- Геометрическое программирование
- Коническое программирование на конусе второго порядка
- Полуопределённое программирование
- Принцип максимума энтропии с подходящими ограничениями
Метод множителей Лагранжа
Рассмотрим задачу выпуклой минимизации, заданную в стандартной форме с функцией цены [math]\displaystyle{ f(x) }[/math] и ограничениям-неравенствам [math]\displaystyle{ g_i(x)\leqslant 0 }[/math] для [math]\displaystyle{ 1 \leqslant i \leqslant m }[/math]. Тогда область определения [math]\displaystyle{ \mathcal{X} }[/math] равна:
- [math]\displaystyle{ \mathcal{X}=\left\{x\in X \vert g_1(x), \ldots, g_m(x)\leqslant 0\right\}. }[/math]
Функция Лагранжа для задачи
- [math]\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). }[/math]
Для любой точки [math]\displaystyle{ x }[/math] из [math]\displaystyle{ X }[/math], которая минимизирует [math]\displaystyle{ f }[/math] на [math]\displaystyle{ X }[/math], существуют вещественные числа [math]\displaystyle{ \lambda_{0},\lambda_1, \ldots, \lambda_{m}, }[/math], называемые множителями Лагранжа, для которых выполняются одновременно условия:
- [math]\displaystyle{ x }[/math] минимизирует [math]\displaystyle{ L(y,\lambda_{0},\lambda_{1},\ldots ,\lambda_{m}) }[/math] над всеми [math]\displaystyle{ y \in X, }[/math]
- [math]\displaystyle{ \lambda_{0},\lambda_{1},\ldots ,\lambda_{m} \geqslant 0, }[/math] по меньшей мере с одним [math]\displaystyle{ \lambda_{k} \gt 0, }[/math]
- [math]\displaystyle{ \lambda_{1}g_{1}(x)=\cdots=\lambda_{m}g_{m}(x)=0 }[/math] (дополняющая нежёсткость).
Если существует «сильная допустимая точка», то есть точка [math]\displaystyle{ z }[/math], удовлетворяющая
- [math]\displaystyle{ g_{1}(z), \ldots, g_{m}(z)\lt 0, }[/math]
то утверждение выше может быть усилено до требования [math]\displaystyle{ \lambda_{0}=1 }[/math].
И обратно, если некоторое [math]\displaystyle{ x }[/math] из [math]\displaystyle{ X }[/math] удовлетворяет условиям (1)-(3) для скаляров [math]\displaystyle{ \lambda_{0},\ldots,\lambda_{m} }[/math] с [math]\displaystyle{ \lambda_{0}=1 }[/math], то [math]\displaystyle{ x }[/math] определённо минимизирует [math]\displaystyle{ f }[/math] на [math]\displaystyle{ X }[/math].
Алгоритмы
Задачи выпуклого программирования решаются следующими современными методами:[15]
- Методы пучков субградиентов} (Вольф, Лемерикал, Кивель),
- Субградиентные проекционные методы (Поляк),
- Метод внутренней точки[1], использующий самосогласованные барьерные функции[16] и саморегулярные барьерные функции[17].
- Метод секущих плоскостей
- Метод эллипсоидов
- Субградиентные методы
- Субградиенты сноса и метод сноса+штрафа
Субградиентные методы могут быть реализованы просто, потому они широко используются[18][19]. Двойственные субградиентные методы — это субградиентные методы, применённые к двойственной задаче. Метод сноса+штрафа аналогичен двойственному субградиентному методу, но использует среднее по времени от основных переменных.
Расширения
Расширения выпуклого программирования включают оптимизацию двояковыпуклых , псевдовыпуклых и квазивыпуклых функций. Расширения теории выпуклого анализа и итеративные методы для приблизительного решения невыпуклых задач оптимизации встречаются в области обобщённой выпуклости, известной как абстрактный выпуклый анализ.
См. также
- Двойственность
- Условия Каруша — Куна — Таккера
- Оптимизация (математика)
- Метод проксимального градиента
Примечания
- ↑ 1,0 1,1 Nesterov, Nemirovskii, 1994.
- ↑ Murty, Kabadi, 1987, с. 117–129.
- ↑ Sahni, 1974, с. 262—279.
- ↑ Pardalos, Vavasis, 1991, с. 15—22.
- ↑ Boyd, Vandenberghe, 2004, с. 17.
- ↑ Christensen, Klarbring, 2008, с. chpt. 4.
- ↑ Boyd, Vandenberghe, 2004.
- ↑ Boyd, Vandenberghe, 2004, с. 8.
- ↑ Hiriart-Urruty, Lemaréchal, 1996, с. 291.
- ↑ Ben-Tal, Nemirovskiĭ, 2001, с. 335–336.
- ↑ 11,0 11,1 11,2 11,3 Boyd, Vandenberghe, 2004, с. chpt. 4.
- ↑ Boyd, Vandenberghe, 2004, с. chpt. 2.
- ↑ Rockafellar, 1993, с. 183–238.
- ↑ Agrawal, Verschueren, Diamond, Boyd, 2018, с. 42–60.
- ↑ О методах выпуклого программирования см. книги Ирриарта-Уррути и Лемерикала (несколько книг) и книги Рушчиньского, Берцекаса, а также Бойда и Вандерберге (методы внутренней точки).
- ↑ Nesterov, Nemirovskii, 1995.
- ↑ Peng, Roos, Terlaky, 2002, с. 129–171.
- ↑ Bertsekas, 2009.
- ↑ 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
Для улучшения этой статьи желательно: |