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

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

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

Определение

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

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

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

где целевая функция $f$ выпукла, как и множество допустимых решений $C$. Если такая точка существует, её называют оптимальной точкой. Множество всех оптимальных точек называется оптимальным множеством. Если $f$ не ограничена на $C$ или инфимум не достигается, говорят, что оптимизации не ограничена. Если же $C$ пусто, говорят о недопустимой задаче.

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

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

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

При условиях

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

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

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

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

Свойства

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

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

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

Примеры

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

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

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

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

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

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

Алгоритмы

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

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

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

Расширения

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

См. также

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

Ссылки

• Stephen Boyd, Lieven Vandenberghe, Convex optimization (pdf)
• EE364a: Convex Optimization I, EE364b: Convex Optimization II, Страница курса оксфордского университета
• 6.253: Convex Analysis and Optimization, страница курса MIT OCW
• Brian Borchers, An overview of software for convex optimization