Levenberg-Marquardt-Algorithmus

Der Levenberg-Marquardt-Algorithmus, benannt nach Kenneth Levenberg und Donald Marquardt, ist ein numerischer Optimierungsalgorithmus zur Lösung nichtlinearer Ausgleichs-Probleme mit Hilfe der Methode der kleinsten Quadrate. Das Verfahren kombiniert das Gauß-Newton-Verfahren mit einer Regularisierungstechnik, die absteigende Funktionswerte erzwingt.

Der Levenberg-Marquardt-Algorithmus ist deutlich robuster als das Gauß-Newton-Verfahren, das heißt, er konvergiert mit einer hohen Wahrscheinlichkeit auch bei schlechten Startbedingungen, allerdings ist auch hier Konvergenz nicht garantiert. Ferner ist er bei Anfangswerten, die nahe dem Minimum liegen, oft etwas langsamer.

Beschreibung

Für die nichtlineare Funktion ${\displaystyle F:\mathbb {R} ^{m}\to \mathbb {R} ^{n},\;m<n,}$ soll das Kleinste-Quadrate-Minimierungsproblem (mit einer kleineren Anzahl von unabhängigen Variablen gegenüber der Zahl der Funktionskomponenten)

${\displaystyle \min _{x\in \mathbb {R} ^{m}}\|F(x)\|_{2}^{2}}$

ausgehend von einer Startnäherung ${\displaystyle x_{0}}$ gelöst werden.

Wie beim Gauß-Newton-Verfahren wird F(x) in jedem Schritt durch eine Linearisierung ersetzt und das Ersatzproblem:

${\displaystyle \min _{x\in \mathbb {R} ^{m}}\|F(x_{k})+J(x_{k})(x-x_{k})\|_{2}^{2}}$

betrachtet. Dabei ist J die Jacobi-Matrix der Funktion F.

Der Standard Gauß-Newton-Schritt berechnet den neuen Punkt ${\displaystyle x_{k+1}}$ als Lösung eines linearen Gleichungssystems mit der Koeffizientenmatrix ${\displaystyle J^{T}J}$. Wenn diese Matrix schlecht konditioniert oder singulär ist, kann der Algorithmus nur einen suboptimalen (d. h. die Zielfunktion wird nicht verbessert) bzw. gar keinen Schritt machen. Besonders bei schlecht konditionierten und „fast singulären“ Matrizen ergeben sich zudem erhebliche numerische Schwierigkeiten. Der Levenberg-Marquardt-Algorithmus umgeht diese Probleme, indem er die Koeffizientenmatrix des linearen Gleichungssystems auf die Form ${\displaystyle J^{T}J+\Delta }$ erweitert, wobei ${\displaystyle \Delta }$ eine Diagonalmatrix ist die sicherstellt, dass der gesamte Term positiv definit ist.

Der vollständige Levenberg-Marquardt-Iterationsschritt lautet

${\displaystyle x_{k+1}=x_{k}-\alpha _{k}\left(J(x_{k})^{T}J(x_{k})+\Delta _{k}\right)^{-1}J(x_{k})^{T}F(x_{k})}$

wobei ${\displaystyle \alpha _{k}>0}$ eine Schrittweite ist.

Eine weit verbreitete Form für die Diagonalmatrix ist ${\displaystyle \Delta _{k}=\beta _{k}I}$, mit ${\displaystyle \beta _{k}\geq 0}$ und ${\displaystyle I}$ der Einheitsmatrix. Diese Form wurde auch in den originalen Artikeln von Levenberg und Marquardt vorgeschlagen. Für den Fall ${\displaystyle \beta _{k}=0}$ reduziert sich der Levenberg-Marquardt Iterationsschritt zum Gauß-Newton Schritt. Im Fall ${\displaystyle \beta _{k}\gg 0}$ dominiert hingegen die Einheitsmatrix gegenüber dem Term ${\displaystyle J^{T}J}$, und der Levenberg-Marquardt-Iterationsschritt reduziert sich zu einem Gradientenschritt. Mit der Wahl von ${\displaystyle \beta _{k}}$ kann somit stufenlos zwischen Gradientenschritt und Gauß-Newton Schritt gewählt werden.

Eine alternative Sichtweise ergibt sich aus der Beobachtung, dass das linearisierte Ersatzproblem ${\displaystyle \min _{x\in \mathbb {R} ^{m}}\|F(x_{k})+J(x_{k})(x-x_{k})\|_{2}^{2}}$ nur in einer kleinen Umgebung des Linearisierungspunkts eine gute Annäherung an das Originalproblem darstellt. Eine unrestringierte Minimierung macht jedoch unter Umständen sehr große Schritte, die diese kleine Umgebung verlassen. Aus diesem Grund ersetzt man die unrestringierte Optimierung durch die restringierte Optimierung ${\displaystyle \min _{\|x-x_{k}\|<r_{k}}\|F(x_{k})+J(x_{k})(x-x_{k})\|_{2}^{2}}$ mit ${\displaystyle r_{k}>0}$, d. h. man beschränkt die Optimierung auf eine kleine Nachbarschaft um den Linearisierungspunkt. Aus diesem Grund werden Methoden dieser Art häufig Trust-Region-Verfahren genannt. Man kann zeigen, dass die restringierte Optimierung genau auf die Form ${\displaystyle J^{T}J+\beta _{k}I}$ für die Koeffizientenmatrix des linearen Gleichungssystems führt.

Der Levenberg-Marquardt-Algorithmus variiert adaptiv die Koeffizientenaktualisierungen zwischen dem Gradientenabstieg und dem Gauß-Newton-Verfahren

${\displaystyle [J^{T}WJ+\lambda I]\ h_{lm}=J^{T}W(y-{\hat {y}})}$

wobei kleine Werte des Dämpfungskoeffizienten ${\displaystyle \lambda }$ zu einem Gauß-Newton-Update führen und große Werte von ${\displaystyle \lambda }$ zu einem Update für den Gradientenabstieg führen. Wenn eine Iteration zu einer schlechteren Approximation ${\displaystyle \chi ^{2}(a+h_{lm})>\chi ^{2}(a)}$ führt, wird ${\displaystyle \lambda }$ erhöht. Andernfalls nähert sich die Levenberg-Marquardt-Methode, wenn sich die Lösung verbessert, dem Gauß-Newton-Verfahren, und die Lösung beschleunigt typischerweise das lokale Minimum.

Es gibt verschiedene Varianten des Levenberg-Marquardt-Algorithmus. In Iteration ${\displaystyle i}$ wird der Schritt ${\displaystyle h}$ durch Vergleich von ${\displaystyle \chi ^{2}(a)}$ mit ${\displaystyle \chi ^{2}(a+h_{lm})}$ bewertet. Der Schritt wird akzeptiert, wenn der metrische ${\displaystyle \rho _{i}}$ größer als ein benutzerdefinierter Schwellenwert ${\displaystyle \epsilon _{4}>0}$ ist. Diese Metrik ist ein Maß für die tatsächliche Verbesserung von ${\displaystyle \chi ^{2}}$:

${\displaystyle \rho _{i}(h_{lm})={\frac {\chi ^{2}(a)-\chi ^{2}(a+h_{lm})}{\left\vert h_{lm}^{T}(\lambda _{i}\operatorname {diag} (J^{T}WJ)h_{lm}+J^{T}W(y-{\hat {y}}(a)))\right\vert }}}$

Wenn in einer Iteration ${\displaystyle \rho _{i}(h)>\epsilon _{4}}$ ein ausreichend besser als ${\displaystyle a}$ ist, wird ${\displaystyle a}$ durch ${\displaystyle a+h}$ ersetzt und ${\displaystyle \lambda }$ durch einen Faktor reduziert. Andernfalls wird ${\displaystyle \lambda }$ um einen Faktor erhöht, und der Algorithmus fährt mit der nächsten Iteration fort.^[1]

Konvergenz

Das Levenberg-Marquardt-Verfahren geht lokal in das Gauß-Newton-Verfahren über. Damit ist die Konvergenz lokal linear und nahe dem Optimum sogar quadratisch.

Literatur

• K. Levenberg: A Method for the Solution of Certain Problems in Least Squares, Quart. Appl. Math. 2, 164-168, 1944.
• D. Marquardt: An Algorithm for Least-Squares Estimation of Nonlinear Parameters, SIAM J. Appl. Math. 11, 431-441, 1963.
• Jorge J. Moré: The Levenberg-Marquardt algorithm: Implementation and theory. In G. A. Watson (ed.): Numerical Analysis. Dundee 1977, Lecture Notes Math. 630, 1978, S. 105–116
• P. Gill, W. Murray und M. Wright: Practical Optimization, Academic Press 1981
• J. E. Dennis, Jr., und R. B. Schnabel: Numerical methods for unconstrained optimization and nonlinear equations. Prentice-Hall Series in Computational Mathematics, Englewood Cliffs 1983

Weblinks

Frei verfügbare Implementierungen des Levenberg-Marquardt-Algorithmus:

• gnuplot, freies Grafikprogramm
• lmdif, in Fortran, klassische Implementierung aus Netlib / Minpack. Lizenz: Public Domain
  • lmfit, an Netlib::Minpack::lmfid angelehnte, in sich geschlossene C-Bibliothek, für allgemeine Minimierung und für Kurvenanpassung nach der Methode der kleinsten Quadrate. FreeBSD-Lizenz
• levmar, in C/C++, mit Schnittstellen für Matlab, Perl und Python. Lizenz: GPL
• mpfit, Implementierung in IDL
• csmpfit, C# Portierung von mpfit
• minpack.lm, Implementierung in R
• C/C++ Minpack, Implementierung in C/C++

Einzelnachweise

1. Henri P. Gavin, Duke University: The Levenberg-Marquardt algorithm for nonlinear least squares curve-fitting problems