Выпуклая оптимизация

Подобласть математической оптимизации

Выпуклая оптимизация — это раздел математической оптимизации , изучающий проблему минимизации выпуклых функций над выпуклыми множествами (или, что то же самое, максимизации вогнутых функций над выпуклыми множествами). Многие классы задач выпуклой оптимизации допускают алгоритмы с полиномиальным временем ^[1] , тогда как математическая оптимизация, как правило, NP-трудна . ^{[2] [3] [4]}

Определение

Абстрактная форма

Задача выпуклой оптимизации определяется двумя ингредиентами: ^{[5] [6]}

• Целевая функция , представляющая собой вещественнозначную выпуклую функцию от n переменных, .; ${\displaystyle f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R} }$
• Допустимое множество , которое является выпуклым подмножеством . ${\displaystyle C\subseteq \mathbb {R} ^{n}}$

Цель задачи – найти некоторое достигающее ${\displaystyle \mathbf {x^{\ast }} \in C}$

${\displaystyle \inf\{f(\mathbf {x} ):\mathbf {x} \in C\}}$.

В целом возможны три варианта существования решения: ^{[7] : гл.4.}

• Если такая точка x * существует, ее называют оптимальной точкой или решением ; совокупность всех оптимальных точек называется оптимальным множеством ; и проблема называется разрешимой .
• Если неограничено снизу по , или нижняя грань не достигается, то задача оптимизации называется неограниченной . ${\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}}}$

где: ^{[7] : глава 4}

• ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$– вектор переменных оптимизации;
• Целевая функция является выпуклой функцией ; ${\displaystyle f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R} }$
• Функции ограничения неравенства , , являются выпуклыми функциями; ${\displaystyle g_{i}:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle i=1,\ldots ,m}$
• Функции ограничения равенства , , являются аффинными преобразованиями , то есть имеют вид: , где – вектор, – скаляр. ${\displaystyle h_{i}:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle i=1,\ldots ,p}$ ${\displaystyle h_{i}(\mathbf {x} )=\mathbf {a_{i}} \cdot \mathbf {x} -b_{i}}$ ${\displaystyle \mathbf {a_{i}} }$ ${\displaystyle b_{i}}$

Допустимое множество задачи оптимизации состоит из всех точек, удовлетворяющих неравенству и ограничениям равенства. Это множество выпукло, потому что оно выпукло, множества подуровней выпуклых функций выпуклы, аффинные множества выпуклы и пересечение выпуклых множеств выпукло. ^{[7] : глава 2} ${\displaystyle C}$ ${\displaystyle \mathbf {x} \in {\mathcal {D}}}$ ${\displaystyle {\mathcal {D}}}$

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

Форма эпиграфа (стандартная форма с линейной целью)

В стандартной форме можно без ограничения общности считать, что целевая функция f является линейной функцией . Это связано с тем, что любую программу с общей целью можно преобразовать в программу с линейной целью, добавив одну переменную t и одно ограничение следующим образом: ^{[9] : 1.4}

${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} ,t}{\operatorname {minimize} }}&&t\\&\operatorname {subject\ to} &&f(\mathbf {x} )-t\leq 0\\&&&g_{i}(\mathbf {x} )\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}}$

Коническая форма

Любую выпуклую программу можно представить в конической форме , что означает минимизацию линейной цели над пересечением аффинной плоскости и выпуклого конуса: ^{[9] : 5.1}

${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&c^{T}x\\&\operatorname {subject\ to} &&x\in (b+L)\cap K\end{aligned}}}$

где K — замкнутый заостренный выпуклый конус , L — линейное подпространство в Rn ^, а b — вектор в ^Rn . Линейная программа в стандартной форме в частном случае, когда K является неотрицательным ортантом R ⁿ .

Устранение ограничений линейного равенства

Можно преобразовать выпуклую программу в стандартной форме в выпуклую программу без ограничений равенства. ^{[7] : 132} Обозначим ограничения равенства h _i ( x )=0 как Ax = b , где A имеет n столбцов. Если Ax = b неразрешима, то, конечно, исходная задача неразрешима. В противном случае оно имеет некоторое решение x ₀ , и множество всех решений можно представить в виде: Fz + x 0 _, где z находится в R ^k , k = n -rank( A ), а F - n -k матрица. Подстановка x = Fz + x ₀ в исходную задачу дает:

${\displaystyle {\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&f(\mathbf {F\mathbf {z} +\mathbf {x} _{0}} )\\&\operatorname {subject\ to} &&g_{i}(\mathbf {F\mathbf {z} +\mathbf {x} _{0}} )\leq 0,\quad i=1,\dots ,m\\\end{aligned}}}$

где переменные — z . Обратите внимание, что переменных ранга ( A ) меньше. Это означает, что в принципе можно ограничить внимание задачами выпуклой оптимизации без ограничений равенства. Однако на практике часто предпочитают сохранять ограничения равенства, поскольку они могут сделать некоторые алгоритмы более эффективными, а также облегчить понимание и анализ проблемы.

Особые случаи

Следующие классы задач являются задачами выпуклой оптимизации или могут быть сведены к задачам выпуклой оптимизации посредством простых преобразований: ^{[7] : глава 4  [10]}

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

• Задачи линейного программирования — это простейшие выпуклые программы. В LP все целевые и ограничивающие функции линейны.
• Квадратичное программирование является следующим по простоте. В QP все ограничения линейны, но целью может быть выпуклая квадратичная функция.
• Программирование конусов второго порядка является более общим.
• Полуопределенное программирование носит более общий характер.
• Коническая оптимизация имеет еще более общий характер — см. рисунок справа,

Другие особые случаи включают в себя;

• Наименьших квадратов
• Квадратичная минимизация с выпуклыми квадратичными ограничениями
• Геометрическое программирование
• Максимизация энтропии с соответствующими ограничениями.

Характеристики

Ниже приведены полезные свойства задач выпуклой оптимизации: ^{[11] [7] : глава 4.}

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

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

Алгоритмы

Неограниченные и ограниченные равенством задачи

Выпуклые программы, которые легче всего решить, — это задачи без ограничений или задачи только с ограничениями-равенствами. Поскольку все ограничения равенства являются линейными, их можно устранить с помощью линейной алгебры и интегрировать в цель, превращая таким образом проблему с ограничениями равенства в задачу без ограничений.

В классе задач без ограничений (или задач с ограничениями равенства) самыми простыми являются те, в которых цель является квадратичной . Для этих задач все условия ККТ (которые необходимы для оптимальности) линейны, поэтому их можно решать аналитически. ^{[7] : глава 11}

Для задач без ограничений (или с ограничениями равенства) с общей выпуклой целью, которая дважды дифференцируема, можно использовать метод Ньютона . Ее можно рассматривать как сведение общей выпуклой задачи без ограничений к последовательности квадратичных задач. ^{[7] : глава 11.} Метод Ньютона можно комбинировать с поиском линии для соответствующего размера шага, и можно математически доказать, что он быстро сходится.

Другими эффективными алгоритмами неограниченной минимизации являются градиентный спуск (частный случай наискорейшего спуска ).

Общие проблемы

Более сложные проблемы связаны с ограничениями неравенства. Распространенный способ их решения — свести их к задачам без ограничений, добавив к целевой функции барьерную функцию , обеспечивающую ограничения неравенства. Такие методы называются методами внутренней точки . ^{[7] : глава 11} Их необходимо инициализировать путем нахождения допустимой внутренней точки с использованием так называемых методов фазы I , которые либо находят допустимую точку, либо показывают, что таковая не существует. Методы фазы I обычно заключаются в сведении рассматриваемого поиска к более простой задаче выпуклой оптимизации. ^{[7] : глава 11}

Задачи выпуклой оптимизации также можно решить следующими современными методами: ^[12]

• Пакетные методы (Вульфа, Лемарешаля, Кивила) и
• Методы субградиентного проектирования (Поляк),
• Методы внутренних точек ^[1] , в которых используются самосогласованные барьерные функции ^[13] и саморегулярные барьерные функции. ^[14]
• Методы секущей плоскости
• Эллипсоидный метод
• Субградиентный метод
• Двойные субградиенты и метод «дрейф плюс штраф».

Субградиентные методы легко реализуются и поэтому широко используются. ^[15] Двойные субградиентные методы — это субградиентные методы, применяемые к двойственной задаче . Метод дрейфа плюс штрафа аналогичен методу двойного субградиента, но он требует усреднения по времени основных переменных. ^{[ нужна цитата ]}

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

Рассмотрим задачу выпуклой минимизации, заданную в стандартной форме функцией стоимости и ограничениями-неравенствами для . Тогда домен : ${\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}$

И наоборот, если некоторый in удовлетворяет (1)–(3) для скаляров с , то обязательно минимизируется по . ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle \lambda _{0},\ldots ,\lambda _{m}}$ ${\displaystyle \lambda _{0}=1}$ ${\displaystyle x}$ ${\displaystyle f}$ ${\displaystyle X}$

Программное обеспечение

Существует большая программная экосистема для выпуклой оптимизации. В этой экосистеме есть две основные категории: решатели с одной стороны и инструменты моделирования (или интерфейсы ) с другой.

Решатели сами реализуют алгоритмы и обычно пишутся на C. Они требуют от пользователей задавать задачи оптимизации в очень специфических форматах, которые могут быть неестественными с точки зрения моделирования. Инструменты моделирования — это отдельные части программного обеспечения, которые позволяют пользователю задавать оптимизацию в синтаксисе более высокого уровня. Они управляют всеми преобразованиями в и из пользовательской модели высокого уровня и формата ввода/вывода решателя.

В таблице ниже показано сочетание инструментов моделирования (таких как CVXPY и Convex.jl) и решателей (таких как CVXOPT и MOSEK). Эта таблица ни в коем случае не является исчерпывающей.

Приложения

Выпуклая оптимизация может использоваться для моделирования задач в широком спектре дисциплин, таких как системы автоматического управления , оценка и обработка сигналов , связь и сети, проектирование электронных схем , ^{[7] : 17} анализ данных и моделирование, финансы , статистика ( оптимальные экспериментальные design ), ^[20] и структурная оптимизация , где концепция аппроксимации доказала свою эффективность. ^{[7] [21]} Выпуклая оптимизация может использоваться для моделирования проблем в следующих областях:

• Оптимизация портфеля . ^[22]
• Анализ рисков наихудшего случая. ^[22]
• Оптимальная реклама. ^[22]
• Варианты статистической регрессии (включая регуляризацию и квантильную регрессию ). ^[22]
• Подбор модели ^[22] (в частности, многоклассовая классификация ^[23] ).
• Оптимизация производства электроэнергии . ^[23]
• Комбинаторная оптимизация . ^[23]
• Невероятностное моделирование неопределенности . ^[24]
• Локализация с помощью беспроводных сигналов ^[25]

Расширения

Расширения выпуклой оптимизации включают оптимизацию двояковыпуклых , псевдовыпуклых и квазивыпуклых функций. Расширения теории выпуклого анализа и итерационные методы приближенного решения невыпуклых задач минимизации происходят в области обобщенной выпуклости , также известной как абстрактный выпуклый анализ. ^{[ нужна цитата ]}

Смотрите также

• Двойственность
• Условия Каруша – Куна – Такера
• Проблема оптимизации
• Метод проксимального градиента
• Алгоритмические задачи на выпуклых множествах

Примечания

1. Нестеров и Немировский 1994.
2. Мурти, Катта; Кабади, Сантош (1987). «Некоторые NP-полные задачи квадратичного и нелинейного программирования». Математическое программирование . 39 (2): 117–129. дои : 10.1007/BF02592948. hdl : 2027.42/6740 . S2CID  30500771.
3. Сахни, С. «Проблемы, связанные с вычислениями», в SIAM Journal on Computing, 3, 262–279, 1974.
4. Квадратичное программирование с одним отрицательным собственным значением является NP-сложным, Панос М. Пардалос и Стивен А. Вавасис в Журнале глобальной оптимизации , том 1, номер 1, 1991, стр. 15-22.
5. Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1996). Алгоритмы выпуклого анализа и минимизации: основы. п. 291. ИСБН 9783540568506.
6. Бен-Тал, Аарон; Немировский, Аркадий Семенович (2001). Лекции по современной выпуклой оптимизации: анализ, алгоритмы и инженерные приложения. стр. 335–336. ISBN 9780898714913.
7. Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация (PDF) . Издательство Кембриджского университета . ISBN 978-0-521-83378-3. Проверено 12 апреля 2021 г.
8. «Типы задач оптимизации - Выпуклая оптимизация» . 9 января 2011 г.
9. Аркадий Немировский (2004). Полиномиальные методы внутренней точки в выпуклом программировании.
10. Агравал, Акшай; Вершуерен, Робин; Даймонд, Стивен; Бойд, Стивен (2018). «Система перезаписи для задач выпуклой оптимизации» (PDF) . Контроль и решение . 5 (1): 42–60. arXiv : 1709.04494 . дои : 10.1080/23307706.2017.1397554. S2CID  67856259.
11. Рокафеллар, Р. Тиррелл (1993). «Множители Лагранжа и оптимальность» (PDF) . Обзор СИАМ . 35 (2): 183–238. CiteSeerX 10.1.1.161.7209 . дои : 10.1137/1035044. 
12. О методах выпуклой минимизации см. тома Хириарта-Уррути и Лемарешаля (связка) и учебники Рущинского , Берцекаса , Бойда и Ванденберге (внутренняя точка).
13. Нестеров, Юрий; Аркадий, Немировский (1995). Полиномиальные алгоритмы внутренней точки в выпуклом программировании . Общество промышленной и прикладной математики. ISBN 978-0898715156.
14. Пэн, Цзимин; Роос, Корнелис; Терлаки, Тамаш (2002). «Саморегулярные функции и новые направления поиска линейной и полуопределенной оптимизации». Математическое программирование . 93 (1): 129–171. дои : 10.1007/s101070200296. ISSN  0025-5610. S2CID  28882966.
15. «Численная оптимизация». Серия Springer по исследованию операций и финансовой инженерии . 2006. doi : 10.1007/978-0-387-40065-5.
16. Борчерс, Брайан. «Обзор программного обеспечения для выпуклой оптимизации» (PDF) . Архивировано из оригинала (PDF) 18 сентября 2017 г. Проверено 12 апреля 2021 г.
17. «Добро пожаловать в документацию CVXPY 1.1 — CVXPY 1.1.11» . www.cvxpy.org . Проверено 12 апреля 2021 г.
18. Уделл, Мадлен; Мохан, Каранвир; Цзэн, Дэвид; Хонг, Дженни; Даймонд, Стивен; Бойд, Стивен (17 октября 2014 г.). «Выпуклая оптимизация в Джулии». arXiv : 1410,4821 [math.OC].
19. «Дисциплинированная выпуклая оптимизация - CVXR» . www.cvxgrp.org . Проверено 17 июня 2021 г.
20. Критенсен/Кларбринг, гл. 4.
21. Шмит, Луизиана; Флери, К. 1980: Структурный синтез путем объединения концепций аппроксимации и двойственных методов . Дж. Амер. Инст. Аэронавт. Астронавт 18 лет, 1252–1260 гг.
22. Бойд, Стивен; Даймонд, Стивен; Чжан, Цзюньцзы; Агравал, Акшай. «Приложения выпуклой оптимизации» (PDF) . Архивировано (PDF) из оригинала 1 октября 2015 г. Проверено 12 апреля 2021 г.
23. Малик, Жером (28 сентября 2011 г.). «Выпуклая оптимизация: приложения, формулировки, расслабления» (PDF) . Архивировано (PDF) из оригинала 12 апреля 2021 г. Проверено 12 апреля 2021 г.
24. Бен Хаим Ю. и Элишакофф И., Выпуклые модели неопределенности в прикладной механике, Elsevier Science Publishers, Амстердам, 1990.
25. Ахмад Баззи, Дирк Т.М. Слок и Лиза Мейлхак. «Онлайн-оценка угла прихода при наличии взаимной связи». Семинар IEEE по статистической обработке сигналов (SSP), 2016 г. ИИЭР, 2016.

Рекомендации

• Берцекас, Дмитрий П.; Недич, Ангелия; Оздаглар, Асуман (2003). Выпуклый анализ и оптимизация . Бельмонт, Массачусетс: Athena Scientific. ISBN 978-1-886529-45-8.
• Берцекас, Дмитрий П. (2009). Теория выпуклой оптимизации . Бельмонт, Массачусетс: Athena Scientific. ISBN 978-1-886529-31-1.
• Берцекас, Дмитрий П. (2015). Алгоритмы выпуклой оптимизации . Бельмонт, Массачусетс: Athena Scientific. ISBN 978-1-886529-28-1.
• Борвейн, Джонатан; Льюис, Адриан (2000). Выпуклый анализ и нелинейная оптимизация: теория и примеры, второе издание (PDF) . Спрингер . Проверено 12 апреля 2021 г.
• Кристенсен, Питер В.; Андерс Кларбринг (2008). Введение в структурную оптимизацию. Том. 153. Springer Science & Business Media. ISBN 9781402086663.

• Хириар-Уррути, Жан-Батист, и Лемарешаль, Клод . (2004). Основы выпуклого анализа . Берлин: Шпрингер.
• Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). Алгоритмы выпуклого анализа и минимизации, Том I: Основы . Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. Том. 305. Берлин: Springer-Verlag. стр. xviii+417. ISBN 978-3-540-56850-6. МР  1261420.
• Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). Алгоритмы выпуклого анализа и минимизации, Том II: Расширенная теория и методы расслоения . Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. Том. 306. Берлин: Springer-Verlag. стр. xviii+346. ISBN 978-3-540-56852-0. МР  1295240.
• Кивиэль, Кшиштоф К. (1985). Методы спуска для недифференцируемой оптимизации . Конспект лекций по математике. Нью-Йорк: Springer-Verlag. ISBN 978-3-540-15642-0.
• Лемарешаль, Клод (2001). «Лагранжева релаксация». В Михаэле Юнгере и Денисе Наддефе (ред.). Вычислительная комбинаторная оптимизация: доклады весенней школы, проходившей в замке Дагштуль, 15–19 мая 2000 г. Конспекты лекций по информатике. Том. 2241. Берлин: Springer-Verlag. стр. 112–156. дои : 10.1007/3-540-45586-8_4. ISBN 978-3-540-42877-0. MR  1900016. S2CID  9048698.
• Нестеров Юрий; Немировский, Аркадий (1994). Полиномиальные методы внутренних точек в выпуклом программировании . СИАМ.
• Нестеров Юрий. (2004). Вводные лекции по выпуклой оптимизации , Kluwer Academic Publishers
• Рокафеллар, RT (1970). Выпуклый анализ . Принстон: Издательство Принстонского университета.

• Рущинский, Анджей (2006). Нелинейная оптимизация . Издательство Принстонского университета.
• Шмит, Луизиана; Флери, К. 1980: Структурный синтез путем объединения концепций аппроксимации и двойственных методов . Дж. Амер. Инст. Аэронавт. Астронавт 18 лет, 1252–1260 гг.

Внешние ссылки

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