Gradientenverfahren

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.

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 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[Bearbeiten]

Ausgehend von einem Anfangspunkt x^{(0)} wird die Richtung des steilsten Abstiegs durch die Ableitung d^{(j)} = -\nabla f\left(x^{(j)}\right) bestimmt, wobei \nabla den Nabla-Operator bezeichnet, d.h. den Vektor der partiellen Ableitungen von f\left(x^{(j)}\right) 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\left(x^{(j)}\right).

Hier ist d^{(j)} = - \nabla f\left(x^{(j)}\right) 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\left(x^{(j)}\right).

Man berechnet in diesem Fall also die Schrittweite durch

f\left(x^{(j+1)}\right)=\underset{\alpha >0}{\min}\ {f\left(x^{(j)} - \alpha\nabla f\left(x^{(j)}\right)\right)}.

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

Spezialfall: Quadratische Funktionale[Bearbeiten]

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\left(x^{(j)}\right) = 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\left(x^{(j)}\right)

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

 \alpha^{(j)} = \underset{t \in \mathbb{R}}{\operatorname{arg\,min}} J\left(x^{(j)} + t d^{(j)}\right) = \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[Bearbeiten]

Eingabe: geeigneter Startvektor  x_0 
    
for k = 0 to n-1
        d_k = -\nabla J(x_k) = b - Ax_k; 
        \alpha_k = \dfrac{d^T_k d_k}{d_k^T A d_k}
        x_{k+1} = x_k + \alpha_k \cdot d_k 
end

Ausgabe: Minimalstelle x_n des Energiefunktionals.

Konvergenzgeschwindigkeit[Bearbeiten]

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 \|y\|_A = \sqrt{\langle y, A y\rangle} die sogenannte Energienorm bezüglich A und  \kappa_2(A) die Kondition der Matrix  A bezüglich der Spektralnorm.

Literatur[Bearbeiten]

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