Startseite    
MathematikPoolNRW Projekt Hintergründe Kontakt


Konjugiertes Gradientenverfahren für quadratische Funktionen

Im Fall einer quadratischen Funktion der Gestalt

$f(\vec{x}) = \frac{1}{2} \vec{x} Q \vec{x}^{\ T}- \vec{a} \vec{x}^{\ T} + c_1$
bezeichnet man zwei Tupel $\vec{u}$ und $\vec{v}$ konjugiert, wenn sie bzgl. der Matrix $Q$ orthogonal sind, d.h. wenn gilt
$\vec{u} Q \vec{v}^{\ T} = 0$.

Für das konjugierte Gradientenverfahren wählen wir zunächst einen Startpunkt $\vec{x}_0$ und berechnen den Gradienten $\nabla_f(\vec{x}_0)$ an dieser Stelle.
Wir nehmen an, dass $\vec{x}_0$ nicht schon ein kritischer Punkt von $f$ ist, also $\nabla_f(\vec{x}_0) \ne (0,0)$ gilt.
Dann gibt es eine Richtung $\vec{d}_0 \ne (0,0)$ mit der Eigenschaft $\nabla_f(\vec{x}_0)^T \vec{d}_0 \ne 0$.
Wir untersuchen nun das Verhalten von $f$ auf dem Halbstrahl, der bei $\vec{x}_0$ beginnt und in Richtung von $\vec{d}_0$ verläuft.
Dazu betrachten wir die Funktion einer Variablen $h(t) := f(\vec{x}_0+t \vec{d}_0)$, $t \ge 0$.
Ist $\vec{d}_0$ ein Einheitsvektor (Länge 1), so gibt $t$ die Schrittweite an, um die wir uns von $\vec{x}_0$ entfernen.
Man nennt $\vec{d}_0$ nun eine Abstiegsrichtung für $f$ im Punkte $\vec{x}_0$, falls $\nabla_f(\vec{x}_0)^T \vec{d}_0 < 0$ gilt.
Ist $\vec{d}_0$ eine Abstiegsrichtung, so gilt $h(t)<f(\vec{x}_0)$ für alle hinreichend kleinen $t>0$.
Eine sinnvolle Wahl für die Schrittweite ergibt sich, wenn man $h(t)$ minimiert.
Wir setzen nun $\vec{d}_0=-\nabla_f(\vec{x}_0)$ und bestimmen das Minimum $t_1>0$ der Funktion $h(t) = f(\vec{x}_0+t \vec{d}_0)$.
Es ist offensichtlich, dass $\vec{d}_0=-\nabla_f(\vec{x}_0)$ eine Abstiegsrichtung liefert, denn $\nabla_f(\vec{x}_0) \vec{d}_0 = -\vert\vert\nabla_f(\vec{x}_0)\vert\vert^2 < 0$.

Beispiel:   Zur Minimierung der Funktion
$ f(\vec{x})= \frac{1}{2} \vec{x} \left( \begin{array}{cc} 2& 1\cr 1& 2 \end{array} \right) \vec{x}^{\ T} - (-2,0)\vec{x}^{\ T} + (-1) $
wählen wir z.B. den Startpunkt $\vec{x}_0=(0,0)$.
Der Gradient an dieser Stelle ist $\nabla_f(0,0)=(2,0)$ und wir müssen $f$ von $(0,0)$ aus in die Richtung $\vec{d}_0=-(2,0)$ minimieren.
D.h. wir berechnen das Minimum der Funktion $h(t)=f((0,0)+t \cdot (-2,0))=f(-2t,0)=4t^2-4t-1$,
welches wir in der Nullstelle $t_1=\frac{1}{2}$ der Ableitung $h'(t)=8t-4$ finden.


Wir erhalten einen neuen Iterationspunkt $\vec{x}_1 = \vec{x}_0+t_1 \vec{d}_0$ und berechnen den Gradienten an dieser Stelle $\vec{x}_1 $.
Als nächstes müssen wir ein zu $\vec{d}_0$ konjugiertes Tupel $\vec{d}_1$ bestimmen und dann die Funktion $f$ ausgehend von $\vec{x}_1 $ entlang dieser Richtung $\vec{d}_1$ minimieren, d.h. das Minimum $t_2 \ge 0 $ der Funktion $f(\vec{x}_1+t \vec{d}_1)$ bestimmen.
Man kann zeigen, dass der neue Iterationspunkt $\vec{x}_2 = \vec{x}_1 + t_2 \vec{d}_1$ dann schon das gesuchte strenge Minimum $\vec{x}^{\ *}$ der quadratischen Funktion $f$ ist.
Ein zu $\vec{d}_0$ konjugiertes Tupel $\vec{d}_1$ erhalten wir, indem wir
$\vec{d}_1 = -\nabla_f(\vec{x}_1)+ \alpha_1 \vec{d}_0$ mit $\alpha_1 = \frac{ (\nabla_f(\vec{x}_1))(\nabla_f(\vec{x}_1))^T} { (\nabla_f(\vec{x}_0)) (\nabla_f(\vec{x}_0))^T}$
setzen.


Zusammenfassend erhalten wir den folgenden Algorithmus:

  Konjugiertes Gradientenverfahren für quadratische Funktionen:
     Wähle einen Startpunkt $\vec{x}_0$ und setze $\vec{d}_0=-\nabla_f(\vec{x}_0)$;
     Wiederhole für $k=1,2$
          Bestimme das Minimum$t_k>0$ der Funktion $h(t)=f(\vec{x}_{k-1}+t\vec{d}_{k-1})$;
          Setze $\vec{x}_k = \vec{x}_{k-1} + t_k \vec{d}_{k-1}$;
          Setze $\vec{d}_k = - \nabla_f(\vec{x}_k)+ \alpha_k \vec{d}_{k-1}$, wobei $\alpha_k = \frac{ (\nabla_f(\vec{x}_k))(\nabla_f(\vec{x}_k))^T} { (\nabla_f(\vec{x}_{k-1})) (\nabla_f(\vec{x}_{k-1}))^T}$;
alt=Java nicht aktiv !


Wegen $\nabla_f(\vec{x}_{k-1}) = \vec{x}_{k-1}Q - \vec{a}$ und
\begin{eqnarray*} h'(t) &=& \nabla_f(\vec{x}_{k-1}+t\vec{d}_{k-1}) (\vec{d}_{k... ...c{x}_{k-1})(\vec{d}_{k-1})^T + t\vec{d}_{k-1}Q(\vec{d}_{k-1})^T \end{eqnarray*}

erhält man die (eindeutig bestimmte) exakte Schrittweite

$t_k := -\frac{\nabla_f(\vec{x}_{k-1})(\vec{d}_{k-1})^T} {\vec{d}_{k-1}Q(\vec{d}_{k-1})^T}$.
In dieser Gleichung ist der Nenner grösser Null (da $Q$ positiv definit ist) und der Zähler kleiner Null (da $\vec{d}_{k-1}$ Abstiegsrichtung ist).
Man erhält also wie gewünscht einen Wert grösser Null für $t_k$.


Beispiel (Fortsetzung):
Unser neuer Iterationspunkt ist nun $\vec{x}_1 =(0,0)+\frac{1}{2}(-2,0)=(-1,0)$.
Der Gradient an dieser Stelle ist $\nabla_f(-1,0)=(0,-1)$.
Für $\alpha_k$ berechnen wir $\frac{0^2 \ + \ (-1)^2}{(-2)^2 \ + \ 0^2} = \frac{1}{4}$ und müssen nun $f$ von $\vec{x}_1 $ aus
in die zu $\vec{d}_0$ konjugierte Richtung $\vec{d}_1= (0,1) + \frac{1}{4} (-2,0) = (-\frac{1}{2},1)$ minmieren,
d.h. das Minimum der Funktion $h(t)=f((-1,0) + t \cdot (-\frac{1}{2},1))$ bestimmen.
Dazu berechnen wir die Nullstelle $t_2=-\frac{(0,-1)(-\frac{1}{2},1)^T}{(0,\frac{3}{2})(-\frac{1}{2},1)^T} =\frac{2}{3}$ der ersten Ableitung $h'(t)$.
Der Punkt $\vec{x}^{\ *} = \vec{x}_2 = (-1,0) + \frac{2}{3}(-\frac{1}{2},1) = (-\frac{4}{3},\frac{2}{3})$ ist dann das gesuchte strenge Minimum von $f$.