レーベンバーグ・マルカート法
数学および計算科学において、レーベンバーグ・マルカート法(レーベンバーグ・マルカートほう、英: Levenberg–Marquardt algorithm、LM法、レーベンバーグ・マーカート法)とは、非線形最小二乗問題の解法の一つをいう。特に曲線回帰を最小二乗法により行う場合によく用いられる。LM法はガウス・ニュートン法(GN法)と最急降下法を内挿した手法といえる。GN法よりもロバストであり、初期値が解から大きく外れていた場合でも解けることが多いが、ふるまいの良い関数に対してはGN法よりも収束が遅い傾向を示す。 LM法は、GN法に信頼領域法を適用したものとみることもできる。
1944年、フランクフォード・アーセナル(英語版)職員ケネス・レーヴェンバーグ(英語版)により初発表され、1963年にデュポン勤務の統計家、ドナルド・マーカート(英語版)により再発見された。また、Girard, Wynne, Morrison によりそれぞれ独立に再発見されている。
LM法は、一般的な曲線回帰問題を解く必要のあるアプリケーションソフトウェアで広く用いられる。GN法を取り入れているため多くの場合で1次解法よりも収束速度が速いが、他の反復法と同様、LM法で保証されているのは局所最小値への収束のみであり、大域最小値が得られる保証はない。
悪いフィッティング結果
ましなフィッティング結果
良いフィッティング結果
この例では、関数 y = a cos  ( b X ) + b sin  ( a X ) {\displaystyle y=a\cos \left(bX\right)+b\sin \left(aX\right)} をGNU Octave上のレーベンバーグ・マルカート法実装leasqr関数をもちいてフィッティングする。グラフから、パラメーターフィッティング結果が徐々に改善し、 a = 100 {\displaystyle a=100} 、 b = 102 {\displaystyle b=102} の曲線に近付いていく様子が見てとれる。初期パラメータが元のパラメータに近い場合にのみ、曲線が正確に一致する。この例は、レーベンバーグ・マルカート法が初期条件に非常に敏感であることを示す一例である。その理由の1つは、複数の最小点 (関数) が存在すること、つまりcos(βx)に一致するパラメータの値はˆβだけでなくˆβ+2nπと複数あることである。
ここで、f(x)とJは通常のアルゴリズムでもすでに計算されているため、追加で計算する必要があるのはf(x+hδ)だけである。有限差分ステップhの選択によってはアルゴリズムが不安定になる場合があるが、通常はおよそ0.1が妥当である。
加速度は速度と反対の方向を指す可能性があり、減衰が小さすぎて収束が失速するのを防ぐために、ステップの採用条件に加速度に関する以下のような追加の基準が追加される。
2 ‖ a k ‖ ‖ v k ‖ ≤ α {\displaystyle {\frac {2\left\|{\boldsymbol {a}}_{k}\right\|}{\left\|{\boldsymbol {v}}_{k}\right\|}}\leq \alpha }
ここでαは通常は1未満の固定値とされる。より難しい問題ではより小さい値とする。
測地加速度項を追加すると、収束速度が大幅に向上する可能性があり、特にアルゴリズムが目的関数ランドスケープ上の狭い峡谷を移動する場合に有用である。このような場合、2次の項の効果によりステップ幅はより小さく、精度が高くなる。