Benutzer:Titus Telearis/Levenberg-Marquardt-Algorithmus

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoßen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit dem Autor Titus Telearis auf.

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 $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)

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

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

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

$\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.

Zusätzlich fordert man beim Levenberg-Marquardt-Algorithmus allerdings, dass $\|x-x_{k}\|_{2}^{2}<r_{k}$. Durch diese Zusatzbedingung kann man eine Verkleinerung von $\|F(x_{k})\|_{2}^{2}$ in jedem Schritt erzwingen. Dazu wird der Parameter $r_{k}$ entsprechend angepasst.

Konvergenz

Das Levenberg-Marquardt-Verfahren geht lokal in das Newton-Verfahren über. Damit ist die Konvergenz lokal 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 finden sich unter

• 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

Kategorie:Optimierungsalgorithmus