Выпуклость с точки зрения анализа

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

Выпуклая функция — функция, у которой отрезок (хорда), соединяющий две любые точки графика, лежит не ниже самого графика: $f(\lambda x+(1-\lambda)y)\le \lambda f(x)+(1-\lambda)f(y)$ для $\lambda\in[0,1]$.

Зачем нам выпуклость

Главная боль оптимизации — локальные минимумы. Выпуклость её устраняет: у выпуклой функции на выпуклом множестве любой локальный минимум автоматически глобальный. Это значит, что простой градиентный спуск, оказавшись в любой впадине, оказывается в лучшей впадине. Поэтому теория выпуклой оптимизации (Boyd) — фундамент, на котором стоят надёжные методы.

Определение через хорду

Возьмём две точки $x$ и $y$. Соедините соответствующие точки графика отрезком. Если для любых $x,y$ этот отрезок проходит над графиком (или по нему), функция выпукла:

$$f\big(\lambda x+(1-\lambda)y\big)\ \le\ \lambda f(x)+(1-\lambda)f(y),\quad \lambda\in[0,1].$$

Парабола $x^2$ выпукла, $e^x$ выпукла, $|x|$ выпукла (хоть и не гладкая). А $\sin x$ или $-x^2$ — нет.

Критерий через гессиан

Для дважды дифференцируемой функции выпуклость эквивалентна тому, что гессиан положительно полуопределён всюду:

$$\nabla^2 f(x)\succeq 0\quad\text{для всех }x.$$

В одном измерении это просто $f''(x)\ge 0$ везде. Удобно: чтобы доказать выпуклость, не нужно перебирать пары точек, достаточно проверить знак второй производной.

Проверяем хорду кодом

Возьмём $f(x)=x^2$ (выпукла) и убедимся, что середина хорды не ниже графика.

def f(x):
    return x * x

def check_convex(a, b, lam=0.5):
    mid_x = lam * a + (1 - lam) * b
    chord = lam * f(a) + (1 - lam) * f(b)   # точка на хорде
    graph = f(mid_x)                        # точка на графике
    return graph, chord

for (a, b) in [(-2, 2), (0, 4), (1, 3)]:
    graph, chord = check_convex(a, b)
    ok = "выпукло" if graph <= chord + 1e-9 else "НЕ выпукло"
    print(f"[{a},{b}]: график={graph}, хорда={chord} -> {ok}")

Вывод:

[-2,2]: график=0.0, хорда=4.0 -> выпукло
[0,4]: график=4.0, хорда=8.0 -> выпукло
[1,3]: график=4.0, хорда=5.0 -> выпукло

Во всех случаях график лежит под хордой — функция выпукла. Для $-x^2$ неравенство развернулось бы.

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

Выпуклость множества — родственное понятие: множество $X$ выпукло, если вместе с любыми двумя точками оно содержит и весь отрезок между ними. Шар, полупространство $\{x: a^\top x\le b\}$, пересечение полупространств (многогранник) — выпуклы. Звезда или кольцо — нет. Задача $\min f(x)$ s.t. $x\in X$ называется выпуклой, когда выпуклы и $f$, и $X$.

Как работает под капотом

Доказательство «локальный = глобальный» короткое и красивое. Пусть $x^*$ — локальный минимум, но существует $y$ с $f(y)<f(x^*)$. Рассмотрим точку $z=\lambda x^*+(1-\lambda)y$ при малом $1-\lambda$. По выпуклости $f(z)\le \lambda f(x^*)+(1-\lambda)f(y)< f(x^*)$. Но $z$ как угодно близко к $x^*$ — противоречие с локальной минимальностью. Значит такого $y$ нет, и $x^*$ глобален.

Частые ошибки

Проверять выпуклость в одной точке. $f''\ge 0$ должно выполняться всюду, а не в избранной точке.
Путать выпуклость функции и множества. Это два разных (хотя связанных) свойства.
Считать сумму выпуклых невыпуклой. Наоборот: сумма выпуклых выпукла, максимум выпуклых выпукл — это удобные правила для конструирования.

Итоги

Выпуклая функция: хорда над графиком; критерий $\nabla^2 f\succeq 0$ всюду (в 1D — $f''\ge 0$).
Выпуклое множество содержит отрезок между любыми своими точками.
В выпуклой задаче локальный минимум = глобальный — отсюда надёжность методов.