記憶制限 BFGS 法#
読み: きおくせいげんびーえふじーえすほう
英名: Limited Memory BFGS Method
別名: L-BFGS 法
BFGS 法は近似行列 \(B_k\) あるいは \(H_k\) を記憶する必要があり,大規模な問題を解こうとするとメモリの壁に阻まれてしまう.1980年に Nocedal [1] はメモリの使用量を削減した BFGS 法として記憶制限 BFGS 法を提案した.
BFGS 法の \(H_k\) の公式を次のように変形する.
\(V_i=I-\displaystyle\frac{y_i s_i^\top}{s_i^\top y_i}\) とおくと \(H_{k+1}=V_{k}^\top H_{k}V_{k} + \displaystyle\frac{s_{k}s_{k}^\top}{s_{k}^\top y_{k}}\) と書くことができる.右辺の \(H_{k}\) を \(H_{k-1},H_{k-2},\ldots\) と変形していくと
ただし \(H_0\) は初期行列,\(\displaystyle\prod_{i=0}^{k}{V_i}=V_0V_1 \cdots V_{k}\) とする.BFGS 法では \(V_0,V_1,\ldots,V_k\) のすべてが \(H_{k+1}\) の更新に寄与している.記憶制限 BFGS 法では \(V_0,V_1,\ldots,V_k\) をすべて使用するのではなく最新の \(m\) 個の \(V_{k-m+1},V_{k-m+2},\ldots,V_k\) のみ使用して以下のように行列を更新する.
\(H_k\) は BFGS 法と同様の仮定のもと \(\{(s_j,y_j)\}_{j=k-m+1}^k\) に対してセカント条件を満し,対称性,正定値性を持つ.\(H_k\) とベクトルの積は \(H_0\) と \(2m\) 本のベクトル \(\{(s_j,y_j)\}_{j=k-m+1}^k\) を記憶すれば実行できるため \(H_0\) が疎行列ならばメモリの使用量を削減することができる.
関連
参考文献
Jorge Nocedal. Updating Quasi-Newton Matrices with Limited Storage. Mathematics of Computation, 35(151):773, jul 1980. URL: https://www.jstor.org/stable/2006193?origin=crossref, doi:10.2307/2006193.
矢部博. 工業基礎 最適化とその応用. 数理工学社, 2006.