Interested Article - Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно
- 2021-04-04
- 1
Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно (BFGS) ( англ. Broyden — Fletcher — Goldfarb — Shanno algorithm ) — итерационный метод численной оптимизации , предназначенный для нахождения локального максимума/минимума нелинейного функционала без ограничений.
BFGS — один из наиболее широко применяемых квазиньютоновских методов . В квазиньютоновских методах не вычисляется напрямую гессиан функции. Вместо этого гессиан оценивается приближенно, исходя из сделанных до этого шагов. Также существуют модификация данного метода с ограниченным использованием памяти ( ), который предназначен для решения нелинейных задач с большим количеством неизвестных, а также модификация с ограниченным использованием памяти в многомерном кубе ( ).
Данный метод находит минимум любой дважды непрерывно дифференцируемой выпуклой функции. Несмотря на эти теоретические ограничения, как показывает опыт, BFGS хорошо справляется и с невыпуклыми функциями.
Описание
Пусть решается задача оптимизации функционала:
Методы второго порядка решают данную задачу итерационно, с помощью разложения функции в полином второй степени:
где — гессиан функционала в точке . Зачастую вычисление гессиана трудоемки, поэтому BFGS алгоритм вместо настоящего значения вычисляет приближенное значение , после чего находит минимум полученной квадратичной задачи:
Как правило, после этого осуществляется поиск вдоль данного направления точки, для которой выполняются условия Вольфе .
В качестве начального приближения гессиана можно брать любую невырожденную, хорошо обусловленную матрицу. Часто берут единичную матрицу . Приближенное значение гессиана на следующем шаге вычисляется по формуле:
где — единичная матрица, — шаг алгоритма на итерации, — изменение градиента на итерации.
Поскольку вычисление обратной матрицы вычислительно сложно, вместо того, чтобы вычислять , обновляется обратная к матрица :
где .
Алгоритм
дано
инициализировать
while
найти направление
вычислить , удовлетворяет условиям Вольфе
обозначить и
вычислить
end
Литература
- Nocedal, Jeorge; Wright, Stephen J. Numerical Optimization. — 2nd edition. — USA: Springer, 2006. — ISBN 978-0-387-30303-1 .
- Avriel, Mordecai. . — Dover Publishing, 2003. — ISBN 0-486-43227-0 .
- 2021-04-04
- 1