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

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

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

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

Описание

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

$\arg \underset{x}{\min }f(x).$

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

$f(x_k+p)=f(x_k)+\mathrm{\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}\mathrm{\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=\mathrm{\nabla }{f}_{k+1}-\mathrm{\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}$.

Алгоритм

дано $\epsilon ,x_0$
инициализировать $C_0$
$k=0$
while $||\mathrm{\nabla }{f}_k||>\epsilon$
    найти направление $p_k=-C_k\mathrm{\nabla }{f}_k$
    вычислить $x_{k+1}=x_k+{\alpha }_k{p}_k$, ${\alpha }_k$ удовлетворяет условиям Вольфе
    обозначить $s_k=x_{k+1}-x_k$ и $y_k=\mathrm{\nabla }{f}_{k+1}-\mathrm{\nabla }{f}_k$
    вычислить $C_{k+1}$
    $k=k+1$
end

Литература

1. Шаблон:Книга
2. Шаблон:Книга