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

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

Определение

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

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

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

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

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

В целом есть три варианта существования решения:

• Если такая точка x * существует, ее называют оптимальной точкой или решением ; совокупность всех оптимальных точек называется оптимальным множеством ; и проблема называется разрешимой .
• Если $f$ неограничен снизу над $C$, или нижняя грань не достигается, то задача оптимизации называется неограниченной .
• В противном случае, если $C$ если множество пусто, то задача называется неразрешимой .

Стандартная форма

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

${\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}}$

где:

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

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

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

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

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

${\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}}$

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

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

${\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. ^н .

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

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

${\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 ) меньше. Это означает, что в принципе можно ограничить внимание задачами выпуклой оптимизации без ограничений равенства. Однако на практике часто предпочитают сохранять ограничения равенства, поскольку они могут сделать некоторые алгоритмы более эффективными, а также облегчить понимание и анализ проблемы.

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

Следующие классы задач являются задачами выпуклой оптимизации или могут быть сведены к задачам выпуклой оптимизации посредством простых преобразований:

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

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

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

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

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

Ниже приведены полезные свойства задач выпуклой оптимизации:

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим задачу выпуклой минимизации, заданную в стандартной форме функцией стоимости $f(x)$ и ограничения неравенства $g_{i}(x)\leq 0$ для $1\leq i\leq m$. Тогда домен ${\mathcal {X}}$ является:

${\mathcal {X}}=\left\{x\in X\vert g_{1}(x),\ldots ,g_{m}(x)\leq 0\right\}.$

Функция Лагранжа для этой задачи:

$L(x,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})=\lambda _{0}f(x)+\lambda _{1}g_{1}(x)+\cdots +\lambda _{m}g_{m}(x).$

Для каждой точки $x$ в $X$ что сводит к минимуму $f$ над $X$, существуют действительные числа $\lambda _{0},\lambda _{1},\ldots ,\lambda _{m},$ называемые множителями Лагранжа , которые одновременно удовлетворяют этим условиям:

1. $x$ сводит к минимуму $L(y,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})$ общий $y\in X,$
2. $\lambda _{0},\lambda _{1},\ldots ,\lambda _{m}\geq 0,$ хотя бы с одним $\lambda _{k}>0,$
3. $\lambda _{1}g_{1}(x)=\cdots =\lambda _{m}g_{m}(x)=0$ (дополнительная расслабленность).

Если существует «строго допустимая точка», т. е. точка $z$ удовлетворяющий

$g_{1}(z),\ldots ,g_{m}(z)<0,$

тогда приведенное выше утверждение можно усилить, потребовав, чтобы $\lambda _{0}=1$.

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

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

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

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

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

Программа	Язык	Описание	ФОСС ?	Ссылка
CVX	МАТЛАБ	Интерфейсы с решателями SeDuMi и SDPT3; предназначен только для выражения задач выпуклой оптимизации.	Да
CVXMOD	Питон	Интерфейсы с решателем CVXOPT .	Да
CVXPY	Питон
Convex.jl	Юлия	Дисциплинированное выпуклое программирование, поддерживает множество решателей.	Да
CVXR	Р		Да
ЯЛМИП	МАТЛАБ, Октава	Интерфейсы с решателями CPLEX, GUROBI, MOSEK, SDPT3, SEDUMI, CSDP, SDPA, PENNON; также поддерживает целочисленную и нелинейную оптимизацию, а также некоторую невыпуклую оптимизацию. Может выполнять надежную оптимизацию с неопределенностью в ограничениях LP/SOCP/SDP.	Да
лаборатория ЛМИ	МАТЛАБ	Выражает и решает задачи полуопределенного программирования (называемые «линейными матричными неравенствами»).	Нет
Переводчик LMIlab		Преобразует лабораторные проблемы LMI в проблемы SDP.	Да
ксЛМИ	МАТЛАБ	Похож на лабораторию LMI, но использует решатель SeDuMi.	Да
АИММС		Может выполнять надежную оптимизацию линейного программирования (с помощью MOSEK для решения конусного программирования второго порядка) и смешанного целочисленного линейного программирования . Пакет моделирования для LP+SDP и робастных версий.	Нет
РИМ		Система моделирования для надежной оптимизации. Поддерживает устойчивую к распределению оптимизацию и наборы неопределенностей .	Да
ГлоптиПоли 3	МАТЛАБ, Октава	Система моделирования для полиномиальной оптимизации.	Да
СОСТУЛС		Система моделирования для полиномиальной оптимизации . Использует SDPT3 и SeDuMi. Требуется набор инструментов для символьных вычислений.	Да
РазреженныйPOP		Система моделирования для полиномиальной оптимизации. Использует решатели SDPA или SeDuMi.	Да
Комплексный комплекс		Поддерживает методы primal-dual для LP + SOCP. Может решать задачи LP, QP, SOCP и смешанного целочисленного линейного программирования.	Нет
CSDP	С	Поддерживает методы primal-dual для LP + SDP. Доступны интерфейсы для MATLAB, R и Python. Доступна параллельная версия. Решатель SDP.	Да
CVXOPT	Питон	Поддерживает методы primal-dual для LP + SOCP + SDP. Использует масштабирование Нестерова-Тодда. Интерфейсы к МОСЭК и DSDP.	Да
МОИСЕЙ		Поддерживает методы primal-dual для LP + SOCP.	Нет
СеДуМи	MATLAB, Октава, MEX	Решает LP+SOCP+SDP. Поддерживает методы primal-dual для LP + SOCP + SDP.	Да
СДПА	С++	Решает ЛП+СДП. Поддерживает методы primal-dual для LP + SDP. Доступны версии с параллельной и повышенной точностью.	Да
СДПТ3	MATLAB, Октава, MEX	Решает LP+SOCP+SDP. Поддерживает методы primal-dual для LP + SOCP + SDP.	Да
ConicBundle		Поддерживает коды общего назначения LP + SOCP + SDP. Использует метод пакета. Специальная поддержка ограничений SDP и SOCP.	Да
ДСДП		Поддерживает коды общего назначения для LP + SDP. Использует метод двойной внутренней точки.	Да
ЛОГОТИП		Поддерживает коды общего назначения для SOCP, которые рассматриваются как задача нелинейного программирования.	Нет
ПЕННОН		Поддерживает коды общего назначения. Использует расширенный метод Лагранжа, особенно для проблем с ограничениями SDP.	Нет
СДПЛР		Поддерживает коды общего назначения. Использует факторизацию низкого ранга с расширенным методом Лагранжа.	Да
ГАМС		Система моделирования для задач линейного, нелинейного, смешанного целочисленного линейного/нелинейного и конического программирования второго порядка.	Нет
Услуги по оптимизации		Стандарт XML для кодирования проблем оптимизации и их решения.

Приложения

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

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

Расширения

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

См. также

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

Ссылки

• Берцекас, Дмитрий П.; Недич, Ангелия; Оздаглар, Асуман (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: Основы . Фундаментальные принципы математических наук. Том 305. Берлин: Springer-Verlag. стр. xviii+417. ISBN  978-3-540-56850-6 . МР   1261420 .
• Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (1993). Алгоритмы выпуклого анализа и минимизации, Том II: Расширенная теория и методы расслоения . Фундаментальные принципы математических наук. Том 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 . МР   1900016 . S2CID   9048698 .
• Nesterov, Yurii; Nemirovskii, Arkadii (1994). Interior Point Polynomial Methods in Convex Programming . SIAM.
• Нестеров Юрий. (2004). Вводные лекции по выпуклой оптимизации , Kluwer Academic Publishers
• Рокафеллар, RT (1970). Выпуклый анализ . Принстон: Издательство Принстонского университета.

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

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

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