Kurs:Optimierung II/Das Gradientenverfahren

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Nachdem nun eine Reihe von Schrittweitenregeln zur Verfügung stehen, kehren wir wieder zu dem eigentlichen Problem zurück, zur Lösung der unrestringierten Optimierungsaufgabe

wobei wir hier generell die Voraussetzungen (V1) - (V3) aus Abschnitt 2.3 als erfüllt ansehen. Ziel ist es, einen kritischen Punkt von zu bestimmen, welcher möglichst ein lokaler Minimalpunkt von sein sollte, aber im Einzelfall auch ein Sattelpunkt von sein mag. Dabei gehen wir von dem Modellalgorithmus 2.5 aus, den wir uns mit einer für das ganze Verfahren fest gewählten Schrittweitenregel verbunden denken. In diesem und den folgenden Kapiteln 5 bis 8 wollen wir nun spezielle Verfahren diskutieren, indem wir unterschiedliche Vorschriften für die Richtungswahl im Algorithmus festlegen.

Das einfachste aller Verfahren zur Lösung von ist das Gradientenverfahren, bei dem man in einem nichtkritischen Punkt die Richtung

wählt. Offenbar ist in diesem Fall und damit gemäß Lemma 2.2 Abstiegsrichtung für in (vgl. Beispiel 2.3). Das Gradientenverfahren mit einer semieffizienten Schrittweitenregel lautet demnach:

Algorithmus 4.1 (Gradientenverfahren)[Bearbeiten]

(0) Wähle eine semieffiziente Schrittweitenregel und ein . Setze .
(1) Falls ist, stop! ( ist kritische Lösung von Problem .)
(2) Setze .
(3) Bestimme eine Schrittweite gemäß der Schrittweitenregel und setze
(4) Setze und gehe nach (1).

Im Hinblick auf die folgenden Konvergenzaussagen können wir das Gradientenverfahren tatsächlich mit einer beliebigen semieffizienten Schrittweitenregel verknüpfen. Denn in diesem Fall sind mit

die Voraussetzungen von Satz 2.17 erfüllt, so dass wir aus diesem Satz unmittelbar die folgende Konvergenzaussage schließen können.

Satz 4.2[Bearbeiten]

Die Voraussetzungen (V1) - (V3) seien erfüllt. Bricht Algorithmus 4.1 nicht nach endlich vielen Schritten ab, so erzeugt er eine unendliche Folge , für welche gilt:
(i) Jeder Häufungspunkt von ist kritische Lösung von .
(ii) Besitzt genau eine kritische Lösung , so ist .
(iii) Ist zusätzlich (V4) erfüllt, so folgt und gilt dann mit der Konstante aus (2.24) für die Schrittweitenregel und mit einem
(4.1)
sowie
(4.2)

Das Gradientenverfahren konvergiert also für jede der in Kapitel 3 vorgestellten Schrittweitenregeln. Sind die Voraussetzungen (V1) - (V4) erfüllt, so konvergiert sogar die gesamte Iteriertenfolge und konvergiert die zugehörige Folge der Funktionswerte mindestens linear. Langsame Konvergenz ist offenbar zu befürchten, wenn die Konstante sehr klein ist ("zu befürchten", da die Abschätzung in (4.1) ja im Einzelfall sehr grob sein kann). Die Konstante hängt dabei von der gewählten Schrittweitenregel ab und kann den entsprechenden Sätzen in Kapitel 3 entnommen werden. Insbesondere hat man für die exakten Schrittweiten gemäß Satz 3.3

(4.3)

Für diese Schrittweiten muss man also mit langsamer Konvergenz des Gradientenverfahrens rechnen, wenn die Zahl sehr klein ist.

Wir wollen nun das Gradientenverfahren mit einer exakten Schrittweite noch genauer für den Fall untersuchen, dass es auf eine quadratische Funktion

(4.4)

mit positiv definiter Matrix angewendet wird. Gemäß (2.14) ist in diesem Fall die Kondition von bezüglich der Spektralnorm und implizieren daher (4.1) und (4.2) mit (4.3) die Abschätzungen

und

Diese Abschätzungen können noch etwas verbessert werden zu

(4.5)

und mit einer Konstante zu

(4.6)

(Übung!). Die Abschätzungen beschreiben zwar nur ein mögliches "worst case" Verhalten des Gradientenverfahrens, sein reales Verhalten kommt diesem jedoch leider oft sehr nahe. Es muss demnach mit um so langsamerer Konvergenz der Folge der Funktionswerte gerechnet werden, je größer die Kondition von ist.

Die Konvergenzaussagen für quadratische Funktionen gelten qualitativ auch für jeden lokalen Minimalpunkt einer beliebigen Funktion , in dem die hinreichenden Optimalitätsbedingungen zweiter Ordnung aus Satz 1.14 erfüllt sind. Denn in einem solchen Fall kann in der Umgebung von durch das quadratische Taylor-Polynom

(4.7)

mit positiv definiter Matrix angenähert werden. Langsame Konvergenz des Gradientenverfahrens ist dann für zu erwarten, wenn die Kondition der Hesse-Matrix groß ist.

Beispiel 4.3[Bearbeiten]

Das Gradientenverfahren mit exakter Schrittweite sei auf die quadratische Funktion

angewendet. Das Problem hat für dieses die Lösung und den Minimalwert . Die Kondition von ist mit in diesem Fall nicht sehr groß (vgl. Beispiel 2.7). Für die in (4.5) und (4.6) vorkommende Konstante ergibt sich damit aber

was auf mögliche langsame Konvergenz hinweist.

Wir wollen uns die Iteriertenfolge genauer anschauen. Es ist in diesem Fall

womit wir gemäß (3.5) für die Minimumschrittweite erhalten:

Mit folgt weiter

für

Startet man nun das Gradientenverfahren mit , so ist und damit

Weiter ist damit und somit

Der Fortschritt des Gradientenverfahrens dürfte also sehr gering ausfallen. Konkret ergeben sich für die ersten Iterierten die in unten stehender Tabelle angegebenen Zahlen. Startet man allerdings das Gradientenverfahren mit dem Punkt und , so ist und damit . Die Lösung des Problems wird also in diesem Fall mit einer Iteration des Verfahrens erreicht.


Das im letzten Beispiel gezeigte Verhalten des Gradientenverfahrens kann man in der Praxis häufig beobachten. Nachdem das Verfahren, wenn man entfernt von der Lösung startet, über einige Iterationen hinweg manchmal gute Fortschritte erzielt, kann es in der Nähe einer Lösung oft inakzeptabel langsam werden. (Mit einer Iteration ist hier - und analog bei anderen Verfahren - ein Durchlauf der Schritte (1) bis (4) des Algorithmus 4.1 gemeint.) Dennoch gab es bis ca. 1960 zum Gradientenverfahren keine nennenswerte Alternative.