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:
- (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.
- 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)
![{\displaystyle 0\leq f(x^{k+1})-f(x^{*})\leq (1-2\beta \vartheta )\left[f(x^{k})-f(x^{*})\right],\quad k\in \mathbb {N} _{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce0ea505f9433446311b5de1edb682431e0921a5)
- 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
![{\displaystyle 0\leq f(x^{k+1})-f(x^{*})\leq \left({\frac {\operatorname {cond} (Q)-1}{\operatorname {cond} (Q)}}\right)\left[f(x^{k})-f(x^{*})\right],\quad k\in \mathbb {N} _{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/057115819189cad9b9dc496ea9d45da396c07a51)
und

Diese Abschätzungen können noch etwas verbessert werden zu
- (4.5)
![{\displaystyle f(x^{k+1})-f(x^{*})\leq \left({\frac {\operatorname {cond} (Q)-1}{\operatorname {cond} (Q)+1}}\right)^{2}\left[f(x^{k})-f(x^{*})\right],\quad k\in \mathbb {N} _{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50bcf545d99a4d528098c537cca7c61aab5206d1)
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.
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.