24.03.2021

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


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

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

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

Описание

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

arg ⁡ min x f ( x ) . {displaystyle 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 , {displaystyle f(x_{k}+p)=f(x_{k})+ abla f^{T}(x_{k})p+{frac {1}{2}}p^{T}H(x_{k})p,}

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

p k = − B k − 1 ∇ f ( x k ) . {displaystyle p_{k}=-B_{k}^{-1} abla f(x_{k}).}

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

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

B k + 1 = B k − B k s k s k T B k s k T B k s k + y k y k T y k T s 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}}},}

где I {displaystyle I} — единичная матрица, s k = x k + 1 − x k {displaystyle s_{k}=x_{k+1}-x_{k}} — шаг алгоритма на итерации, y k = ∇ f k + 1 − ∇ f k {displaystyle y_{k}= abla f_{k+1}- abla f_{k}} — изменение градиента на итерации.

Поскольку вычисление обратной матрицы вычислительно сложно, вместо того, чтобы вычислять B k − 1 {displaystyle B_{k}^{-1}} , обновляется обратная к B k {displaystyle B_{k}} матрица C k = B k − 1 {displaystyle 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 , {displaystyle C_{k+1}=(I- ho _{k}s_{k}y_{k}^{T})C_{k}(I- ho _{k}y_{k}s_{k}^{T})+ ho _{k}s_{k}s_{k}^{T},}

где ρ k = 1 y k T s k {displaystyle ho _{k}={frac {1}{y_{k}^{T}s_{k}}}} .

Алгоритм

дано ε , x 0 {displaystyle varepsilon ,;x_{0}}
инициализировать C 0 {displaystyle C_{0}}
k = 0 {displaystyle k=0}
while | | ∇ f k | | > ε {displaystyle || abla f_{k}||>varepsilon }
    найти направление p k = − C k ∇ f k {displaystyle p_{k}=-C_{k} abla f_{k}}
    вычислить x k + 1 = x k + α k p k {displaystyle x_{k+1}=x_{k}+alpha _{k}p_{k}} , α k {displaystyle alpha _{k}} удовлетворяет условиям Вольфе
    обозначить s k = x k + 1 − x k {displaystyle s_{k}=x_{k+1}-x_{k}} и y k = ∇ f k + 1 − ∇ f k {displaystyle y_{k}= abla f_{k+1}- abla f_{k}}
    вычислить C k + 1 {displaystyle C_{k+1}}
    k = k + 1 {displaystyle k=k+1}
end






Яндекс.Метрика