Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
Mathematik-Online-Kurs: Differentialrechnung mehrerer Veränderlicher - Ableitungsregeln

Methode des steilsten Abstiegs

[vorangehende Seite] [nachfolgende Seite] [Gesamtverzeichnis][Seitenübersicht]

Die Methode des steilsten Abstiegs dient zur Minimierung multivariater Funktionen $ f(x_1,\ldots,x_n)$. Zur Durchführung eines Iterationsschrittes $ x\to y$ wird zunächst der negative Gradient

$\displaystyle d = -\operatorname{grad}f(x) $

als lokal beste Abstiegsrichtung berechnet. Dann wird $ y$ als eine Minimalstelle von $ f$ in Richtung von $ d$ bestimmt:

$\displaystyle f(y) = \min_{t\ge 0} f(x+td) \,. $

\includegraphics[width=0.55\linewidth]{Bild_Steilster_Abstieg_Aussage}

Wie in der Abbildung illustriert, ist die Suchrichtung orthogonal zu der Niveaumenge durch $ x$ und berührt eine Niveaumenge zu einem kleineren Funktionswert in $ y$.

Die Konvergenz der durch die Methode des steilsten Abstiegs erzeugten Folge $ x_0,x_1,\ldots$ kann unter sehr allgemeinen Voraussetzungen gezeigt werden. Hinreichend ist, dass $ f$ nach unten beschränkt ist und $ \operatorname{grad}f$ in einer Umgebung $ U$ der Menge $ \{x: f(x) \leq f(x_0)\}$ Lipschitz-stetig ist, d.h.

$\displaystyle \Vert \operatorname{grad}f(x) - \operatorname{grad}f(\tilde x) \Vert \le L \Vert x-\tilde x\Vert,\quad x,\tilde x\in U \,. $

Dann gilt

$\displaystyle \sum_{\ell=0}^\infty \Vert\operatorname{grad}f(x_\ell)\Vert^2 < \infty \,; $

insbesondere ist $ \Vert\operatorname{grad}f(x_\ell)\Vert$ eine Nullfolge.

Dies impliziert insbesondere, dass jeder Häufungspunkt der Folge $ x_0,x_1,\ldots$ ein kritischer Punkt von $ f$ ist. Dass es sich um ein lokales Minimum handelt ist statistisch gesehen fast sicher, kann jedoch nicht zwingend gefolgert werden.

In dem Algorithmus braucht die eindimensionale Minimierung nur näherungsweise durchgeführt werden. Die Suchrichtung $ d$ muss nicht als der negative Gradient gewählt, und eine globale Minimalstelle $ y$ nicht bestimmt werden. Entscheidend für die Konvergenz ist lediglich, dass in jedem Iterationsschritt eine Reduktion des Funktionswertes proportional zu $ \Vert\operatorname{grad}f(x)\Vert^2$ erreicht wird.

Download:

(Dateityp: .m, 312 ,  22.06.2016)

Für eine quadratische Funktion

$\displaystyle f(x) = \frac{1}{2} x^{\text{t}} A x - b^{\text{t}} x $

mit einer symmetrischen positiv definiten Matrix $ A$ hat ein Iterationsschritt $ x\to y$ der Methode des steilsten Abstiegs die Form

$\displaystyle y = x + t d,\ d = -$grad$\displaystyle f(x) = b - Ax \,. $

Das Minimum von

\begin{displaymath} \begin{array}{rcl} f(x+td) &=& \frac{1}{2} (x+td)^{\text{t... ...,t^2 + (x^{\text{t}}Ad - b^{\text{t}}d)\,t + c \end{array} \end{displaymath}

lässt sich in diesem Fall explizit angeben. Durch Nullsetzen der Ableitung nach $ t$ erhält man

$\displaystyle 0=d^{\text{t}}Ad\, t - (\underbrace{b-Ax}_{d})^{\text{t}}d $

und somit die Formel

$\displaystyle t = \frac{d^{\text{t}} d}{d^{\text{t}}Ad} $

für den Halbgeradenparameter.

Wie die Abbildung zeigt, kann es zu unerwünschten Oszillationen kommen, wenn $ A$ Eigenwerte stark unterschiedlicher Größenordnung besitzt. Ein extremes Beispiel erhält man für

$\displaystyle A = \left(\begin{array}{cc} 1&0 \\ 0&100 \end{array}\right),\quad b = \left(\begin{array}{c} 0 \\ 0 \end{array}\right) \,. $

Für $ x=(\begin{array}{cc} c & 1 \end{array})^{\text{t}}$ ist

$\displaystyle d = -\,\left(\begin{array}{c} c \\ 100 \end{array}\right),\quad Ad = -\, \left(\begin{array}{c} c \\ 10^4 \end{array}\right) $

und

$\displaystyle d^{\text{t}}d = c^2 + 10^4,\quad d^{\text{t}}Ad = c^2 + 10^6,\quad t = \frac{c^2 + 10^4}{c^2 + 10^6} \,. $

Damit folgt

$\displaystyle y= \left(\begin{array}{c} c \\ 1 \end{array}\right) - \frac{... ...}{c^2 + 10^6} \left(\begin{array}{c} 10^4/c \\ -1 \end{array}\right) \,. $

Konkret erhält man für $ c=100$

$\displaystyle y = \frac{99}{101} \left(\begin{array}{c} x_1 \\ -x_2 \end{array}\right) \,. $

Man erkennt, dass in jedem Iterationsschritt der Abstand zum Minimum im Ursprung nur um weniger als $ 1\%$ verringert wird.

[vorangehende Seite] [nachfolgende Seite] [Gesamtverzeichnis][Seitenübersicht]
  automatisch erstellt am 5.1.2017