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([
        -400*x[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: Чем квазиньютоновские методы отличаются от метода Ньютона?
<details>
<summary>💡 Подсказка</summary>
Подумай про вычислительную сложность матрицы Гессе
</details>
<details>
<summary>✅ Ответ</summary>
Квазиньютоновские методы аппроксимируют H⁻¹, не вычисляя точный Гессиан. Это даёт O(n²) вместо O(n³) операций на итерацию.
</details>
Задание 2: Что означает условие кривизны s_k^T y_k > 0?
<details>
<summary>💡 Подсказка</summary>
Связано с выпуклостью функции
</details>
<details>
<summary>✅ Ответ</summary>
Это условие означает, что функция локально выпукла. Нарушение условия может привести к потере положительной определённости B_k.
</details>
Задание 3: Реализуй простое обновление ранга-1 (формула Бройдена):
B_{k+1} = B_k + (s_k - B_k y_k)(s_k - B_k y_k)^T / ||s_k - B_k y_k||²
code
Python
def broyden_update(B, s, y):
    # Твой код здесь
    pass
Продвинутый уровень 🟡
Задание 4: Объясни, почему L-BFGS эффективнее BFGS для больших размерностей?
<details>
<summary>✅ Ответ</summary>
L-BFGS хранит только последние m векторов {s_i, y_i} вместо полной матрицы B. Память: O(mn) вместо O(n²).
</details>
Задание 5: Реализуй двухциклевую рекурсию L-BFGS для вычисления B_k ∇f:
code
Python
def lbfgs_two_loop(grad, s_history, y_history, gamma=1.0):
    """L-BFGS двухциклевая рекурсия"""
    m = len(s_history)  # количество сохранённых пар
    q = grad.copy()
    alpha = np.zeros(m)
    
    # Первый цикл (назад)
    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 y_k > 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, y_i} и используй двухциклевую рекурсию
💡 Почему: Иначе теряешь главное преимущество 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 небольших моделей, где точность важнее скорости одной итерации.