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

Материал из in.wiki
Перейти к навигации Перейти к поиску

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

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

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

Описание[править | править код]

Пусть решается задача оптимизации функционала: arg min x f ( x ) . \arg\min_x f(x). Методы второго порядка решают данную задачу итерационно, с помощью разложения функции в полином второй степени: f ( x k + p ) = f ( x k ) + ∇ f T ( x k ) p + 1 2 p T H ( x k ) p , f(x_k + p) = f(x_k) + \nabla f^T(x_k) p + \frac{1}{2} p^T H(x_k) p, где H H  — гессиан функционала f f в точке x x . Зачастую вычисление гессиана трудоемки, поэтому BFGS алгоритм вместо настоящего значения H ( x ) H(x) вычисляет приближенное значение B k B_k , после чего находит минимум полученной квадратичной задачи: p k = − B k − 1 ∇ f ( x k ) . p_k = - B_k^{-1}\nabla f(x_k). Как правило, после этого осуществляется поиск вдоль данного направления точки, для которой выполняются условия Вольфе.

В качестве начального приближения гессиана можно брать любую невырожденную, хорошо обусловленную матрицу. Часто берут единичную матрицу. Приближенное значение гессиана на следующем шаге вычисляется по формуле: B k + 1 = B k − B k s k s k T B k T s k T B k s k + y k y k T y k T s k , B_{k + 1} = B_k - \frac{B_k s_k s_k^T B_k^T}{s_k^T B_k s_k} + \frac{y_k y_k^T}{y_k^T s_k}, где I I  — единичная матрица, s k = x k + 1 − x k s_k = x_{k + 1} - x_k  — шаг алгоритма на итерации, y k = ∇ f k + 1 − ∇ f k y_k = \nabla f_{k + 1} - \nabla f_{k}  — изменение градиента на итерации.

Поскольку вычисление обратной матрицы вычислительно сложно, вместо того, чтобы вычислять B k − 1 B_k^{-1} , обновляется обратная к B k B_k матрица C k = B k − 1 C_k = B_k^{-1} : C k + 1 = ( I − ρ k s k y k T ) C k ( I − ρ k y k s k T ) + ρ k s k s k T , C_{k + 1} = (I - \rho_k s_k y_k^T)C_k(I - \rho_k y_k s_k^T) + \rho_k s_k s_k^T, где ρ k = 1 y k T s k \rho_k = \frac{1}{y_k^T s_k} .

Алгоритм[править | править код]

дано ε , x 0 \varepsilon,\;x_0
инициализировать C 0 C_0
k = 0 k = 0
while | | ∇ f k | | > ε ||\nabla f_k|| > \varepsilon
    найти направление p k = − C k ∇ f k p_k = - C_k \nabla f_k
    вычислить x k + 1 = x k + α k p k x_{k + 1} = x_k + \alpha_k p_k , α k \alpha_k удовлетворяет условиям Вольфе
    обозначить s k = x k + 1 − x k s_k = x_{k + 1} - x_{k} и y k = ∇ f k + 1 − ∇ f k y_k = \nabla f_{k + 1} - \nabla f_k
    вычислить C k + 1 C_{k + 1}
    k = k + 1 k = k + 1
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.

Шаблон:Методы оптимизации

Источник — https://in.wiki/w/index.php?title=Алгоритм_Бройдена_—_Флетчера_—_Гольдфарба_—_Шанно&oldid=1575217