27.04.2023

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

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

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

Определение

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

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

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

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

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

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

Минимизировать f ( x ) {displaystyle f(mathbf {x} )} При условиях g i ( x ) ⩽ 0 , i = 1 , … , m h i ( x ) = 0 , i = 1 , … , p , {displaystyle {egin{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 ∈ R n {displaystyle xin mathbb {R} ^{n}} является переменной оптимизации, функции f , g 1 , … , g m {displaystyle f,g_{1},ldots ,g_{m}} выпуклы, а функции h 1 , … , h p {displaystyle h_{1},ldots ,h_{p}} аффинны .

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

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

Свойства

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

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

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

Примеры

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

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

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

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

X = { x ∈ X | g 1 ( x ) , … , g m ( x ) ⩽ 0 } . {displaystyle {mathcal {X}}=left{xin Xvert g_{1}(x),ldots ,g_{m}(x)leqslant 0 ight}.}

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

L ( x , λ 0 , λ 1 , … , λ m ) = λ 0 f ( x ) + λ 1 g 1 ( x ) + ⋯ + λ m g m ( x ) . {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).}

Для любой точки x {displaystyle x} из X {displaystyle X} , которая минимизирует f {displaystyle f} на X {displaystyle X} , существуют вещественные числа λ 0 , λ 1 , … , λ m , {displaystyle lambda _{0},lambda _{1},ldots ,lambda _{m},} , называемые множителями Лагранжа, для которых выполняются одновременно условия:

x {displaystyle x} минимизирует L ( y , λ 0 , λ 1 , … , λ m ) {displaystyle L(y,lambda _{0},lambda _{1},ldots ,lambda _{m})} над всеми y ∈ X , {displaystyle yin X,}

λ 0 , λ 1 , … , λ m ⩾ 0 , {displaystyle lambda _{0},lambda _{1},ldots ,lambda _{m}geqslant 0,} по меньшей мере с одним λ k > 0 , {displaystyle lambda _{k}>0,}

λ 1 g 1 ( x ) = ⋯ = λ m g m ( x ) = 0 {displaystyle lambda _{1}g_{1}(x)=cdots =lambda _{m}g_{m}(x)=0} (дополняющая нежёсткость).

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

g 1 ( z ) , … , g m ( z ) < 0 , {displaystyle g_{1}(z),ldots ,g_{m}(z)<0,}

то утверждение выше может быть усилено до требования λ 0 = 1 {displaystyle lambda _{0}=1} .

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

Алгоритмы

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

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

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

Расширения

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