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

Выпуклая оптимизация — это подраздел математической оптимизации , изучающий проблему минимизации выпуклых функций на выпуклых множествах (или, что эквивалентно, максимизации вогнутых функций на выпуклых множествах). Многие классы задач выпуклой оптимизации допускают алгоритмы полиномиального времени, ^[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 С}$
• В противном случае, если — пустое множество, то задача считается неразрешимой .${\displaystyle С}$

Задача выпуклой оптимизации находится в стандартной форме, если она записана как

${\displaystyle {\begin{align}&{\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{align}}}$

где: ^{[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 ,м}$
• Функции ограничения равенства , , являются аффинными преобразованиями , то есть имеют вид: , где — вектор, а — скаляр.${\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 С}$${\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 все ограничения линейны, но цель может быть выпуклой квадратичной функцией.
• Программирование конусов второго порядка является более общим.
• Полуопределенное программирование является более общим.
• Коническая оптимизация еще более общая — см. рисунок справа.

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

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

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

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

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

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

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

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

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

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

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

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

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

This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. (April 2021) (Learn how and when to remove this message)

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

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

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

• 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
• Брайан Борчерс, Обзор программного обеспечения для выпуклой оптимизации
• Книга «Выпуклая оптимизация» Ливена Ванденберге и Стивена П. Бойда