Выпуклый анализ - это раздел математики, посвященный изучению свойств выпуклые функции и выпуклые множества, часто с приложениями в выпуклой минимизации, подобласти теории оптимизации.
A выпуклое множество - это множество C ⊆ X для некоторого векторного пространства X, такое, что для любых x, y ∈ C и λ ∈ [0, 1], тогда
A выпуклая функция - любая расширенная вещественнозначная функция f: X → R ∪ {± ∞}, которая удовлетворяет неравенству Йенсена, т.е. для любых x, y ∈ X и любого λ ∈ [0, 1], тогда
Эквивалентно, выпуклая функция - это любая (расширенная) вещественнозначная функция такая, что ее эпиграф
- выпуклое множество.
выпуклое сопряженное расширенного действительного числа (не обязательно выпуклого) функция f: X → R ∪ {± ∞} - это f *: X * → R ∪ {± ∞}, где X * - двойное пространство X и
Биконъюгат функции f: X → R ∪ {± ∞} является сопряженным элементом, обычно записываемым как f **: X → R ∪ {± ∞}. Двойное сопряжение полезно для того, чтобы показать, когда выполняется сильная или слабая двойственность (с помощью функции возмущения ).
Для любого x ∈ X неравенство f ** (x) ≤ f (x) следует из неравенства Фенхеля – Юнга. Для правильных функций, f = f ** тогда и только тогда, когда f является выпуклым и полунепрерывным снизу по теореме Фенхеля – Моро.
A выпуклая минимизация (прямая) задача имеет вид
такая, что f: X → R ∪ {± ∞} - выпуклая функция, а M ⊆ X - выпуклое множество.
В теории оптимизации принцип двойственности гласит, что проблемы оптимизации можно рассматривать с одной из двух точек зрения: с основной проблемы или с двойственной проблемы.
В общем случае даны две двойные пары , разделенные локально выпуклыми пробелами (X, X *) и (Y, Y *). Тогда, учитывая функцию f: X → R ∪ {+ ∞}, мы можем определить прямую задачу как нахождение x такого, что
Если есть условия ограничения, их можно встроить в функцию f, разрешив где I - индикаторная функция. Тогда пусть F: X × Y → R ∪ {± ∞} - функция возмущения такая, что F (x, 0) = f (x).
Двойственная задача относительно выбранной функции возмущения задается следующим образом:
где F * - выпуклое сопряжение по обеим переменным F.
разрыв двойственности - это разность правой и левой частей неравенства
Этот принцип аналогичен принципу слабой двойственности. Если две стороны равны друг другу, то говорят, что задача удовлетворяет сильной двойственности.
Существует много условий для выполнения сильной двойственности, например:
Для задачи выпуклой минимизации с ограничениями неравенства
двойственная по Лагранжу задача:
где целевая функция L (x, u) - двойственная функция Лагранжа определяется следующим образом: