Konjugiertes Gradientenverfahren für differenzierbare Funktionen
Im Fall von nichtquadratischen, aber zweimal stetig differenzierbaren Funktionen begnügen wir uns damit, kritische Punkte von zu bestimmen.
Dabei ist eine Funktion zweimal stetig differenzierbar, wenn sowohl der Gradient, als auch die Hessematrix in allen Punkten stetige Funktionen sind.
Dazu wenden wir einfach das konjugierte Gradientenverfahren solange an, bis ein Abbruchkriterium (z.B. eine bestimmte Anzahl an Iterationsschritten oder eine obere Schranke für die Norm des Gradienten) erreicht ist.
Damit erhalten wir den Algorithmus:
Konjugiertes Gradientenverfahren für differenzierbare Funktionen:
|
Wähle einen Startpunkt und
und setze
und ;
Solange und wiederhole ; Bestimme ein Minimum der Funktion ; Setze ; Setze ; |
Für die Wahl von gibt es verschiedene Vorschläge:
Allerdings ist die Minimierung der Funktion hier nicht mehr so einfach wie im quadratischen Fall.
Um das Minimum zu bestimmen, bietet sich z.B. das (eindimensionale) Newton-Verfahren an,
d.h. wir berechnen eine Folge von Werten gemäss
Dieses Verfahren ist jedoch nicht sehr sicher, da es uns auch ein Maximum oder auch ein 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 liefert.
Dieses Verfahren bestimmt ein so, dass die beiden Bedingungen
Die Bedingungen (W1) und (W2) werden als strenge Wolfe-Powell-Bedingungen bezeichnet.
Für die erste Ableitung der Funktion gilt
und für die zweite .
Line-Search Algorithmus zur Schrittweitenbestimmung:
|
Setze , und ;
Solange wiederhole Falls oder ( und ) Setze und stoppe; Falls Setze und stoppe; Falls Setze und stoppe; Setze ; Setze und stoppe; |
Zoom(, ): Setze ; Solange wiederhole Setze ; Falls Setze ; sonst Setze ; Falls oder Setze ; sonst Falls Setze ; Falls Setze und stoppe; Setze ; Setze und stoppe; |
Es kann gezeigt werden, dass dieser Algorithmus mit einer Schrittweite ,
welches die strengen Wolfe-Powell-Bedingungen
erfüllt, terminiert, falls eine Abstiegsrichtung ist,
entlang der nach unten beschränk ist.
Falls der Algorithmus jedoch mit terminiert, so ist entweder
keine Abstiegsrichtung
oder
nicht
nach unten beschränkt.
Da das konjugierte Gradientenverfahren aber immer Abstiegsrichtungen
berechnet, muss der zweite Fall gelten.
Dann ist aber auch die Funktion in Richtung von nicht nach unten
beschränkt und das Gradientenverfahren bricht erfolglos
ab, d.h. vom Startvektor
aus kann das Verfahren kein strenges lokales Minimum finden.