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

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

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

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

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

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

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

 \arg\min_x f(x).

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

 f(x_k + p) = f(x_k) + \nabla f^T(x_k) p + \frac{1}{2} p^T H(x_k) p,

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

p_k = - B_k^{-1}\nabla f(x_k).

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

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

B_{k + 1} = B_k - \frac{B_k s_k s_k^T B_k}{s_k^T B_k s_k} + \frac{y_k y_k^T}{y_k^T s_k},

где I — единичная матрица, s_k = x_{k + 1} - x_k — шаг алгоритма на итерации, y_k = \nabla f_{k + 1} - \nabla f_{k} — изменение градиента на итерации.

Поскольку вычисление обратной матрицы вычислительно сложно, вместо того, чтобы вычислять B_k, обновляется обратная  B_k матрица C_k = B_k^{-1}:

 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.

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

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