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

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

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

Содержание

  • 1 Выпуклые множества
  • 2 Выпуклые функции
  • 3 Выпуклое сопряжение
    • 3.1 Биконъюгирование
  • 4 Выпуклая минимизация
    • 4.1 Двойная задача
      • 4.1.1 Двойственность Лагранжа
  • 5 См. Также
  • 6 Примечания
  • 7 Ссылки
  • 8 Внешние ссылки

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

A выпуклое множество - это множество C ⊆ X для некоторого векторного пространства X, такое, что для любых x, y ∈ C и λ ∈ [0, 1], тогда

λ Икс + (1 - λ) y ∈ C {\ displaystyle \ lambda x + (1- \ lambda) y \ in C}\ lambda x + (1- \ lambda) y \ in C .

Выпуклые функции

A выпуклая функция - любая расширенная вещественнозначная функция f: X → R ∪ {± ∞}, которая удовлетворяет неравенству Йенсена, т.е. для любых x, y ∈ X и любого λ ∈ [0, 1], тогда

f (λ x + (1 - λ) y) ≤ λ f (x) + (1 - λ) f (y) {\ displaystyle f (\ lambda x + (1- \ lambda) y) \ leq \ lambda f (x) + (1- \ lambda) f (y)}f (\ lambda x + (1- \ lambda) y) \ leq \ lambda f (x) + (1- \ лямбда) f (y) .

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

{(x, r) ∈ X × R: f (x) ≤ r} {\ displaystyle \ left \ {(x, r) \ in X \ times \ mathbf {R}: f (x) \ leq r \ right \}}\ left \ {(x, r) \ in X \ times {\ mathbf {R}}: f (x) \ leq r \ right \}

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

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

выпуклое сопряженное расширенного действительного числа (не обязательно выпуклого) функция f: X → R ∪ {± ∞} - это f *: X * → R ∪ {± ∞}, где X * - двойное пространство X и

f ∗ (x ∗) = sup x ∈ X {⟨x ∗, x⟩ - f (x)}. {\ displaystyle f ^ {*} (x ^ {*}) = \ sup _ {x \ in X} \ left \ {\ langle x ^ {*}, x \ rangle -f (x) \ right \}. }f ^ {*} (x ^ {*}) = \ sup _ {{x \ in X}} \ left \ {\ langle x ^ {*}, x \ rangle -f (x) \ right \}.

Биконъюгат

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

Для любого x ∈ X неравенство f ** (x) ≤ f (x) следует из неравенства Фенхеля – Юнга. Для правильных функций, f = f ** тогда и только тогда, когда f является выпуклым и полунепрерывным снизу по теореме Фенхеля – Моро.

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

A выпуклая минимизация (прямая) задача имеет вид

inf x ∈ M f (x) {\ displaystyle \ inf _ {x \ in M} f (x)}\ inf _ {{x \ in M}} f (x)

такая, что f: X → R ∪ {± ∞} - выпуклая функция, а M ⊆ X - выпуклое множество.

Двойная проблема

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

В общем случае даны две двойные пары , разделенные локально выпуклыми пробелами (X, X *) и (Y, Y *). Тогда, учитывая функцию f: X → R ∪ {+ ∞}, мы можем определить прямую задачу как нахождение x такого, что

inf x ∈ X f (x). {\ displaystyle \ inf _ {x \ in X} f (x).}\ inf _ {{x \ in X}} f (x).

Если есть условия ограничения, их можно встроить в функцию f, разрешив f = f + I ограничения {\ displaystyle f = f + I _ {\ mathrm {constraints}}}f = f + I _ {\ mathrm {constraints}} где I - индикаторная функция. Тогда пусть F: X × Y → R ∪ {± ∞} - функция возмущения такая, что F (x, 0) = f (x).

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

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

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

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

sup y ∗ ∈ Y ∗ - F ∗ (0, y ∗) ≤ inf x ∈ XF (x, 0). {\ displaystyle \ sup _ {y ^ {*} \ in Y ^ {*}} - F ^ {*} (0, y ^ {*}) \ leq \ inf _ {x \ in X} F (x, 0).}\ sup _ {{y ^ {*} \ in Y ^ {*}}} - F ^ {*} (0, y ^ {*}) \ leq \ inf _ {{x \ in X}} F (x, 0).

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

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

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

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

min x f (x) с учетом g i (x) ≤ 0 для i = 1,..., m.

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

sup u inf x L (x, u) при условии u i (x) ≥ 0 для i = 1,..., m.

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

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

См. также

Примечания

Ссылка erences

  • Ж.-Б. Хириарт-Уррути; С. Лемарешаль (2001). Основы выпуклого анализа. Берлин: Springer-Verlag. ISBN 978-3-540-42205-1.
  • Певец, Иван (1997). Абстрактный выпуклый анализ. Серия монографий и расширенных текстов Канадского математического общества. Нью-Йорк: John Wiley Sons, Inc., стр. Xxii + 491. ISBN 0-471-16015-6. MR 1461544.
  • Stoer, J.; Витцгалл, К. (1970). Выпуклость и оптимизация в конечных размерах. 1 . Берлин: Springer. ISBN 978-0-387-04835-2.
  • A.G. Кусраев; С.С. Кутателадзе (1995). Субдифференциалы: теория и приложения. Дордрехт: Kluwer Academic Publishers. ISBN 978-94-011-0265-0.

Внешние ссылки

  • СМИ, относящиеся к Анализ выпуклости на Wikimedia Commons
Последняя правка сделана 2021-05-15 11:21:47
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте