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

Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно (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}^{T}}{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}^{-1}$, обновляется обратная к $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},$

где $\rho _{k}={\frac {1}{y_{k}^{T}s_{k}}}$.

Алгоритм

дано $\varepsilon ,\;x_{0}$
инициализировать $C_{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.