レーベンバーグ・マルカート アルゴリズムはどのように詳細に機能するのですか?

関数を最小化することは、表面の最低点を見つけようとするようなものです。丘陵地を歩いていて、最低点に到達しようとしていると考えてください。下り坂になる方向を見つけて、下り坂がなくなるまで歩きます。次に、下り坂になる新しい方向を選択し、下り坂がなくなるまでその方向に歩きます。最終的には(うまくいけば)、下り坂の方向がなくなるポイントに到達するでしょう。その後、(局所的な) 最小値になります。

LM アルゴリズムと他の多くの最小化アルゴリズムは、このスキームを使用します。

最小化される関数が F で、反復の点 x(n) にいるとします。 F(x(n+1))

まず、点 x(n) における F の線形近似を計算します。線形関数の下り坂の方向を見つけるのは簡単なので、線形近似関数を使用して下り坂の方向を決定します。次に、この選択した方向にどれだけ進むことができるかを知る必要があります。近似線形関数が x(n) 付近の大きな領域の F の適切な近似値である場合、かなり大きなステップを取ることができます。それが x(n) に非常に近いだけの適切な近似である場合、非常に小さなステップしか取ることができません。

これが LM の機能です。x(n) で F の線形近似を計算し、下り坂の方向を示します。次に、線形関数が x(n) で F をどれだけ適切に近似しているかに基づいて、ステップの大きさを計算します。 LM は、このように決定された方向に基本的にステップを踏み、F の線形近似がどれだけ減少したかを実際の関数 F がどれだけ減少したかを比較することによって、近似関数がどれほど優れているかを把握します。それらが近い場合、近似関数は適切であり、少し大きなステップを取ることができます.それらが近くない場合、近似関数は適切ではないため、後退してより小さなステップを実行する必要があります.


  • http://en.wikipedia.org/wiki/Levenberg–Marquardt_algorithm を試す
  • Ananth Ranganathan による PDF チュートリアル
  • JavaNumerics の実装はかなり読みやすい
  • ICS には C/C++ 実装があります

LM アルゴリズムの基本的な考え方は数ページで説明できますが、高速で堅牢な製品レベルの実装には、多くの微妙な最適化が必要です。最新技術は、Moré らによる Minpack の実装であり、Moré 1978 (http://link.springer.com/content/pdf/10.1007/BFb0067700.pdf) および Minpack ユーザー ガイド (http://link.springer.com/content/pdf/10.1007/BFb0067700.pdf) によって詳細に文書化されています。 ://www.mcs.anl.gov/~more/ANL8074b.pdf)。コードを調べるには、私の C 翻訳 (https://jugit.fz-juelich.de/mlz/lmfit) の方がおそらく元の Fortran コードよりもアクセスしやすいでしょう。