Startseite    
MathematikPoolNRW Projekt Hintergründe Kontakt


Konjugiertes Gradientenverfahren für differenzierbare Funktionen

Im Fall von nichtquadratischen, aber zweimal stetig differenzierbaren Funktionen $f$ begnügen wir uns damit, kritische Punkte von $f$ zu bestimmen.
Dabei ist eine Funktion zweimal stetig differenzierbar, wenn sowohl der Gradient, als auch die Hessematrix in allen Punkten $(x_1,x_2)$ stetige Funktionen sind.

Dazu wenden wir einfach das konjugierte Gradientenverfahren solange an, bis ein Abbruchkriterium (z.B. eine bestimmte Anzahl $kmax>0$ an Iterationsschritten oder eine obere Schranke $0< \epsilon < 1$ für die Norm $\vert\vert\nabla_f(\vec{x})\vert\vert:=\vert\vert\vec{g} \vert\vert :=\sqrt{g_1^{\ 2}+g_2^{\ 2}}$ des Gradienten) erreicht ist.

Damit erhalten wir den Algorithmus:
 
  Konjugiertes Gradientenverfahren für differenzierbare Funktionen:
     Wähle einen Startpunkt $\vec{x}_0$ und $\epsilon > 0$ und setze $\vec{d}_0=-\nabla_f(\vec{x}_0)$ und $k=0$;
     Solange $\vert\vert\nabla_f(\vec{x}_k)\vert\vert > \epsilon$ und $k < kmax$ wiederhole
          $k=k+1$;
          Bestimme ein 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}$;

Für die Wahl von $\alpha_k$ gibt es verschiedene Vorschläge:
\begin{displaymath} \makebox[42mm][l]{\emph{Hestenes-Stiefel (1952)}:}\hspace*{... ...{d}_{k-1} (\nabla_f(\vec{x}_{k}) - \nabla_f(\vec{x}_{k-1}))^T} \end{displaymath} alt=Java nicht aktiv !
\begin{displaymath} \makebox[42mm][l]{\emph{Fletcher-Reeves (1964)}:}\hspace*{5... ...))^T} {(\nabla_f(\vec{x}_{k-1})) (\nabla_f(\vec{x}_{k-1}))^T} \end{displaymath} alt=Java nicht aktiv !
\begin{displaymath} \makebox[42mm][l]{\emph{Polak-Ribiere (1969)}:} \hspace*{5m... ...)^T} {(\nabla_f(\vec{x}_{k-1})) (\nabla_f(\vec{x}_{k-1}))^T} \end{displaymath} alt=Java nicht aktiv !



Allerdings ist die Minimierung der Funktion $h(t)=f(\vec{x}_{k-1}+t\vec{d}_{k-1})$ hier nicht mehr so einfach wie im quadratischen Fall.
Um das Minimum $t_k>0$ zu bestimmen, bietet sich z.B. das (eindimensionale) Newton-Verfahren an,
d.h. wir berechnen eine Folge von Werten $t_{k,v} \ (v=1,2,...)$ gemäss
\begin{displaymath}t_{k,v+1} = t_{k,v} - \frac{h'(t_{k,v})}{h''(t_{k,v})}\end{displaymath}
ausgehend vom Startwert $t_{k,0}=0$.
Dieses Verfahren ist jedoch nicht sehr sicher, da es uns auch ein Maximum oder auch ein $t_k \le 0$ liefern kann.
Wir werden daher im folgenden ein anderes Verfahren zur Schrittweitenbestimmung vorstellen,
welches wir anwenden, falls uns das Newton-Verfahren ein Maximum oder ein $t_k \le 0$ liefert.
Dieses Verfahren bestimmt ein $t_k>0$ so, dass die beiden Bedingungen
$ \begin{array}{lrcllccccc} (W1) & h(t) & \le & h(0)+p_1 \cdot t \cdot h'(0) &... ...h'(t)\vert & \le & p_2 \cdot \vert h'(0)\vert &mit&p_1&<&p_2&<&1 \end{array} $
erfüllt sind. (in der Praxis wird z.B. $p_1=10^{-4}$ und $p_2=10^{-1}$ gesetzt)
Die Bedingungen (W1) und (W2) werden als strenge Wolfe-Powell-Bedingungen bezeichnet.
Für die erste Ableitung der Funktion $h(t)$ gilt $h'(t) = \nabla_f(\vec{x}_{k-1}+t\vec{d}_{k-1}) (\vec{d}_{k-1})^T$
und für die zweite $h''(t) = \vec{d}_{k-1} H_f(\vec{x}_{k-1}+t\vec{d}_{k-1}) (\vec{d}_{k-1})^T$.

  Line-Search Algorithmus zur Schrittweitenbestimmung:
     Setze $t_0=0$, $t_1=1$ und $i=0$;
     Solange $i<imax$ wiederhole
          $i=i+1$
          Falls $h(t_i)>h(0)+p_1 \cdot t_i \cdot h'(0)$ oder ( $h(t_i) \ge h(t_{i-1})$ und $i>1$)
               Setze $t_k = Zoom(t_{i-1},t_i)$ und stoppe;
          Falls $h'(t_i) \ge 0$
               Setze $t_k = Zoom(t_i,t_{i-1})$ und stoppe;
          Falls $\vert h'(t_i)\vert \le p_2 \cdot \vert h'(0)\vert$
               Setze $t_k = t_i$ und stoppe;
          Setze $t_{i+1} = 2 \cdot t_i$;
     Setze $t_k = 0$ und stoppe;

  Zoom($t_{lo}$, $t_{hi}$):
     Setze $j=0$;
     Solange $j<jmax$ wiederhole
          $j=j+1$
          Setze $c=(h(t_{hi})-h(t_{lo})-(t_{hi}-t_{lo}) \cdot h'(t_{lo}))\ /\ (t_{hi}-t_{lo})^2$;
          Falls $c>0$
               Setze $t_j=t_{lo} - h'(t_{lo})/(2c)$;
          sonst
               Setze $t_j=(t_{lo}+t_{hi})/2$;
          Falls $h(t_j)>h(0)+p_1 \cdot t_j \cdot h'(0)$ oder $h(t_j) \ge h(t_{lo})$
               Setze $t_{hi}=t_j$;
          sonst
               Falls $h'(t_j) \cdot (t_{hi}-t_{lo}) \ge 0$
                    Setze $t_{hi}=t_{lo}$;
               Falls $\vert h'(t_j)\vert \le p_2 \cdot \vert h'(0)\vert$
                    Setze $t_k = t_j$ und stoppe;
               Setze $t_{lo} = t_j$;
     Setze $t_k = 0$ und stoppe;

Es kann gezeigt werden, dass dieser Algorithmus mit einer Schrittweite $t_k>0$, welches die strengen Wolfe-Powell-Bedingungen
erfüllt, terminiert, falls $\vec{d}_{k-1}$ eine Abstiegsrichtung ist, entlang der $f$ nach unten beschränk ist.
Falls der Algorithmus jedoch mit $t_k = 0$ terminiert, so ist entweder $\vec{d}_{k-1}$ keine Abstiegsrichtung
oder $h(t)=f(\vec{x}_{k-1}+t\vec{d}_{k-1})$ nicht nach unten beschränkt.
Da das konjugierte Gradientenverfahren aber immer Abstiegsrichtungen $\vec{d}_{k-1}$ berechnet, muss der zweite Fall gelten.
Dann ist aber auch die Funktion $f$ in Richtung von $\vec{d}_{k-1}$ nicht nach unten beschränkt und das Gradientenverfahren bricht erfolglos
ab, d.h. vom Startvektor $\vec{x}_{0}$ aus kann das Verfahren kein strenges lokales Minimum finden.