Математический анализ
Экстремумы функций многих переменных
SVM (Support Vector Machine) находит гиперплоскость максимального отступа, решая задачу с ограничениями. Метод множителей Лагранжа превращает это в безусловную оптимизацию. Тот же аппарат используется в задачах размещения дата-центров, конструировании нейронных архитектур и молекулярной динамике.
- SVM: максимизация отступа $\frac{2}{\|w\|}$ при ограничениях $y_i(w^T x_i + b) \geq 1$
- Инженерия: оптимизация формы конструкции при ограничении по весу
- Экономика: максимизация полезности потребителя при бюджетном ограничении
- Нейросети: регуляризация L2 как штраф к функции потерь (вариант Лагранжа)
- Робототехника: планирование траектории с ограничениями по крутящему моменту
Цели урока
- Находить критические точки функции нескольких переменных и классифицировать их с помощью матрицы Гессе
- Применять достаточные условия экстремума через знакоопределённость Гессе
- Решать задачи оптимизации с ограничениями методом множителей Лагранжа
Предварительные знания
- Градиент и частные производные
- Симметричные матрицы и их собственные значения
- Квадратичные формы и их знакоопределённость
Критические точки и Гессе
Критическая точка $x^*$: $\nabla f(x^*) = 0$. Для классификации используется матрица Гессе $H_{ij} = \frac{\partial^2 f}{\partial x_i \partial x_j}$. Критерий: если $H$ положительно определена - минимум, отрицательно определена - максимум, индефинитна (смешанные знаки собственных значений) - седловая точка.
Критерий Сильвестра для положительной определённости: все угловые миноры $\Delta_k > 0$. Для $2\times 2$: $\frac{\partial^2 f}{\partial x^2} > 0$ и $\det H > 0$. Для $n\times n$: $n$ условий на главные миноры.
Метод множителей Лагранжа
Задача: $\min f(x)$ при $g(x) = 0$. Функция Лагранжа: $\mathcal{L}(x, \lambda) = f(x) + \lambda g(x)$. Необходимое условие: $\nabla_x \mathcal{L} = 0$ и $g(x) = 0$. Множитель $\lambda$ показывает, насколько изменится оптимальное значение при ослаблении ограничения: $\frac{df^*}{db} = -\lambda$ для ограничения $g(x) = b$.
Критические точки - необходимое условие
При обучении BERT-Large (340M параметров) градиент функции потерь обращается в нуль в тысячах точек: локальных минимумах, глобальном минимуме и - намного чаще - в сёдловых точках. Исследование Dauphin et al. 2014 показало: в высокоразмерных пространствах отношение числа сёдловых точек к локальным минимумам экспоненциально растёт с размерностью. Gradient descent в нейросетях по большей части уходит от сёдел, а не выбирается из локальных минимумов.
Нахождение критических точек функции потерь нейросети вычислительно недостижимо из-за высокой размерности. На практике gradient descent не ищет критические точки явно - он просто следует вдоль отрицательного градиента, и если попадает в точку с малым градиентом, это может быть минимум или сёдло. Именно поэтому шум SGD полезен: он помогает уйти от сёдел.
Найдите критические точки f(x, y) = x² + xy + y² − 3x.
Ответ следует непосредственно из определения и свойств рассматриваемого математического объекта.
Гессиан и достаточное условие классификации
Метод K-FAC (Kronecker-Factored Approximate Curvature) аппроксимирует Гессиан функции потерь нейросети для ускорения оптимизации. При каждой критической точке матрица Гессиана определяет локальную форму loss surface. Собственные значения Гессиана: все положительные - минимум, все отрицательные - максимум, смешанные - сёдловая точка.
В высокоразмерных пространствах параметров вычисление полного Гессиана (P×P матрица для P весов) недостижимо. Метод Ланцоша позволяет оценить наибольшие и наименьшие собственные значения за O(P) операций. Число обусловленности κ = λ_max/λ_min прямо предсказывает скорость сходимости gradient descent: большое κ означает медленную сходимость и необходимость предобуславливания.
Для f(x,y) = x³ + y³ − 3xy найдите критические точки и классифицируйте их Гессианом.
Ответ следует непосредственно из определения и свойств рассматриваемого математического объекта.
Метод множителей Лагранжа - оптимизация с ограничениями
Метод опорных векторов (SVM) находит разделяющую гиперплоскость с максимальным зазором, решая задачу: минимизировать ‖w‖²/2 при условии yᵢ(w·xᵢ + b) ≥ 1 для всех обучающих примеров. При 1 000 000 обучающих примеров задача имеет 1 000 000 ограничений. Метод множителей Лагранжа переводит её в двойственную форму, допускающую эффективное решение через QP-солверы.
Двойственная задача SVM, полученная через множители Лагранжа, обнаруживает, что только опорные векторы (ближайшие к разделяющей плоскости обучающие примеры) имеют ненулевые множители. Все остальные примеры не влияют на решение. Это разреженность SVM - прямое следствие теории множителей Лагранжа и условий Куна - Таккера.
Найти максимум f(x, y) = xy при ограничении x + y = 10 методом множителей Лагранжа.
Ответ следует непосредственно из определения и свойств рассматриваемого математического объекта.
Классификация критической точки $f(x,y) = x^3 - 3xy^2$
$\nabla f = (3x^2 - 3y^2, -6xy) = 0$ при $(0,0)$. $H = \begin{pmatrix} 6x & -6y \\ -6y & -6x \end{pmatrix}$. При $(0,0)$: $H = 0$ - критерий Гессе неприменим. Это точка обезьяньего седла с тремя горбами и тремя впадинами.
SVM через Лагранжа: геометрический смысл
Задача: $\min \frac{1}{2}\|w\|^2$ при $y_i(w^T x_i + b) \geq 1$. Двойственная задача (KKT): $\max \sum_i \alpha_i - \frac{1}{2}\sum_{i,j} \alpha_i \alpha_j y_i y_j x_i^T x_j$. Ненулевые $\alpha_i$ соответствуют опорным векторам на границе отступа.
Итоги
- Критические точки находятся из $\nabla f = 0$, классифицируются по знаку собственных значений Гессе
- Положительная определённость Гессе - достаточное условие локального минимума; индефинитность - седло
- Метод Лагранжа $\nabla f = -\lambda \nabla g$ объединяет оптимизацию с ограничениями в одну систему уравнений
Связь с другими темами
Метод Лагранжа обобщается на задачи с неравенствами (KKT-условия) и на бесконечномерные пространства (вариационное исчисление). Собственные значения Гессе напрямую связаны с кривизной поверхности из дифференциальной геометрии.
- Связанные темы — развивает
Вопросы для размышления
- Почему для SVM задача в двойственном пространстве (через $\alpha_i$) часто проще исходной задачи?
- Седловые точки в оптимизации нейросетей: это проблема или ресурс? Почему Adam не застревает в седлах так часто, как SGD?
- Критерий второго порядка для минимума требует положительную определённость Гессе. Что происходит, когда Гессе вырождена (нулевое собственное значение)?