Gradientenverfahren

Das Verfahren des steilsten Abstiegs, auch Gradientenverfahren genannt, ist ein Verfahren, das in der Numerik eingesetzt wird, um allgemeine Optimierungsprobleme zu lösen. Dabei geht man (am Beispiel eines Minimierungsproblemes) 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.

Das Verfahren konvergiert oftmals sehr langsam, da es sich dem Optimum entweder mit einem starken Zick-Zack-Kurs nähert oder der Betrag des Gradienten in der Nähe des Optimums sehr klein ist, wodurch die Länge der Iterationsschritte dann ebenfalls sehr klein ist. 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

Das Gradientenverfahren ist einsetzbar, wenn es um die Minimierung einer reellwertigen, differenzierbaren Funktion $f: \mathbb{R}^n \rightarrow \mathbb{R}$ geht; also um das Optimierungsproblem

$\underset{x \in \mathbb{R}^n}{\rm min} \ f(x).$

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

Das Verfahren

Ausgehend von einem Anfangspunkt $x^{(0)}$ wird die Richtung des steilsten Abstiegs durch die Ableitung $d^{(j)} = -\nabla f(x^{(j)})$ bestimmt, wobei $\nabla$ den Nabla-Operator bezeichnet, d.h. den Vektor der partiellen Ableitungen von $f(x^{(j)})$ nach den Variablen $x^{(j)}_1,x^{(j)}_2,...x^{(j)}_n$. Dann wird wie folgt iteriert:

$x^{(j+1)} = x^{(j)} - \alpha^{(j)} \nabla f(x^{(j)}).$

Hier ist $d^{(j)} = - \nabla f(x^{(j)})$ der negative Gradient von $f$, also die Abstiegsrichtung dieses Verfahrens, und $\alpha^{(j)}$ bezeichnet die Schrittweite. Diese Schrittweite muss in jedem Schritt des Iterationsverfahrens bestimmt werden; hierfür gibt es unterschiedliche Möglichkeiten. Eine Methode besteht darin, $\alpha^{(j)}$ durch die Minimierung der Funktion auf dem (eindimensionalen) "Strahl" $x^{(j)}(\alpha)$ zu bestimmen, der ausgehend von $x^{(j)}$ in Richtung des negativen Gradienten zeigt:

$x^{(j)}(\alpha) = x^{(j)} - \alpha \nabla f(x^{(j)}).$

Man berechnet in diesem Fall also die Schrittweite durch $f(x^{(j+1)})=\underset{\alpha >0}{\rm min}\ {f(x^{(j)} - \alpha \nabla f(x^{(j)}))}$. Dies ist ein einfaches, eindimensionales Optimierungsproblem, für das es spezielle Verfahren der Schrittweitenbestimmung gibt.

Spezialfall: Quadratische Funktionale

Typischerweise wird ein Energiefunktional der Form

$J(x) = \frac{1}{2} x^TAx - b^Tx$

minimiert. Dabei ist $A$ eine symmetrisch positiv definite Matrix. Ausgehend von einem Anfangspunkt $x^{(0)}$ wird die Richtung des steilsten Abstiegs natürlich durch die Ableitung $d^{(j)} = -\nabla J(x^{(j)}) = b - Ax^{(j)}$ bestimmt, wobei $\nabla$ den Nabla-Operator bezeichnet. Dann wird wie folgt iteriert

$x^{(j+1)} = x^{(j)} + \alpha^{(j)} d^{(j)} = x^{(j)} - \alpha^{(j)} \nabla J(x^{(j)})$

$\alpha^{(j)}$ bezeichnet die Schrittweite des Verfahrens und kann durch

$\alpha^{(j)} = \min_{t \in \mathbb{R}} J(x^{(j)} + t d^{(j)}) = \frac{{d^{(j)}}^T d^{(j)}}{{d^{(j)}}^T A d^{(j)}}$

berechnet werden. Das Verfahren konvergiert dann für einen beliebigen Startwert gegen einen Wert $x^*$, so dass $J(x^*)$ minimal ist.

Algorithmus in Pseudocode

Eingabe: geeigneter Startvektor $\ x_0$

For k = 0 To n

$d_k = -\nabla J(x_k) = b - Ax_k;$

$\alpha_k = \frac{d^T_k d_k}{d_k^T A d_k}$

$x_{k+1} = x_k + \alpha_k \cdot d_k$

end

Ausgabe: Minimum des Energiefunktionals.

Konvergenzgeschwindigkeit

Das Gradientenverfahren liefert eine Folge $x_k \in \mathbb{R}^n$ mit

$\|x_k - x\|_A \leq \left( \frac{\kappa_2 (A) - 1}{\kappa_2 (A) + 1} \right)^k \|x_0 - x\|_A$

Dabei bezeichnet $\kappa_2$ die Kondition der Matrix $A$.

Literatur

• Andreas Meister: Numerik linearer Gleichungssysteme. 2. Auflage. Vieweg, Wiesbaden 2005, ISBN 3-528-13135-7.