Anstieg-Abstieg ist ein Optimierungsalgorithmus der ersten Ordnung. Um ein lokales Minimum einer Funktion mit dem Anstieg-Abstieg zu finden, unternimmt man proportional der Verneinung des Anstiegs (oder des ungefähren Anstiegs) der Funktion am aktuellen Punkt Schritte. Wenn stattdessen man proportional zum positiven vom Anstieg Schritte unternimmt, nähert man sich einem lokalen Maximum dieser Funktion; das Verfahren ist dann als Anstieg-Aufstieg bekannt.

Anstieg-Abstieg ist auch bekannt als steilster Abstieg oder die Methode des steilsten Abstiegs. Wenn bekannt, weil der letzte, Anstieg-Abstieg mit der Methode des steilsten Abstiegs nicht verwirrt sein sollte, um Integralen näher zu kommen.

Beschreibung

Anstieg-Abstieg basiert auf der Beobachtung dass, wenn die mehrvariable Funktion definiert wird und differentiable in einer Nachbarschaft eines Punkts, dann am schnellsten Abnahmen, wenn man von in der Richtung auf den negativen Anstieg an geht. Hieraus folgt dass, wenn

:

für eine genug kleine Zahl, dann. Mit dieser Beobachtung im Sinn fängt man mit einer Annahme für ein lokales Minimum dessen an, und denkt die Folge

solch dass

:

Wir haben

:

so hoffentlich läuft die Folge zum gewünschten lokalen Minimum zusammen. Bemerken Sie, dass dem Wert der Schritt-Größe erlaubt wird, sich bei jeder Wiederholung zu ändern. Mit bestimmten Annahmen auf der Funktion (zum Beispiel, konvex und Lipschitz) und besondere Wahlen (z.B, gewählt über eine Liniensuche, die die Bedingungen von Wolfe befriedigt), kann die Konvergenz zu einem lokalen Minimum versichert werden. Wenn die Funktion konvex ist, sind alle lokalen Minima auch globale Minima, so in diesem Fall kann Anstieg-Abstieg zur globalen Lösung zusammenlaufen.

Dieser Prozess wird im Bild nach rechts illustriert. Hier wird angenommen, auf dem Flugzeug definiert zu werden, und dass sein Graph eine Schüssel-Gestalt hat. Die blauen Kurven sind die Höhenlinien, d. h. die Gebiete, auf denen der Wert dessen unveränderlich ist. Ein roter Pfeil, der an einem Punkt entsteht, zeigt die Richtung des negativen Anstiegs an diesem Punkt. Bemerken Sie, dass der (negative) Anstieg an einem Punkt zur Höhenlinie orthogonal ist, die diesen Punkt durchgeht. Wir sehen, dass Anstieg-Abstieg uns zum Boden der Schüssel, d. h. zum Punkt führt, wo der Wert der Funktion minimal ist.

Beispiele

Anstieg-Abstieg hat Probleme mit pathologischen Funktionen wie die Funktion von Rosenbrock gezeigt hier.

:

Die Rosenbrock-Funktion hat ein schmales gekrümmtes Tal, das das Minimum enthält. Der Boden des Tales ist sehr flach. Wegen des gekrümmten flachen Tales ist die Optimierung zig-zagging langsam mit kleinem stepsizes zum Minimum.

Die "Zig-Zagging" Natur der Methode ist auch unten offensichtlich, wo die Anstieg-Aufstieg-Methode darauf angewandt wird.

Beschränkungen

Für einige der obengenannten Beispiele ist Anstieg-Abstieg in der Nähe vom Minimum relativ langsam: Technisch ist seine asymptotische Rate der Konvergenz vielen anderen Methoden untergeordnet. Für schlecht bedingte konvexe Probleme Anstieg-Abstieg zunehmend 'Zickzacke' weil weisen die Anstiege fast orthogonal zur kürzesten Richtung zu einem minimalen Punkt hin. Für mehr Details, sieh die Anmerkungen unten.

Für Non-Differentiable-Funktionen werden Anstieg-Methoden schlecht-definiert. Für lokal Probleme von Lipschitz und besonders für konvexe Minimierungsprobleme sind Bündel-Methoden des Abstiegs bestimmt. Nichtabfallmethoden, wie Subanstieg-Vorsprung-Methoden, können auch verwendet werden. Diese Methoden sind normalerweise langsamer als Anstieg-Abstieg. Eine andere Alternative für Non-Differentiable-Funktionen soll die Funktion "glätten", oder hat die Funktion nach einer glatten Funktion gebunden. In dieser Annäherung wird das glatte Problem in der Hoffnung behoben, dass die Antwort der Antwort für das nichtglatte Problem nah ist (gelegentlich, kann das streng gemacht werden).

Lösung eines geradlinigen Systems

Anstieg-Abstieg kann verwendet werden, um ein System von geradlinigen Gleichungen, wiederformuliert als ein quadratisches Minimierungsproblem, z.B, mit geradlinig kleinste Quadrate zu lösen. Lösung von

:

im Sinne des geradlinigen kleinste Quadrate wird als Minderung der Funktion definiert

:

Im traditionellen geradlinig kleinste Quadrate für den echten und die Euklidische Norm, wird in welchem Fall verwendet

:

In diesem Fall kann die Liniensuchminimierung, die lokal optimale Schritt-Größe auf jeder Wiederholung findend, analytisch durchgeführt werden, und ausführliche Formeln für lokal optimalen sind bekannt.

https://hpcrd.lbl.gov/~meza/papers/Steepest%20Descent.pdf

Um geradlinige Gleichungen zu lösen, wird Anstieg-Abstieg mit der verbundenen Anstieg-Methode selten verwendet, die eine der populärsten Alternativen ist. Die Geschwindigkeit der Konvergenz des Anstieg-Abstiegs hängt vom maximalen und minimalen eigenvalues dessen ab, während die Geschwindigkeit der Konvergenz von verbundenen Anstiegen eine kompliziertere Abhängigkeit vom eigenvalues hat, und aus dem Vorbedingen einen Nutzen ziehen kann. Anstieg-Abstieg zieht auch aus dem Vorbedingen einen Nutzen, aber das wird als allgemein nicht getan.

Lösung eines nichtlinearen Systems

Anstieg-Abstieg kann auch verwendet werden, um ein System von nichtlinearen Gleichungen zu lösen. Unten ist ein Beispiel, das zeigt, wie man den Anstieg-Abstieg verwendet, um für drei unbekannte Variablen, x, x, und x zu lösen. Dieses Beispiel zeigt eine Wiederholung des Anstieg-Abstiegs.

Denken Sie ein nichtlineares Gleichungssystem:

:

\begin {Fälle }\

3x_1-\cos (x_2x_3)-\tfrac {3} {2} =0 \\

4x_1^2-625x_2^2+2x_2-1=0 \\

\exp (-x_1x_2) +20x_3 +\tfrac {10\pi-3} {3} =0

\end {Fälle }\

</Mathematik>

nehmen Sie an, dass wir die Funktion haben

:

3x_1-\cos (x_2x_3)-\tfrac {3} {2} \\

4x_1^2-625x_2^2+2x_2-1 \\

\exp (-x_1x_2) +20x_3 +\tfrac {10\pi-3} {3} \\

\end {bmatrix} </Mathematik>

wo:

x_1 \\

x_2 \\

x_3 \\

\end {bmatrix} </Mathematik>

und die objektive Funktion

:::

Mit der anfänglichen Annahme

: x_1 \\ x_2 \\ x_3 \\\end {bmatrix }\

\begin {bmatrix }\

0 \\

0 \\

0 \\\end {bmatrix} </Mathematik>

Wir wissen das

:wo:

Die Jacobian Matrix

:

J_G = \begin {bmatrix }\

3 & \sin (x_2x_3) x_3 & \sin (x_2x_3) x_2 \\

8x_1 &-1250x_2+2 & 0 \\

- x_2\exp {(-x_1x_2)} &-x_1\exp (-x_1x_2) & 20 \\

\end {bmatrix }\</Mathematik>

Dann diese Begriffe an bewertend

:

J_G \left (\mathbf {x} ^ {(0) }\\Recht) = \begin {bmatrix }\

3 & 0 & 0 \\

0 & 2 & 0 \\

0 & 0 & 20

\end {bmatrix }\</Mathematik>und:

- 2.5 \\

- 1 \\

10.472

\end {bmatrix} </Mathematik>

So dass

:

- 7.5 \\

- 2 \\

209.44

\end {bmatrix}. </Mathematik>

und:

F \left (\mathbf {x} ^ {(0) }\\Recht) = 0.5 ((-2.5) ^2 + (-1) ^2 + (10.472) ^2) = 58.456 </Mathematik>

Jetzt muss ein passender solch dass gefunden werden. Das kann mit einigen einer Vielfalt von Liniensuchalgorithmen getan werden. Man könnte auch einfach schätzen, der gibt

:

0.0075 \\

0.002 \\

- 0.20944 \\

\end {bmatrix} </Mathematik>

an diesem Wert, bewertend

:

F \left (\mathbf {x} ^ {(1) }\\Recht) = 0.5 ((-2.48) ^2 + (-1.00) ^2 + (6.28) ^2) = 23.306 </Mathematik>

Die Abnahme von zum Wert des nächsten Schrittes dessen ist eine beträchtliche Abnahme in der objektiven Funktion. Weitere Schritte würden seinen Wert reduzieren, bis eine Lösung des Systems gefunden wurde.

Anmerkungen

Anstieg-Abstieg arbeitet in Räumen jeder Zahl von Dimensionen sogar in unendlich-dimensionalen. Im letzten Fall ist der Suchraum normalerweise ein Funktionsraum, und man berechnet die Ableitung von Gâteaux des funktionellen, das zu minimieren ist, um die Abfallrichtung zu bestimmen.

Der Anstieg-Abstieg kann viele Wiederholungen nehmen, um ein lokales Minimum mit einer erforderlichen Genauigkeit zu schätzen, wenn die Krümmung in verschiedenen Richtungen für die gegebene Funktion sehr verschieden ist. Für solche Funktionen heilt das Vorbedingen, das die Geometrie des Raums ändert, um die Funktionsniveau-Sätze wie konzentrische Kreise zu gestalten, die langsame Konvergenz. Das Konstruieren und die Verwendung des Vorbedingens können jedoch rechenbetont teuer sein.

Der Anstieg-Abstieg kann mit einer Liniensuche verbunden werden, die lokal optimale Schritt-Größe auf jeder Wiederholung findend. Das Durchführen der Liniensuche kann zeitraubend sein. Umgekehrt kann das Verwenden eines festen kleinen schlechte Konvergenz nachgeben.

Methoden, die auf der Methode von Newton und Inversion der Jute mit verbundenen Anstieg-Techniken gestützt sind, können bessere Alternativen sein. Allgemein laufen solche Methoden in weniger Wiederholungen zusammen, aber die Kosten jeder Wiederholung sind höher. Ein Beispiel ist die BFGS Methode, die im Rechnen auf jedem Schritt eine Matrix besteht, durch die der Anstieg-Vektor multipliziert wird, um in eine "bessere" Richtung einzutreten, die mit einem hoch entwickelteren Liniensuchalgorithmus verbunden ist, den "besten" Wert Für äußerst große Probleme zu finden, wo die Computerspeicherprobleme vorherrschen, sollte eine Methode des beschränkten Gedächtnisses wie L-BFGS statt BFGS oder des steilsten Abstiegs verwendet werden.

Anstieg-Abstieg kann als die Methode von Euler angesehen werden, um gewöhnliche Differenzialgleichungen eines Anstieg-Flusses zu lösen.

Ein rechenbetontes Beispiel

Der Anstieg-Abfallalgorithmus wird angewandt, um ein lokales Minimum der Funktion f (x) =x3x+2, mit der Ableitung f (x) =4x9x zu finden. Hier ist eine Durchführung auf der Pythonschlange-Programmiersprache.

1. Von der Berechnung erwarten wir, dass das lokale Minimum an x=9/4 vorkommt

x_old = 0

x_new = 6 # Der Algorithmus fängt an x=6 an

eps = 0.01 # Schritt-Größe

Präzision = 0.00001

def f_prime (x):

kehren Sie 4 * x ** 3 - 9 * x ** 2 zurück

während abs (x_new - x_old)> Präzision:

x_old = x_new

x_new = x_old - eps * f_prime (x_old)

Druck "Lokales Minimum kommt an", x_new vor

</Quelle>

Das obengenannte Stück des Codes muss hinsichtlich der Schritt-Größe gemäß dem System in der Nähe modifiziert werden, und Konvergenz kann schneller durch das Verwenden einer anpassungsfähigen Schritt-Größe gemacht werden. Im obengenannten Fall ist die Schritt-Größe nicht anpassungsfähig. Es bleibt an 0.01 in allen Richtungen, die manchmal die Methode verursachen können, durch das Abweichen vom Minimum zu scheitern.

Erweiterungen

Anstieg-Abstieg kann erweitert werden, um Einschränkungen durch das Umfassen zu behandeln

ein Vorsprung auf den Satz von Einschränkungen. Diese Methode ist

nur ausführbar, wenn der Vorsprung auf einem Computer effizient berechenbar ist. Unter passenden Annahmen,

diese Methode läuft zusammen. Diese Methode ist ein spezifischer Fall des rückwärts gerichteten Algorithmus für Eintönigkeitseinschließungen (der konvexe Programmierung und abweichende Ungleichheit einschließt).

Eine andere Erweiterung des Anstieg-Abstiegs ist wegen Yurii Nesterovs von 1983, und ist nachher verallgemeinert worden. Er stellt eine einfache Modifizierung des Algorithmus zur Verfügung, der schnellere Konvergenz für konvexe Probleme ermöglicht. Spezifisch, wenn die Funktion konvex ist und Lipschitz ist, und es nicht angenommen wird, dass das dann stark konvex ist, wird der Fehler im objektiven Wert, der an jedem Schritt durch die Anstieg-Abfallmethode erzeugt ist, dadurch begrenzt. Mit der Beschleunigungstechnik von Nesterov nimmt der Fehler daran ab.. Die Methode ist bemerkenswert, da sie im Wesentlichen keine schwere Extraberechnung, noch schnellere Konvergenz von Erträgen verlangt.

Siehe auch

• Verbundene Anstieg-Methode
• Stochastischer Anstieg-Abstieg
• Rprop
• Delta-Regel
• Bedingungen von Wolfe
• Das Vorbedingen
• Nelder-Weide-Methode
• Mordecai Avriel (2003). Nichtlineare Programmierung: Analyse und Methoden. Das Veröffentlichen von Dover. Internationale Standardbuchnummer 0-486-43227-0.
• Jan A. Snyman (2005). Praktische Mathematische Optimierung: Eine Einführung in die Grundlegende Optimierungstheorie und Klassischen und Neuen Anstieg-basierten Algorithmen. Springer, der Veröffentlicht. Internationale Standardbuchnummer 0-387-24348-8