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

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

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

Выпуклые множестваПравить

Основная статья: Выпуклое множество

Выпуклое множество является множеством   для некоторого векторного пространства X, такое что для любых   и  [1]

 .

Выпуклая функцияПравить

Основная статья: Выпуклая функция

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

 [1].

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

 

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

Выпуклое сопряжениеПравить

Основная статья: Выпуклое сопряжение

Выпуклое сопряжение расширенной вещественнозначной (не обязательно выпуклой) функции   — это функция  , где X* является двойственным пространством пространства X[2], такая что

 

Двойное сопряжениеПравить

Двойное сопряжение функции   — это сопряжение сопряжения, что обычно записывается как  . Двойное сопряжение полезно, когда нужно показать, что выполняется сильная или слабая двойственность[en] (с помощью функции возмущений[en]).

Для любого   неравенство   вытекает из неравенства Фенхеля. Для собственной функции[en] f = f** тогда и только тогда, когда f выпукла и полунепрерывна снизу по теореме Фенхеля — Моро[2][3].

Выпуклая минимизацияПравить

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

 

такая что   является выпуклой функцией, а   является выпуклым множеством.

Двойственная задачаПравить

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

общем случае, если дана двойственная пара[en][4] отделимых локально выпуклых пространств   и функция  , мы можем определить прямую задачу как нахождение такого  , что   Другими словами,   — это инфимум (точная нижняя граница) функции  .

Если имеются ограничения, они могут быть встроены в функцию  , если положить  , где   — индикаторная функция[en]. Пусть теперь   (для другой двойственной пары  ) будет функцией возмущений[en], такой что  [5].

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

 

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

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

 

где   — выпуклое сопряжение от обоих переменных, а   означает супремум (точную верхнюю границу)[6][7][5][6].

 

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

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

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

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

  при условиях   для i = 1, …, m.

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

  при условиях   для i = 1, …, m,

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

 

ПримечанияПравить

  1. 1 2 3 Rockafellar, 1997.
  2. 1 2 Zălinescu, 2002, с. 75–79.
  3. Borwein, Lewis, 2006, с. 76–77.
  4. Двойственная пара — это тройка  , где   — векторное пространство над полем  ,   — множество всех линейных отображений  , а третий элемент — билинейная форма  .
  5. 1 2 Boţ, Wanka, Grad, 2009.
  6. 1 2 Csetnek, 2010.
  7. Zălinescu, 2002, с. 106–113.
  8. Borwein, Lewis, 2006.
  9. Boyd, Vandenberghe, 2004.

ЛитератураПравить

  • Jonathan Borwein, Adrian Lewis. Convex Analysis and Nonlinear Optimization: Theory and Examples. — 2. — Springer, 2006. — ISBN 978-0-387-29570-1.
  • Stephen Boyd, Lieven Vandenberghe. Convex Optimization. — Cambridge University Press, 2004. — ISBN 978-0-521-83378-3.
  • R. Tyrrell Rockafellar. Convex Analysis. — Princeton, NJ: Princeton University Press, 1997. — ISBN 978-0-691-01586-6.
  • Radu Ioan Boţ, Gert Wanka, Sorin-Mihai Grad. Duality in Vector Optimization. — Springer, 2009. — ISBN 978-3-642-02885-4.
  • Constantin Zălinescu. Convex analysis in general vector spaces. — River Edge, NJ: World Scientific Publishing Co., Inc., 2002. — С. 106–113. — ISBN 981-238-067-1.
  • Ernö Robert Csetnek. Overcoming the failure of the classical generalized interior-point regularity conditions in convex optimization. Applications of the duality theory to enlargements of maximal monotone operators. — Logos Verlag Berlin GmbH, 2010. — ISBN 978-3-8325-2503-3.
  • Jonathan Borwein, Adrian Lewis. Convex Analysis and Nonlinear Optimization: Theory and Examples. — 2. — Springer, 2006. — ISBN 978-0-387-29570-1.
  • Hiriart-Urruty J.-B., Lemaréchal C. Fundamentals of convex analysis. — Berlin: Springer-Verlag, 2001. — ISBN 978-3-540-42205-1.
  • Ivan Singer. Abstract convex analysis. — New York: John Wiley & Sons, Inc., 1997. — С. xxii+491. — (Canadian Mathematical Society series of monographs and advanced texts). — ISBN 0-471-16015-6.
  • Stoer J., Witzgall C. Convexity and optimization in finite dimensions. — Berlin: Springer, 1970. — Т. 1. — ISBN 978-0-387-04835-2.
  • Kusraev A.G., Kutateladze S.S. Subdifferentials: Theory and Applications. — Dordrecht: Kluwer Academic Publishers, 1995. — ISBN 978-94-011-0265-0.
  • Кусраев А. Г., Кутателадзе С. С. Субдифференциалы. Теория и приложения. Ч. 2.. — 2-е, перераб.. — Новосибирск: Изд-во Ин-та математики, 2003. — ISBN 5–86134–116–8.