Математика / Численная оптимизация

Обновление BFGS для обратной матрицы Гессе

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

Опубликовано: 1 ноября 2026 г.Обновлено: 1 ноября 2026 г.

Оптимизация и исследование операций Страницы с задачами и решениями Есть историческая справка Диагностика условий

Формула

H_{k+1}=(I-\rho sy^T)H_k(I-\rho ys^T)+\rho ss^T,\quad\rho=(y^Ts)^{-1}

Схема Одномерное секущее условие BFGS

При положительном s·y обновлённое H положительно; в примере y=4 даёт H=0,5.

Обозначения

$x$: аргумент, состояние или вектор данных конкретной задачи, единицы исходной модели
$n,k,i,j$: целые индексы узла, шага либо компоненты, безразмерные
$ε / err$: допуск или оценка вычислительной ошибки, если она используется, единицы результата

Условия применения

Векторы s и y должны иметь одинаковую размерность, а знаменатель y^T s не должен быть нулём; для сохранения положительной определённости обычно требуют y^T s>0. Матрица H_0 должна быть симметричной, вычисления выполняют без смешения H и обратного Гессиана.

Ограничения

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

Подробное объяснение

BFGS обновляет H, приближение обратной матрицы Гессе, чтобы оно выполнило секущее условие H_{k+1}y=s. Так алгоритм извлекает информацию о кривизне из уже вычисленных градиентов.

Скаляр ρ существует лишь при y^Ts≠0. В задачах минимизации с корректным линейным поиском обычно стремятся к y^Ts>0: это помогает сохранить положительную определённость H.

В одном измерении формула становится особенно понятной: новое H равно s/y, то есть обратной наблюдаемой кривизне. Это проверяет как знак, так и множитель ρ.

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

В одном измерении I−ρsy=1−(1/8)·2·4=0, поэтому первый член обновления исчезает. Второй равен ρs²=(1/8)·4=0,5. Этот расчёт одновременно проверяет секущее условие H_1y=0,5·4=2=s.

Четыре независимые работы Бройдена, Флетчера, Голдфарба и Шанно в 1970 году привели к формуле, получившей аббревиатуру BFGS. Важная практическая линия продолжилась ограниченной по памяти версией L-BFGS, популярной для задач с очень многими переменными.

Как пользоваться формулой

Выпишите H_{k+1}=(I-\rho sy^T)H_k(I-\rho ys^T)+\rho ss^T,\quad\rho=(y^Ts)^{-1} и отметьте искомую величину; не заменяйте её одноимённым параметром из другой модели.
Подготовьте данные в требуемой форме: проверьте индексы, знак, область аргумента, нормировку либо размерность.
Выполните первое задание по действиям и сохраните промежуточные значения каждого коэффициента, отношения или суммы.
Проверьте результат естественным способом: симметрией, точным частным случаем, невязкой или исходным ограничением.
Разберите второе задание: изменённые данные показывают границу применимости и предупреждают типичную ошибку метода.

Историческая справка

Алгоритм BFGS назван по Чарльзу Бройдену, Роджеру Флетчеру, Дональду Голдфарбу и Дэвиду Шанно; связанные работы появились в 1970 году. Это важная веха квазиньютоновских методов: вместо явных вторых производных обновляется приближение обратного Гессиана по разности точек s и градиентов y. Условие y^Ts>0 играет центральную роль, поскольку поддерживает положительную определённость при подходящих предпосылках. В вычислительной практике особенно известна ограниченная по памяти модификация L-BFGS.

Историческая линия формулы

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

Пример

В одномерном случае H_0=1, s=2, y=4, ρ=1/8. Формула даёт H_1=(1−ρsy)²H_0+ρs²=0+4/8=0,5, то есть обратную кривизну 1/2. В одном измерении I−ρsy=1−(1/8)·2·4=0, поэтому первый член обновления исчезает. Второй равен ρs²=(1/8)·4=0,5. Этот расчёт одновременно проверяет секущее условие H_1y=0,5·4=2=s. BFGS обновляет H, приближение обратной матрицы Гессе, чтобы оно выполнило секущее условие H_{k+1}y=s. Так алгоритм извлекает информацию о кривизне из уже вычисленных градиентов. Скаляр ρ существует лишь при y^Ts≠0. В задачах минимизации с корректным линейным поиском обычно стремятся к y^Ts>0: это помогает сохранить положительную определённость H.

Частая ошибка

Нельзя вычислять ρ как 1/(s^Ts): в BFGS нужен y^Ts. Нельзя игнорировать знак y^Ts. Не следует хранить полную H в огромной задаче, если требуется L-BFGS. И не надо называть H настоящей обратной матрицей Гессе без проверки квадратичности функции. В разборе «Обновление BFGS для обратной матрицы Гессе» проверяют именно обозначения и условия данной записи.

Практика

Задачи с решением

Одномерное обновление BFGS

Условие. В одномерном BFGS возьмите s=1, y=5, H_0=1.

Решение. ρ=(ys)⁻¹=1/5=0,2. Первый множитель 1−ρsy=0, поэтому H_1=ρs²=0,2.

Ответ. H_1=0,2.

Обновление при отрицательных s и y

Условие. В одномерном BFGS возьмите s=−2, y=−6, H_0=1.

Решение. ys=12, ρ=1/12. Первый множитель снова нуль; H_1=ρs²=4/12=1/3.

Ответ. H_1=1/3.

Дополнительные источники

https://doi.org/10.1093/comjnl/13.3.317
https://doi.org/10.1090/S0025-5718-1970-0274029-X

Связанные формулы

Математика

Отражение в методе Нелдера—Мида

$x_r=\bar x+\alpha(\bar x-x_w),\quad\alpha=1$

Отражение в методе Нелдера—Мида даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.

Математика

Условия Каруша—Куна—Таккера: комплементарная нежёсткость

$\lambda_i g_i(x)=0,\quad\lambda_i\ge0,\quad g_i(x)\le0$

Условия Каруша—Куна—Таккера: дополнительная нежёсткость даёт не только вычислительную запись, но и правило, какие данные определяют результат и как проверить его численно. Формула применяется к строго указанной модели; ниже разобраны предпосылки, два решённых задания и границы корректной интерпретации.

Математика

Симплекс-метод: правило минимального отношения

$\theta^*=\min_{i:a_{ij}>0}\frac{b_i}{a_{ij}}$

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