Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно (BFGS) (англ. Broyden — Fletcher — Goldfarb — Shanno algorithm) — итерационный метод численной оптимизации, предназначенный для нахождения локального максимума/минимума нелинейного функционала без ограничений.

BFGS — один из наиболее широко применяемых квазиньютоновских методов. В квазиньютоновских методах не вычисляется напрямую гессиан функции. Вместо этого гессиан оценивается приближенно, исходя из сделанных до этого шагов. Также существуют модификация данного метода с ограниченным использованием памяти (L-BFGS), который предназначен для решения нелинейных задач с большим количеством неизвестных, а также модификация с ограниченным использованием памяти в многомерном кубе (L-BFGS-B).

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

Пусть решается задача оптимизации функционала:

Методы второго порядка решают данную задачу итерационно, с помощью разложения функции в полином второй степени:

где  — гессиан функционала в точке . Зачастую вычисление гессиана трудоемки, поэтому BFGS алгоритм вместо настоящего значения вычисляет приближенное значение , после чего находит минимум полученной квадратичной задачи:

Как правило, после этого осуществляется поиск вдоль данного направления точки, для которой выполняются условия Вольфе.

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

где  — единичная матрица,  — шаг алгоритма на итерации,  — изменение градиента на итерации.

Поскольку вычисление обратной матрицы вычислительно сложно, вместо того, чтобы вычислять , обновляется обратная к матрица :

где .

дано
инициализировать

while
    найти направление
    вычислить , удовлетворяет условиям Вольфе
    обозначить и
    вычислить
   
end

Литература

[править | править код]
  1. Nocedal, Jeorge; Wright, Stephen J. Numerical Optimization. — 2nd edition. — USA: Springer, 2006. — ISBN 978-0-387-30303-1.
  2. Avriel, Mordecai. Nonlinear Programming: Analysis and Methods. — Dover Publishing, 2003. — ISBN 0-486-43227-0.