トップ > 数理計画用語集 > 記憶制限 BFGS 法

数理計画用語集

記憶制限 BFGS 法

読み:きおくせいげんびーえふじーえすほう
英名:Limited Memory BFGS Method
別名:L-BFGS 法
関連BFGS 法

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

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

\[\begin{align} H_{k+1} &= H_{k}-\displaystyle\frac{H_{k}y_{k}s_{k}^\top +s_{k}y_{k}^\top H_{k}}{s_{k}^\top y_{k}}+\left(1+\displaystyle\frac{y_{k}^\top H_{k}y_{k}}{s_{k}^\top y_{k}} \right)\displaystyle\frac{s_{k}s_{k}^\top}{s_{k}^\top y_{k}} \\ &= \left(I-\displaystyle\frac{y_{k}s_{k}^\top}{s_{k}^\top y_{k}} \right)^\top H_{k} \left(I-\displaystyle\frac{y_{k}s_{k}^\top}{s_{k}^\top y_{k}} \right) + \displaystyle\frac{s_{k}s_{k}^\top}{s_{k}^\top y_{k}} \end{align}\]

$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$ と変形していくと

\[\begin{align} 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{align}\]

ただし $H_0$ は初期行列,$\displaystyle\prod_{i=0}^{k}{V_i}=V_0V_1 \cdots V_{k}$ とする.BFGS 法では $V_0,V_1,\cdots,V_k$ のすべてが $H_{k+1}$ の更新に寄与している.記憶制限 BFGS 法では $V_0,V_1,\cdots,V_k$ をすべて使用するのではなく最新の $m$ 個の $V_{k-m+1},V_{k-m+2},\cdots,V_k$ のみ使用して以下のように行列を更新する.

\[\begin{align} 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{align}\]

$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] 矢部博,工業基礎 最適化とその応用,数理工学社,2006
[2] J. Nocedal, Updating quasi-Newton matrices with limited storage, Mathematics of Computation 35, 1980, 773-782