トップ > 数理計画用語集 > BFGS 法

数理計画用語集

BFGS 法

読み:びーえふじーえすほう
関連準ニュートン法記憶制限 BFGS 法

準ニュートン法において,目的関数 $f(x)$ の点 $x_k$ におけるヘッセ行列 $\nabla^2 f(x_k)$ に対する近似行列 $B_k$ の更新方法の一つで,1970年にBroyden,Fletcher,Goldfarb,Shannoによって各々独立に発表された手法のことである.具体的に定式化すると,$s_k=x_{k+1}-x_k$,$y_k=\nabla f(x_{k+1})-\nabla f(x_k)$ とおいたとき,

\[ B_{k+1}=B_k+\frac{y_k y_k^\top}{y_k^\top s_k}-\frac{B_k s_k s_k^\top B_k^\top}{s_k^\top B_k s_k} \]

によって,近似行列 $B_{k+1}$ が更新される.なお,この式のことを BFGS 公式という.BFGS 法の主な特徴としては,$B_{k+1}$ が $s_k$ 方向で $\nabla^2 f(x_{k+1})$ を近似することを課すセカント条件を満たすこと,$B_k$ が対称ならば $B_{k+1}$ も対称であること,$B_k$ が正定値かつ一次独立な $y_k$,$s_k$ に対し $y_k^\top s_k \gt 0$ ならば $B_{k+1}$ も正定値となることが挙げられる.なお,ヘッセ行列 $\nabla^2 f(x_k)$ の逆行列 $\nabla^2 f(x_k)^{-1}$ の近似として $B_k$ の逆行列 $H_k$ を用いると,探索方向は直接 $d_k=-H_k\nabla f(x_k)$ により求まる.$H_k$ は

\[ H_{k+1}=H_k+\left(1+\frac{y_k^\top H_k y_k}{y_k^\top s_k}\right)\frac{s_k s_k^\top}{y_k^\top s_k}-\frac{H_k y_k s_k^\top + s_k y_k^\top H_k^\top}{y_k^\top s_k} \]

によって更新できる.この式自体を BFGS 公式とも表す.

[参考]
福島雅夫,新版 数理計画入門,朝倉書店,2011
矢部博,工業基礎 最適化とその応用,数理工学社,2006