Лекція 20. BFGS і L-BFGS: практичні квазіньютонівські методи

Коротко про лекцію

Лекція показує, як використовувати інформацію про кривизну без прямого обчислення повного Гессіана на кожній ітерації. Ви розберете ідею BFGS, L-BFGS та практичний вибір між Newton і квазіньютонівськими методами.

Практичний сенс. Метод Ньютона використовує матрицю Гессе, але побудова й зберігання повної матриці стають дорогими для великих задач. Квазіньютонівські методи відновлюють інформацію про кривизну з послідовних градієнтів. BFGS працює з повною апроксимацією матриці, а L-BFGS зберігає лише обмежену історію векторів.

Постановка та базові поняття

1. Яку проблему розв’язують квазіньютонівські методи

Великі моделі часто мають доступний градієнт, бо його можна отримати аналітично, автоматичного диференціювання або ефективним кодом.

матриця Гессе може бути значно дорожчою.

Тому практичне питання звучить так: чи можна використати поведінку градієнт між ітераціями, щоб наблизити кривизна?

BFGS відповідає позитивно.

Алгоритм не вимагає від функції повертати матрицю Гессе.

Він накопичує інформацію про те, як змінювався градієнт після реальних кроків.

крок Ньютона потребує:

\[ H_k s_k=-g_k \]

де:

\[ g_k=\nabla f(x_k) \]

а \(H_k\) — наближення оберненої матриці Гессе.

Для \(n\) змінних повна матриця Гессе має \(n^2\) елементів.

При \(n=10000\) це вже 100 мільйонів чисел.

Крім пам’яті, потрібні похідні другого порядку та лінійна алгебра з великою матрицею.

BFGS шукає практичний компроміс: використовує градієнти й поступово вчиться локальній кривизні.

1.1. Що означають BFGS, L-BFGS і «квазіньютонівський»

Квазіньютонівський метод намагається отримати переваги методу Ньютона без явного обчислення матриці Гессе. Частина «квазі» означає «наближений»: кривизна відновлюється з того, як змінюється градієнт між послідовними точками.

Назва BFGS складається з прізвищ Бройдена, Флетчера, Гольдфарба та Шанно. Це усталене міжнародне скорочення, тому його зберігаємо. L-BFGS означає варіант з обмеженою пам’яттю: повна матриця не зберігається, натомість використовуються кілька останніх пар «крок — зміна градієнта».

Отже, ці назви описують спосіб будувати напрям руху, поступово наближаючи інформацію про кривизну.

2. Ідея апроксимації кривизни

Позначимо:

\[ B_k \]

як наближення матриці Гессе.

Тоді напрям можна будувати з системи:

\[ B_k p_k=-g_k \]

Альтернативно можна апроксимувати обернену матрицю Гессе:

\[ H_k\approx B_k^{-1} \]

і будувати:

\[ p_k=-H_k g_k \]

У різних джерелах позначення \(B_k\) та \(H_k\) можуть відрізнятися, тому важливо читати визначення.

У цій лекції головна ідея важливіша за символічний варіант.

3. Дві точки дають інформацію про кривизну

Важливо не плутати два вектори.

\(s_k\) живе у просторі змінних і описує фактичний рух.

\(y_k\) також має розмір \(n\), але описує зміну градієнт.

Якщо переставити їх місцями, умова січної змінює математичний зміст.

У коді краще використовувати явні назви:

step_vector
gradient_change

Це зменшує ризик помилки в формула оновлення.

Після кроку маємо дві точки:

\[ x_k \]

і:

\[ x_{k+1} \]

Вектор зміни точки:

\[ s_k=x_{k+1}-x_k \]

Градієнти:

\[ g_k=\nabla f(x_k) \]

\[ g_{k+1}=\nabla f(x_{k+1}) \]

Вектор зміни градієнта:

\[ y_k=g_{k+1}-g_k \]

Пара \((s_k,y_k)\) містить інформацію про локальну кривизну.

4. Чому зміна градієнта пов’язана з матрицею Гессе

Цей зв’язок можна побачити через наближення Тейлора для градієнта.

Для малого \(s\):

\[ \nabla f(x+s)\approx \nabla f(x)+H(x)s \]

Переносимо старий градієнт:

\[ \nabla f(x+s)-\nabla f(x)\approx H(x)s \]

Ліва частина — це \(y_k\).

Тому спостережувана пара \((s_k,y_k)\) є експериментальним зразком дії матриці Гессе.

BFGS збирає такі зразки послідовно.

Для малого \(s_k\):

\[ g_{k+1}\approx g_k+H(x_k)s_k \]

Тому:

\[ y_k\approx H(x_k)s_k \]

Це аналог локальної лінійної моделі для градієнта.

Квазіньютонівський оновлення будує матрицю, яка узгоджується з цією інформацією.

Умова:

\[ B_{k+1}s_k=y_k \]

називається умова січної, або умовою січної.

5. Чому однієї пари недостатньо для точної матриці Гессе

Векторне рівняння:

\[ Bs=y \]

задає інформацію тільки про дію матриці вздовж одного напряму \(s\).

Для багатовимірної задачі існує багато матриць, що задовольняють одну таку умову.

BFGS вибирає спеціальне оновлення, яке змінює попередню матрицю контрольованим способом.

Так поступово накопичується інформація з різних напрямів.

Математична логіка

6. Кривизна в парі векторів

Для точної квадратичної функції:

\[ y_k=Hs_k \]

тому:

\[ y_k^Ts_k= s_k^THs_k \]

Якщо \(H\) додатно визначена, цей скаляр додатний для ненульового \(s_k\).

Отже, умова кривизни має прямий зв’язок із додатною кривизною.

Пошук довжини кроку умови часто допомагають гарантувати цю властивість.

Якщо градієнт зашумлений або крок дуже малий, значення може бути чисельно ненадійним.

Скаляр:

\[ y_k^Ts_k \]

має важливий зміст.

Для додатно визначеної локальної кривизни очікується:

\[ y_k^Ts_k>0 \]

Цю умову називають умова кривизни.

Вона допомагає зберігати додатну визначеність BFGS-наближення.

Якщо значення дуже мале або від’ємне, оновлення потребує обережності.

7. BFGS-оновлення наближення матриці Гессе

Формулу не потрібно запам’ятовувати дослівно.

Для курсу важливі чотири властивості.

Перша: оновлення використовує стару наближення.

Друга: використовує лише \(s_k\) і \(y_k\) з нової ітерації.

Третя: виконує умова січної.

Четверта: за відповідних умов зберігає додатну визначеність.

Саме ці властивості пояснюють практичну цінність BFGS.

Одна з форм BFGS-оновлення:

\[ \begin{aligned} B_{k+1} &= B_k- \frac{ B_ks_ks_k^TB_k }{ s_k^TB_ks_k }\\ &\quad+ \frac{ y_ky_k^T }{ y_k^Ts_k } \end{aligned} \]

Формула виглядає громіздкою, але її роль проста.

Перший поправка прибирає частину старої інформації вздовж \(s_k\).

Другий поправка додає інформацію, узгоджену з новою зміною градієнта.

У практичному коді рідко потрібно реалізовувати цю формулу вручну.

8. BFGS-наближення оберненої матриці

Можна оновлювати наближення оберненої матриці Гессе.

Позначимо його через \(M_k\).

Введемо:

\[ \rho_k= \frac{1}{y_k^Ts_k} \]

Тоді BFGS-оновлення оберненої матриці має форму:

\[ \begin{aligned} M_{k+1} &= \left( I-\rho_ks_ky_k^T \right) M_k \left( I-\rho_ky_ks_k^T \right)\\ &\quad+ \rho_ks_ks_k^T \end{aligned} \]

Після цього напрям:

\[ p_k=-M_kg_k \]

Для першого знайомства важливо розуміти структуру: матриця уточнюється з історії кроків і градієнтів.

9. Початкова матриця

Одинична матриця означає, що на старті всі напрями вважаються однаково масштабованими.

Після перших пар \((s,y)\) наближення адаптується.

Іноді \(M_0\) масштабують одним додатним коефіцієнтом.

Це може краще відповідати локальному масштабу кривизна.

Готові реалізація мають власні правила початкового налаштування.

Для навчальної логіки \(I\) є найпростішим і прозорим стартом.

На старті інформації про кривизну ще мало.

Простий вибір:

\[ M_0=I \]

де \(I\) — одинична матриця.

Тоді перший напрям:

\[ p_0=-g_0 \]

тобто алгоритм починає як градієнтний спуск.

Після наступних ітерацій наближення змінюється.

10. Чому потрібен пошук довжини кроку

Крок впливає на якість пара \((s_k,y_k)\).

Якщо \(\alpha\) надто мале, обидва вектори можуть бути близькими до чисельного шуму.

Якщо крок поганий, умова кривизни може порушитися.

Пошук довжини кроку за сильними умовами Вольфа часто використовується разом із BFGS саме через хороші теоретичні властивості.

Для цієї лекції достатньо пам’ятати: напрям BFGS і пошук довжини кроку утворюють єдину практичну систему.

BFGS зазвичай поєднується з пошуком довжини кроку.

Напрям \(p_k\) визначається матричною наближення.

Далі обирається \(\alpha_k\):

\[ x_{k+1}=x_k+\alpha_kp_k \]

Якісний пошук довжини кроку допомагає виконувати умова кривизни і підтримувати стабільне оновлення.

Тому теми пошуку довжини кроку та BFGS безпосередньо пов’язані.

11. Умова січної як багатовимірний аналог

В одновимірному методі січних похідна оцінюється за зміною значень.

У BFGS аналогічна ідея працює для зміни градієнта.

Ми спостерігаємо:

\[ s_k \]

і:

\[ y_k \]

та вимагаємо, щоб нова матриця правильно відображала цей зв’язок.

Тому квазіньютонівський метод можна читати як систематичне навчання локальної кривизни з даних ітерацій.

Алгоритм і покроковий розбір

12. Базовий алгоритм BFGS

Критерій зупинки зазвичай знову пов’язаний із нормою градієнта.

Тобто квазіньютонівське оновлення змінює спосіб побудови напряму, але не змінює базову стаціонарну умову:

\[ \|\nabla f(x_k)\|_2\le\varepsilon \]

Це важливий зв’язок із градієнтний спуск і метод Ньютона.

Методи відрізняються тим, як використовують похідна інформація для формування наступного руху.

Перевірка мінімізатор залишається спільною.

вибрати стартову точку \(x_0\);
задати \(M_0=I\);
обчислити \(g_k\);
перевірити нормою градієнта;
побудувати \(p_k=-M_kg_k\);
виконати пошук довжини кроку;
отримати \(x_{k+1}\);
обчислити \(g_{k+1}\);
сформувати \(s_k\) і \(y_k\);
перевірити умова кривизни;
оновити \(M_k\);
повторити цикл.

У порівнянні з методом Ньютона явна матриця Гессе не потрібна.

13. Простий числовий приклад для пари векторів

Обчислимо також норми:

\[ \|s_k\|_2= \sqrt{0.5^2+(-0.2)^2} \]

і:

\[ \|y_k\|_2= \sqrt{1.0^2+(-0.8)^2} \]

Ці числа показують масштаб зміни точки та градієнт.

Якщо обидва вектори надзвичайно малі, оновлення може бути чутливим до округлення.

Тому практичні реалізації мають захисні перевірки.

У студентській роботі достатньо перевірити \(y^Ts\) і пояснити його знак.

Нехай після одного кроку:

\[ s_k= \begin{pmatrix} 0.5\\ -0.2 \end{pmatrix} \]

а зміна градієнта:

\[ y_k= \begin{pmatrix} 1.0\\ -0.8 \end{pmatrix} \]

Перевіримо:

\[ y_k^Ts_k= 1.0\cdot0.5+ (-0.8)(-0.2) \]

Отримуємо:

\[ y_k^Ts_k=0.66 \]

Значення додатне.

Тому умова кривизни виконується.

14. Що перевіряти перед оновленням

Потрібно перевірити:

\[ y_k^Ts_k>\varepsilon \]

де \(\varepsilon\) — невеликий поріг.

Якщо знаменник близький до нуля, формула оновлення стає чисельно небезпечною.

У такому випадку оновлення можна пропустити або застосувати стабілізовану стратегію.

Готові бібліотеки містять власні механізми захисту.

15. Чому BFGS часто швидший за градієнтний спуск

На вузькій долині градієнт напрям часто дивиться поперек долини.

BFGS-наближення поступово вчиться, які напрями круті, а які пласкі.

Тому матричне перетворення градієнт може повернути напрям ближче до довгої осі долини.

Менше зигзагу означає менше ітерацій.

При цьому один BFGS крок дорожчий за простий градієнтний крок.

Практична перевага виникає, коли скорочення кількості ітерацій компенсує додаткову лінійну алгебру.

Градієнтний спуск використовує тільки поточний градієнт.

BFGS використовує ще й історію того, як градієнт змінювався.

Тому напрям поступово враховує локальний масштаб і поворот долини.

На витягнутих функціях це може суттєво зменшити зигзаг.

BFGS не має повної ньютонівської інформації, але часто наближається до неї практично.

16. Функція Розенброка

Градієнт Розенброка має компоненти:

\[ \frac{\partial f}{\partial x}=-400x(y-x^2)-2(1-x) \]

\[ \frac{\partial f}{\partial y}=200(y-x^2) \]

Ці формули використовуються в прикладі SciPy.

Перед запуском чисельного розв’язувача їх бажано перевірити градієнт чисельно.

Розенброка має простий точний мінімізатор, тому добре підходить для навчальної перевірки.

У реальній задачі точного мінімізатора часто немає.

Для демонстрації квазіньютонівських методів часто використовують:

\[ f(x,y)= 100(y-x^2)^2+(1-x)^2 \]

Мінімізатор:

\[ (x^*,y^*)=(1,1) \]

і:

\[ f(x^*,y^*)=0 \]

Функція має вузьку вигнуту долину.

Вона добре показує проблему градієнтний спуск і перевагу методів, які враховують кривизну.

Траєкторія BFGS на Rosenbrock

17. Що видно на траєкторії

Стартова точка:

\[ (-1.2,1) \]

розташована далеко від мінімізатор.

BFGS поступово рухається до вузької долини та повертає напрям відповідно до накопиченої кривизни.

Траєкторія не є прямою.

Кожний новий градієнт уточнює наближення.

Саме ця адаптація відрізняє BFGS від простого фіксованого градієнтного кроку.

Програмна реалізація та перевірка

18. BFGS у SciPy

Параметр jac=rosenbrock_gradient передає аналітичний градієнт.

Якщо jac не передати, SciPy може оцінювати похідна чисельно залежно від методу та параметрів.

Для навчального прикладу явний градієнт корисніший.

Він дозволяє перевірити похідну окремо та зрозуміти, яку інформацію використовує BFGS.

Параметр gtol задає числовий допуск, пов’язаний із нормою градієнта.

Точну інтерпретацію API потрібно звіряти з документацією конкретної версії SciPy.

# Імпортуємо NumPy, SciPy для обчислень, розв’язання моделі та її перевірки.
import numpy as np
from scipy.optimize import minimize


# Описуємо функцію Розенброка, на якій перевірятимемо квазіньютонівський метод.
def rosenbrock(point):
    x = point[0]
    y = point[1]

    # Повертаємо обчислене значення, яке використає наступний крок алгоритму або перевірки.
    return (
        100.0 * (y - x ** 2) ** 2
        + (1.0 - x) ** 2
    )


# Описуємо аналітичний градієнт функції Розенброка для BFGS.
def rosenbrock_gradient(point):
    x = point[0]
    y = point[1]

    # Повертаємо обчислене значення, яке використає наступний крок алгоритму або перевірки.
    return np.array([
        -400.0 * x * (y - x ** 2)
        - 2.0 * (1.0 - x),
        200.0 * (y - x ** 2),
    ])


# Задаємо конкретну точку, план або множники, для яких далі виконаємо математичну перевірку.
start = np.array([
    -1.2,
    1.0,
])

# Запускаємо нелінійний розв’язувач із явно заданими функцією, стартом і потрібними похідними або обмеженнями.
result = minimize(
    rosenbrock,
    start,
    jac=rosenbrock_gradient,
    method="BFGS",
    options={
        "gtol": 1e-8,
    },
)

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print(result.x)
print(result.fun)
print(result.success)
print(result.nit)

19. Очікуваний результат

Точка повинна бути близькою до:

[1. 1.]

Значення функції — близьким до нуля.

result.success має бути істинним за коректного завершення.

result.nit показує кількість ітерацій.

Після чисельного розв’язувача нормою градієнта потрібно перевірити окремо.

20. Математична перевірка

Для Розенброка функція є сумою квадратів:

\[ 100(y-x^2)^2\ge0 \]

і:

\[ (1-x)^2\ge0 \]

Тому:

\[ f(x,y)\ge0 \]

Рівність можлива, коли:

\[ x=1 \]

та:

\[ y=x^2=1 \]

Отже, точка \((1,1)\) є глобальним мінімізатор.

Це дає сильний еталон для перевірки BFGS.

Для знайденої точки \(\hat{x}\):

\[ r_g= \|\nabla f(\hat{x})\|_2 \]

Також перевіряємо:

\[ f(\hat{x})\ge0 \]

Для Розенброка точний еталон відомий:

\[ r_x= \left\| \hat{x}- \begin{pmatrix} 1\\ 1 \end{pmatrix} \right\|_2 \]

Це навчальна додаткова перевірка.

21. Чому L-BFGS потрібен для великих задач

Оцінимо пам’ять грубо.

При \(n=10000\) повна щільна матриця містить:

\[ 10^8 \]

чисел.

Якщо одне float64 займає 8 байтів, тільки матриця потребує близько 800 МБ.

При ще більшому \(n\) витрати швидко стають неприйнятними.

L-BFGS зберігає кілька векторів довжини \(n\).

Тому різниця за пам’яттю стає фундаментальною.

Повний BFGS зберігає матрицю розміру:

\[ n\times n \]

Пам’ять зростає приблизно як:

\[ O(n^2) \]

L-BFGS означає BFGS з обмеженою пам’яттю.

Він не зберігає повну матрицю.

Замість цього зберігається невелика кількість останніх пар:

\[ (s_k,y_k) \]

22. Обмежена історія

Параметр \(m\) визначає, скільки останніх пари кривизни використовуються.

Велике \(m\) зберігає більше історії, але збільшує пам’ять і обчислення.

Мале \(m\) економить ресурси, але може давати грубіше наближення кривизни.

На практиці \(m\) вибирають помірним.

Готовий чисельний розв’язувач приховує двопрохідна рекурсія, яка обчислює напрям без явної матриці.

Для курсу важливо розуміти саме принцип обмежена пам’ять.

Нехай зберігається \(m\) останніх пар.

Тоді обсяг пам’яті приблизно масштабується як:

\[ O(mn) \]

де \(m\) зазвичай значно менше за \(n\).

Наприклад, при \(m=10\) потрібно зберігати близько кількох десятків векторів довжини \(n\).

Це набагато дешевше за матрицю \(n\times n\) для великого \(n\).

Порівняння пам’яті BFGS і L-BFGS

23. L-BFGS-B і межі змінних

Межі змінних можуть бути різними для кожної координати.

Наприклад:

\[ 0\le x_1\le1 \]

і:

\[ -5\le x_2\le5 \]

У SciPy це задається через bounds.

Після запуск чисельного розв’язувача їх потрібно перевірити незалежно.

Наявність межі змінних змінює логіка зупинки поблизу активної межі.

Тому простий нормою градієнта вже не завжди є єдиною умовою з обмеженнями стаціонарність.

У SciPy часто використовується method="L-BFGS-B".

Літера B означає підтримку простих межі змінних для змінних.

Наприклад:

\[ 0\le x_i\le1 \]

Такий метод зручний для великих гладких задач із коробковими обмеженнями.

Повний аналіз з обмеженнями оптимізація з’явиться пізніше.

Тут достатньо розуміти, що API може поєднувати обмежена пам’ять і межі змінних.

24. Відмінність BFGS та L-BFGS

Ознака	BFGS	L-BFGS
Кривизна	повна матрична наближення	обмежена історія
Пам’ять	приблизно \(O(n^2)\)	приблизно \(O(mn)\)
Малі та середні задачі	дуже зручний	також придатний
Дуже великі задачі	може бути дорогим	практично привабливий
явна матриця Гессе	не потрібна	не потрібна

Обидва методи використовують градієнт.

Інтерпретація, межі та підсумок

25. Типові помилки

Ще одна помилка — очікувати однакову траєкторія BFGS у різних бібліотеках.

Пошук довжини кроку, критерії зупинки та деталі реалізації можуть відрізнятися.

Правильність слід оцінювати за якість розв’язку і математичний нев’язки.

Також не варто використовувати останні цифри мінімізатор як єдиний критерій.

Для задач із кількома рівноцінними розв’язками важливі цільова функція і допустимість.

Типова помилка. BFGS називають методом Ньютона без матриці Гессе. Насправді він будує власне наближення кривизни з історії градієнтів.

Друга помилка — плутають \(s_k\) та \(y_k\).

Третя — ігнорують умова кривизни.

Четверта — BFGS запускається з неправильним градієнт.

П’ята — повний BFGS використовується для дуже великого \(n\) без оцінки пам’яті.

26. Перевірка градієнта залишається обов’язковою

BFGS сильно залежить від різниць градієнтів.

Якщо градієнт має систематичну помилку, наближення кривизни також стає неправильною.

Тому чисельний перевірка градієнта особливо важливий.

Перед довгим запуском варто перевірити кілька точок.

Малий нев’язка між аналітичним та чисельним градієнтом значно підвищує довіру до чисельного розв’язувача.

27. Чому статус методу все одно потрібно читати

Квазіньютонівський чисельний розв’язувач може завершитися через числовий допуск, пошук довжини кроку невдале завершення або іншу чисельну причину.

Тому фінальний звіт повинен містити:

STATUS
X
OBJECTIVE
GRAD_NORM
ITERATIONS

За наявності межі змінних додається їх перевірка.

Одне число цільова функція не описує якість завершення.

28. Практичний вибір

У навчальній послідовності методи можна порівняти так.

Градієнтний спуск має найпростішу ітерацію та найменше вимоги до похідних.

метод Ньютона використовує повну кривизна інформація і дорогий розв’язання лінійної системи.

BFGS наближає кривизна з історії градієнт.

L-BFGS жертвує частиною історії заради масштабованості.

Ця схема допомагає обирати метод за розмірністю та доступністю похідних.

Для невеликої гладкої задачі з доступною матрицею Гессе метод Ньютона може бути дуже ефективним.

Якщо матриця Гессе дорога, BFGS є сильним практичним вибором.

Для великої кількості змінних L-BFGS економить пам’ять.

Для задач із простими межі змінних часто використовують L-BFGS-B.

Вибір методу повинен враховувати розмірність, доступність похідних і структуру обмежень.

28.1. BFGS і метод Ньютона

Метод Ньютона отримує кривизну безпосередньо з матриці Гессе.

BFGS відновлює наближення поступово.

На початку BFGS може поводитися ближче до градієнтний спуск.

Після кількох якісних пар кривизни напрями краще враховують локальну геометрію.

Тому BFGS часто називають квазіньютонівський метод.

Його перевага полягає в меншій витрати на обчислення похідних.

28.2. Що означає обмежена пам’ять на практиці

L-BFGS не зберігає старі пари безмежно.

Коли історія повна, найстаріша пара видаляється.

Алгоритм використовує тільки останні \(m\) спостережень.

Тому використання пам’яті залишається контрольованим навіть при довгому запуску оптимізації.

Це робить метод придатним для задач із сотнями тисяч параметрів, якщо цільова функція і градієнт можна ефективно обчислювати.

28.3. Перевірка пари кривизни

У власній реалізації можна логувати:

S_NORM
Y_NORM
Y_DOT_S

Якщо \(y^Ts\) часто дуже мале або від’ємний, потрібно перевірити градієнт, пошук довжини кроку або модель геометрія.

Такі діагностика допомагають відрізнити задача у цільова функція від задача у оновлення.

28.4. Підсумковий вибір між чотирма методами

Градієнтний спуск має найпростішу структуру.

метод Ньютона має найповнішу локальну інформацію про кривизну.

BFGS підходить для задач помірного розміру зі щільними матрицями без явної матриці Гессе.

L-BFGS підходить для великомасштабної гладкої оптимізації.

Усі методи потребують перевіреної цільової функції, похідних, критерії зупинки та статус.

28.5. Коли BFGS не є найкращим вибором

Якщо градієнт дуже шумний, різниці \(y_k\) також стають шумними.

Тоді наближення кривизни може бути нестабільною.

Для nonгладкий цільова функція класичний BFGS також втрачає частину теоретичних властивостей.

Якщо точна матриця Гессе дешева і розмірність мала, метод Ньютона може бути кращим.

Тому BFGS є сильним універсальний метод для гладких задач, але вибір завжди залежить від структури задачі.

28.6. Фінальна перевірка

Після BFGS або L-BFGS потрібно перевірити:

статус чисельного розв’язувача;
цільова функція;
нормою градієнта;
межі змінних, якщо вони є;
скінченні значення;
ітерації і функція обчислення.

Для навчальної Розенброка функція додатково доступна відстань до \((1,1)\).

28.7. Контроль відтворюваності

Для повторення запуску BFGS потрібно зберегти стартову точку, метод, числовий допуск для градієнта та параметри пошуку довжини кроку.

Для L-BFGS-B додаються межі змінних.

Якщо результати порівнюються між версіями бібліотеки, важливо фіксувати версію SciPy.

Це дозволяє відділити математичну різницю від деталі реалізації.

28.8. Практична самоперевірка

Потрібно розрізняти Ньютона, BFGS і L-BFGS за джерелом кривизна інформація та витрати пам’яті.

Також потрібно вміти обчислити \(s_k\), \(y_k\), перевірити \(y_k^Ts_k\) і прочитати BFGS результат чисельного розв’язувача.

Для L-BFGS потрібно розуміти обмежену історію як спосіб зменшення витрати пам’яті.

28.9. Контрольна думка

Квазіньютонівський метод не звільняє від перевірки похідних. Навпаки, BFGS будує наближення кривизни саме зі змін градієнта, тому помилка в градієнт накопичується в напрямах наступних ітерацій.

28.10. Практична інтерпретація

BFGS навчається кривизні під час руху. Кожна успішна ітерація додає нову інформацію через пара кроку та зміни градієнт. L-BFGS зберігає лише найсвіжішу частину цієї історії, щоб контролювати витрати пам’яті.

28.11. Контрольний висновок

Для BFGS потрібно розуміти роль історія градієнтів, а для L-BFGS — обмеженої історія. Обидва методи завершуються тим самим математичний перевірка: цільова функція, нев’язка стаціонарності і статус.

28.12. Фінальна примітка

Квазіньютонівський результат потребує такого самого математичного контролю, як інші чисельні методи.

Інтерактивна самоперевірка лекції

Пройдіть 10 коротких питань. Після кожної відповіді ви побачите пояснення, а за потреби — підказку й повний розбір.

29. Підсумок

Квазіньютонівські методи відновлюють інформацію про кривизну зі змін точки та градієнта. Вектор \(s_k=x_{k+1}-x_k\) описує фактичний крок, а \(y_k=\nabla f(x_{k+1})-\nabla f(x_k)\) показує зміну локального нахилу. Умова січної пов’язує ці вектори з матричним наближенням кривизни, а умова \(y_k^Ts_k>0\) підтримує коректну геометрію оновлення.

BFGS зберігає повне щільне наближення, тому витрати пам’яті ростуть приблизно як \(O(n^2)\). L-BFGS використовує лише обмежену історію останніх пар \((s_k,y_k)\) і краще масштабується для великої кількості змінних. Для простих меж змінних практичним варіантом є L-BFGS-B.

Надійність BFGS починається з правильно перевіреного градієнта та коректного пошуку довжини кроку. Після розв’язання контролюють статус, ціль, фінальну точку й норму градієнта. Ці методи завершують блок локальних алгоритмів і підводять до структурної теми опуклості, яка дозволяє пов’язати локальні умови з глобальними висновками.