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

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

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

Определение

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

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

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

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

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

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

Минимизировать $f(𝐱)$

При условиях

$\begin{array}{ccc}& & g_i(𝐱)⩽0,i=1,\dots ,m\\ & & h_i(𝐱)=0,i=1,\dots ,p,\end{array}$

где $x\in {ℝ}^n$ является переменной оптимизации, функции $f,g_1,\dots ,g_m$ выпуклы, а функции $h_1,\dots ,h_p$ аффинны Шаблон:Sfn.

В этих терминах функция $f$ является целевой функцией задачи, а функции $g_i$ и $h_i$ именуются функциями ограничений. Допустимое множество решений задачи оптимизации — это множество, состоящее из всех точек $x\in {ℝ}^n$, удовлетворяющих условиям $g_1(x)⩽0,\dots ,g_m(x)⩽0$ и $h_1(x)=0,\dots ,h_p(x)=0$. Это множество выпукло, поскольку множества подуровня выпуклой функции выпуклы, аффинные множества также выпуклы, а пересечение выпуклых множеств является выпуклым множествомШаблон:Sfn.

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

Свойства

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

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

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

Примеры

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

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

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

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

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

$𝒳=\{x\in X|g_1(x),\dots ,g_m(x)⩽0\}.$

Функция Лагранжа для задачи

$L(x,{\lambda }_0,{\lambda }_1,\dots ,{\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,\dots ,{\lambda }_m,$, называемые множителями Лагранжа, для которых выполняются одновременно условия:

1. $x$ минимизирует $L(y,{\lambda }_0,{\lambda }_1,\dots ,{\lambda }_m)$ над всеми $y\in X,$
2. ${\lambda }_0,{\lambda }_1,\dots ,{\lambda }_m⩾0,$ по меньшей мере с одним ${\lambda }_k>0,$
3. ${\lambda }_1{g}_1(x)=\cdots ={\lambda }_m{g}_m(x)=0$ (дополняющая нежёсткость).

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

$g_1(z),\dots ,g_m(z)<0,$

то утверждение выше может быть усилено до требования ${\lambda }_0=1$.

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

Алгоритмы

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

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

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

Расширения

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Еремин И. И., Астафьев Н. Н. Введение в теорию линейного и выпуклого программирования. - Шаблон:М., Наука, 1976. - 189 c.
• Каменев Г. К. Оптимальные адаптивные методы полиэдральной аппроксимации выпуклых тел. М.: ВЦ РАН, 2007, 230 с. ISBN 5-201-09876-2.
• Каменев Г. К. Численное исследование эффективности методов полиэдральной аппроксимации выпуклых тел. М: Изд. ВЦ РАН, 2010, 118с. ISBN 978-5-91601-043-5.

Ссылки

• 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