Выпуклые функции: определения и критерии

Зачем изучать выпуклые функции?

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

Определение выпуклой функции

Функция f: ℝⁿ → ℝ (или f: dom(f) → ℝ, где dom(f) — выпуклое множество) называется выпуклой, если для любых x, y ∈ dom(f) и любого λ ∈ [0,1]:

f(λx + (1−λ)y) ≤ λf(x) + (1−λ)f(y)

Геометрический смысл: рассмотрим две точки на графике функции: A = (x, f(x)) и B = (y, f(y)). Правая часть λf(x) + (1−λ)f(y) — это точка на хорде AB, соответствующая параметру λ. Левая часть f(λx + (1−λ)y) — это значение функции в той же точке по горизонтали. Выпуклость означает: график функции лежит ниже любой хорды. Хорда «нависает» над графиком.

Если выполняется строгое неравенство (< вместо ≤) при x ≠ y и λ ∈ (0,1) — функция строго выпуклая. У строго выпуклой функции минимум единственен.

Вогнутая функция: f вогнутая, если −f выпуклая. Неравенство «переворачивается».

Примеры выпуклых функций

В одной переменной:

f(x) = x² — выпуклая (парабола «смотрит вверх»)
f(x) = eˣ — выпуклая (экспонента)
f(x) = |x| — выпуклая, но не дифференцируемая в 0
f(x) = x log x на x > 0 — выпуклая (используется в теории информации)
f(x) = log x на x > 0 — вогнутая

В нескольких переменных:

f(x) = ‖x‖² = x₁² + ... + xₙ² — выпуклая
f(x) = max(x₁, ..., xₙ) — выпуклая (максимум из линейных функций)
f(x) = log(Σᵢ eˣⁱ) — «мягкий максимум», log-sum-exp, выпуклая и гладкая
f(X) = λ_max(X) — максимальное собственное значение симметричной матрицы — выпуклая

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

Прямая проверка определения часто неудобна. На практике используют аналитические критерии.

Критерий первого порядка (для дифференцируемых функций):

f выпуклая ⟺ для всех x, y ∈ dom(f): f(y) ≥ f(x) + ∇f(x)ᵀ(y − x)

Смысл: касательная гиперплоскость к графику в любой точке x лежит ниже (или касается) графика. Градиент ∇f(x) даёт «наилучшую линейную аппроксимацию» f вблизи x, и для выпуклой функции эта аппроксимация — глобальная нижняя оценка.

Важное следствие: если ∇f(x*) = 0, то x* — глобальный минимум! Действительно, f(y) ≥ f(x*) + 0 = f(x*) для всех y.

Критерий второго порядка (для дважды дифференцируемых функций):

f выпуклая ⟺ ∇²f(x) ≽ 0 для всех x ∈ dom(f)

Здесь ∇²f(x) — матрица Гессе (матрица вторых частных производных), ≽ 0 означает «положительно полуопределённая» (все собственные значения ≥ 0).

Смысл: функция «изгибается вверх» во всех направлениях. Для f(x) = x² имеем f''(x) = 2 > 0 — выпуклая. Для f(x) = −x² имеем f''(x) = −2 < 0 — вогнутая.

Подуровневые множества и надграфик

Подуровневое множество C_α = {x : f(x) ≤ α} — все точки, где функция не превышает α.

Теорема: если f выпуклая, то все подуровневые множества C_α выпуклые.

Надграфик epi(f) = {(x, t) : f(x) ≤ t} — «всё, что выше графика», включая сам график.

Ключевая теорема: f выпуклая ⟺ epi(f) — выпуклое множество в ℝⁿ⁺¹.

Это связывает теорию функций и теорию множеств: задача минимизации выпуклой функции эквивалентна нахождению «нижней точки» выпуклого тела.

Операции, сохраняющие выпуклость

Зная несколько простых выпуклых функций, можно строить сложные:

Сумма: f₁ + f₂ выпуклая, если f₁ и f₂ выпуклые
Неотрицательная шкалировка: λf при λ ≥ 0 выпуклая
Максимум: max(f₁, f₂, ..., fₘ) выпуклая (максимум выпуклых функций выпуклый)
Аффинная подстановка: f(Ax + b) выпуклая (если f выпуклая)
Супремум: sup_{y ∈ S} f(x, y) выпуклая по x (если f(·, y) выпуклая для каждого y)

Полный разбор примера

Задача: проверить выпуклость f(x₁, x₂) = x₁² + 2x₁x₂ + 3x₂² с помощью критерия второго порядка.

Шаг 1: Вычислим частные производные второго порядка. ∂f/∂x₁ = 2x₁ + 2x₂, ∂²f/∂x₁² = 2 ∂f/∂x₂ = 2x₁ + 6x₂, ∂²f/∂x₂² = 6 ∂²f/∂x₁∂x₂ = 2

Шаг 2: Матрица Гессе (не зависит от x в этом примере): ∇²f = [[2, 2], [2, 6]]

Шаг 3: Проверяем положительную полуопределённость. Критерий Сильвестра:

Ведущий минор 1×1: 2 > 0 ✓
Определитель 2×2: 2·6 − 2·2 = 12 − 4 = 8 > 0 ✓

Оба ведущих минора положительны → матрица положительно определена → f строго выпуклая.

Шаг 4: Находим минимум. ∇f(x) = 0: 2x₁ + 2x₂ = 0, 2x₁ + 6x₂ = 0. Из первого уравнения: x₁ = −x₂. Подставляем во второе: −2x₂ + 6x₂ = 0 → x₂ = 0, x₁ = 0. Минимум в точке (0, 0), f(0, 0) = 0.

Применения

Регрессия: среднеквадратичная ошибка f(w) = ‖Xw − y‖² — выпуклая (критерий: ∇²f = 2XᵀX ≽ 0). Поэтому градиентный спуск всегда находит глобальный минимум.

Логистическая регрессия: функция потерь − Σ [yᵢ log σ(wᵀxᵢ) + (1−yᵢ) log(1 − σ(wᵀxᵢ))] — выпуклая по w. Гарантия сходимости любого метода первого порядка.

Финансы: функция среднеквадратичного риска портфеля wᵀΣw (Σ — ковариационная матрица, ≽ 0) — выпуклая. Минимизация риска — выпуклая задача с уникальным решением.