目次
はじめに
今回は局所最適化解法、つまり初期値依存性のある解法を比較する。遺伝的アルゴリズムなど、大域的最適化解法については別の機会に。
局所最適化解法の違いは、誤差関数の微分について以下の観点から比べるとわかりやすいと思う。
- 一階微分（勾配ベクトル）を用いるのかどうか
- 二階微分（ヘッセ行列）を用いるのかどうか
- 二階微分を用いない場合、
- 二階微分に相当するものを近似で求めるか
- それとも、近似すらしないで二階微分に相当するものはあきらめるか
Nelder-Mead法（ネルダーミード法）
- シンプレックス法やアメーバ法とも呼ばれる
- 局所最適化解法であり、初期値に依存
- 一階微分も二階微分も用いない
- 収束が遅い
- 解が変な方向に行きにくい
勾配降下法（最急降下法）
- 局所最適化解法であり、初期値に依存
- 一階微分を用いるが、二階微分は用いない
- 微分情報を用いる分まだマシだが、収束は早くはない
- イメージとしては、等高線に対して直角に進むため、ジグザグに移動することで回り道になり、収束が遅くなる
ニュートン法
- 局所最適化解法であり、初期値に依存
- 一階微分と二階微分を用いる
- 二階微分まで用いるため収束が速い
- イメージとしては、最急降下法のようにジグザグではなく、まっすぐ解に向かって進んでいく
- 初期値によっては解が変な方向に行ってしまうリスクがある
- 二階微分つまりヘッセ行列の逆行列を求める必要があり、計算負荷が高く、メモリも食う
準ニュートン法
- 局所最適化解法であり、初期値に依存
- 一階微分を用いるが、二階微分は用いない
- 二階微分を用いないが、二階微分の項を一階微分の二乗を用いて近似する
- 近似的にだが二次の項を考慮するため、収束が比較的速い
- ヘッセ行列の逆行列を求める必要がなく、計算負荷を軽くでき、メモリ効率もよい
- 二階微分の項の近似公式がいくつもあり、有名なものにBFGS公式がある
ガウスニュートン法
- 局所最適化解法であり、初期値に依存
- 一般の最適化には使えず、誤差関数が二乗和のときにのみ使える
（つまり非線形最小二乗問題にのみ使える） - そのほかは準ニュートン法と同じ
Levenberg-Marquardt法（レーベンバーグマーカート法）
- 局所最適化解法であり、初期値に依存
- 一般の最適化には使えず、誤差関数が二乗和のときにのみ使える
- 一階微分を用いるが、二階微分は用いない
- 最急降下法とガウス・ニュートン法のハイブリッド（合わせ技）
- 解から遠い初期のうちは最急降下法で慎重に、つまり一次近似で進み、解に近づくとガウス・ニュートン法に切り替えて大胆に、つまり二次近似で進む
- ダンピングファクターといわれるパラメーターλをもつ
- λが大きいほど最急降下法に近くなり、λが小さいほどガウス・ニュートン法に近くなる
- 前段階に比べて誤差が拡大したら、λを大きくして最急降下法っぽく慎重に進む
- 前段階に比べて誤差が縮小したら、λを小さくしてガウス・ニュートン法っぽく大胆に進む
- 収束が速い
- 二階微分を用いないため計算負荷やメモリ負荷も比較的軽い
あわせて読みたい
ニュートン法と勾配降下法の違い | Quant College
偏微分方程式 (PDE) の陽解法と陰解法：解き方の違い、特徴、精度、安定条件 | Quant College
偏微分方程式の数値解法によるプライシング | Quant College
【簡単にわかりやすく解説】モンテカルロ法とは？利点と欠点は？【モンテカルロシミュレーション】 | Quant College