Gradientenabstiegsverfahren

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Das Gradientenverfahren, auch Verfahren des steilsten Abstiegs genannt, ist ein Verfahren, das in der Numerik eingesetzt wird, um allgemeine Optimierungsprobleme zu lösen. Dabei geht man (am Beispiel eines Minimierungsproblems) von einem Näherungswert aus. Von diesem schreitet man in Richtung des negativen Gradienten (der die Richtung des steilsten Abstiegs von diesem Näherungswert angibt) fort, bis man keine numerische Verbesserung mehr erzielt.[1]

Das Verfahren konvergiert oftmals sehr langsam, da es sich dem Optimum mit einem starken Zickzack-Kurs nähert. Für die Lösung von symmetrisch positiv definiten linearen Gleichungssystemen bietet das Verfahren der konjugierten Gradienten hier eine immense Verbesserung. Der Gradientenabstieg ist mit dem Bergsteigeralgorithmus (hill climbing) verwandt.

Das Optimierungsproblem[Bearbeiten]

Das Gradientenverfahren ist einsetzbar, wenn es um die Minimierung einer reellwertigen, differenzierbaren Funktion geht; also um das Optimierungsproblem

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

Wesentliche Schritte[Bearbeiten]

  • Gradient zeigt in die Richtung der "stärksten" Steigung.
  • der negative Gradient zeigt daher in die Richtung, in der die Funktionswerte von fallen.
  • Es kann passieren, dass man bei einem Iterationsschritt über das lokale Minimum der Funktion hinwegspringt. Dann würde man die Schrittweite entsprechend verkleinern, um den Funktionswert von weiter zu minimieren.
  • Abbruchbedingung für das Gradientabstiegsverfahren wäre, wenn wir mit der Iteration eine Stelle gefunden haben an der der Gradient von 0 ist
.

Allgemein ist der Gradient eine Stelle wie folgt über die partiellen Ableitungen definiert:

Beispiel für einen Gradienten[Bearbeiten]

Sei :

Damit können wir den Gradienten an eine bestimmten Stelle im Definitionsbereich berechnen:

Das Verfahren[Bearbeiten]

Als Einführung in das Gradientenabstiegsverfahren wird eine vereinfachte Schrittweitenberechung verwendet.

  • Das Verfahren bricht ab, wenn der Gradient der Nullvektor ist.
  • Ist der Gradient nicht der Nullvektor, wird der negative Gradient zunächst auf die Länge 1 normiert und mit der Schrittweite multipliziert.
  • Die Schrittweite wird halbiert, wenn nach dem Iterationsschritt der Funktionwert (z.B. Kosten) nicht abnehmen.
  • Eine weitere Abbruchbedingung für die Iteration ist, wenn die Schrittweite eine Genauigkeitsgrenze unterschreitet (d.h. ).

Start der Optimierung[Bearbeiten]

Als Anfangspunkt wird eine Stelle aus dem Definitionsbereich der Funktion ausgewählt, für die man lokale Minima mit dem Gradientenabstiegsverfahren annähern möchte.

Richtung des steilsten Abstiegs[Bearbeiten]

Ausgehend von einem Anfangspunkt bzw. von der aktuelle Stelle für den nächsten Iterationsschritt wird die Richtung des steilsten Abstiegs durch bestimmt, wobei den Gradienten von an der Stelle bezeichnet. Dieser zeigt in die Richtung des "größten Anstiegs". Das negative Vorzeichen vor dem Gradienten sorgt dafür, dass man sich mit den Iterationsschritten in die Richtung des stärksten Abfalls bewegt (z.B. Minimierung der Kostenfunktion ).

Normierung des Richtungsvektors[Bearbeiten]

Das vereinfachte Interationsverfahren bricht bei der Bedingung ab. Ansonsten wird der Richtungsvektor für den folgenden Iterationsschritt normiert:

mit Euklidischer Norm

Formal notiert man diesen Iterationsschritt wie folgt:

Festlegung der Schrittweite[Bearbeiten]

Die Schrittweite wird so lange für den nächsten Iterationsschritt verwendet, bis sich die Kostenfunktion mit dem nachfolgende Schritt erhöht. In diesem einführenden Beispiel wird die Schrittweite halbiert. Formal

Die Schrittweitenverkleinerung kann allgemein auch durch einen Faktor mit über

ersetzt werden.

Dabei ist die Schrittweite im j-ten Iterationschritt. Diese Schrittweite muss in jedem Schritt des Iterationsverfahrens bestimmt werden. Hierfür gibt es im Allgemeinen unterschiedliche Möglichkeiten, wie die Rückführung der Schrittweitenbestimmung auf ein eindimensionales Optimierungsproblem. Die hier gewählte Schrittweitenoptimierung ist als Einführung in das Thema gewählt worden.

Gradientenabstieg in Tabellenkalkulation[Bearbeiten]

In der folgenden ZIP-Datei von GitHub befindet sich eine LibreOffice-Datei mit einem exemplarischen Gradientenabstieg für die Kostenfunktion:

.

Die Kostenfunktion hat auf ihrem Definitionsbereich unendlich viele lokale Minima. Das Minimum der Kostenfunktion ist nach Definition -1. In jeder Tabellenzeile wird ein Iterationsschritt durchgeführt und überprüft, ob die Kostenfunktion nach dem Iterationsschritt tatsächlich abnimmt.

Rückführung auf ein eindimensionales Optimierungsproblem[Bearbeiten]

Eine Methode besteht darin, durch die Minimierung der Funktion auf dem (eindimensionalen) "Strahl" zu bestimmen, der ausgehend von in Richtung des negativen Gradienten zeigt. Die eindimensionale zu minimierende Funktion ist wie folgt definiert.

mit

Man berechnet in diesem Fall das mit so, dass minimal wird. d.h.:

Dies ist ein einfaches, eindimensionales Optimierungsproblem, für das es spezielle Verfahren der Schrittweitenbestimmung gibt.

Schrittweiten und iterierte Schrittweitenverkleinerung[Bearbeiten]

Eine andere Methode besteht darin, von der Minimierung der Funktion abhängig zu machen, d. h. von der Bedingung . Wird mit dem Iterationsschritt der Funktionswert mit einer Startschrittweite nicht vermindert, verkleinert man die Schrittweite z. B. mit mit weiter, bis die Schrittweite ausgehend von in Richtung des negativen Gradienten tatsächlich einen Funktionswert liefert und setzt .

Hat man im Iterationsverfahren eine Stelle mit erreicht, liegt eventuell eine lokale Extremstelle von vor (Überprüfung bzw. Abbruch des Iterationsverfahrens).

Abbruchbedingung[Bearbeiten]

Ein zentrales Kriterium für eine Abbruchbedingung ist, dass ist. Wie in der reellen eindimensionalen Analysis muss sich an dieser Stelle keine lokales Minimum befinden (eindimensional Sattelpunkt, mehrdimensional z.B. Sattelfläche). Wenn für zweimal stetig differenzierbar ist und die Hesse-Matrix an dieser Stelle positiv definit ist, liegt in hinreichendes Kriterium für ein lokales Minimum. Dieses wird ausgegeben und die Iteration abgebrochen.

Wird der Algorithmus auf einem Computer ausgeführt, ist ein mögliches weiteres Abbruchkriterium die Schrittweitenlänge, wenn diese kleiner wird als eine untere Grenze mit der Bedingung .

Ferner kann das Gradientenabstiegsverfahren abgebrochen werden, wenn die Verbesserung der Optimierung von in den Interationsschritten kleiner als eine untere Grenze wird.

Durch solche Abbruchkriterien wird algorithmisch gewährleistet, dass das Gradientenabstiegsverfahren nicht in einer Endlosschleife der Iterationen landet.

Videos[Bearbeiten]

Literatur[Bearbeiten]

  1. „Gradientenverfahren“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 24. September 2016, 13:24 UTC. URL: https://de.wikipedia.org/w/index.php?title=Gradientenverfahren&oldid=158180650 (Abgerufen: 21. November 2017, 11:49 UTC)
  2. 2,0 2,1 Gradientenabstieg mit Tabellenkalkulation, Jörg Rapp, Engelbert Niehaus (2018) GitHub Repository https://github.com/niebert/GradientDescent - ZIP: https://github.com/niebert/GradientDescent/archive/master.zip (letzter Zugriff 2019/04/28)