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

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

Определение

Задача выпуклого программирования — это задача оптимизации , в которой целевая функция является выпуклой функцией и область допустимых решений выпукла . Функция ${\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}$ . Если такая точка существует, её называют оптимальной точкой . Множество всех оптимальных точек называется оптимальным множеством . Если ${\displaystyle f}$ не ограничена на ${\displaystyle C}$ или инфимум не достигается, говорят, что оптимизации не ограничена . Если же ${\displaystyle C}$ пусто, говорят о недопустимой задаче .

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

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

Минимизировать ${\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}}$ аффинны .

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

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

Свойства

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

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

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

Примеры

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

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

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

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

Алгоритмы

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

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

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

Расширения

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

См. также

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

Примечания

Литература

Ссылки

• Stephen Boyd, Lieven Vandenberghe, (pdf)
• , , Страница курса оксфордского университета
• , страница курса MIT OCW
• Brian Borchers,