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

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

Определения

Множество $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) \le \alpha f(x) + (1 - \alpha)f(y)$

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

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

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

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

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

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

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

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

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

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

2) $f(y) \ge 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 )] \ge f(\mathbb{E}\xi )$

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

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

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

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