Gradientenverfahren

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Das Gradientenverfahren wird in der Numerik eingesetzt, um allgemeine Optimierungsprobleme zu lösen. Dabei schreitet man (am Beispiel eines Minimierungsproblems) von einem Startpunkt aus entlang einer Abstiegsrichtung, bis keine numerische Verbesserung mehr erzielt wird. Wählt man als Abstiegsrichtung den negativen Gradient, also die Richtung des lokal steilsten Abstiegs, erhält man das Verfahren des steilsten Abstiegs. Manchmal werden die Begriffe Gradientenverfahren und Verfahren des steilsten Abstiegs synonym verwendet. Im Allgemeinen bezeichnet Gradientenverfahren eine Optimierungsmethode, bei der die Abstiegsrichtung durch Gradienteninformation gewonnen wird, also nicht notwendigerweise auf den negativen Gradient beschränkt ist.[1]

Das Verfahren des steilsten Abstiegs konvergiert oftmals sehr langsam, da es sich dem stationären Punkt mit einem starken Zickzack-Kurs nähert. Andere Verfahren für die Berechnung der Abstiegsrichtung erreichen teils deutlich bessere Konvergenzgeschwindigkeiten, so bietet sich für die Lösung von symmetrisch positiv definiten linearen Gleichungssystemen beispielsweise das Verfahren der konjugierten Gradienten an. Der Gradientenabstieg ist mit dem Bergsteigeralgorithmus (hill climbing) verwandt.

Das Optimierungsproblem[Bearbeiten | Quelltext bearbeiten]

Das Gradientenverfahren ist einsetzbar, um eine reellwertige, differenzierbare Funktion zu minimieren:

Hierbei handelt es sich um ein Problem der Optimierung ohne Nebenbedingungen, auch unrestringiertes Optimierungsproblem genannt.

Das Verfahren[Bearbeiten | Quelltext bearbeiten]

Das Gradientenverfahren generiert ausgehend von einem Startpunkt eine Folge von Punkten gemäß der Iterationsvorschrift

wobei eine positive Schrittweite ist und eine Abstiegsrichtung. Dabei werden sowohl als auch in jedem Iterationsschritt so bestimmt, dass die Folge zu einem stationären Punkt von konvergiert.

Bestimmen der Abstiegsrichtung[Bearbeiten | Quelltext bearbeiten]

Abstiegsrichtungen haben einen Winkel größer als 90° mit dem Gradienten im Punkt . Die strichlierte Gerade ist die Tangente an die Isolinie der zweidimensionalen Funktion, sie stellt den Grenzfall dar bei dem der Winkel mit dem Gradient 90° beträgt. Die Abstiegsrichtung zeigt in Richtung des negativen Gradienten, d. h. in Richtung des steilsten Abstiegs.

Eine Abstiegsrichtung im Punkt ist ein Vektor , der

erfüllt. Intuitiv bedeutet das, dass der Winkel zwischen und größer als 90° ist. Da der Gradient in Richtung des steilsten Anstiegs zeigt, ist eine Richtung entlang derer sich der Funktionswert verringert.

Viele Gradientenmethoden berechnen die Abstiegsrichtung anhand

wobei eine positiv definite Matrix ist. In diesem Fall lautet die Bedingung für die Abstiegsrichtung

und ist dank der positiven Definitheit von immer erfüllt.

Mit der Wahl der Matrix erhält man folgende Algorithmen:

  • , wobei die Einheitsmatrix ist, ergibt das Verfahren des steilsten Abstiegs. Die Absteigsrichtung ist in diesem Fall einfach der negative Gradient, .
  • , wobei sodass positiv definit ist, ist ein diagonal skalierter steilster Abstieg. Oft werden die als Approximation der Inversen der 2. Ableitung gewählt, also .
  • , die Inverse Hesse-Matrix, ergibt das Newton-Verfahren für die Lösung nichtlinearer Minimierungsprobleme.
  • Da die Berechnung der Hesse-Matrix oft aufwändig ist, gibt es eine Klasse von Algorithmen welche eine Approximation verwenden. Solche Methoden werden als Quasi-Newton-Verfahren bezeichnet, es gibt verschiedene Arten wie die Approximation berechnet wird. Ein wichtiger Vertreter aus der Klasse der Quasi-Newton Methoden ist der BFGS Algorithmus.
  • Falls das Optimierungsproblem in der speziellen Form , also als Summe von Quadraten von Funktionen, gegeben ist, erhält man mit , wobei die Jacobi-Matrix von im Punkt ist, das Gauß-Newton-Verfahren.

Bestimmen der Schrittweite[Bearbeiten | Quelltext bearbeiten]

Die Bestimmung der Schrittweite ist ein wichtiger Teil des Gradientenverfahren, der großen Einfluss auf die Konvergenz haben kann. Ausgehend vom Iterationsschritt betrachtet man den Wert von entlang der Linie , also . Man spricht in diesem Zusammenhang oft auch von Liniensuche. Die ideale Wahl wäre es, die Schrittweite als jenen Wert zu berechnen, der die Funktion minimiert, also das eindimensionale Problem

zu lösen. Dies wird als exakte Liniensuche bezeichnet, und wird in dieser Form in der Praxis selten angewandt, da selbst für einfache Optimierungsprobleme die exakte Bestimmung der Schrittweite sehr rechenaufwändig ist.

Als Alternative zur exakten Liniensuche lockert man die Erfordernisse und beschränkt sich darauf, dass der Funktionswert sich mit jedem Iterationsschritt "genügend" verringert. Dies wird auch als inexakte Liniensuche bezeichnet. Die einfachste Möglichkeit besteht darin, die Schrittweite ausgehend von einem Startwert (z.B ) so lange zu verringern, bis erreicht ist. Diese Methode funktioniert in der Praxis oft zufriedenstellend, man kann jedoch zeigen, dass für manche pathologischen Funktionen diese Liniensuche zwar in jedem Schritt den Funktionswert verringert, die Folge jedoch nicht zu einem stationärem Punkt konvergiert.

Armijo-Bedingung[Bearbeiten | Quelltext bearbeiten]

Die Armijo-Bedingung formalisiert das Konzept "genügend" in der geforderten Verringerung des Funktionswertes. Die Bedingung wird modifiziert zu

mit . Die Armijo-Bedingung umgeht die Konvergenzprobleme aus der vorigen einfachen Bedingung, indem sie fordert dass die Verringerung zumindest proportional zur Schrittweite und zur Richtungsableitung ist, mit Proportionalitätskonstante . In der Praxis werden oft sehr kleine Werte verwendet, z. B. .

Backtracking Liniensuche[Bearbeiten | Quelltext bearbeiten]

Die Armijo-Bedingung gilt immer wenn die Schrittweite genügend klein ist, und kann damit zum Stillstand des Gradientenverfahrens führen – der Schritt ist so klein dass kein nennenswerter Fortschritt mehr gemacht wird. Eine einfache Kombination aus wiederholter Verkleinerung der Schrittweite und der Armijo-Bedingung ist die Backtracking Liniensuche. Sie stellt sicher, dass die Schrittweite klein genug ist um die Armijo-Bedingung zu erfüllen, andererseits aber nicht zu klein. In Pseudocode:

Wähle Startwert für , z. B. , wähle Konstanten 
while 
  
end
Setze 

Die Backtracking Liniensuche verringert die Schrittweite wiederholt um den Faktor , bis die Armijo-Bedingung erfüllt ist. Sie terminiert garantiert nach einer endlichen Anzahl von Schritten und wird wegen ihrer Einfachheit oft in Praxis verwendet.

Konvergenz[Bearbeiten | Quelltext bearbeiten]

Im Allgemeinen konvergiert das Gradientenverfahren weder zu einem globalen noch zu einem lokalen Minimum. Garantiert werden kann nur die Konvergenz zu einem stationären Punkt, also einem Punkt mit . Schränkt man die Klasse der Zielfunktionen auf konvexe Funktionen ein, so sind stärkere Garantien möglich, siehe konvexe Optimierung.

Konvergenzgeschwindigkeit[Bearbeiten | Quelltext bearbeiten]

Für den allgemeinen Fall kann weder über die Konvergenzgeschwindigkeit der Folge noch über die Konvergenzgeschwindigkeit der Folge eine Aussage getroffen werden. Ist eine Lipschitz-Konstante von , so kann man zeigen, dass die Norm der Gradienten mit der Rate gegen 0 konvergiert, wobei eine positive Konstante ist.

Spezialfall: Quadratische Funktionale[Bearbeiten | Quelltext bearbeiten]

Typischerweise wird ein Energiefunktional der Form

minimiert. Es handelt sich also um ein unrestringiertes quadratisches Programm. Dabei ist eine symmetrisch positiv definite Matrix. Ausgehend von einem Anfangspunkt wird die Richtung des steilsten Abstiegs natürlich durch die Ableitung bestimmt, wobei den Nabla-Operator bezeichnet. Dann wird wie folgt iteriert

bezeichnet die Schrittweite des Verfahrens und kann durch

berechnet werden. Das Verfahren konvergiert dann für einen beliebigen Startwert gegen einen Wert , so dass minimal ist.

Algorithmus in Pseudocode[Bearbeiten | Quelltext bearbeiten]

Eingabe: geeigneter Startvektor 
for k = 0 to n-1
  
  
  
end
Ausgabe: Minimalstelle  des Energiefunktionals.

Konvergenzgeschwindigkeit[Bearbeiten | Quelltext bearbeiten]

Das Gradientenverfahren liefert eine Folge mit

.

Dabei bezeichnet die sogenannte Energienorm bezüglich und die Kondition der Matrix bezüglich der Spektralnorm.

Anwendungsbeispiel[Bearbeiten | Quelltext bearbeiten]

Der Gradientenabstieg in Form von Backpropagation ist ein bedeutendes Verfahren zum Trainieren überwacht lernender künstlicher neuronaler Netze.

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

  • Yurii Nesterov: "Introductory Lectures on Convex Optimization: A Basic Course." Springer Science & Business Media, 2003, ISBN 978-1-4419-8853-9.
  • Dimitri P. Bertsekas: Nonlinear Programming. Second Edition, Athena Scientific, 1995, ISBN 9781886529144.
  • Jorge Nocedal, Stephen Wright: "Numerical Optimization." Springer Science & Business Media, 2000, ISBN 9780387987934.
  • Andreas Meister: Numerik linearer Gleichungssysteme. 2. Auflage. Vieweg, Wiesbaden 2005, ISBN 3-528-13135-7.

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Bertsekas, Dimitri P: Nonlinear programming. ISBN 978-1-886529-05-2.