Выпуклое программирование

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

Выпуклое программирование находит применение в целом ряде дисциплин, таких как автоматические системы управления, оценка и обработка сигналов, коммуникации и сети, схемотехника^[5], анализ данных и моделирование, финансы, статистика (оптимальный план эксперимента^[англ.])^[6] и структурная оптимизация^{[англ.][7]}. Развитие вычислительной техники и алгоритмов оптимизации сделало выпуклое программирование почти столь же простым как линейное программирование^[8].

Определение

Задача выпуклого программирования — это задача оптимизации, в которой целевая функция является выпуклой функцией и область допустимых решений выпукла. Функция ${\displaystyle f}$, отображающая некоторое подмножество ${\displaystyle \mathbb {R} ^{n}}$ в ${\displaystyle \mathbb {R} \cup \{\pm \infty \}}$, является выпуклой, если область определения выпукла и для всех ${\displaystyle \theta \in [0,1]}$, и всех ${\displaystyle x,y}$ в их области определения ${\displaystyle f(\theta x+(1-\theta )y)\leqslant \theta f(x)+(1-\theta )f(y)}$. Множество выпукло, если для всех его элементов ${\displaystyle x,y}$ и любого ${\displaystyle \theta \in [0,1]}$ также и ${\displaystyle \theta x+(1-\theta )y}$ принадлежит множеству.

В частности, задачей выпуклого программирования является задача нахождения некоторого ${\displaystyle \mathbf {x^{\ast }} \in C}$, на котором достигается

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

где целевая функция ${\displaystyle f}$ выпукла, как и множество допустимых решений ${\displaystyle C}$^[9][10]. Если такая точка существует, её называют оптимальной точкой. Множество всех оптимальных точек называется оптимальным множеством. Если ${\displaystyle f}$ не ограничена на ${\displaystyle C}$ или инфимум не достигается, говорят, что оптимизации не ограничена. Если же ${\displaystyle C}$ пусто, говорят о недопустимой задаче^[11].

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

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

Минимизировать ${\displaystyle f(\mathbf {x} )}$

При условиях

${\displaystyle {\begin{aligned}&&g_{i}(\mathbf {x} )\leqslant 0,\quad i=1,\dots ,m\\&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}}$

где ${\displaystyle x\in \mathbb {R} ^{n}}$ является переменной оптимизации, функции ${\displaystyle f,g_{1},\ldots ,g_{m}}$ выпуклы, а функции ${\displaystyle h_{1},\ldots ,h_{p}}$ аффинны ^[11].

В этих терминах функция ${\displaystyle f}$ является целевой функцией задачи, а функции ${\displaystyle g_{i}}$ и ${\displaystyle h_{i}}$ именуются функциями ограничений. Допустимое множество решений задачи оптимизации — это множество, состоящее из всех точек ${\displaystyle x\in \mathbb {R} ^{n}}$, удовлетворяющих условиям ${\displaystyle g_{1}(x)\leqslant 0,\ldots ,g_{m}(x)\leqslant 0}$ и ${\displaystyle h_{1}(x)=0,\ldots ,h_{p}(x)=0}$. Это множество выпукло, поскольку множества подуровня выпуклой функции выпуклы, аффинные множества также выпуклы, а пересечение выпуклых множеств является выпуклым множеством^[12].

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

Свойства

Полезные свойства задач выпуклого программирования^[13][11]:

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

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

Примеры

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

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

• Метод наименьших квадратов
• Линейное программирование
• Выпуклая квадратичная оптимизация с линейными ограничениями
• Квадратичное программирование в квадратичных ограничениях^[англ.]
• Коническая оптимизация^[англ.]
• Геометрическое программирование
• Коническое программирование на конусе второго порядка^[англ.]
• Полуопределённое программирование
• Принцип максимума энтропии с подходящими ограничениями

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

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

${\displaystyle {\mathcal {X}}=\left\{x\in X\vert g_{1}(x),\ldots ,g_{m}(x)\leqslant 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}\geqslant 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}$.

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

Алгоритмы

Задачи выпуклого программирования решаются следующими современными методами:^[15]

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

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

Расширения

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

См. также

• Двойственность
• Условия Каруша — Куна — Таккера
• Оптимизация (математика)
• Метод проксимального градиента