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

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

Текущая версия

Статья написана с использованием LLM DeepSeek-V3 и проверена участником Д. Николаев 16:50, 3 июля 2026 (MSD)

Квазиньютоновские методы (англ. quasi-Newton methods) — класс итерационных методов безусловной оптимизации, предназначенных для решения задачи

где — дважды непрерывно дифференцируемая функция. В основе методов лежит построение последовательности приближений к матрице Гессе (либо к обратной к ней) с использованием только информации о градиентах функции, что позволяет избежать прямого вычисления и обращения гессиана.

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

История

Первый квазиньютоновский метод был разработан физиком Уильямом Дэвидоном (William C. Davidon) в середине 1950-х годов в Аргоннской национальной лаборатории. Дэвидон работал над длительными оптимизационными расчётами, которые не удавалось завершить из-за низкой надёжности и производительности компьютеров того времени — сбои происходили до окончания вычислений. Предложенный им метод позволял ускорить сходимость, не требуя вычисления вторых производных. Статья Дэвидона не была принята к публикации и долгое время оставалась техническим отчётом ^[1].

В 1963 году Роджер Флетчер (Roger Fletcher) и Майкл Пауэлл (Michael J. D. Powell) независимо изучили работу Дэвидона, доказали, что предложенный алгоритм значительно эффективнее и надёжнее существовавших методов, и опубликовали его в усовершенствованном виде ^[1]. Этот алгоритм получил название DFP (Davidon–Fletcher–Powell).

В 1965 году Чарльз Бройден (Charles G. Broyden) предложил другой подход к обновлению приближения гессиана ^[1]. В 1970 году независимо друг от друга Бройден, Флетчер, Дональд Гольдфарб (Donald Goldfarb) и Дэвид Шенно (David F. Shanno) разработали BFGS — формулу обновления, которая оказалась наиболее эффективной на практике и в настоящее время является стандартом в этой области ^[1].

Математическая формулировка

Постановка задачи

Пусть решается задача безусловной минимизации дифференцируемой функции . Метод Ньютона использует итерационную схему

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

Квазиньютоновские методы обходят эти ограничения, заменяя точный гессиан его приближением (либо приближением ), которое строится итеративно на основе градиентов, вычисленных в предыдущих точках.

Квазиньютоновское условие

На каждом шаге метода строится квадратичная модель целевой функции в окрестности текущей точки:

Направление спуска выбирается как

После перехода в новую точку , где , требуется, чтобы новое приближение удовлетворяло так называемому квазиньютоновскому условию (или условию секущей):

где

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

В терминах приближения обратного гессиана квазиньютоновское условие принимает вид:

Обновление приближения

Матрица (или ) строится как минимальная модификация предыдущей матрицы, удовлетворяющая квазиньютоновскому условию. В общем виде обновление записывается как:

где — матрица поправки. Различные методы отличаются выбором этой поправки.

Основные алгоритмы

Метод Дэвидона — Флетчера — Пауэлла (DFP)

Метод DFP был первым широко распространённым квазиньютоновским методом. Он обновляет приближение обратного гессиана по формуле:

Эта формула является обновлением ранга 2 (сумма двух матриц ранга 1) и гарантирует положительную определённость , если положительно определена и .

Алгоритм DFP: Выбрать начальную точку и начальную матрицу (или другую положительно определённую). На итерации вычислить направление . Найти длину шага с помощью линейного поиска: . Положить , . Вычислить . Обновить по формуле DFP. Проверить критерий остановки; если не достигнут, перейти к шагу 2.

Метод Бройдена — Флетчера — Гольдфарба — Шенно (BFGS)

Метод BFGS, предложенный независимо четырьмя авторами в 1970 году, является наиболее популярным квазиньютоновским методом. Он обновляет приближение самого гессиана :

Для обратного гессиана эквивалентная формула имеет вид:

Метод BFGS является «двойственным» к DFP в том смысле, что BFGS получается из DFP заменой . На практике BFGS обычно превосходит DFP по устойчивости и скорости сходимости ^[1].

Алгоритм BFGS аналогичен DFP с заменой шага обновления.

Метод SR1 (Symmetric Rank-One)

Метод SR1 использует обновление ранга 1:

Этот метод не гарантирует положительной определённости и может приводить к неограниченным направлениям спуска, однако в некоторых приложениях (например, при решении систем нелинейных уравнений) он оказывается полезным ^[1].

Метод Бройдена (Broyden's method)

Первоначальный метод Бройдена 1965 года был разработан для решения систем нелинейных уравнений. В применении к оптимизации он даёт несимметричное обновление:

Из-за потери симметрии этот метод реже используется для задач безусловной минимизации, но нашёл применение в задачах с несимметричными системами ^[1].

Семейство Бройдена

Все перечисленные методы могут быть объединены в однопараметрическое семейство Бройдена:

где — скалярный параметр, а

При получается метод BFGS, при — метод DFP.

Сходимость

Для сильно выпуклых дважды дифференцируемых функций с липшицевым гессианом квазиньютоновские методы (DFP и BFGS) обладают сверхлинейной сходимостью ^[1]:

Это означает, что скорость сходимости выше линейной (как у градиентного спуска), но ниже квадратичной (как у метода Ньютона). Вблизи оптимума квазиньютоновские методы асимптотически приближаются к методу Ньютона.

Для невыпуклых функций сходимость может быть менее гарантированной, и на практике часто используют модификации (например, Damped BFGS), обеспечивающие сохранение положительной определённости ^[1].

Модификации для больших задач

L-BFGS (Limited-memory BFGS)

Для задач с большим числом переменных () хранение и обновление полной матрицы размера становится невозможным. Метод L-BFGS (limited-memory BFGS) хранит не саму матрицу, а только последние пар (обычно ). Направление спуска вычисляется с использованием двухпроходного алгоритма, который имитирует умножение на градиент без явного формирования матрицы ^[1].

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

Модификация L-BFGS-B (L-BFGS with Bounds) учитывает ограничения типа .

Диагональные и блочные квазиньютоновские методы

Для задач машинного обучения с очень большим числом параметров (нейронные сети) разработаны диагональные и блочно-диагональные квазиньютоновские приближения, учитывающие структуру задачи (например, послойную структуру нейронной сети) ^[1].

Системные аспекты реализации

При реализации квазиньютоновских методов в распределённых вычислительных системах ключевыми вопросами являются: Параллельное вычисление градиентов — основная вычислительная нагрузка при работе с большими объёмами данных (например, в задачах эмпирического риска). Распределённое хранение и обновление матрицы — для полного BFGS требуется синхронизация матрицы между узлами, что накладывает ограничения на масштабируемость. Асинхронные и стохастические варианты — разработаны стохастические квазиньютоновские методы (SQN, SBFGS) для работы с мини-батчами данных, что особенно актуально в машинном обучении. Проблема потери положительной определённости — при накоплении вычислительных погрешностей в рекуррентных процедурах может нарушаться положительная определённость матрицы ; для её восстановления используются модифицированное разложение Холецкого, регуляризация или демпфирование обновлений ^[1].

Применение в машинном обучении

Квазиньютоновские методы широко применяются в машинном обучении для:

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

• Обучения нейронных сетей — как пакетные методы обучения (batch training), а также в виде стохастических и блочных модификаций.

• Непрерывного обучения — для эффективного обновления моделей на новых данных.

• Двухуровневой оптимизации (bilevel optimization) — для ускорения решения вложенных задач.

• В задачах с большими данными предпочтение часто отдаётся методу L-BFGS благодаря его линейной по размерности памяти сложности ^[1].

См. также

• Метод Ньютона

• Градиентный спуск

• Метод сопряжённых градиентов

• Метод доверительных интервалов

• Стохастическая оптимизация

• Машинное обучение

Литература

• Nocedal, J.; Wright, S. J. Numerical Optimization // Springer Series in Operations Research and Financial Engineering. — 2006.

• Fletcher, R. Practical Methods of Optimization // John Wiley & Sons. — 1987.

• Broyden, C. G. The Convergence of a Class of Double-rank Minimization Algorithms // Journal of the Institute of Mathematics and Its Applications. — 1970. — Т. 6. — С. 76–90.

• Davidon, W. C. Variable Metric Method for Minimization // SIAM Journal on Optimization. — 1991. — Т. 1. — С. 1–17. (переиздание технического отчёта 1959 года)

• Liu, D. C.; Nocedal, J. On the Limited Memory BFGS Method for Large Scale Optimization // Mathematical Programming. — 1989. — Т. 45. — С. 503–528.