Квазиньютоновские методы и BFGS

Квазиньютоновские методы берут скорость Ньютона почти даром: они оценивают кривизну по тому, как меняется градиент.

Квазиньютоновские методы заменяют дорогой гессиан дешёвым приближением $B_k\approx\nabla^2 f$, обновляемым по разностям градиентов; самый известный — BFGS.

Мотивация: Ньютон без гессиана

Ньютон быстр, но требует гессиана ($O(n^2)$ памяти, $O(n^3)$ обращения) и вторых производных. Идея квазиньютоновских методов: а что если оценивать кривизну попутно, наблюдая, как меняется градиент от шага к шагу? Если градиент сильно изменился при малом сдвиге — кривизна велика; если слабо — мала. Это и есть секущее уравнение.

Секущее условие

Обозначим сдвиг $s_k=x_{k+1}-x_k$ и изменение градиента $y_k=\nabla f(x_{k+1})-\nabla f(x_k)$. В одном измерении $f''\approx y_k/s_k$ — буквально определение второй производной через разность первых. В многомерии это секущее уравнение:

$$B_{k+1}\,s_k=y_k.$$

Оно недоопределено (одно векторное условие на целую матрицу), и разные способы «достроить» $B_{k+1}$ дают разные методы. BFGS — самый удачный из них: он обновляет приближение обратного гессиана так, чтобы оно оставалось симметричным и положительно определённым, минимально меняясь от шага к шагу.

Метод секущих как мини-BFGS

Чтобы пощупать идею «гессиан из разности градиентов» исполнимо, реализуем одномерный аналог — метод секущих для минимизации, заменяющий $f''(x_k)$ на $\dfrac{f'(x_k)-f'(x_{k-1})}{x_k-x_{k-1}}$.

def fp(x):                # f'(x) для f = x^4 - 3x^3 + 2
    return 4 * x ** 3 - 9 * x ** 2

x_prev, x = 3.5, 3.0
g_prev = fp(x_prev)
for k in range(1, 8):
    g = fp(x)
    curv = (g - g_prev) / (x - x_prev)     # приближение f''
    x_prev, g_prev = x, g
    x = x - g / curv                        # шаг квази-Ньютона
    print(f"шаг {k}: x={x:.10f}  ошибка={abs(x - 2.25):.2e}")

Вывод:

шаг 1: x=2.6058394161  ошибка=3.56e-01
шаг 2: x=2.3860722229  ошибка=1.36e-01
шаг 3: x=2.2823585917  ошибка=3.24e-02
шаг 4: x=2.2535171408  ошибка=3.52e-03
шаг 5: x=2.2500987972  ошибка=9.88e-05
шаг 6: x=2.2500003081  ошибка=3.08e-07
шаг 7: x=2.2500000000  ошибка=2.71e-11

Без единого вычисления $f''$ метод секущих сошёлся к $x^*=2.25$ почти так же быстро, как Ньютон (сходимость порядка $\approx1.6$ — «золотая» сверхлинейная). Полноразмерный BFGS делает то же самое в $n$ измерениях, аккуратно обновляя матрицу.

BFGS и L-BFGS

Метод	Память	Когда применять
Ньютон	$O(n^2)$ + $O(n^3)$ шаг	Малые $n$, есть гессиан
BFGS	$O(n^2)$, шаг $O(n^2)$	Средние $n$ (до тысяч)
L-BFGS	$O(mn)$, $m\sim 5..20$	Большие $n$ (миллионы)

L-BFGS (limited-memory BFGS) хранит не всю матрицу, а лишь последние $m$ пар $(s_k,y_k)$ и восстанавливает действие приближённого обратного гессиана на вектор «на лету». Это делает его пригодным для задач с миллионами переменных — стандартный выбор для гладкой оптимизации в науке и классическом ML.

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

BFGS поддерживает приближение $H_k\approx[\nabla^2 f]^{-1}$ напрямую (чтобы не обращать матрицу) и обновляет его формулой ранга-2, гарантирующей положительную определённость при выполнении условия кривизны $s_k^\top y_k>0$. Положительная определённость критична: она гарантирует, что направление $-H_k\nabla f$ — направление спуска. Сверхлинейная сходимость BFGS приближается к квадратичной Ньютона, но без вторых производных и без $O(n^3)$ — отсюда его популярность.

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

Игнорировать условие кривизны. Если $s_k^\top y_k\le 0$, обновление BFGS портит положительную определённость — обновление пропускают.
Полный BFGS на огромных $n$. $O(n^2)$ памяти не влезет; нужен L-BFGS.
Без line search. Квазиньютоновские методы тоже требуют контроля длины шага (условия Вольфе) для надёжности.

Итоги

Квазиньютон оценивает кривизну по разности градиентов (секущее условие $B_{k+1}s_k=y_k$).
BFGS даёт сверхлинейную сходимость без гессиана; L-BFGS масштабируется на миллионы переменных.
Нужно условие кривизны $s_k^\top y_k>0$ и line search; это рабочая лошадка гладкой оптимизации.