L-BFGS法
L-BFGS法は、所与の初期推定x0から、反復的により良い推定値x1, x2, ...を算出する。目的関数の微分値gk := ∇f(xk)を降下の方向の算出だけでなく、ヘッセ行列(2次微分)の推定値の更新にも用いる。
L-BFGS法は他の準ニュートン法アルゴリズムと多くの部分は共通だが、行列とベクトルの乗算dk = −Hkgkの実行方法が大きく異なる。ここで、dkはニュートン方向の近似値、gkは現在の勾配であり、Hkはヘッセ行列の逆行列である。これまでの履歴を使用してこの方向ベクトルを算出する複数のアプローチが発表されているが、ここでは、「2ループ再帰」と呼ばれる一般的なアプローチを示す。
k回目の反復における位置xkおよび勾配gk ≡ ∇f(xk)を所与とする。また、すべてのベクトルは列ベクトルとし、直近m回の更新履歴を次の形式で記憶していることを仮定する。
s k = x k + 1 − x k {\displaystyle s_{k}=x_{k+1}-x_{k}}
y k = g k + 1 − g k {\displaystyle y_{k}=g_{k+1}-g_{k}}
ここで、 ρ k = 1 y k ⊤ s k {\displaystyle \rho _{k}={\frac {1}{y_{k}^{\top }s_{k}}}} とし、H0kをk回目の反復での逆ヘッセ行列の初期推定値とする。