Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно
Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно (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
- Пожарный аэродромный автомобиль
- Беэ, Иштван
- Асеев, Владимир Григорьевич
- Литостратиграфическое и структурное расчленение докембрия
- Докембрий - фундамент Варисцийской мобильной зоны
- Малые элементы в качестве индикаторов первичной природы, метаморфических пород и руд
- Главные эпохи образования рудоносных формаций и стратиформного оруденения в Забайкалье и Прибайкалье
- Эволюция корообразования на Украинском кристаллическом щите и ее влияние на осадконакопление в докембрии
- Вопросы химизма позднеархейской коры выветривания Курской магнитной аномалии
- Делта (округ, Колорадо)