記憶制限 BFGS 法

記憶制限 BFGS 法#

  • 読み: きおくせいげんびーえふじーえすほう

  • 英名: Limited Memory BFGS Method

  • 別名: L-BFGS 法

BFGS 法は近似行列 \(B_k\) あるいは \(H_k\) を記憶する必要があり,大規模な問題を解こうとするとメモリの壁に阻まれてしまう.1980年に Nocedal [1] はメモリの使用量を削減した BFGS 法として記憶制限 BFGS 法を提案した.

BFGS 法の \(H_k\) の公式を次のように変形する.

(38)#\[\begin{split}\begin{array}{ll} H_{k+1} &= H_{k}-\frac{H_{k}y_{k}s_{k}^\top +s_{k}y_{k}^\top H_{k}}{s_{k}^\top y_{k}}+\left(1+\frac{y_{k}^\top H_{k}y_{k}}{s_{k}^\top y_{k}} \right)\frac{s_{k}s_{k}^\top}{s_{k}^\top y_{k}} \\ &= \left(I-\frac{y_{k}s_{k}^\top}{s_{k}^\top y_{k}} \right)^\top H_{k} \left(I-\frac{y_{k}s_{k}^\top}{s_{k}^\top y_{k}} \right) + \frac{s_{k}s_{k}^\top}{s_{k}^\top y_{k}} \end{array}\end{split}\]

\(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\) と変形していくと

(39)#\[\begin{split}\begin{array}{ll} H_{k+1} = &\left( \prod_{i=0}^{k}{V_i} \right)^\top H_0 \left( \prod_{i=0}^{k}{V_i} \right) \\ &+ \sum_{j=0}^{k}{\left( \prod_{i=j+1}^{k}{V_i} \right)^\top \displaystyle\frac{s_j s_j^\top}{s_j^\top y_j} \left( \prod_{i=j+1}^{k}{V_i} \right)} \end{array}\end{split}\]

ただし \(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\) のみ使用して以下のように行列を更新する.

(40)#\[\begin{split}\begin{array}{ll} H_{k+1} = &\left( \prod_{i=k-m+1}^{k}{V_i} \right)^\top H_0 \left( \prod_{i=k-m+1}^{k}{V_i} \right) \\ &+ \sum_{j=k-m+1}^{k}{\left( \prod_{i=j+1}^{k}{V_i} \right)^\top \displaystyle\frac{s_j s_j^\top}{s_j^\top y_j} \left( \prod_{i=j+1}^{k}{V_i} \right)} \end{array}\end{split}\]

\(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\) が疎行列ならばメモリの使用量を削減することができる.

関連

参考文献

[1]

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.

[2]

矢部博. 工業基礎 最適化とその応用. 数理工学社, 2006.