Gauß-Newton-Verfahren

Verfahren zur nichtlinearen Minimierung

Das Gauß-Newton-Verfahren (nach Carl Friedrich Gauß und Isaac Newton) ist ein numerisches Verfahren zur Lösung nichtlinearer Minimierungsprobleme nach der Methode der kleinsten Quadrate. Das Verfahren ist verwandt mit dem Newton-Verfahren zur Lösung nichtlinearer Optimierungsprobleme, hat jedoch den Vorteil, dass die für das Newton-Verfahren notwendige Berechnung der 2. Ableitung entfällt. Speziell für große Probleme mit mehreren zehntausend Parametern ist die Berechnung der 2. Ableitung oft ein limitierender Faktor.

Das OptimierungsproblemBearbeiten

Das Gauß-Newton-Verfahren löst Probleme bei denen das Minimum einer Summe von Quadraten stetig differenzierbarer Funktionen   gesucht ist, also

 

mit  . Mit der euklidischen Norm   lässt sich das auch schreiben als

 

mit  . Probleme dieser Form kommen in der Praxis häufig vor, insbesondere ist das nichtlineare Problem   äquivalent zur Minimierung von   unter der Voraussetzung, dass   eine Nullstelle besitzt.

Das Gauß-Newton-Verfahren wird sehr häufig verwendet, um nichtlineare Ausgleichsprobleme zu lösen. In diesem Fall ergeben sich die Komponentenfunktionen   als Abweichung einer Modellfunktion   von bekannten Beobachtungen bzw. Messwerten  , also  . Ist die Modellfunktion   eine lineare Abbildung, ergibt sich der Standardfall der Methode der kleinsten Quadrate mit linearer Modellfunktion.

Die MethodeBearbeiten

Die Grundidee des Gauß-Newton-Verfahrens besteht darin, die Zielfunktion   zu linearisieren und die Linearisierung im Sinne der kleinsten Quadrate zu optimieren. Die Linearisierung, also die Taylorentwicklung 1. Ordnung, von   im Punkt   lautet

 .

Die Matrix   ist die Jacobi-Matrix und wird oft mit   bezeichnet. Man erhält das lineare kleinste-Quadrate Problem

 ,

mit Gradient  .

Nullsetzen des Gradienten liefert die sogenannten Normalgleichungen

 

mit der expliziten Lösung

 .

Daraus ergibt sich direkt der Gauß-Newton-Iterationsschritt

 ,

wobei   deutlich macht, dass die Jacobi-Matrix an der Stelle   ausgewertet wird und   eine Schrittweite ist.

Um das lineare Gleichungssystem im Gauß-Newton-Iterationsschritt zu lösen gibt es verschiedene Möglichkeiten abhängig von der Problemgröße und der Struktur:[1]

  • Kleine Probleme ( ) werden am besten mit der QR-Zerlegung gelöst
  • Für große Probleme bietet sich die Cholesky-Zerlegung an, da die Matrix   per Konstruktion symmetrisch ist. Für dünnbesetzte   gibt es speziell angepasste Cholesky-Varianten
  • Als allgemeine Möglichkeit kann das CG-Verfahren verwendet werden, wobei hier üblicherweise eine Vorkonditionierung notwendig ist

KonvergenzBearbeiten

Der Update-Vektor im Gauß-Newton-Iterationsschritt hat die Form  , wobei  . Wenn   vollen Rang hat, so ist   und damit auch   positiv definit. Andererseits ist   der Gradient des quadratischen Problems  , somit ist   eine Abstiegsrichtung, d. h., es gilt  . Daraus folgt (bei geeigneter Wahl der Schrittweite  ) die Konvergenz der Gauß-Newton-Methode zu einem stationären Punkt. Aus dieser Darstellung lässt sich auch erkennen, dass die Gauß-Newton Methode im Wesentlichen ein skaliertes Gradientenverfahren mit der positiv definiten Skalierungsmatrix   ist.

Über die Konvergenzgeschwindigkeit kann im Allgemeinen keine Aussage getroffen werden. Falls der Startpunkt   sehr weit vom Optimum entfernt ist oder die Matrix   schlecht konditioniert ist, so konvergiert die Gauß-Newton-Methode u. U. nur sublinear. In vielen praktischen Anwendungsfällen konvergiert die Gauß-Newton-Methode jedoch wesentlich schneller und kann in manchen Fällen sogar dieselbe quadratische Konvergenz wie die Newton-Methode erreichen. Dies ist aus der Verwandtschaft zur Newton-Methode ersichtlich: Die Taylorentwicklung 2. Ordnung der Zielfunktion lautet

 

wobei   die Hesse-Matrix im Punkt   ist. Für den Fall dass   klein ist (z. B. wenn   fast linear ist, oder wenn die Komponentenfunktionen   in der Nähe des Optimums sehr klein sind), kann der quadratische Term vernachlässigt werden und die Gauß-Newton-Methode konvergiert superlinear. Gilt im optimalen Punkt   dass  , dann ist der entsprechende Newton-Schritt identisch mit dem Gauss-Newton-Schritt und die Konvergenz der Gauß-Newton-Methode ist quadratisch.

ErweiterungBearbeiten

Um das Verhalten im Fall von schlecht konditionierten bzw. singulären   zu verbessern, kann der Gauß-Newton-Iterationsschritt folgendermaßen modifiziert werden

 ,

wobei die Diagonalmatrix   so gewählt wird, dass   positiv definit ist. Mit der Wahl  , also einem skalaren Vielfachen der Identitätsmatrix, erhält man den Levenberg-Marquardt-Algorithmus.

BeispielBearbeiten

 
Die Rosenbrock Funktion mit  .

Die Rosenbrock-Funktion

 

wird häufig als Test für Optimierungsmethoden verwendet, da sie wegen des schmalen und flachen Tals, in welchem iterative Methoden nur kleine Schritte machen können, eine Herausforderung darstellt. Die Konstanten werden üblicherweise mit   gewählt, das globale Optimum liegt in diesem Fall bei   mit dem Funktionswert  .

Um die Gauß-Newton-Methode anzuwenden, muss die Rosenbrock-Funktion zunächst in die Form "Summe von Quadraten von Funktionen" gebracht werden. Da die Rosenbrock-Funktion bereits aus einer Summe von zwei Termen besteht, wählt man den Ansatz

 

und

 .

Das Gauß-Newton-Problem für die Rosenbrock-Funktion lautet somit

  wobei  .

Die Jacobi-Matrix ergibt sich als   und damit ist  . Da   vollen Rang hat, ist   positiv definit und die Inverse  existiert. Zur Bestimmung der Schrittweite   kommt folgende einfache Liniensuche zum Einsatz:

  1. Starte mit  .
  2. Berechne den neuen Punkt   mit  .
  3. Wenn   setze   und gehe zur nächsten Iteration.
  4. Ansonsten halbiere   und gehe zu 2.

Die Liniensuche erzwingt, dass der neue Funktionswert kleiner als der vorherige ist; sie terminiert garantiert (mit ev. sehr kleinem  ), da   eine Abstiegsrichtung ist.

Als Startpunkt wird   gewählt. Die Gauß-Newton-Methode konvergiert in wenigen Iterationen zum globalen Optimum:

 
Optimierung der Rosenbrock Funktion mit der Gauß-Newton Methode
Optimierung mit Gauß-Newton Methode
     
0 (0, -0.1) 2
1 (0.1250, -0.0875) 1.8291
2 (0.2344, -0.0473) 1.6306
3 (0.4258, 0.0680) 1.6131
4 (0.5693, 0.2186) 1.3000
5 (0.7847, 0.5166) 1.0300
6 (1.0, 0.9536) 0.2150
7 (1.0, 1.0) 1.1212e-27

Das Gradientenverfahren (mit derselben Liniensuche) liefert im Vergleich dazu folgendes Ergebnis, es findet selbst nach 500 Iterationen nicht zum Optimum:

 
Optimierung der Rosenbrock Funktion mit dem Gradientenverfahren
Optimierung mit Gradientenverfahren
     
0 (0, -0.1) 2
1 (0.0156, 0.0562) 1.2827
2 (0.0337, -0.0313) 1.0386
3 (0.0454, 0.0194) 0.9411
4 (0.0628, -0.0077) 0.8918
5 (0.0875, 0.0286) 0.8765
     
500 (0.8513, 0.7233) 0.0223

LiteraturBearbeiten

  • Dimitri P. Bertsekas: ''Nonlinear Programming.'' Second Edition, Athena Scientific, 1995, ISBN 9781886529144.
  • Yurii Nesterov: "Introductory Lectures on Convex Optimization: A Basic Course." Springer Science & Business Media, 2003, ISBN 978-1-4419-8853-9.
  • Jorge Nocedal, Stephen Wright: "Numerical Optimization." Springer Science & Business Media, 2000, ISBN 9780387987934.
  • Amir Beck: "Introduction to Nonlinear Optimization." SIAM, 2014, ISBN 978-1611973648.

EinzelnachweiseBearbeiten

  1. Ceres Solver Dokumentation. Abgerufen am 10. Mai 2019.