Levenberg-Marquardt法
- LM 法はガウスニュートン法 (非線形最小二乗問題を対象にしてる)のための手法
そもそもの流れの整理
- 最急降下法 (簡単だけど、条件数が悪いと困る)
- 共役勾配法 (連立一次方程式の解法が狭義二次凸最小化問題を解くことと同値、n 次元なら、 n回の反復で収束)
- 共役方向の生成は Gram-Schmid の直交化が簡単
- 非線形の問題に拡張するためには、行列 A を陽に扱えない、パラメータ $\beta$ の表現が色々ある
- ニュートン法 (二次モデルの最小化に基づいた解法、ただし、 $H$ が正定値とは限らないので、以下の代替手法がある)
- Damping
- $H$ を適当な正定値対称行列で近似 (準ニュートン法)
- 信頼領域法
- ガウスニュートン法 (最小二乗法の場合近似可能)
- 準ニュートン法 (テイラー展開での二次の項までを正定値対称行列 $B$ を使って求める、セカント条件)
- DFP 公式 (セカント条件を満たす簡単な $B$ )
- BFGS 公式 ($B$ の中で一番有効とされてるやつ、 Broyden, Fletcher, Goldfarb, Shanno)
- 逆行列を保持するパターンを H公式、そうじゃないパターンを B公式と呼ぶ
- 記憶制限 準ニュートン法 (上記までは以前として、巨大行列 $B$ とかを保持しなきゃいけない)
- $B$ ではなく、ベクトル $V_k$ を保持して、 $B$ みたいなものを計算できるようにする
- $V_1$ から、$V_n$ まで持つのは大変なので、直近のいくつかのみを保持する
- 信頼領域法 (ニュートン法は局所収束早いけど、降下方向を生成するとは限らない)
- これまでの直線探索法が降下方向を定めてから Step Size 決定をしてるが、信頼領域法では、二次モデルが妥当な領域を与えてから、探索方向を決定している
- 信頼領域は、有界閉集合なので、 $B$ の正定値姓に関わらず、部分問題は最小解を持つ (正定値性の制約がもはやいらない)
- 制約付き最小化を厳密に解くのが難しいので、近似手法として Dogleg Method が有名
- 最急降下方向ベクトル $d_s$ 方向で、信頼領域上の最小点 $x_{c_p}$ と、ニュートン方向を結ぶ線分の信頼領域の淵( $x_k$ からの距離が信頼区間に一致)との交点を、次の $x_{\text{trial}}$ に選ぶ
- 信頼領域が広いと、ニュートン方向 / 信頼領域が狭いと、最急降下方向
- 信頼領域法の部分問題を解くことと、 Damping をしたニュートン方程式を解くことに関連する（5章の章末問題4）
- これは、ニュートン方程式に対する Levenberg-Marquardt法の修正に対応？
Reference
Tikhonov damping (aka Tikhonov regularization)
Reference
