Теория выпуклости

Немного матана для дальнейших математических изысканий

Определения

Множество $X$ называется выпуклым, если $\forall x,y\in X,\forall \alpha \in (0,1):\alpha x+(1-\alpha )y\in X$

Функция $f(x)$, заданная на выпуклом множестве $X\subset \mathbb {R} ^{d}$, называется выпуклой, если $\forall \alpha \in (0,1),\forall x,y\in X$:

$f(\alpha x+(1-\alpha )y)\leq \alpha f(x)+(1-\alpha )f(y)$

Если неравенство строгое (и $x\neq y$!!!!), то функция строго выпукла.

Полезные факты

1) Любая норма - выпуклая функция.

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

3) Глобальный минимум строго выпуклой функции единственен.

4) Заданная на выпуклом $X$ функция $f(x):\mathbb {R} ^{d}\rightarrow \mathbb {R}$ выпукла тогда и только тогда, когда $g(\alpha )=f(x+\alpha y)$, где $x,y$ - любые из $X$, является одномерной выпуклой функцией.

Подробно доказательство можно увидеть здесь, но оно в лоб.

Критерии выпуклости

Для дважды дифференцируемой $f(x)$ следующие утверждения эквивалентны:

1) $f$ выпукла

2) $f(y)\geq f(x)+\bigtriangledown f(x)^{T}(y-x)$

3) $\bigtriangledown ^{2}f(x)\succeq 0$

В билетах написано что можно без доказательства, для желающих вотъ.

Критерии строгой выпуклости

Для дифференцируемой $f(x)$ выпуклость эквивалентна $f(y)>f(x)+\bigtriangledown f(x)^{T}(y-x)$.

Замечание: из $\bigtriangledown ^{2}f(x)\succ 0$ следует строгая выпуклость, да, но не наоборот.

Неравенство Йенсена

Для выпуклой функции и любой случайной величины $\xi$:

$\mathbb {E} [f(\xi )]\geq f(\mathbb {E} \xi )$

Доказательство: для $f$ записать из критерия выпуклости неравенство 2 для $x=\xi$ (ага, случайной величины!) и $y=\mathbb {E} \xi$, после чего взять матожидание от сторон неравенства. Подробнее тут.

Обращение неравенства Йенсена в равенство

Для строго выпуклой $f$ неравенство Йенсена обращается в равенство тогда и только тогда, когда $\xi =\mathbb {E} \xi$ с вероятностью 1.

Доказательство: аналогично доказательству неравенства Йенсена для выпуклой $f$, для строгой выпуклости там образуется строгое неравенство. При этом мы ж требовали в определении строгой выпуклости, что $x\neq y$, то есть брать $x=\xi$ и $y=\mathbb {E} \xi$, если они с вероятностью 1 равны, нельзя.