有名な最適化アルゴリズムの比較 ⑴

今回は局所最適化解法、つまり初期値依存性のある解法を比較する。遺伝的アルゴリズムなど、大域的最適化解法については別の機会に。
 
Nelder-Mead法    ネルダーメード法
 
・シンプレックス法やアメーバ法とも呼ばれる
・局所最適化解法であり、初期値に依存
・一階微分も二階微分も用いない
・収束が遅い
・解が変な方向に行きにくい
 
最急降下法
 
・局所最適化解法であり、初期値に依存
・一階微分を用いるが、二階微分は用いない
・微分情報を用いる分まだマシだが、収束は早くはない
・イメージとしては、等高線に対して直角に進むため、ジグザグに移動するため回り道になり、収束が遅くなる
 
ニュートン法
 
・局所最適化解法であり、初期値に依存
・一階微分と二階微分を用いる
・二階微分まで用いるため収束が速い
・イメージとしては、最急降下法のようにジグザグではなく、まっすぐ解に向かって進んでいく
・初期値によっては解が変な方向に行ってしまうリスクがある
・二階微分つまりヘッセ行列の逆行列を求める必要があり、計算負荷が高く、メモリも食う
 
準ニュートン法
 
・局所最適化解法であり、初期値に依存
・一階微分を用いるが、二階微分は用いない
・二階微分を用いないが、二階微分の項を一階微分の二乗を用いて近似する
・近似的にだが二次の項を考慮するため、収束が比較的速い
・ヘッセ行列の逆行列を求める必要がなく、計算負荷を軽くでき、メモリ効率もよい
・二階微分の項の近似公式がいくつもあり、有名なものにBFGS公式がある。
 
ガウス・ニュートン法
 
・局所最適化解法であり、初期値に依存
・一般の最適化には使えず、誤差関数が二乗和のときにのみ使える。つまり非線形最小二乗問題にのみ使える
・そのほかは準ニュートン法と同じ
 
Levenberg-Marquardt法
 
・局所最適化解法であり、初期値に依存
・一般の最適化には使えず、誤差関数が二乗和のときにのみ使える
・一階微分を用いるが、二階微分は用いない
・最急降下法とガウス・ニュートン法の合わせ技
・解から遠い初期のうちは最急降下法で慎重に、つまり一次近似で進み、解に近づくとガウス・ニュートン法に切り替えて大胆に、つまり二次近似で進む
・ダンピングファクターといわれるパラメーターλをもつ
・λが大きいほど最急降下法に近くなり、
    λが小さいほどガウス・ニュートン法に近くなる
・前段階に比べて誤差が拡大したら、λを大きくして最急降下気味に進む
・前段階に比べて誤差が縮小したら、λを小さくしてガウス・ニュートン気味に進む
・収束が速い
・二階微分を用いないため計算負荷やメモリ負荷も比較的軽い
 

—–