Выпуклый анализ

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

Выпуклые множества

Выпуклое множество является множеством C ⊆ X {displaystyle Csubseteq X} для некоторого векторного пространства X, такое что для любых x , y ∈ C {displaystyle x,yin C} и λ ∈ [ 0 , 1 ] {displaystyle lambda in [0,1]}

λ x + ( 1 − λ ) y ∈ C {displaystyle lambda x+(1-lambda )yin C} .

Выпуклая функция

Выпуклая функция — это любая расширенная вещественнозначная функция f : X → R ∪ { ± ∞ } {displaystyle f:X o mathbb {R} cup {pm infty }} , которая удовлетворяет неравенству Йенсена, то есть, для любых x , y ∈ X {displaystyle x,yin X} и любой λ ∈ [ 0 , 1 ] {displaystyle lambda in [0,1]}

f ( λ x + ( 1 − λ ) y ) ⩽ λ f ( x ) + ( 1 − λ ) f ( y ) {displaystyle f(lambda x+(1-lambda )y)leqslant lambda f(x)+(1-lambda )f(y)} .

Эквивалентно, выпуклой функцией является любая (расширенная) вещественнозначная функция, такая что её надграфик

{ ( x , r ) ∈ X × R : f ( x ) ⩽ r } {displaystyle left{(x,r)in X imes mathbf {R} :f(x)leqslant r ight}}

является выпуклым множеством.

Выпуклое сопряжение

Выпуклое сопряжение расширенной вещественнозначной (не обязательно выпуклой) функции f : X → R ∪ { ± ∞ } {displaystyle f:X o mathbb {R} cup {pm infty }} — это функция f ∗ : X ∗ → R ∪ { ± ∞ } {displaystyle f^{*}:X^{*} o mathbb {R} cup {pm infty }} , где X* является двойственным пространством пространства X, такая что

f ∗ ( x ∗ ) = sup x ∈ X { ⟨ x ∗ , x ⟩ − f ( x ) } . {displaystyle f^{*}(x^{*})=sup _{xin X}left{langle x^{*},x angle -f(x) ight}.}

Двойное сопряжение

Двойное сопряжение функции f : X → R ∪ { ± ∞ } {displaystyle f:X o mathbb {R} cup {pm infty }} — это сопряжение сопряжения, что обычно записывается как f ∗ ∗ : X → R ∪ { ± ∞ } {displaystyle f^{**}:X o mathbb {R} cup {pm infty }} . Двойное сопряжение полезно, когда нужно показать, что выполняется сильная или слабая двойственность (с помощью функции возмущений).

Для любого x ∈ X {displaystyle xin X} неравенство f ∗ ∗ ( x ) ⩽ f ( x ) {displaystyle f^{**}(x)leqslant f(x)} вытекает из неравенства Фенхеля. Для собственной функции f = f** тогда и только тогда, когда f выпукла и полунепрерывна снизу по теореме Фенхеля — Моро.

Выпуклая минимизация

(Прямая) задача выпуклого программирования, это задача вида

inf x ∈ M f ( x ) {displaystyle inf _{xin M}f(x)}

такая что f : X → R ∪ { ± ∞ } {displaystyle f:X o mathbb {R} cup {pm infty }} является выпуклой функцией, а M ⊆ X {displaystyle Msubseteq X} является выпуклым множеством.

Двойственная задача

Принцип двойственности в оптимизации утверждает, что задачи оптимизации можно рассматривать с двух точек зрения, как прямую задачу или двойственную задачу.

общем случае, если дана двойственная пара отделимых локально выпуклых пространств ( X , X ∗ ) {displaystyle left(X,X^{*} ight)} и функция f : X → R ∪ { + ∞ } {displaystyle f:X o mathbb {R} cup {+infty }} , мы можем определить прямую задачу как нахождение такого x ^ {displaystyle {hat {x}}} , что f ( x ^ ) = inf x ∈ X f ( x ) . {displaystyle f({hat {x}})=inf _{xin X}f(x).,} Другими словами, f ( x ^ ) {displaystyle f({hat {x}})} — это инфимум (точная нижняя граница) функции f {displaystyle f} .

Если имеются ограничения, они могут быть встроены в функцию f {displaystyle f} , если положить f ~ = f + I c o n s t r a i n t s {displaystyle { ilde {f}}=f+I_{mathrm {constraints} }} , где I {displaystyle I} — индикаторная функция. Пусть теперь F : X × Y → R ∪ { + ∞ } {displaystyle F:X imes Y o mathbb {R} cup {+infty }} (для другой двойственной пары ( Y , Y ∗ ) {displaystyle left(Y,Y^{*} ight)} ) будет функцией возмущений, такой что F ( x , 0 ) = f ~ ( x ) {displaystyle F(x,0)={ ilde {f}}(x)} .

Двойственная задача для этой функции возмущения по отношению к выбранной задаче определяется как

sup y ∗ ∈ Y ∗ − F ∗ ( 0 , y ∗ ) {displaystyle sup _{y^{*}in Y^{*}}-F^{*}(0,y^{*})}

где F* является выпуклым сопряжением по обоим переменным функции F.

Разрыв двойственности — это разность правой и левой частей неравенства

sup y ∗ ∈ Y ∗ − F ∗ ( 0 , y ∗ ) ⩽ inf x ∈ X F ( x , 0 ) , {displaystyle sup _{y^{*}in Y^{*}}-F^{*}(0,y^{*})leqslant inf _{xin X}F(x,0),,}

где F ∗ {displaystyle F^{*}} — выпуклое сопряжение от обоих переменных, а sup {displaystyle sup } означает супремум (точную верхнюю границу).

sup y ∗ ∈ Y ∗ − F ∗ ( 0 , y ∗ ) ⩽ inf x ∈ X F ( x , 0 ) . {displaystyle sup _{y^{*}in Y^{*}}-F^{*}(0,y^{*})leqslant inf _{xin X}F(x,0).}

Этот принцип тот же самый, что и слабая двойственность. Если обе стороны равны, говорят, что задача удовлетворяет условиям сильной двойственности.

Существует много условий для сильной двойственности, такие как:

• F = F**, где F является функцией возмущений для прямой и двойственной задач, а F** является двойным сопряжением функции F;
• прямая задача является задачей линейного программирования;
• Условие Слейтера для задач выпуклого программирования.

Двойственность Лагранжа

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

min x f ( x ) {displaystyle min _{x}f(x)} при условиях g i ( x ) ⩽ 0 {displaystyle g_{i}(x)leqslant 0} для i = 1, …, m.

двойственной задачей Лагранжа будет

sup u inf x L ( x , u ) {displaystyle sup _{u}inf _{x}L(x,u)} при условиях u i ( x ) ⩾ 0 {displaystyle u_{i}(x)geqslant 0} для i = 1, …, m,

где целевая функция L(x, u) является двойственной функцией Лагранжа, определённой следующим образом:

L ( x , u ) = f ( x ) + ∑ j = 1 m u j g j ( x ) {displaystyle L(x,u)=f(x)+sum _{j=1}^{m}u_{j}g_{j}(x)}