Квазиньютоновские методы: быстрая оптимизация без Гессиана

🎯 Зачем это нужно?

Представь, что ты тренируешь нейронную сеть с миллионами параметров 🧠. Метод Ньютона требует вычисления и обращения матрицы Гессе размером миллион×миллион - это займёт вечность! А градиентный спуск сходится слишком медленно.

Квазиньютоновские методы - это золотая середина: - TensorFlow и PyTorch: L-BFGS для обучения моделей с небольшим числом параметров - SciPy optimize: BFGS используется в scipy.optimize.minimize по умолчанию - Финтех: оптимизация портфелей в Goldman Sachs и JPMorgan

📚 История вопроса

В 1970 году четыре математика независимо придумали один метод: Бройден, Флетчер, Гольдфарб и Шанно. Получился BFGS - один из самых популярных алгоритмов оптимизации! 🏆

Идея гениальна в простоте: “А что если не вычислять Гессиан точно, а аппроксимировать его по градиентам?”

💡 Интуиция

Метод Ньютона говорит: “Иди в направлении H⁻¹∇f” (обратный Гессиан × градиент) Градиентный спуск: “Иди против градиента: -∇f”

Квазиньютоновские методы: “Будем УГАДЫВАТЬ обратный Гессиан B ≈ H⁻¹, улучшая догадку на каждом шаге!”

[МЕДИА: image_01] Описание: Схема сравнения траекторий сходимости разных методов оптимизации на овражной функции Промпт: “optimization comparison illustration, showing convergence paths of gradient descent (zigzag), Newton method (direct), and quasi-Newton (smooth curve), contour plot background, educational style, clean modern design”

📐 Формальное определение

Квазиньютоновские методы итерационно строят аппроксимацию B_k ≈ H⁻¹(x_k):

Итерация: 1. Направление: d_k = -B_k ∇f(xk) 2. Шаг: x{k+1} = x_k + α_k d_k (αk из line search) 3. Обновление: B{k+1} = обновить(B_k, s_k, y_k)

где sk = x{k+1} - x_k, yk = ∇f(x{k+1}) - ∇f(x_k)

Условие кривизны: B_{k+1} y_k = s_k (квазиньютоновское условие)

🔍 Примеры с разбором

BFGS формула обновления

Формула Бройдена-Флетчера-Гольдфарба-Шанно:

B_{k+1} = B_k + (s_k s_k^T)/(s_k^T y_k) - (B_k y_k y_k^T B_k)/(y_k^T B_k y_k)

Интуиция: - Первое слагаемое: “добавляем информацию о новом направлении s_k” - Второе слагаемое: “вычитаем старую неточную информацию в направлении y_k”

[МЕДИА: image_02] Описание: Пошаговая визуализация обновления аппроксимации Гессиана в BFGS Промпт: “step-by-step BFGS matrix update visualization, before and after matrices shown as heatmaps, arrows showing transformation, mathematical formulas, technical illustration style”

Пример: оптимизация функции Розенброка

f(x,y) = 100(y - x²)² + (1 - x)²

Код реализации: ```python import numpy as np from scipy.optimize import minimize

def rosenbrock(x): return 100*(x[1] - x[0]2)2 + (1 - x[0])**2

def rosenbrock_grad(x): return np.array([ -400x[0](x[1] - x[0]2) - 2(1 - x[0]), 200(x[1] - x[0]2) ])

BFGS оптимизация

result = minimize(rosenbrock, [0, 0], method=‘BFGS’, jac=rosenbrock_grad) print(f”Решение: {result.x}“) # ≈ [1, 1] print(f”Итераций: {result.nit}“) # ~30 🎮 Практика Базовый уровень 🟢 Задание 1: Чем квазиньютоновские методы отличаются от метода Ньютона?

# Первый цикл (назад)
for i in range(m-1, -1, -1):
    # Твой код здесь
    pass

# Начальное приближение
r = gamma * q

# Второй цикл (вперёд)  
for i in range(m):
    # Твой код здесь
    pass

return -r  # направление спуска

Челлендж 🔴 Задание 6: Докажи, что если B_k положительно определена и s_k^T yk > 0, то B{k+1} (BFGS обновление) тоже положительно определена. Задание 7: Реализуй адаптивное масштабирование γ_k в L-BFGS: γk = (s{k-1}^T y{k-1})/(y{k-1}^T y_{k-1}) code Python def adaptive_scaling(s_prev, y_prev): # Вычисли оптимальное начальное приближение pass ⚠️ Частые ошибки ❌ Ошибка: Использование BFGS для невыпуклых функций без проверки условия кривизны ✅ Правильно: Проверяй s_k^T y_k > 0, иначе переходи к градиентному шагу 💡 Почему: Нарушение условия кривизны делает B_k неположительно определённой ❌ Ошибка: Хранение полной матрицы B в L-BFGS ✅ Правильно: Храни только векторы {s_i, yi} и используй двухциклевую рекурсию 💡 Почему: Иначе теряешь главное преимущество L-BFGS - экономию памяти ❌ Ошибка: Забывать про line search в квазиньютоновских методах ✅ Правильно: Всегда используй Wolfe conditions для выбора длины шага 💡 Почему: Без правильного line search может не выполняться условие кривизны 🎓 Главное запомнить ✅ Квазиньютоновские методы аппроксимируют H⁻¹ без его вычисления ✅ BFGS: B{k+1} = B_k + ρs_k s_k^T - B_k y_k y_k^T B_k/(y_k^T B_k y_k) ✅ L-BFGS экономит память, храня только последние m пар векторов 🔗 Связь с другими темами Квазиньютоновские методы развивают идеи градиентной оптимизации (урок 287) и готовят к пониманию современных адаптивных методов типа Adam. В глубоком обучении L-BFGS используется для fine-tuning небольших моделей, где точность важнее скорости одной итерации.