Русская Википедия:Выпуклый анализ

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

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

Шаблон:Основная статья Выпуклое множество является множеством <math>C \subseteq X</math> для некоторого векторного пространства X, такое что для любых <math>x, y \in C</math> и <math>\lambda \in [0, 1]</math>Шаблон:Sfn

<math>\lambda x + (1 - \lambda)y \in C</math>.

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

Шаблон:Основная статья Выпуклая функция — это любая расширенная вещественнозначная функция <math>f : X \to \R \cup \{\pm\infty\}</math>, которая удовлетворяет неравенству Йенсена, то есть, для любых <math>x, y \in X</math> и любой <math>\lambda \in [0, 1]</math>

<math>f(\lambda x + (1 - \lambda)y) \leqslant \lambda f(x) + (1-\lambda) f(y)</math>Шаблон:Sfn.

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

<math>\left\{(x,r) \in X \times \mathbf{R}: f(x) \leqslant r \right\}</math>

является выпуклым множествомШаблон:Sfn.

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

Шаблон:Основная статья Выпуклое сопряжение расширенной вещественнозначной (не обязательно выпуклой) функции <math>f : X \to \R \cup \{\pm\infty\}</math> — это функция <math>f^* : X^* \to \R \cup \{\pm\infty\}</math>, где X* является двойственным пространством пространства XШаблон:Sfn, такая что

<math>f^*(x^*) = \sup_{x \in X} \left \{\langle x^*,x \rangle - f(x) \right \}.</math>

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

Двойное сопряжение функции <math>f : X \to \R \cup \{\pm\infty\}</math> — это сопряжение сопряжения, что обычно записывается как <math>f^{**} : X \to \R \cup \{\pm\infty\}</math>. Двойное сопряжение полезно, когда нужно показать, что выполняется сильная или слабая двойственность (с помощью Шаблон:Не переведено 5).

Для любого <math>x \in X</math> неравенство <math>f^{**}(x) \leqslant f(x)</math> вытекает из неравенства Фенхеля. Для Шаблон:Не переведено 5 f = f** тогда и только тогда, когда f выпукла и полунепрерывна снизу по теореме Фенхеля — МороШаблон:SfnШаблон:Sfn.

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

Шаблон:Основная статья (Прямая) задача выпуклого программирования, это задача вида

<math>\inf_{x \in M} f(x)</math>

такая что <math>f : X \to \R \cup \{\pm\infty\}</math> является выпуклой функцией, а <math>M \subseteq X</math> является выпуклым множеством.

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

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

общем случае, если дана Шаблон:Не переведено 5[1] отделимых локально выпуклых пространств <math>\left(X,X^*\right)</math> и функция <math>f: X \to \mathbb{R} \cup \{+\infty\}</math>, мы можем определить прямую задачу как нахождение такого <math>\hat{x}</math>, что <math>f(\hat{x}) = \inf_{x \in X} f(x). \,</math> Другими словами, <math>f(\hat{x})</math> — это инфимум (точная нижняя граница) функции <math>f</math>.

Если имеются ограничения, они могут быть встроены в функцию <math>f</math>, если положить <math>\tilde{f} = f + I_{\mathrm{constraints}}</math>, где <math>I</math> — Шаблон:Не переведено 5. Пусть теперь <math>F: X \times Y \to \R \cup \{+\infty\}</math> (для другой двойственной пары <math>\left(Y,Y^*\right)</math>) будет Шаблон:Не переведено 5, такой что <math>F(x,0) = \tilde{f}(x)</math>Шаблон:Sfn.

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

<math>\sup_{y^* \in Y^*} -F^*(0,y^*)</math>

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

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

<math>\sup_{y^* \in Y^*} -F^*(0,y^*) \leqslant \inf_{x \in X} F(x,0), \,</math>

где <math>F^*</math> — выпуклое сопряжение от обоих переменных, а <math>\sup</math> означает супремум (точную верхнюю границу)Шаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn.

<math>\sup_{y^* \in Y^*} -F^*(0,y^*) \leqslant \inf_{x \in X} F(x,0).</math>

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

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

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

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

<math>\min_x f(x)</math> при условиях <math>g_i(x) \leqslant 0</math> для i = 1, …, m.

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

<math>\sup_u \inf_x L(x, u)</math> при условиях <math>u_i(x) \geqslant 0</math> для i = 1, …, m,

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

<math>L(x,u) = f(x) + \sum_{j=1}^m u_j g_j(x)</math>

Примечания

Шаблон:Примечания

Литература

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Двойственная пара — это тройка <math>\left(X,X^*,\langle,\rangle\right)</math>, где <math>X</math> — векторное пространство над полем <math>F</math>, <math>X^*</math> — множество всех линейных отображений <math>\phi \colon X \to F</math>, а третий элемент — билинейная форма <math>X^* \times X \to F \colon (\phi, x) \mapsto \phi(x)</math>.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Выпуклый_анализ&oldid=9476869