Levenberg-Marquardt-Algorithmus

Der Levenberg-Marquardt-Algorithmus, benannt nach Kenneth Levenberg und Donald Marquardt ist ein numerischer Optimierungsalgorithmus, der eine, in der Regel nicht-lineare Funktion minimiert. Diese Lösungsstrategie kombiniert das Gauß-Newton-Verfahren und das Gradientenabstiegsverfahren. Der LMA ist deutlich robuster als der GNA, dh. er konvergiert mit einer hohen Wahrscheinlichkeit auch bei schlechten Startbedingungen. Jedoch ist er bei Anfangswerten, die nahe dem Minimum liegen oft etwas langsamer.

Ziel des Algorithmus ist es, eine zweifach differenzierbare Funktion $f$ zu minimieren. Dabei gilt :

$f:\mathbb {R} ^{n}\rightarrow \mathbb {R}$

Da für nicht-quadratische Funktionen die Hesse-Matrix $H(x_{k})$ nicht immer positiv definit ist, könnte der Algorithmus möglicherweise in eine falsche Richtung laufen. Darum wird ein Korrektur-Term $\nu _{k}\cdot I$ eingeführt.

$H_{k}=H(x_{k})+\nu _{k}\cdot I$

$x_{k+1}=x_{k}-H_{k}^{-1}\nabla f(x_{k})$

Da nun $H_{k}>0$ lassen sich nach folgendem Schema der Punkt $x_{k+1}$ berechnen :

Man wählt ein passendes $\nu _{0}$ und einen Startpunkt $x_{0}$, an dem $\nabla f(x_{0}$) und $H(x_{0})$ errechnet werden. Außerdem werden noch drei Konstanten $c_{0},c_{1},c_{2}>1$ benötigt.

1. $H_{k}=H(x_{k})+\nu _{k}\cdot I$
2. Falls $H_{k}$ nicht positiv definit, dann $\nu _{k}=c_{0}\cdot \nu _{k}$ und gehe zurück zu 1.
3. $x_{k+1}=x_{k}-H_{k}^{-1}\nabla f(x_{k})$
4. Falls $f(x_{k+1})>f(x_{k})$ dann $\nu _{k}=c_{1}\cdot \nu _{k}$, $x_{k+1}=x_{k}$ und gehe zurück zu 1.
5. $\nu _{k+1}={\nu _{k} \over c_{2}}$
6. $k\rightarrow k+1$

Literatur

• Levenberg, K. "A Method for the Solution of Certain Problems in Least Squares." Quart. Appl. Math. 2, 164-168, 1944.
• Marquardt, D. "An Algorithm for Least-Squares Estimation of Nonlinear Parameters." SIAM J. Appl. Math. 11, 431-441, 1963.