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

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

Выпуклая оптимизация — это подраздел математической оптимизации , изучающий проблему минимизации выпуклых функций на выпуклых множествах (или, что эквивалентно, максимизации вогнутых функций на выпуклых множествах). Многие классы задач выпуклой оптимизации допускают алгоритмы полиномиального времени, ^[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] : chpt.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 — линейное подпространство R ⁿ , а b — вектор в R ⁿ . Линейная программа в стандартной форме в частном случае, когда K — неотрицательный ортант R ⁿ .

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

Можно преобразовать выпуклую программу в стандартной форме в выпуклую программу без ограничений равенства. ^{[7] : 132} Обозначим ограничения равенства h _i ( x )=0 как Ax = b , где A имеет n столбцов. Если Ax = b недопустимо, то, конечно, исходная задача недопустима. В противном случае она имеет некоторое решение x ₀ , и множество всех решений можно представить как: Fz + x ₀ , где 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 . Обратите внимание, что переменных на rank( A ) меньше. Это означает, что в принципе можно ограничить внимание задачами выпуклой оптимизации без ограничений равенства. На практике, однако, часто предпочитают сохранять ограничения равенства, поскольку они могут сделать некоторые алгоритмы более эффективными, а также облегчить понимание и анализ проблемы.

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

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

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

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

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

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

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

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

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

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

Алгоритмы

Задачи без ограничений и с ограничениями по равенству

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

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

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

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

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

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

Наоборот, если некоторый в удовлетворяет (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} анализ данных и моделирование, финансы , статистика ( оптимальное экспериментальное проектирование ), ^[20] и структурная оптимизация , где концепция аппроксимации доказала свою эффективность. ^{[7] [21]} Выпуклая оптимизация может использоваться для моделирования проблем в следующих областях:

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

Расширения

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

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

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

Примечания

1. Нестеров и Немировский 1994.
2. Мурти, Катта; Кабади, Сантош (1987). «Некоторые NP-полные задачи квадратичного и нелинейного программирования». Математическое программирование . 39 (2): 117–129. doi :10.1007/BF02592948. hdl : 2027.42/6740 . S2CID  30500771.
3. Сахни, С. «Проблемы, связанные с вычислениями», в журнале SIAM Journal on Computing, 3, 262--279, 1974.
4. Pardalos, Panos M.; Vavasis, Stephen A. (1991). «Квадратичное программирование с одним отрицательным собственным значением является NP-трудным». Journal of Global Optimization . 1 : 15–22. doi :10.1007/BF00120662.
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 . doi :10.1080/23307706.2017.1397554. S2CID  67856259.
11. Рокафеллар, Р. Тиррелл (1993). «Множители Лагранжа и оптимальность» (PDF) . Обзор SIAM . 35 (2): 183–238. CiteSeerX 10.1.1.161.7209 . doi :10.1137/1035044. 
12. О методах выпуклой минимизации см. тома Хириарта-Уррути и Лемарешаля (связка) и учебники Рущинского , Берцекаса , Бойда и Ванденберге (внутренняя точка).
13. Нестеров, Юрий; Аркадий, Немировский (1995). Полиномиальные алгоритмы внутренних точек в выпуклом программировании . Общество промышленной и прикладной математики. ISBN 978-0898715156.
14. Пэн, Джиминг; Роос, Корнелис; Терлаки, Тамас (2002). «Саморегулярные функции и новые направления поиска для линейной и полуопределенной оптимизации». Математическое программирование . 93 (1): 129–171. doi :10.1007/s101070200296. ISSN  0025-5610. S2CID  28882966.
15. "Численная оптимизация". Springer Series in Operations Research and Financial Engineering . 2006. doi :10.1007/978-0-387-40065-5. ISBN 978-0-387-30303-1.
16. Борчерс, Брайан. "Обзор программного обеспечения для выпуклой оптимизации" (PDF) . Архивировано из оригинала (PDF) 2017-09-18 . Получено 12 апреля 2021 .
17. «Добро пожаловать в CVXPY 1.1 — документация CVXPY 1.1.11». www.cvxpy.org . Получено 12.04.2021 .
18. Уделл, Мадлен; Мохан, Каранвир; Зенг, Дэвид; Хонг, Дженни; Даймонд, Стивен; Бойд, Стивен (17 октября 2014 г.). «Выпуклая оптимизация в Julia». arXiv : 1410.4821 [math.OC].
19. "Дисциплинированная выпуклая оптимизация - CVXR". www.cvxgrp.org . Получено 2021-06-17 .
20. Критенсен/Кларбринг, гл. 4.
21. Шмит, LA; Флери, C. 1980: Структурный синтез путем объединения концепций аппроксимации и дуальных методов . J. Amer. Inst. Aeronaut. Astronaut 18, 1252-1260
22. Boyd, Stephen; Diamond, Stephen; Zhang, Junzi; Agrawal, Akshay. "Convex Optimization Applications" (PDF) . Архивировано (PDF) из оригинала 2015-10-01 . Получено 12 апреля 2021 г. .
23. Малик, Жером (28.09.2011). "Выпуклая оптимизация: приложения, формулировки, релаксации" (PDF) . Архивировано (PDF) из оригинала 12.04.2021 . Получено 12 апреля 2021 г. .
24. Бен Хаим Ю. и Элишакофф И., Выпуклые модели неопределенности в прикладной механике, Elsevier Science Publishers, Амстердам, 1990
25. Ахмад Бацци, Дирк ТМ Слок и Лиза Мейлак. «Оценка угла прибытия в режиме реального времени при наличии взаимной связи». Семинар IEEE по статистической обработке сигналов (SSP) 2016 года. IEEE, 2016.

Ссылки

• Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). Выпуклый анализ и оптимизация . Belmont, MA.: 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) . Springer . Получено 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.
• Kiwiel, Krzysztof C. (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
• Рокафеллар, Р. Т. (1970). Выпуклый анализ . Принстон: Princeton University Press.

• Рущинский, Анджей (2006). Нелинейная оптимизация . Издательство Принстонского университета.
• Шмит, LA; Флери, C. 1980: Структурный синтез путем объединения концепций аппроксимации и дуальных методов . J. Amer. Inst. Aeronaut. Astronaut 18, 1252-1260

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

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