Kurs:Optimierung II/Das Gradientenverfahren

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

$(P):\text{ Minimiere }f(x)\text{ über alle }x\in {ℝ}^n,$

wobei wir hier generell die Voraussetzungen (V1) - (V3) aus Abschnitt 2.3 als erfüllt ansehen. Ziel ist es, einen kritischen Punkt von $f$ zu bestimmen, welcher möglichst ein lokaler Minimalpunkt von $f$ sein sollte, aber im Einzelfall auch ein Sattelpunkt von $f$ 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 $(P)$ ist das Gradientenverfahren, bei dem man in einem nichtkritischen Punkt $x^k$ die Richtung

$p^k:=-\mathrm{\nabla }f(x^k)$

wählt. Offenbar ist in diesem Fall $\mathrm{\nabla }f(x^k{)}^T{p}^k<0$ und damit $p^k$ gemäß Lemma 2.2 Abstiegsrichtung für $f$ in $x^k$ (vgl. Beispiel 2.3). Das Gradientenverfahren mit einer semieffizienten Schrittweitenregel lautet demnach:

Algorithmus 4.1 (Gradientenverfahren)

(0) Wähle eine semieffiziente Schrittweitenregel und ein $x^0\in {ℝ}^n$. Setze $k:=0$.

(1) Falls $\mathrm{\nabla }f(x^k)=0$ ist, stop! ($x^k$ ist kritische Lösung von Problem $(P)$.)

(2) Setze $p^k:=-\mathrm{\nabla }f(x^k)$.

(3) Bestimme eine Schrittweite $t_k>0$ gemäß der Schrittweitenregel und setze

$x^{k+1}:=x^k+t_k{p}^k.$

(4) Setze $k:=k+1$ 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

$H_k:=I,m=M:=1$

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

Die Voraussetzungen (V1) - (V3) seien erfüllt. Bricht Algorithmus 4.1 nicht nach endlich vielen Schritten ab, so erzeugt er eine unendliche Folge $\left\{x^k\right\}$, für welche gilt:

(i) Jeder Häufungspunkt von $\left\{x^k\right\}$ ist kritische Lösung von $(P)$.

(ii) Besitzt $(P)$ genau eine kritische Lösung $x^{*}$, so ist $\underset{k\to \mathrm{\infty }}{\lim }{x}^k=x^{*}$.

(iii) Ist zusätzlich (V4) erfüllt, so folgt $\underset{k\to \mathrm{\infty }}{\lim }{x}^k=x^{*}$ und gilt dann mit der Konstante $\vartheta >0$ aus (2.24) für die Schrittweitenregel und mit einem $c>0$

(4.1) $0\le f(x^{k+1})-f(x^{*})\le (1-2\beta \vartheta )[f(x^k)-f(x^{*})],k\in {\mathbb{N}}_0$

sowie

(4.2) $\Vert x^k-x^{*}\Vert \le c{\left(\sqrt{1-2\beta \vartheta }\right)}^k,k\in {\mathbb{N}}_0.$

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 $2\beta \vartheta$ sehr klein ist ("zu befürchten", da die Abschätzung in (4.1) ja im Einzelfall sehr grob sein kann). Die Konstante $\vartheta$ 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) $\vartheta :={\vartheta }_M={\vartheta }_C=\frac{1}{2\gamma }$

Für diese Schrittweiten muss man also mit langsamer Konvergenz des Gradientenverfahrens rechnen, wenn die Zahl $\beta /\gamma$ 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) $f(x):=\frac{1}{2}{x}^{T}Qx+c^{T}x+\alpha ,x\in {ℝ}^n$

mit positiv definiter Matrix $Q$ angewendet wird. Gemäß (2.14) ist in diesem Fall $\mathrm{cond}(Q)=\gamma /\beta$ die Kondition von $Q$ bezüglich der Spektralnorm und implizieren daher (4.1) und (4.2) mit (4.3) die Abschätzungen

$0\le f(x^{k+1})-f(x^{*})\le \left(\frac{\mathrm{cond}(Q)-1}{\mathrm{cond}(Q)}\right)[f(x^k)-f(x^{*})],k\in {\mathbb{N}}_0$

und

$\Vert x^k-x^{*}\Vert \le c{\left(\sqrt{\frac{\mathrm{cond}(Q)-1}{\mathrm{cond}(Q)}}\right)}^k,k\in {\mathbb{N}}_0.$

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

(4.5) $f(x^{k+1})-f(x^{*})\le {\left(\frac{\mathrm{cond}(Q)-1}{\mathrm{cond}(Q)+1}\right)}^2[f(x^k)-f(x^{*})],k\in {\mathbb{N}}_0$

und mit einer Konstante $\tilde{c}>0$ zu

(4.6) $\Vert x^k-x^{*}\Vert \le \tilde{c}{\left(\frac{\mathrm{cond}(Q)-1}{\mathrm{cond}(Q)+1}\right)}^k,k\in {\mathbb{N}}_0$

(Ü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 $\{f(x^k)\}$ gerechnet werden, je größer die Kondition von $Q$ ist.

Die Konvergenzaussagen für quadratische Funktionen gelten qualitativ auch für jeden lokalen Minimalpunkt $x^{*}$ einer beliebigen Funktion $f\in C^2({ℝ}^n)$, in dem die hinreichenden Optimalitätsbedingungen zweiter Ordnung aus Satz 1.14 erfüllt sind. Denn in einem solchen Fall kann $f$ in der Umgebung von $x^{*}$ durch das quadratische Taylor-Polynom

(4.7) $q^{*}(x):=f(x^{*})+\mathrm{\nabla }f(x^{*}{)}^T(x-x^{*})+(x-x^{*}{)}^T{\mathrm{\nabla }}^{2}f(x^{*})(x-x^{*})$

mit positiv definiter Matrix ${\mathrm{\nabla }}^{2}f(x^{*})$ angenähert werden. Langsame Konvergenz des Gradientenverfahrens ist dann für $f$ zu erwarten, wenn die Kondition der Hesse-Matrix ${\mathrm{\nabla }}^{2}f(x^{*})$ groß ist.

Beispiel 4.3

Das Gradientenverfahren mit exakter Schrittweite sei auf die quadratische Funktion

$f(x):=\frac{1}{2}{x}^{T}Qx\text{ mit }Q:=\left(\begin{array}{cc}2& 0\\ 0& 2\cdot 10^3\end{array}\right)\text{ und }x\in {ℝ}^2$

angewendet. Das Problem $(P)$ hat für dieses $f$ die Lösung $x^{*}:=0$ und den Minimalwert $f(x^{*})=0$. Die Kondition von $Q$ ist mit $\mathrm{cond}(Q)=10^3$ 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

$\frac{\mathrm{cond}(Q)-1}{\mathrm{cond}(Q)+1}=0.9980,$

was auf mögliche langsame Konvergenz hinweist.

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

$p:=-\mathrm{\nabla }f(x)=-Qx,$

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

$t_M(x,p)=-\frac{\mathrm{\nabla }f(x{)}^{T}p}{p^{T}Qp}=\frac{x^T{Q}^{2}x}{x^T{Q}^{3}x}=\frac{x_1^2+10^6{x}_2^2}{2(x_1^2+10^9{x}_2^2)}.$

Mit $t_k:=t_M(x^k,p^k)$ folgt weiter

$x^{k+1}=x^k-t_{k}Q{x}^k=(I-t_{k}Q)x^k=\left(\begin{array}{cc}1-{\rho }_k& 0\\ 0& 1-10^3{\rho }_k\end{array}\right)x^k$

für

${\rho }_k:=2t_k=\frac{x_1^2+10^6{x}_2^2}{x_1^2+10^9{x}_2^2}.$

Startet man nun das Gradientenverfahren mit $x^0:=(1,10^{-3}{)}^T$, so ist ${\rho }_0\approx 2\cdot 10^{-3}$ und damit

$(x_1^1,x_2^1{)}^T\approx (x_1^0,-x_2^0{)}^T.$

Weiter ist damit ${\rho }_1\approx {\rho }_0$ und somit

$(x_1^2,x_2^2{)}^T\approx (x_1^0,x_2^0{)}^T.$

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 $x^0:=(0,1{)}^T$ und $f(x^0)=1000$, so ist ${\rho }_0=10^{-3}$ und damit $x^1=0=x^{*}$. Die Lösung des Problems wird also in diesem Fall mit einer Iteration des Verfahrens erreicht.

$\begin{array}{ccccc}k& x_1^k& x_2^k& f(x_1^k,x_2^k)& {\rho }_k\\ \text{HLINE TBD}0& 1.000000& 0.001000& 1.001000& 0.001998\\ 1& 0.998002& -0.000998& 0.997004& 0.001998\\ 2& 0.996008& +0.000996& 0.993024& 0.001998\\ 3& 0.994018& -0.000994& 0.989060& 0.001998\end{array}$

---

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.