Wie funktioniert der Levenberg-Marquardt-Algorithmus im Detail, aber auf verständliche Weise?

Ich bin ein Programmierer, der lernen möchte, wie der Levenberg-Marquardt-Kurvenanpassungsalgorithmus funktioniert, damit ich ihn selbst implementieren kann. Gibt es irgendwo ein gutes Tutorial, das erklären kann, wie es im Detail funktioniert, wenn der Leser ein Programmierer und kein Mathematiker ist?

Mein Ziel ist es, diesen Algorithmus in OpenCL zu implementieren, damit er hardwarebeschleunigt ausgeführt werden kann.

Das Minimieren einer Funktion ähnelt dem Versuch, den tiefsten Punkt einer Oberfläche zu finden. Stellen Sie sich vor, Sie gehen auf einer hügeligen Fläche und versuchen, den tiefsten Punkt zu erreichen. Sie würden die Richtung finden, in der es bergab geht, und gehen, bis es nicht mehr bergab geht. Dann würden Sie eine neue Richtung wählen, die bergab geht, und in diese Richtung gehen, bis es nicht mehr bergab geht, und so weiter. Irgendwann (hoffentlich) würde man einen Punkt erreichen, an dem es keine Richtung mehr bergab gibt. Sie wären dann bei einem (lokalen) Minimum.

Der LM-Algorithmus und viele andere Minimierungsalgorithmen verwenden dieses Schema.

Angenommen, die zu minimierende Funktion ist F und wir befinden uns in unserer Iteration am Punkt x(n). Wir möchten die nächste Iteration x(n+1) finden, so dass F(x(n+1)) < F(x(n)) ist, dh der Funktionswert kleiner ist. Um x(n+1) auszuwählen, benötigen wir zwei Dinge, eine Richtung von x(n) und eine Schrittgröße (wie weit wir in diese Richtung gehen). Der LM-Algorithmus ermittelt diese Werte wie folgt:

Berechnen Sie zunächst eine lineare Näherung an F am Punkt x(n). Es ist einfach, die Abwärtsrichtung einer linearen Funktion herauszufinden, daher verwenden wir die lineare Näherungsfunktion, um die Abwärtsrichtung zu bestimmen. Als nächstes müssen wir wissen, wie weit wir in dieser gewählten Richtung gehen können. Wenn unsere approximierende lineare Funktion eine gute Näherung für F für einen großen Bereich um x(n) ist, können wir einen ziemlich großen Schritt machen. Wenn es eine gute Näherung ist, die nur sehr nahe an x(n) liegt, können wir nur einen sehr kleinen Schritt machen.

Dies ist, was LM tut: Es berechnet eine lineare Annäherung an F bei x(n) und gibt so die Abwärtsrichtung an. Anschließend ermittelt es, wie groß der Schritt sein muss, basierend darauf, wie gut die lineare Funktion F bei x(n) annähert. LM ermittelt, wie gut die Näherungsfunktion ist, indem es grundsätzlich einen Schritt in die so bestimmte Richtung macht und vergleicht, um wie viel die lineare Annäherung an F abgenommen hat, um wie viel die tatsächliche Funktion F abgenommen hat. Wenn sie nahe beieinander liegen, ist die Näherungsfunktion gut und wir können einen etwas größeren Schritt machen. Wenn sie nicht nahe beieinander liegen, ist die Näherungsfunktion nicht gut und wir sollten einen Schritt zurücktreten und einen kleineren Schritt machen.

• Versuchen http://en.wikipedia.org/wiki/Levenberg–Marquardt_algorithm
• PDF-Tutorial von Ananth Ranganathan
• JavaNumerics hat eine ziemlich lesbare Implementierung
• Das IKS verfügt über eine C/C++ Implementierung

Die Grundideen des LM-Algorithmus lassen sich auf wenigen Seiten erklären – für eine schnelle und robuste Implementierung in Produktionsqualität sind jedoch viele subtile Optimierungen erforderlich. Stand der Technik ist nach wie vor die Minpack-Implementierung von Moré et al., ausführlich dokumentiert von Moré 1978 (http://link.springer.com/content/pdf/10.1007/BFb0067700.pdf) und im Minpack-Benutzerhandbuch (http://www.mcs.anl.gov/~more/ANL8074b.pdf). Um den Code zu studieren, meine C-Übersetzung (https://jugit.fz-juelich.de/mlz/lmfit) ist wahrscheinlich zugänglicher als der ursprüngliche Fortran-Code.

Versuchen Numerische Rezepte (Levenberg-Marquardt steht in Abschnitt 15.5). Es ist online verfügbar und ich finde, dass sie Algorithmen detailliert erklären (sie haben den vollständigen Quellcode, wie viel detaillierter kann man noch sein …), aber dennoch zugänglich sind.

ich benutzte diese Notizen aus einem Kurs an der Purdue University einen generischen Levenberg-Marquardt-Kurvenanpassungsalgorithmus in MATLAB zu programmieren, der numerische Ableitungen berechnet und daher jede Funktion der Form akzeptiert f(x;p) Wo p ist ein Vektor von Anpassungsparametern.