BFGS 法#

読み: びーえふじーえすほう
英名: BFGS Algorithm

準ニュートン法において，目的関数 \(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)\) とおいたとき，

(1)#\[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\) は

(2)#\[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 公式とも表す．