WikiSort.ru - Программирование

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

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

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

Описание

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

${\displaystyle \arg \min _{x}f(x).}$

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

${\displaystyle f(x_{k}+p)=f(x_{k})+\nabla f^{T}(x_{k})p+{\frac {1}{2}}p^{T}H(x_{k})p,}$

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

${\displaystyle p_{k}=-B_{k}^{-1}\nabla f(x_{k}).}$

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

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

${\displaystyle 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}}},}$

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

Поскольку вычисление обратной матрицы вычислительно сложно, вместо того, чтобы вычислять ${\displaystyle B_{k}^{-1}}$ , обновляется обратная к ${\displaystyle B_{k}}$ матрица ${\displaystyle C_{k}=B_{k}^{-1}}$ :

${\displaystyle 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},}$

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

Алгоритм

дано ${\displaystyle \varepsilon ,\;x_{0}}$
инициализировать ${\displaystyle C_{0}}$
${\displaystyle k=0}$
while ${\displaystyle ||\nabla f_{k}||>\varepsilon }$
    найти направление ${\displaystyle p_{k}=-C_{k}\nabla f_{k}}$
    вычислить ${\displaystyle x_{k+1}=x_{k}+\alpha _{k}p_{k}}$ , ${\displaystyle \alpha _{k}}$ удовлетворяет условиям Вольфе
    обозначить ${\displaystyle s_{k}=x_{k+1}-x_{k}}$ и ${\displaystyle y_{k}=\nabla f_{k+1}-\nabla f_{k}}$
    вычислить ${\displaystyle C_{k+1}}$
    ${\displaystyle 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.