1. ニュートン法
目的関数 $f: \mathbb{R}^n \to \mathbb{R}$ の最小化を考えます：
\text{minimize} \quad f(x), \quad x \in \mathbb{R}^n
ニュートン法による更新式：
dx = -[\nabla^2 f(x)]^{-1} \nabla f(x)
ここで、$\nabla f(x) \in \mathbb{R}^n$ は勾配、$\nabla^2 f(x) \in \mathbb{R}^{n \times n}$ はヘッセ行列を表します。
準ニュートン法
1. 準ニュートン法の基本概念
ニュートン法は二階微分（ヘッセ行列）を必要としますが、これは以下の理由で計算コストが高くなりがちです：
- 高次元の場合、ヘッセ行列の計算が非常に高い
- 行列の記憶容量が $O(n^2)$ 必要
- 各反復で行列の逆行列計算が必要
準ニュートン法は、ヘッセ行列を直接計算する代わりに、勾配の情報から徐々にヘッセ行列（の近似）を構築していきます。
更新式の基本形
dx = -B_k^{-1} \nabla f(x_k)
ここで：
- $B_k$ はヘッセ行列 $\nabla^2 f(x_k)$ の近似
- $B_k$ は対称性と正定値性を保持するように更新
2. セカント条件
準ニュートン法では、以下のセカント条件を満たすように $B_{k+1}$ を更新します：
B_{k+1}s_k = y_k
ここで：
- $s_k = x_{k+1} - x_k$：位置の変化
- $y_k = \nabla f(x_{k+1}) - \nabla f(x_k)$：勾配の変化
この条件は、一次の差分近似から導かれる自然な要請です。
3. 代表的な更新公式
BFGS法
最も広く使われている準ニュートン法の一つです。
dB = - \frac{B_k s_k s_k^T B_k}{s_k^T B_k s_k} + \frac{y_k y_k^T}{y_k^T s_k}
または、逆行列の直接更新形式：
H_{k+1} = (I - \rho_k s_k y_k^T)H_k(I - \rho_k y_k s_k^T) + \rho_k s_k s_k^T
ここで $H_k = B_k^{-1}$, $\rho_k = 1/(y_k^T s_k)$ です。
BFGS法の特性
BFGS法は以下のような優れた特性を持ちます：
-
正定値性の自動的な保持
- 初期行列 $B_0$ が正定値であれば、更新後も正定値性が自動的に保持される
- 修正ニュートン法のような明示的な正規化が不要
- Wolfe条件を満たすライン探索を行えば $y_k^T s_k > 0$ が保証され、正定値性が維持される
-
効率的な実装
- 逆行列の直接更新形式により、$O(n^3)$ の逆行列計算を回避可能
- 行列-ベクトル積の計算が主要な計算コスト
-
優れた収束特性
- 局所的な超線形収束性を持つ
- 実用的な収束速度と数値的な安定性のバランスが良好
これらの特性により、BFGS法は実践的な最適化問題において広く使用されています。特に、以下のような状況で効果的です：
- ヘッセ行列の計算が困難または高コストな場合
- 問題の規模が中程度（数百〜数千変数）の場合
- 目的関数が十分滑らかな場合
L-BFGS法
Limited-memory BFGS法は、完全な行列を保存せず、過去 $m$ 回分の $(s_k, y_k)$ ペアのみを保持します：
- 記憶容量: $O(mn)$ ($n$ は変数の次元)
- 行列-ベクトル積の計算量: $O(mn)$
- $m$ は通常 3〜20 程度
更新には two-loop recursion アルゴリズムを使用：
\begin{align*}
q &\leftarrow \nabla f(x_k) \\
\text{for } i &= k-1, k-2, ..., k-m \\
\alpha_i &= \rho_i s_i^T q \\
q &\leftarrow q - \alpha_i y_i \\
r &= H_0^k q \\
\text{for } i &= k-m, ..., k-1 \\
\beta &= \rho_i y_i^T r \\
r &\leftarrow r + s_i(\alpha_i - \beta)
\end{align*}
ここで $r$ が最終的な探索方向となります。
セカント条件とKLダイバージェンス
実際、BFGS更新式は以下のKLダイバージェンス最小化問題の解として導出できます：
\min_{B_{k+1}} D_{KL}(B_{k+1} || B_k) \quad \text{subject to} \quad B_{k+1}s_k = y_k, \quad B_{k+1} = B_{k+1}^T
ここで、行列のKLダイバージェンスは以下のように定義されます：
D_{KL}(B_{k+1} || B_k) = \text{tr}(B_{k+1}B_k^{-1}) - \ln\det(B_{k+1}B_k^{-1}) - n
この最適化問題は、新しい近似ヘッセ行列 $B_{k+1}$ が:
- セカント条件を満たし
- 対称性を保持しつつ
- 前回の近似 $B_k$ からの情報理論的な意味での「距離」を最小化
することを要求しています。
興味深いことに、KLダイバージェンスの順序を逆にした最小化問題：
\min_{B_{k+1}} D_{KL}(B_k || B_{k+1}) \quad \text{subject to} \quad B_{k+1}s_k = y_k, \quad B_{k+1} = B_{k+1}^T
を解くと、DFP (Davidon-Fletcher-Powell) 法の更新式が導出されます。