Метод Ньютона в задачах безусловной нелинейной оптимизации

Математический фундамент алгоритма базируется на разложении целевой функции $f(x)$ в ряд Тейлора до второго порядка в окрестности текущей точки $x_k$: $f(x) \approx f(x_k) + \nabla f(x_k)^T(x - x_k) + \frac{1}{2}(x - x_k)^T H(x_k) (x - x_k)$, где $\nabla f$ — вектор градиента, а $H$ — матрица Гессе (Гессиан), состоящая из всех смешанных частных производных второго порядка. Необходимым условием минимума этой квадратичной модели является равенство ее производной нулю. Отсюда напрямую выводится формула шага Ньютона: $x_{k+1} = x_k - H^{-1}(x_k) \nabla f(x_k)$. Вектор $-H^{-1} \nabla f$ называется ньютоновским направлением.

Уникальным преимуществом метода Ньютона является квадратичная сходимость: вблизи точки локального минимума количество верных знаков решения удваивается на каждой итерации. Однако за эту скорость приходится платить колоссальными вычислительными затратами. Для задачи с $n$ переменными необходимо на каждом шаге вычислить $O(n^2)$ элементов матрицы Гессе, а затем решить систему линейных уравнений, что требует $O(n^3)$ операций. Для систем машинного обучения с миллионами параметров вычисление точного Гессиана физически невозможно.

Второй серьезной проблемой классического метода Ньютона является отсутствие гарантии сходимости, если начальная точка выбрана слишком далеко от оптимума или если матрица Гессе не является положительно определенной (алгоритм может сойтись к локальному максимуму или седловой точке). Для решения этой проблемы используются методы доверительных областей (Trust Region) и линейного поиска с условиями Вольфе (Line Search), которые искусственно ограничивают длину шага или модифицируют Гессиан, добавляя к нему диагональную матрицу $\lambda I$ (метод Левенберга-Марквардта), гарантируя положительную определенность и стабильный спуск.

Сложность вычисления аналитического Гессиана породила огромное семейство квазиньютоновских методов (DFP, BFGS, L-BFGS). Эти алгоритмы не вычисляют вторые производные напрямую, а строят их аппроксимацию, накапливая историю изменений градиента на предыдущих шагах. Метод L-BFGS (Limited-memory BFGS) сегодня является стандартом для оптимизации огромных нелинейных систем, предлагая идеальный компромисс между феноменальной сходимостью Ньютоновской парадигмы и строгими ограничениями на использование оперативной памяти.

Список литературы:
1. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. — М.: Мир, 1985.
2. Деннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. — М.: Мир, 1988.
3. Nocedal J., Wright S.J. Numerical Optimization. — Springer, 2006.