BFGS

Материал из MachineLearning.

Версия от 23:22, 9 июля 2026; Iurii Patrakov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Статья написана с использованием LLM GPT-5.5 и проверена участником Iurii Patrakov 03:22, 10 июля 2026 (MSD)

BFGS — это квазиньютоновский метод безусловной гладкой численной оптимизации, который на каждой итерации строит приближение к матрице Гессе или к обратной матрице Гессе, используя только значения градиента. Название происходит от фамилий Чарльза Бройдена, Роджера Флетчера, Дональда Гольдфарба и Дэвида Шанно, независимо предложивших близкие формулы обновления в 1970 году.

Метод применяется для решения задач вида

$\min_{x \in \mathbb{R}^n} f(x),$

где $f$ — дифференцируемая целевая функция. В отличие от метода Ньютона, BFGS не требует явного вычисления и обращения матрицы вторых производных. Вместо этого он постепенно накапливает информацию о кривизне функции по разностям последовательных точек и градиентов. Поэтому BFGS занимает промежуточное положение между простыми градиентными методами и полноценными методами второго порядка.

Содержание

1 Идея метода
2 Алгоритм
3 Исторический контекст
4 Свойства сходимости
5 Значение для искусственного интеллекта и машинного обучения
6 Связь с L-BFGS
7 Применения
8 Ограничения
9 Практические замечания
10 Современные направления
11 См. также
12 Литература
13 Ссылки

Идея метода

В методе Ньютона направление поиска определяется системой

$\nabla^2 f(x_k) p_k = - \nabla f(x_k),$

где $\nabla^2 f(x_k)$ — матрица Гессе. Это направление обычно лучше учитывает геометрию функции, чем антиградиент, но вычисление и обращение матрицы Гессе может быть слишком дорогим или неустойчивым.

BFGS заменяет истинную матрицу Гессе её приближением $B_k$ :

$B_k p_k = - \nabla f(x_k).$

После выбора длины шага $\alpha_k$ новая точка задаётся как

$x_{k+1}=x_k+\alpha_k p_k.$

Обозначим

$s_k = x_{k+1}-x_k,$

$y_k = \nabla f(x_{k+1})-\nabla f(x_k).$

Квазиньютоновское условие требует, чтобы новая матрица $B_{k+1}$ согласовывалась с наблюдаемым изменением градиента:

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

Это условие является многомерным аналогом секущей в одномерном методе. Одного условия недостаточно, чтобы однозначно определить всю матрицу, поэтому BFGS выбирает симметричное обновление ранга два, которое сохраняет положительную определённость при выполнении условия кривизны

$s_k^\top y_k > 0.$

Стандартная формула обновления приближения к матрице Гессе имеет вид:

$B_{k+1} = B_k + \frac{y_k y_k^\top}{y_k^\top s_k} - \frac{B_k s_k s_k^\top B_k}{s_k^\top B_k s_k}.$

На практике часто хранят не $B_k$ , а приближение $H_k \approx B_k^{-1}$ к обратной матрице Гессе. Тогда направление находится без решения линейной системы:

$p_k = -H_k \nabla f(x_k).$

Обновление обратной матрицы записывается так:

$H_{k+1}=(I-\rho_k s_k y_k^T)H_k(I-\rho_k y_k s_k^T)+\rho_k s_k s_k^T,\qquad \rho_k=(y_k^T s_k)^{-1}.$

Алгоритм

Типичная схема BFGS:

выбрать начальную точку $x_0$ и начальное приближение $H_0$ , часто $H_0=I$ ;
вычислить градиент $g_k=\nabla f(x_k)$ ;
найти направление $p_k=-H_k g_k$ ;
выполнить одномерный поиск длины шага $\alpha_k$ , обычно с условиями Вольфе;
положить $x_{k+1}=x_k+\alpha_k p_k$ ;
вычислить $s_k=x_{k+1}-x_k$ и $y_k=\nabla f(x_{k+1})-\nabla f(x_k)$ ;
если $y_k^\top s_k>0$ , обновить $H_k$ по формуле BFGS;
остановиться, если норма градиента, изменение функции или изменение точки стали достаточно малы.

Для новичка BFGS можно понимать как «градиентный спуск с обучающейся системой координат»: метод не просто идёт против градиента, а постепенно выясняет, в каких направлениях функция меняется резко, а в каких полого, и масштабирует шаги соответственно.

Исторический контекст

BFGS возник в развитии методов переменной метрики и квазиньютоновских методов. Ранним важным предшественником был метод Дэвидона — Флетчера — Пауэлла. В 1970 году Бройден, Флетчер, Гольдфарб и Шанно независимо опубликовали работы, приведшие к формуле, которая стала известна как BFGS. Эта формула оказалась особенно удачной: она сочетала простоту, сохранение симметрии, сохранение положительной определённости и хорошие практические свойства сходимости.

С тех пор BFGS стал одним из стандартных методов гладкой оптимизации. Он вошёл в учебники по численной оптимизации, библиотеки научных вычислений и прикладные системы оценки параметров.

Свойства сходимости

Для строго выпуклых достаточно гладких функций при корректном одномерном поиске BFGS обладает глобальной сходимостью к минимуму. В окрестности решения метод часто демонстрирует сверхлинейную сходимость: ошибка уменьшается быстрее, чем при любом фиксированном линейном коэффициенте, хотя метод не вычисляет настоящую матрицу Гессе.

Важные условия хорошей работы:

градиенты должны быть достаточно точными;
одномерный поиск должен поддерживать условие кривизны $s_k^\top y_k>0$ ;
целевая функция должна быть достаточно гладкой в области поиска;
начальное приближение $H_0$ должно иметь разумный масштаб.

На квадратичных функциях с положительно определённой матрицей Гессе BFGS тесно связан с методом сопряжённых градиентов: при точном одномерном поиске направления обладают сопряжённостью, а решение может быть найдено за конечное число шагов в точной арифметике.

Значение для искусственного интеллекта и машинного обучения

В машинном обучении многие задачи сводятся к минимизации функции потерь:

$\min_\theta L(\theta),$

где $\theta$ — параметры модели. BFGS важен потому, что использует информацию о кривизне без явного построения полной матрицы вторых производных. Это особенно полезно в задачах, где градиент доступен, но простой градиентный спуск сходится медленно из-за плохой обусловленности.

Типичные применения:

оценивание параметров статистических моделей методом максимального правдоподобия;
обучение моделей с умеренным числом параметров;
логистическая регрессия;
условные случайные поля;
оптимизация гладких регуляризованных функций потерь;
настройка параметров в научных моделях и задачах обратного моделирования;
локальная дооптимизация после более грубых методов поиска.

Для больших нейронных сетей классический BFGS обычно непрактичен, потому что хранит плотную матрицу размера $n \times n$ . Если параметров миллионы или миллиарды, это невозможно по памяти. Поэтому в глубоком обучении чаще применяются стохастические методы первого порядка: стохастический градиентный спуск, Adam, RMSProp. Однако идеи BFGS сохраняют значение: они лежат в основе методов с ограниченной памятью, стохастических квазиньютоновских методов и гибридных алгоритмов, которые пытаются использовать кривизну в больших моделях.

Связь с L-BFGS

L-BFGS — вариант BFGS с ограниченной памятью. Он не хранит всю матрицу $H_k$ , а использует последние пары $(s_i,y_i)$ . Это снижает потребление памяти с $O(n^2)$ до $O(mn)$ , где $m$ — небольшое число сохранённых пар, обычно от 5 до 50.

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

Применения

BFGS и его варианты используются в следующих областях:

численная оптимизация гладких функций без ограничений;
статистическое оценивание и максимизация правдоподобия;
байесовская апостериорная оптимизация;
обучение линейных и обобщённых линейных моделей;
оптимизация гиперпараметров в гладких постановках;
вычислительная физика, химия и биоинформатика;
эконометрика и оценивание структурных моделей;
подзадачи в методах последовательного квадратичного программирования.

В прикладных пакетах BFGS доступен, например, в SciPy, R, GNU Scientific Library, Julia Optim.jl и других системах научных вычислений.

Ограничения

Несмотря на надёжность, BFGS не является универсальным методом.

Основные ограничения:

память $O(n^2)$ делает классический вариант непригодным для очень больших моделей;
метод предполагает гладкость функции и наличие градиента;
шумные градиенты могут портить оценку кривизны;
на невыпуклых функциях матрица кривизны может перестать быть положительно определённой;
качество работы сильно зависит от одномерного поиска;
метод плохо подходит для негладких задач, например с регуляризацией $L_1$ , без специальных модификаций;
при седловых точках и плоских областях поведение может быть менее предсказуемым, чем в выпуклом случае.

В машинном обучении особенно важна проблема стохастического шума. Если $y_k$ вычисляется по разным мини-выборкам, оно может отражать не кривизну функции, а шум выборки. Поэтому прямое применение классического BFGS к большим стохастическим задачам обычно не даёт ожидаемой устойчивости.

Практические замечания

На практике BFGS хорошо работает, когда:

число переменных не слишком велико;
функция гладкая и детерминированная;
градиент вычисляется точно или с малой ошибкой;
начальная точка находится не слишком далеко от разумной области;
одномерный поиск реализован устойчиво.

Если задача плохо масштабирована, полезно нормировать признаки или параметры. Если разные координаты имеют сильно разные масштабы, BFGS всё равно может адаптироваться, но первые итерации будут менее эффективными.

Для невыпуклых задач применяют модификации: демпфированное обновление BFGS, пропуск обновления при плохом $s_k^\top y_k$ , регуляризацию матрицы или доверительные области. Эти приёмы помогают сохранить устойчивость приближения к кривизне.

Современные направления

Современные исследования вокруг BFGS развиваются в нескольких направлениях:

стохастические квазиньютоновские методы для больших выборок;
варианты с ограниченной памятью для высокоразмерных моделей;
демпфированные и регуляризованные обновления для невыпуклой оптимизации;
распределённые и децентрализованные версии BFGS;
методы, устойчивые к шуму функции и градиента;
компактные представления квазиньютоновских матриц;
сочетание квазиньютоновских идей с автоматическим дифференцированием;
применение в гибридных схемах обучения нейронных сетей.

Для специалистов BFGS интересен не только как готовый алгоритм, но и как пример удачного компромисса между геометрией второго порядка и вычислительной стоимостью. Его формула обновления показывает, как из локальных наблюдений о градиенте можно строить глобально полезную метрику пространства параметров.

См. также

Литература

Broyden C. G. The convergence of a class of double-rank minimization algorithms // Journal of the Institute of Mathematics and Its Applications. 1970. Vol. 6. P. 76–90.
Fletcher R. A new approach to variable metric algorithms // The Computer Journal. 1970. Vol. 13, No. 3. P. 317–322.
Goldfarb D. A family of variable metric updates derived by variational means // Mathematics of Computation. 1970. Vol. 24, No. 109. P. 23–26.
Shanno D. F. Conditioning of quasi-Newton methods for function minimization // Mathematics of Computation. 1970. Vol. 24, No. 111. P. 647–656.
Nocedal J., Wright S. J. Numerical Optimization. 2nd ed. Springer, 2006.
Fletcher R. Practical Methods of Optimization. 2nd ed. Wiley, 1987.
Dennis J. E., Schnabel R. B. Numerical Methods for Unconstrained Optimization and Nonlinear Equations. SIAM, 1996.
Liu D. C., Nocedal J. On the limited memory BFGS method for large scale optimization // Mathematical Programming. 1989. Vol. 45. P. 503–528.
Byrd R. H., Hansen S. L., Nocedal J., Singer Y. A stochastic quasi-Newton method for large-scale optimization // SIAM Journal on Optimization. 2016. Vol. 26, No. 2. P. 1008–1031.

Ссылки

Источник — «http://machinelearning.ru/wiki/index.php?title=BFGS»

Категории: Методы оптимизации | Машинное обучение | Численные методы | Искусственный интеллект