Benutzer:Stepri2005/Kurs:Optimierung II/Verfahren der konjugierten Richtungen

Als nächstes wollen wir Verfahren der konjugierten Richtungen und speziell Verfahren der konjugierten Gradienten zur Lösung des unrestringierten Optimierungsproblems

$(P):{\text{ Minimiere }}f(x){\mbox{ über alle }}x\in \mathbb {R} ^{n}$

vorstellen. Letztere Verfahren bezeichnet man auch kurz als CG-Verfahren, wobei „CG“ für engl. „conjugate gradients“ steht. Solche CG-Verfahren konvergieren im Allgemeinen wesentlich schneller als das Gradienten-Verfahren, sind aber normalerweise langsamer als das globalisierte Newton-Verfahren oder Quasi-Newton-Verfahren, welche wir später in den Kapiteln 6 und 7 behandeln werden. Im Vergleich mit letzteren Verfahren haben sie aber auch Vorzüge, die im Einzelfall zum Tragen kommen mögen.

5.1 Motivation der Verfahren

Wir betrachten zunächst nur quadratische Funktionen

(5.1) $f(x):={\frac {1}{2}}x^{T}Qx+c^{T}x+\alpha ,\quad x\in \mathbb {R} ^{n}$

mit positiv definiter Matrix $Q$. Gemäß Korollar 1.18 erhält man die eindeutige Lösung $x^{*}$ von Problem $(P)$ mit einem solchen $f$ als eindeutige Lösung des linearen Gleichungssystems

$\nabla f(x)=Qx+c=0.$

Sie lautet folglich $x^{*}=-Q^{-1}c$. Verfahren zur Minimierung quadratischer Funktionen sind also gleichzeitig auch immer Verfahren zur Lösung linearer Gleichungssysteme und umgekehrt. So werden CG-Verfahren auch vielfach zur Lösung großer linearer Gleichungssysteme mit dünn besetzter, positiv definiter Matrix verwendet, zumeist in Verbindung mit einem Präkonditionierer (s. Abschnitt 5.5).

Grundlegend für die hier diskutierten CG-Verfahren ist die nachstehende Definition.

Definition 5.1

Sei $A\in \mathbb {R} ^{n\times n}$ eine symmetrische und positiv definite Matrix. Vektoren $p^{0},\ldots ,p^{k}\in \mathbb {R} ^{n}$ heißen A-konjugiert, falls $p^{i}\neq 0$ $(i=0,\ldots ,k)$ ist und falls gilt:

$(p^{i})^{T}Ap^{j}=0,\qquad i,j\in \{0,\ldots ,k\},\quad i\neq j.$

Definiert man für eine symmetrische, positiv definite Matrix $A\in \mathbb {R} ^{n\times n}$

(5.2) $\langle x,y\rangle _{A}:=x^{T}Ay,\quad x,y\in \mathbb {R} ^{n},$

so lässt sich leicht zeigen, dass $\langle \cdot ,\cdot \rangle _{A}$ ein Skalarprodukt auf dem $\mathbb {R} ^{n}$ definiert. Die A-Konjugiertheit von Vektoren $p^{0},\ldots ,p^{k}$ bedeutet also, dass $p^{0},\ldots ,p^{k}$ vom Nullvektor verschiedene, bezüglich des Skalarproduktes $\langle \cdot ,\cdot \rangle _{A}$ orthogonale Vektoren sind. Nach einem aus der Linearen Algebra bekannten Ergebnis sind solche Vektoren immer linear unabhängig:

Lemma 5.2

Sind $p^{0},\ldots ,p^{k}$ von 0 verschiedene Vektoren, die bezüglich eines Skalarproduktes $\langle \cdot ,\cdot \rangle$ auf dem $\mathbb {R} ^{n}$ orthogonal zueinander sind, so sind diese linear unabhängig und ist $k\leq n-1$.

Beweis.

Für jedes $i\in \{0,1,\ldots ,k\}$ gilt wegen $\langle p^{i},p^{i}\rangle >0$

$\sum _{j=0}^{k}\alpha _{j}p^{j}=0\Rightarrow \left\langle \sum _{j=0}^{k}\alpha _{j}p^{j},p^{i}\right\rangle =0\Rightarrow \sum _{j=0}^{k}\alpha _{j}\langle p^{j},p^{i}\rangle =0\Rightarrow \alpha _{i}=0.$

Die Vektoren $p^{0},\ldots ,p^{k}$ sind also linear unabhängig. Da höchstens $n$ Vektoren linear unabhängig sein können, ist $k\leq n-1$.

q.e.d.

Wir nehmen nun zunächst an, dass für die in der quadratischen Funktion (5.1) auftretende Matrix $Q$ konjugierte Vektoren $p^{0},\ldots ,p^{n-1}$ bekannt seien. Mit diesen Vektoren als Spalten definieren wir dann die $(n\times n)$-Matrix

$P:={\begin{pmatrix}p^{0}&\ldots &p^{n-1}\end{pmatrix}}.$

Aufgrund der linearen Unabhängigkeit der Vektoren $p^{0},\ldots ,p^{n-1}$ ist $P$ nichtsingulär. Weiter definieren wir die - aufgrund der positiven Definitheit von $Q$ positiven - Zahlen

$d_{i+1}:=(p^{i})^{T}Qp^{i}>0\quad (i=0,\ldots ,n-1)$

und mit diesen die Diagonalmatrix

$D:=P^{T}QP=\operatorname {diag} (d_{1},\ldots ,d_{n}).$

Die Matrix $P$ verwenden wir nun, um mittels der Variablentransformation $x\mapsto y:=P^{-1}x$ zu einer quadratischen Funktion zu gelangen, welche einfacher als die quadratische Funktion $f$ in (5.1) zu minimieren ist. Und zwar liefert diese Transformation

(5.3) $F(y):=f(Py)={\frac {1}{2}}y^{T}\underbrace {P^{T}QP} _{=D}y+(P^{T}c)^{T}y+\alpha =\alpha +\sum _{i=1}^{n}F_{i}(y_{i})$

mit

(5.4) $F_{i}(y_{i}):={\frac {1}{2}}d_{i}y_{i}^{2}+(P^{T}c)_{i}y_{i}.$

Die so gewonnene quadratische Funktion $F(y)$ ist also separierbar, d. h., sie ist als Summe von Funktionen $F_{i}$ darstellbar, die jeweils von Variablen abhängen (in diesem Fall einer einzigen Variablen), die nur in ihr und in keinem weiteren $F_{j}$ mit $j\neq i$ vorkommen. Demzufolge kann $F(y)$ in (5.3) über $y$ minimiert werden, indem jedes $F_{i}$ hinsichtlich der Komponente $y_{i}$ von $y$ minimiert wird. Da $F_{i}wegen<math>d_{i}>0$ gleichmäßig konvex ist, besitzt $F_{i}$ einen eindeutigen Minimalpunkt $y_{i}^{*}$ und gilt demnach

$\min _{y\in \mathbb {R} ^{n}}F(y)=\alpha +\sum _{i=1}^{n}\min _{y_{i}\in \mathbb {R} }F_{i}(y_{i})=\alpha +\sum _{i=1}^{n}F_{i}(y_{i}^{*})=F(y^{*}).$

Der Minimierer $y^{*}$ von $F$ soll nun folgendermaßen komponentenweise generiert werden, wobei $e^{k}$ der $k$-te Standardeinheitsvektor und $y^{0}$ ein beliebiger Vektor ist. Ist $y^{0}$ nicht bereits der Minimierer von $F(y)$, so ist mit einem $t_{0}\in \mathbb {R}$

$\min _{\tau \in \mathbb {R} }F_{1}(\tau )=\min _{t\in \mathbb {R} }F_{1}(y_{1}^{0}+te_{1}^{1})=:F_{1}(y_{1}^{0}+t_{0}e_{1}^{1}).$

Somit ist $y_{1}^{*}:=y_{1}^{0}+t_{0}e_{1}^{1}$ die erste Komponente der gesuchten Lösung $y^{*}$. Wir setzen dann

$y^{1}:=y^{0}+t_{0}e^{1}=(y_{1}^{*},y_{2}^{0},\ldots ,y_{n}^{0})^{T}$

und fahren mit $y^{1}$ für $F_{2}$ in analoger Weise fort, sofern nicht $y^{1}$ bereits die Funktion $F(y)$ minimiert. So erhalten wir $y_{2}^{*}:=y_{2}^{1}+t_{1}e_{2}^{2}$ sowie

$y^{2}:=y^{1}+t_{1}e^{2}=(y_{1}^{*},y_{2}^{*},y_{3}^{0},\ldots ,y_{n}^{0})^{T}.$

Allgemein ist $t_{k}$ also der Minimierer von $F_{k+1}(y_{k+1}^{k}+te_{k+1}^{k+1})$ und

$y^{k+1}:=y^{k}+t_{k}e^{k+1}=(y_{1}^{*},y_{2}^{*},\ldots ,y_{k+1}^{*},y_{k+2}^{0},\ldots ,y_{n}^{0})^{T}.$

Da von dem Vektor $te^{k+1}$ höchstens die $(k+1)$-te Komponente verschieden von 0 ist, folgt damit

$\min _{t\in \mathbb {R} }F(y^{k}+te^{k+1})=\alpha +\sum _{i=1, \atop i\neq k+1}^{n}F_{i}(y_{i}^{k})+\min _{t\in \mathbb {R} }F_{k+1}(y_{k+1}^{k}+te_{k+1}^{k+1})=\alpha +\sum _{i=1, \atop i\neq k+1}^{n}F_{i}(y_{i}^{k})+F_{k+1}(y_{k+1}^{k}+te_{k+1}^{k+1})$

$=\alpha +\sum _{i=1}^{n}F_{i}(y_{i}^{k}+t_{k}e_{i}^{k+1})=F(y^{k}+t_{k}e^{k+1})=F(y^{k+1}).$

Also kann man, ausgehend von einem $y^{0}$, in maximal $n$ Schritten $y^{*}$ ermitteln, indem man für $k=0,1,2,\ldots$ in $y^{k}$ die Koordinatenrichtung $e^{k+1}$ als neue Richtung wählt, dann die Minimum-Schrittweite $t_{k}$ in diese Richtung bestimmt und anschließend $y^{k+1}:=y^{k}+t_{k}e^{k+1}$ setzt. Rückübersetzung in den $x$-Raum liefert schließlich die Iterationsvorschrift

$Py^{k+1}:=Py^{k}+t_{k}Pe^{k+1}\Leftrightarrow x^{k+1}:=x^{k}+t_{k}p^{k}$

und zur Bestimmung der Schrittweite die Formel

$\min _{t\in \mathbb {R} }F(y^{k}+te^{k+1})=\min _{t\in \mathbb {R} }f(P(y^{k}+te^{k+1}))=\min _{t\in \mathbb {R} }f(x^{k}+tp^{k}).$

Man beachte dabei, dass hier $t_{k}$ keine positive Zahl sein muss. Denn mit $p^{0},\ldots ,p^{k},\ldots ,p^{n-1}$ sind ja auch die Vektoren $p^{0},\ldots ,-p^{k},\ldots ,p^{n-1}$ $Q$-konjugiert und hat $t_{k}$ für $-p^{k}$ sicher umgekehrtes Vorzeichen wie für $p^{k}$. Wir wollen $t_{k}$ trotzdem als Minimum-Schrittweite bezeichnen. Gemäß Beispiel 3.5 ist diese für jedes $p^{k}\neq 0$ bestimmt durch

$t_{k}=t_{M}(x^{k},p^{k})=t_{C}(x^{k},p^{k})=-{\frac {\nabla f(x^{k})^{T}p^{k}}{(p^{k})^{T}Qp^{k}}},$

wobei die Abstiegsbedingung $\nabla f(x^{k})^{T}p^{k}<0$ offenbar nicht für beliebige $Q$-konjugierte Vektoren $p^{k}$ erfüllt sein kann.

Wegen des häufigen Vorkommens des Gradienten im Rest dieses Kapitels verwenden wir ab jetzt für jedes $\ell \in \mathbb {N} _{0}$ die Abkürzung

$g^{\ell }:=\nabla f(x^{\ell }).$

Zur Lösung der Aufgabe $(P)$ für eine quadratische Zielfunktion $f$ wie in (5.1) mit positiv definiter Matrix $Q$ haben wir also den folgenden Algorithmus hergeleitet.

Algorithmus 5.3 (Verfahren konjugierter Richtungen für quadratisches f)

(0) Wähle $Q$-konjugierte Richtungen $p^{0},\ldots ,p^{n-1}\in \mathbb {R} ^{n}$ und $x^{0}\in \mathbb {R} ^{n}$. Setze $k:=0$.

(1) Falls $g^{k}=Qx^{k}+c=0$ ist, stop!

(2) Berechne

$t_{k}:=-{\frac {(g^{k})^{T}p^{k}}{(p^{k})^{T}Qp^{k}}}$

und setze

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

(3) Setze $k:=k+1$ und gehe nach (1).

Wie gezeigt wurde, bricht Algorithmus 5.3 in Schritt (1) für $k:=m$ nach höchstens $m\leq n$ Iterationen mit der Lösung $x^{k}$ des Problems $(P)$ ab.

5.2 Erzeugung konjugierter Richtungen

Wie kann man nun $Q$-konjugierte Richtungen erzeugen? Dies ist mit Hilfe des aus der Linearen Algebra bekannten und im nächsten Satz angegebenen Gram-Schmidt-Orthogonalisierungsverfahrens möglich, mit dem $n$ beliebige, linear unabhängige Vektoren bezüglich des Skalarproduktes $\langle \cdot ,\cdot \rangle _{Q}$ orthogonalisiert werden können. (Auf die Normierung wird hier verzichtet.) Mit $\operatorname {span} \{z^{1},\ldots ,z^{m}\}$ ist dabei der von $z^{1},\ldots ,z^{m}\in \mathbb {R} ^{n}$ aufgespannte Teilraum des $\mathbb {R} ^{n}$ gemeint.

Satz 5.4 (Gram-Schmidt)

Sei $\langle \cdot ,\cdot \rangle$ ein Skalarprodukt auf dem $\mathbb {R} ^{n}$ und seien $v^{1},\ldots ,v^{m}\in \mathbb {R} ^{n}$ linear unabhängige Vektoren. Dann sind die durch

$w^{1}:=v^{1},\qquad w^{k}:=v^{k}-\sum _{i=1}^{k-1}{\frac {\left\langle v^{k},w^{i}\right\rangle }{\langle w^{i},w^{i}\rangle }}w^{i}\quad (k=2,\ldots ,m)$

definierten Vektoren $w^{1},\ldots ,w^{m}$ bezüglich $\langle \cdot ,\cdot \rangle$ orthogonal zueinander und es gilt

$\operatorname {span} \left\{v^{1},\ldots ,v^{m}\right\}=\operatorname {span} \left\{w^{1},\ldots ,w^{m}\right\}.$

Wir betrachten nun den folgenden Algorithmus zur Lösung von Problem $(P)$ für eine quadratische Funktion wie in (5.1) mit positiv definiter Matrix $Q$.

=== Algorithmus 5.5 (Verfahren konjugierter Gradienten für quadratisches f)

(0) Wähle $x^{0}\in \mathbb {R} ^{n}$ und setze $p^{0}:=-g^{0}$ und $k:=0$.

(1) Falls $g^{k}=Qx^{k}+c=0$ ist, stop!

(2) Berechne

(5.5) $t_{k}:=-{\frac {(g^{k})^{T}p^{k}}{(p^{k})^{T}Qp^{k}}}$

und setze

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

(3) Berechne

(5.6) $p^{k+1}:=-g^{k+1}-\sum _{i=0}^{k}{\frac {(-g^{k+1})^{T}Qp^{i}}{(p^{i})^{T}Qp^{i}}}p^{i}.$

(4) Setze $k:=k+1$ und gehe nach (1).

Wenn die von Algorithmus 5.5 erzeugten Vektoren $-g^{k}$ linear unabhängig sind, so werden die dadurch erzeugten Richtungen $p^{k}$ offenbar durch eine Gram-Schmidt-Orthogonalisierung der Vektoren $-g^{k}$ bezüglich des Skalarproduktes $\langle \cdot ,\cdot \rangle _{Q}$ gewonnen und sind die Richtungen $p^{k}$ folglich $Q$-konjugiert. Wie in Abschnitt 5.1 gezeigt wurde, bricht in diesem Fall das Verfahren spätestens für $k:=n$ in Schritt (1) mit der Lösung $x^{k}$ von Problem $(P)$ ab. Das folgende Lemma zeigt nun, dass die Vektoren $-g^{i}$ $(i=0,\ldots ,k\leq n-1)$ bezüglich des Skalarproduktes

(5.7) $\langle x,y\rangle :=x^{T}y,\quad x,y\in \mathbb {R} ^{n}$

sogar paarweise zueinander orthogonal sind, woraus ihre lineare Unabhängigkeit gemäß Lemma 5.2 folgt. Wir verwenden dabei die für $f$ in (5.1) geltende Beziehung

(5.8) $g^{k+1}=Qx^{k+1}+c=Q(x^{k}+t_{k}p^{k})+c=g^{k}+t_{k}Qp^{k}.$

Lemma 5.6

Sei $f$ die quadratische Funktion in (5.1) mit positiv definitem $Q$. Dann bricht Algorithmus 5.5 mit $g^{m}=0$ für ein $m$ mit $1\leq m\leq n$ ab und für die durch ihn erzeugten Gradienten $g^{k}$ gilt für jedes $k\leq m-1$, dass $g^{k}\neq 0$ ist sowie

(5.9) $(g^{k})^{T}g^{j}=0\quad (j=0,\ldots ,k-1)$

und

(5.10) $(g^{k})^{T}g^{k}=-(g^{k})^{T}p^{k}.$

Beweis.

Aufgrund von Schritt (1) des Verfahrens gilt $g^{k}\neq 0$ für $k\leq m-1$. Wir wollen nun die Richtigkeit von (5.9) mittels vollständiger Induktion nach $k$ beweisen. Offenbar gilt (5.9) für $k=1$, da mit (5.8), $g^{0}=-p^{0}$ und (5.5) folgt:

$(g^{1})^{T}g^{0}=(g^{0}+t_{0}Qp^{0})^{T}g^{0}=\left\|g^{0}\right\|^{2}-t_{0}(p^{0})^{T}Qp^{0}=0.$

Wir machen jetzt die Induktionsannahme, dass

(5.11) $(g^{k})^{T}g^{j}=0\quad (j=0,\ldots ,k-1)$

für beliebiges, festes $k<m-1$ gilt. Die Vektoren $-g^{0},-g^{1},\ldots ,-g^{k}$ sind dann von Null verschiedene, bezüglich (5.7) orthogonale und nach Lemma 5.2 linear unabhängige Vektoren. Gemäß der Definition der $p^{k}$ impliziert somit die Induktionsannahme gemäß Satz 5.4

(5.12) $(p^{k})^{T}Qp^{j}=0\quad (j=0,\ldots ,k-1)$

und

$\operatorname {span} \{-g^{0},\ldots ,-g^{k}\}=\operatorname {span} \{p^{0},\ldots ,p^{k}\}.$

Für $0\leq j\leq k-1$ kann man daher $p^{j}$ mit gewissen $\alpha _{i}\in \mathbb {R}$ in der Form $p^{j}=\sum _{i=0}^{j}\alpha _{i}(-g^{i})$ darstellen und folgt daher wegen (5.11)

(5.13) $(g^{k})^{T}p^{j}=-\sum _{i=0}^{j}\alpha _{i}(g^{k})^{T}g^{i}=0\quad (j=0,\ldots ,k-1).$

Wir wollen wir nun die Gültigkeit der Gleichungen (5.9) für $k+1$ zeigen, d. h., dass gilt:

$(g^{k+1})^{T}g^{j}=0\quad (j=0,\ldots ,k).$

Sei zunächst $j\in \{0,\ldots ,k-1\}$. Dann haben wir mit (5.8) unter Verwendung der Induktionsannahme (5.11), der Definition (5.6) und der Folgerung (5.12)

$(g^{k+1})^{T}g^{j}=(g^{k}+t_{k}Qp^{k})^{T}g^{j}=t_{k}(p^{k})^{T}Q\left(-p^{j}-\sum _{i=0}^{j-1}{\frac {(-g^{j})^{T}Qp^{i}}{(p^{i})^{T}Qp^{i}}}p^{i}\right)=0.$

Für $j:=k$ erhalten wir schließlich auf ähnliche Weise

$(g^{k+1})^{T}g^{k}=\left\|g^{k}\right\|^{2}+t_{k}(p^{k})^{T}Q\left(-p^{k}-\sum _{i=0}^{k-1}{\frac {(-g^{k})^{T}Qp^{i}}{(p^{i})^{T}Qp^{i}}}p^{i}\right)=\left\|g^{k}\right\|^{2}-t_{k}(p^{k})^{T}Qp^{k}$

$=\left\|g^{k}\right\|^{2}+(g^{k})^{T}p^{k}=\left\|g^{k}\right\|^{2}+(g^{k})^{T}\left(-g^{k}-\sum _{i=0}^{k-1}{\frac {(-g^{k})^{T}Qp^{i}}{(p^{i})^{T}Qp^{i}}}p^{i}\right)=0,$

wobei zum Schluss (5.13) verwendet wurde. Also ist (5.9) gezeigt. Die letzten beiden Identitäten zeigen auch die Gültigkeit von (5.10).

q.e.d.

Man kann also bei Algorithmus 5.5 in der Tat von einem Verfahren der konjugierten Gradienten sprechen. Da $g^{k}\neq 0$ für $0\leq k\leq m-1$ ist, folgt überdies mit (5.10), dass die mit diesem Algorithmus generierten Richtungen $p^{k}$ für diese $k$ Abstiegsrichtungen sind.

5.3 Das Verfahren von Fletcher und Reeves

In der angegebenen Form ist Algorithmus 5.5 aus numerischer Sicht vollkommen unattraktiv, da die Berechnung der Summe in (5.6) zumindest für größere $k$ numerisch sehr teuer ist und mit wachsendem $k$ immer teuerer wird. Bemerkenswerterweise kann man aber diese Summe durch einen einzelnen Term ersetzen, welcher nur die Berechnung der Normen der ohnehin benötigten Vektoren $g^{k}$ und $g^{k+1}$ erfordert. Letzteres zeigt der Beweis des folgenden Lemmas.

Lemma 5.7

Für die in Algorithmus 5.5 erzeugten Richtungen gilt für quadratisches $f$ wie in (5.1) mit positiv definitem $Q$:

$p^{k+1}:=-g^{k+1}+\gamma _{k}p^{k}\ mit\ \gamma _{k}:={\frac {\left\|g^{k+1}\right\|^{2}}{\|g^{k}\|^{2}}}.$

Beweis.

Aus (5.8) folgt

(5.14) $Qp^{j}={\frac {g^{j+1}-g^{j}}{t_{j}}}$

und damit unter Verwendung von (5.9) für $k+1$ anstelle von $k$

$(g^{k+1})^{T}Qp^{j}={\frac {1}{t_{j}}}(g^{k+1})^{T}\left(g^{j+1}-g^{j}\right)=0\quad (j=0,\ldots ,k-1).$

Also folgt die Behauptung unter Verwendung von (5.14), (5.9), (5.5) und (5.10) mit

(5.15) $-\sum _{i=0}^{k}{\frac {(-g^{k+1})^{T}Qp^{i}}{(p^{i})^{T}Qp^{i}}}p^{i}={\frac {(g^{k+1})^{T}Qp^{k}}{(p^{k})^{T}Qp^{k}}}p^{k}={\frac {1}{t_{k}}}{\frac {(g^{k+1})^{T}(g^{k+1}-g^{k})}{(p^{k})^{T}Qp^{k}}}p^{k}=-{\frac {\left\|g^{k+1}\right\|^{2}}{(g^{k})^{T}p^{k}}}p^{k}={\frac {\left\|g^{k+1}\right\|^{2}}{\|g^{k}\|^{2}}}p^{k}.$

q.e.d.

Berücksichtigt man Lemma 5.7, so ist Algorithmus 5.5 für gleichmäßig konvexe, quadratische Funktionen gerade das Verfahren von Hestenes und Stiefel aus dem Jahre 1952, welches 1964 von Fletcher und Reeves auf beliebige Funktionen $f\in C^{1}(\mathbb {R} ^{n})$ verallgemeinert wurde. Dieses lautet wie folgt:

Algorithmus 5.8 (Fletcher-Reeves-Verfahren)

(0) Wähle eine exakte Schrittweitenregel, ein $x^{0}\in \mathbb {R} ^{n}$ und setze $p^{0}:=-g^{0}$ und $k:=0$.

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

(2) Bestimme die Schrittweite $t_{k}>0$ und setze

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

(3) Berechne

$\gamma _{k}:={\frac {\left\|g^{k+1}\right\|^{2}}{\|g^{k}\|^{2}}}$

und setze

$p^{k+1}:=-g^{k+1}+\gamma _{k}p^{k}.$

(4) Setze $k:=k+1$ und gehe nach (1).

Aus dem Vorangegangenen folgt, dass das Verfahren von Fletcher und Reeves für gleichmäßig konvexes, quadratisches $f$ spätestens für $k:=n$ mit der Lösung $x^{k}$ von $(P)$ abbricht.

Wir wollen als nächstes zeigen, dass das Verfahren auch für nichtquadratisches $f$ gegen eine Lösung des unrestringierten Optimierungsproblems $(P)$ konvergiert. Dazu benötigen wir:

Lemma 5.9

Seien $f\in C^{1}(\mathbb {R} ^{n}),x^{k},p^{k}\in \mathbb {R} ^{n}$ beliebige Vektoren und $t_{k}:=t_{k}(x^{k},p^{k})$ eine exakte Schrittweite. Dann gilt für $x^{k+1}:=x^{k}+t_{k}p^{k}$:

(i) $(g^{k+1})^{T}p^{k}=0$ und

(ii) für $p^{k+1}:=-g^{k+1}+s_{k}p^{k}$ mit $s_{k}\in \mathbb {R}$

$(g^{k+1})^{T}p^{k+1}=-\left\|g^{k+1}\right\|^{2}.$

Beweis.

Für jede exakte Schrittweite gilt per Definition

$0=\nabla f(x^{k}+t_{k}p^{k})^{T}p^{k}=(g^{k+1})^{T}p^{k}.$

Also ist Aussage (i) richtig. Mit (i) folgt Aussage (ii) wegen

$(g^{k+1})^{T}p^{k+1}=(g^{k+1})^{T}(-g^{k+1}+s_{k}p^{k})=-\left\|g^{k+1}\right\|^{2}.$

q.e.d.

Für $g^{k+1}\neq 0$ ist nach Aussage (ii) von Lemma 5.9 jede Richtung $p^{k+1}$ der dort angegebenen Form eine Abstiegsrichtung für $f$ in $x^{k+1}$. Da bekanntlich $p^{0}:=-g^{0}\neq 0$ auch eine Abstiegsrichtung ist, ist also das Verfahren von Fletcher-Reeves ein Abstiegsverfahren vom Typ des Modellalgorithmus 2.5. Wir können daher seine Konvergenz für beliebiges $f\in C^{1}(\mathbb {R} ^{n})$ nachweisen, indem wir uns auf die Konvergenzaussage aus Satz 2.14 für den Modellalgorithmus beziehen.

Satz 5.10

Es seien (V1) - (V3) erfüllt.

(i) Bricht Algorithmus 5.8 nicht nach endlich vielen Schritten ab, so erzeugt er eine Folge $\left\{x^{k}\right\}$, die einen Häufungspunkt besitzt, der kritische Lösung von $(P)$ ist und die im Fall, dass auch (V4) erfüllt ist, gegen die Lösung $x^{*}$ von Problem $(P)$ konvergiert.

(ii) Ist die Zielfunktion $f$ quadratisch wie in (5.1) mit positiv definiter Matrix $Q$, so sind die erzeugten Richtungen $p^{j}$ $Q$-konjugiert und bricht das Verfahren spätestens für $k:=n$ mit der Lösung $x^{k}$ von Problem $(P)$ ab.

Beweis.

Algorithmus 5.8 breche nicht nach endlich vielen Schritten ab. Nach Lemma 5.9 ist dann jede vom Algorithmus erzeugte Richtung $p^{k}$ Abstiegsrichtung für $f$ in $x^{k}$. Ferner bekommen wir für $\alpha _{k}$ aus (2.26) mit Aussage (ii) von Lemma 5.9

$\alpha _{k}=-{\frac {\nabla f(x^{k})^{T}p^{k}}{\|\nabla f(x^{k})\|\|p^{k}\|}}=-{\frac {(g^{k})^{T}p^{k}}{\|g^{k}\|\|p^{k}\|}}={\frac {\left\|g^{k}\right\|}{\|p^{k}\|}}.$

Wir setzen nun

$\beta _{k}:={\frac {1}{\|g^{k}\|^{2}\alpha _{k}^{2}}}={\frac {\left\|p^{k}\right\|^{2}}{\|g^{k}\|^{4}}}.$

Wegen $p^{0}=-g^{0}$ ist dann

(5.16) $\beta _{0}:={\frac {\|p^{0}\|^{2}}{\|g^{0}\|^{4}}}={\frac {1}{\|g^{0}\|^{2}}}$

und als Folge der Definitionen von $p^{k}$ und $\gamma _{k-1}$ sowie von Lemma 5.9

$\beta _{k}={\frac {\left\|p^{k}\right\|^{2}}{\|g^{k}\|^{4}}}={\frac {\left\|g^{k}\right\|^{2}+\gamma _{k-1}^{2}\left\|p^{k-1}\right\|^{2}}{\|g^{k}\|^{4}}}={\frac {1}{\|g^{k}\|^{2}}}+{\frac {\left\|g^{k}\right\|^{4}\left\|p^{k-1}\right\|^{2}}{\|g^{k-1}\|^{4}\|g^{k}\|^{4}}}={\frac {1}{\|g^{k}\|^{2}}}+\beta _{k-1},\quad k\geq 1.$

Somit erhalten wir mit (5.16)

$\beta _{k}=\sum _{j=1}^{k}{\frac {1}{\|g^{j}\|^{2}}}+\beta _{0}=\sum _{j=0}^{k}{\frac {1}{\|g^{j}\|^{2}}}$

und demzufolge

(5.17) ${\frac {1}{\alpha _{k}^{2}}}={\frac {\left\|p^{k}\right\|^{2}}{\|g^{k}\|^{2}}}=\left\|g^{k}\right\|^{2}\beta _{k}=1+\left\|g^{k}\right\|^{2}\sum _{j=0}^{k-1}{\frac {1}{\|g^{j}\|^{2}}}.$

Angenommen, $\left\{x^{k}\right\}$ besäße keinen Häufungspunkt, der kritische Lösung von Problem $(P)$ ist. Dann gäbe es ein $\varepsilon >0$ mit $\left\|g^{k}\right\|\geq \varepsilon ,k\in \mathbb {N} _{0}$ und es wäre

${\frac {1}{\alpha _{k}^{2}}}=1+\left\|g^{k}\right\|^{2}\sum _{j=0}^{k-1}{\frac {1}{\|g^{j}\|^{2}}}\leq 1+{\frac {1}{\varepsilon ^{2}}}k\left\|g^{k}\right\|^{2}\leq 1+{\frac {M^{2}}{\varepsilon ^{2}}}k$

mit $M:=\max _{x\in N_{0}}\|\nabla f(x)\|$ für $N_{0}$ aus (2.9). Da $t_{k}$ eine exakte Schrittweite ist, ergäbe sich weiter mit Satz 3.3 und Lemma 5.9

$f(x^{k})-f(x^{k+1})\geq \vartheta _{M}\left\{{\frac {(g^{k})^{T}p^{k}}{\|p^{k}\|}}\right\}^{2}=\vartheta _{M}{\frac {\left\|g^{k}\right\|^{4}}{\|p^{k}\|^{2}}}=\vartheta _{M}\alpha _{k}^{2}\left\|g^{k}\right\|^{2}\geq {\frac {\vartheta _{M}\varepsilon ^{2}}{1+{\frac {M^{2}}{\varepsilon ^{2}}}k}}.$

Summation für $k=0,1,\ldots ,i$ lieferte dann

$f(x^{0})\geq f(x^{i+1})+\sum _{k=0}^{i}{\frac {\vartheta _{M}\varepsilon ^{2}}{1+{\frac {M^{2}}{\varepsilon ^{2}}}k}}\geq f(x^{i+1})+\vartheta _{M}\varepsilon ^{2}+{\frac {\vartheta _{M}\varepsilon ^{2}}{1+{\frac {M^{2}}{\varepsilon ^{2}}}}}\sum _{k=1}^{i}{\frac {1}{k}}.$

Letzteres kann aufgrund der Divergenz der harmonischen Reihe nicht richtig sein, wie man durch Grenzübergang für $i\to \infty$ mit Aussage (iv) von Lemma 2.13 erkennt. Somit besitzt $\left\{x^{k}\right\}$ mindestens einen Häufungspunkt, der kritische Lösung von $(P)$ ist.

Ist zusätzlich (V4) erfüllt, so ergibt sich mit den Aussagen (v) und (vi) von Lemma 2.9 und mit Aussage (i) von Lemma 2.13 für $j=0,\ldots ,k-1$

$\left\|g^{j}\right\|^{2}\geq 2\beta \left(f(x^{j})-f(x^{*})\right)\geq 2\beta \left(f(x^{k})-f(x^{*})\right)\geq {\frac {\beta }{\gamma }}\left\|g^{k}\right\|^{2}.$

Also schließt man mit (5.17)

Fehler beim Parsen (Syntaxfehler): {\displaystyle \frac{\left\|g^k\right\|^2}{\|g^j\|^2} \le \frac \gamma\beta \Rightarrow \frac 1\{\alpha^2_k} \le 1 + \frac \gamma\beta k \Rightarrow \alpha^2_k \ge \frac 1{1 + \frac \gamma\beta k} \Rightarrow \sum^\infty_{k=0} \alpha^2_k = \infty.}

Das heißt, die Zoutendijk-Bedingung ist erfüllt, so dass aus Satz 2.14 die Konvergenz $x^{k}\to x^{*}$ $(k\to \infty )$ folgt. Aussage (ii) ist schließlich eine Konsequenz von Lemma 5.7 und den Ergebnissen aus den Abschnitten 5.1 und 5.2.

q.e.d.

5.4 Das Verfahren von Polak und Ribière

Eine weitere bekannte Variante der Verfahren der konjugierten Gradienten für nichtquadratische Zielfunktionen geht auf Polak und Ribière (1969) zurück. Hier verwendet man statt Lemma 5.7 das folgende Ergebnis.

Lemma 5.11

Für die in Algorithmus 5.3 erzeugten Richtungen gilt für $f$ wie in (5.1) mit positiv definitem $Q$:

(5.18) $p^{k+1}:=-g^{k+1}+\eta _{k}p^{k}$ mit $\eta _{k}:={\frac {(g^{k+1})^{T}(g^{k+1}-g^{k})}{\|g^{k}\|^{2}}}.$

Beweis.

Mit (5.15) und (5.9) schließt man:

$-\sum _{i=0}^{k}{\frac {(-g^{k+1})^{T}Qp^{i}}{(p^{i})^{T}Qp^{i}}}p^{i}={\frac {\left\|g^{k+1}\right\|^{2}}{\|g^{k}\|^{2}}}p^{k}={\frac {(g^{k+1})^{T}(g^{k+1}-g^{k})}{\|g^{k}\|^{2}}}p^{k}.$

q.e.d.

Algorithmus 5.5 in Verbindung mit Formel (5.18) führt zu dem Verfahren von Polak-Ribière, welches für quadratische Funktionen mit dem Verfahren von Fletcher-Reeves zusammenfällt.

Algorithmus 5.12 (Polak-Ribière-Verfahren)

(0) Wähle eine exakte Schrittweitenregel und ein $x^{0}\in \mathbb {R} ^{n}$. Setze $p^{0}:=-g^{0}$ und $k:=0$.

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

(2) Bestimme die Schrittweite $t_{k}>0$ und setze

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

(3) Berechne

$\eta _{k}:={\frac {(g^{k+1})^{T}(g^{k+1}-g^{k})}{\|g^{k}\|^{2}}}$

und setze

$p^{k+1}:=-g^{k+1}+\eta _{k}p^{k}.$

(4) Setze $k:=k+1$ und gehe nach (1).

Für den Konvergenzbeweis beziehen wir uns wiederum auf den allgemeinen Konvergenzsatz 2.14.

Satz 5.13

Es seien (V1) - (V4) erfüllt.

(i) Algorithmus 5.12 bricht entweder nach endlich vielen Schritten ab oder er erzeugt eine Folge $\left\{x^{k}\right\}$ mit $\lim _{k\to \infty }x^{k}=x^{*}$, wobei $x^{*}$ die eindeutige Lösung von $(P)$ ist.

(ii) Ist die Zielfunktion $f$ quadratisch wie in (5.1) mit positiv definiter Matrix $Q$, so sind die erzeugten Richtungen $p^{j}$ $Q$-konjugiert und bricht das Verfahren spätestens für $k:=n$ mit der Lösung $x^{k}$ von Problem $(P)$ ab.

Beweis.

Algorithmus 5.12 breche nicht nach endlich vielen Schritten ab. Aufgrund von Aussage (ii) von Lemma 5.9 ist dann jede vom Algorithmus erzeugte Richtung $p^{k}$ eine Abstiegsrichtung von $f$ in $x^{k}$. Wir wollen nun die Konvergenz des Verfahrens mittels Satz 2.14 nachweisen, indem wir zeigen, dass die Zoutendijk-Bedingung $\sum _{k=0}^{\infty }\alpha _{k}^{2}=\infty$ mit

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikiversity.org/v1/“:): {\displaystyle \alpha_k = - \frac{(g^k)^T p^k}{\|g^k\| \|p^k\} = \frac{\left\|g^k\right\|}{\|p^k\|}}

erfüllt ist (verwende Lemma 5.9 (ii)). Hierzu zeigen wir die Existenz einer Konstanten $\rho >0$ mit

${\frac {\left\|g^{k}\right\|}{\|p^{k}\|}}\geq \rho ,\quad k\in \mathbb {N} _{0}.$

Da eine exakte Schrittweite gewählt wurde, implizieren Teil (i) von Lemma 5.9 und Teil (ii) von Lemma 2.9

$0=t_{k}(g^{k+1})^{T}p^{k}=t_{k}(g^{k})^{T}p^{k}+(g^{k+1}-g^{k})^{T}t_{k}p^{k}\geq t_{k}(g^{k})^{T}p^{k}+\beta t_{k}^{2}\left\|p^{k}\right\|.$

Also gilt mit Aussage (ii) von Lemma 5.9

$t_{k}\leq -{\frac {1}{\beta }}{\frac {(g^{k})^{T}p^{k}}{\|p^{k}\|^{2}}}={\frac {1}{\beta }}{\frac {\left\|g^{k}\right\|^{2}}{\|p^{k}\|^{2}}}.$

Dies liefert unter Anwendung von (V3)

$|\eta _{k}|={\frac {\left|(g^{k+1})^{T}(g^{k+1}-g^{k})\right|}{\|g^{k}\|^{2}}}\leq {\frac {\left\|g^{k+1}\right\|\gamma t_{k}\left\|p^{k}\right\|}{\|g^{k}\|^{2}}}\leq {\frac {\gamma }{\beta }}{\frac {\left\|g^{k+1}\right\|}{\|p^{k}\|}}.$

Demnach folgt mit der Definition von $p^{k+1}$

$\left\|p^{k+1}\right\|\leq \left\|g^{k+1}\right\|+|\eta _{k}|\left\|g^{k}\right\|\leq \left(1+{\frac {\gamma }{\beta }}\right)\left\|g^{k+1}\right\|$

Dies impliziert schließlich $\alpha _{k}\geq 1/\left(1+{\frac {\gamma }{\beta }}\right)$ und damit die Aussage (i) des Satzes. Aussage (ii) folgt aus Satz 5.10, da die Algorithmen 5.8 und 5.12 für gleichmäßig konvexe, quadratische Funktionen zusammenfallen.

q.e.d.

Vergleicht man die Sätze 5.10 und 5.13, so stellt man fest, dass man für das Fletcher-Reeves-Verfahren unter schwächeren Voraussetzungen zu einer Konvergenzaussage kommt. Powell [Pow84] hat sogar anhand eines Gegenbeispiels gezeigt, dass man ohne eine Voraussetzung wie die der gleichmäßigen Konvexität von $f$ auch keine globale Konvergenz des Polak-Ribière-Verfahrens in Verbindung mit einer exakten Schrittweitenregel erwarten kann.

Erstaunlicherweise ist das Fletcher-Reeves- dem Polak-Ribière-Verfahren in der Praxis aber häufig deutlich unterlegen (numerische Vergleiche findet man z. B. in [Fle91] und [GeiKa99]). Powell gibt dafür die folgende Begründung (s. [Fle91]). Wenn das Verfahren kaum Fortschritte macht, also $g^{k}\approx g^{k+1}$ ist, dann hat man im Fall des Polak-Ribière-Verfahrens $\eta _{k}\approx 0$ und erhält man damit $p^{k+1}\approx -g^{k+1}$, d. h. die Richtung steilsten Abstiegs in $x^{k+1}$. Beim Fletcher-Reeves-Verfahren ist in einer solchen Situation aber $\gamma _{k}\approx 1$ und $p^{k+1}$ somit möglicherweise keine sinnvolle Abstiegsrichtung. Weitere Hinweise zu diesen Verfahren, insbesondere auch zur Verwendung anderer Schrittweitenregeln, werden wir im folgenden Abschnitt geben.

5.5 Bemerkungen und Hinweise

Wie gezeigt wurde, sind das Fletcher-Reeves und das Polak-Ribière-Verfahren für eine quadratische Funktion

(5.19) $f(x):={\frac {1}{2}}x^{T}Qx+c^{T}x+\alpha$

mit positiv definiter Matrix $Q$ identisch und liefert dieses CG-Verfahren bei exakter Rechnung nach spätestens $n$ Iterationen die eindeutige Lösung $x^{*}$ des unrestringierten Optimierungsproblems für $f$ (bzw. die eindeutige Lösung $x^{*}$ des linearen Gleichungssystems $Qx=-c$). Tatsächlich sind dafür sogar häufig weniger als $n$ Iterationen erforderlich, was die Verfahren für große Probleme mit mehreren Hundert oder Tausend Variablen attraktiv macht. So kann bewiesen werden, dass das CG-Verfahren bei einem solchen Problem nach spätestens $r$ Iterationen mit der Lösung abbricht, wenn $Q$ nur $r\leq n$ paarweise verschiedene Eigenwerte besitzt (z. B. [NoWri06]).

Eine weitere wichtige Beobachtung im Hinblick auf große Probleme ist die folgende. Sind die $s$ größten Eigenwerte von $Q$ deutlich voneinander separiert und häufen sich die übrigen $n-s$ Eigenwerte an einer Stelle z. B. bei 0, so erzielt das CG-Verfahren eine gute Näherung für den optimalen Zielfunktionswert des Problems nach $s+1$ Iterationen (z. B. [NoWri06]). Die bis dahin erzielte Näherung für die Lösung $x^{*}$ des Problems selbst muss dann jedoch noch keineswegs befriedigend sein. Inbesondere im Fall, dass sich viele Eigenwerte von $Q$ bei 0 häufen, muss man nach diesen ersten $s+1$ Iterationen mit sehr langsamer Konvergenz rechnen, da dann typischerweise auch die Kondition von $Q$ groß ist (vgl. (5.20)). Diese Aussagen sind qualitativ auch auf lokale Lösungen einer nichtquadratischen Funktion $f$, in denen die Optimalitätsbedingungen zweiter Ordnung erfüllt sind, übertragbar, da $f$ in einer Umgebung eines solchen Punktes durch eine gleichmäßig konvexe, quadratische Funktion angenähert werden kann (vgl. (4.7)).

Bei exakter Rechnung bricht das CG-Verfahren für die quadratische Funktion (5.19) mit positiv definitem $Q$ nach höchstens $n$ Iterationen mit der Lösung des Problems ab. Da das CG-Verfahren gerade für Probleme großer Dimension von Bedeutung ist, möchte man aber in der Praxis häufig gar nicht $n$ Iterationen eines solchen Verfahrens ausführen. Daher ist auch für quadratische Funktionen mit positiv definitem $Q$ die Frage von Interesse, wie schnell $x^{k}$ gegen $x^{*}$ strebt. Für diesen Fall konnte Poljak ([Polj87]) die Fehlerabschätzung

(5.20) $\left\|x^{k}-x^{*}\right\|\leq 2{\sqrt {\operatorname {cond} (Q)}}\left({\frac {{\sqrt {\operatorname {cond} (Q)}}-1}{{\sqrt {\operatorname {cond} (Q)}}+1}}\right)^{k}\left\|x^{0}-x^{*}\right\|$

angeben, wobei $\operatorname {cond} (Q)=\gamma /\beta$ die Kondition von $Q$ ist (vgl. (2.14)). Diese Abschätzung liefert zwar häufig eine starke Überschätzung des Fehlers, wie man aus der Praxis weiß, macht aber deutlich, dass das CG-Verfahren um so schneller konvergiert, je kleiner die Kondition von $Q$ ist. Deshalb ist es sinnvoll, die Funktion $f$ in Fällen, bei denen mit einer großen Kondition von $Q$ gerechnet werden muss, mittels einer Variablentransformation in eine quadratische Funktion mit einer Matrix zu überführen, welche eine kleinere Kondition besitzt.

Und zwar setzt man in einem solchen Fall mit einer nichtsingulären Matrix $S\in \mathbb {R} ^{n\times n}$

(5.21) ${\tilde {x}}:=Sx.$

Setzt man $S^{-T}:=[S^{-1}]^{T}$, erhält man damit

${\tilde {f}}({\tilde {x}}):=f(S^{-1}{\tilde {x}})={\frac {1}{2}}{\tilde {x}}^{T}S^{-T}QS^{-1}{\tilde {x}}+(S^{-T}c)^{T}{\tilde {x}}+\alpha .$

Wendet man nun das CG-Verfahren auf ${\tilde {f}}$ an, so bestimmt die Kondition der Matrix $S^{-T}QS^{-1}$ die Konvergenzgeschwindigkeit des Verfahrens. Deshalb sollte $S$ so gewählt werden, dass $S^{-T}QS^{-1}$ eine kleinere Kondition als $Q$ besitzt bzw. sich die Eigenwerte von $S^{-T}QS^{-1}$ teilweise häufen. Die Transformation (5.21) muss dabei nicht explizit durchgeführt werden. Sondern man schreibt Algorithmus 5.8 für ${\tilde {f}}$ mit der Variablen ${\tilde {x}}$ hin und invertiert dann die Transformation, um alle Beziehungen durch die Variable $x$ auszudrücken. Der numerische Aufwand pro Iteration erhöht sich allerdings durch die Transformation (5.21) nicht unbeträchtlich. Ob sich ein solches präkonditioniertes CG-Verfahren lohnt, hängt daher davon ab, ob man für die aktuell vorliegende Matrix $Q$ einen geeigneten Präkonditionierer $S$ angeben kann (vgl. [NoWri06]).

Es sei noch darauf hingewiesen, dass das CG-Verfahren besonders dann für die Lösung großer linearer Gleichungssysteme mit positiv definiter Matrix interessant ist, wenn $Q$ dünn besetzt ist. Denn der größte numerische Aufwand pro Iteration besteht bei ihnen darin, ein Matrix-Vektor-Produkt zu berechnen und dessen Berechnung ist um so „billiger“, je dünner die Matrix besetzt ist. Bei einer Cholesky-Zerlegung $Q=LL^{T}$ dagegen, welche man alternativ zur Lösung eines solchen Gleichungssystems durchführen könnte, ist $L$ häufig sehr viel dichter besetzt als $Q$.

Bei den vorgestellten CG-Verfahren haben wir jeweils eine exakte Schrittweitenregel verwendet, die im quadratischen Fall mit positiv definiter Matrix auch explizit berechnet werden kann (vgl. Beispiel 3.5), die aber für allgemeine nichtlineare Funktionen eher unrealistisch ist. Tatsächlich war man lange Zeit wenig erfolgreich damit gewesen, Konvergenz für nichtquadratisches $f$ mit einer inexakten Schrittweitenregel nachzuweisen. Erst Al-Baali konnte 1985 die Konvergenz des Fletcher-Reeves-Verfahren mit der strengen Wolfe-Powell-Schrittweitenregel beweisen (s. [GeiKa99]), die ja für kleines $\sigma$ Schrittweiten liefert, die im Allgemeinen nicht zu stark von der Curry-Schrittweite abweichen. Einen Konvergenzsatz für das Polak-Ribière-Verfahren mit einer neuen, leicht implementierbaren Schrittweitenregel, welche auf eine Arbeit von Grippo und Lucidi aus dem Jahr 1997 zurückgeht, sowie numerische Vergleiche der unterschiedlichen Verfahren findet man ebenfalls bei [GeiKa99].

Darüber hinaus gibt es eine Reihe von Varianten von CG-Verfahren, die zum Teil die strenge Wolfe-Powell-Schrittweite verwenden, darunter insbesondere solche, welche durch eine Kombination des Fletcher-Reeves- und des Polak-Ribière-Verfahrens versuchen, die guten theoretischen Konvergenzeigenschaften des ersten mit den guten Praxiseigenschaften des zweiten Verfahrens zu verbinden ([GeiKa99]). CG-Verfahren werden auch immer noch weiter erforscht. Es scheint aber so, dass bisher keine der vorgeschlagenen Varianten deutliche Vorzüge gegenüber den anderen besitzt.

Es wird generell empfohlen, die Abstiegsrichtung in CG-Verfahren alle $n$ oder $n+1$ Iterationen zu „korrigieren“ und wieder mit einer neuen Richtung zu beginnen, z. B. mit dem negativen Gradienten in der aktuellen Näherung. Die Aussagen, die man über die Konvergenzgeschwindigkeit von CG-Verfahren für nichtquadratische Funktionen in der Literatur findet, beziehen sich häufig auf eine solche Restartversion, sind aber allesamt eher abschreckend. Für eine Restartversion des Polak-Ribière-Verfahrens mit der Gradientenrichtung haben z. B. McCormick und Ritter ([McCoRi74]) $n$-Schritt superlineare Konvergenz gezeigt, d. h. die superlineare Konvergenz der Folge aller $n$-ten Iterierten.

Für große $n$ ist eine solche $n$-Schritt superlineare Konvergenz natürlich vollkommen inakzeptabel. Dennoch sind CG-Verfahren in der Praxis für große und sehr große Probleme häufig die einzig einsetzbaren Methoden, die wegen der zuvor genannten Gründe oft in weniger als $n$ oder ca. $5n$ Iterationen gute Näherungslösungen liefern. Was die CG-Verfahren für sehr große Probleme überdies attraktiv macht ist die Tatsache, dass bei ihnen der numerische Aufwand pro Iteration sehr gering ist, und dass sie, anders als beispielsweise das Newton-Verfahren und die Quasi-Newton-Verfahren, die in den folgenden beiden Kapiteln vorgestellt werden, nur geringen Speicherplatz benötigen. Beim Fletcher-Reeves-Verfahren müssen nur drei und beim Verfahren von Polak-Ribière nur vier Vektoren, also insbesondere keine Matrizen abgespeichert werden. Die im nächsten Abschnitt behandelten Quasi-Newton-Verfahren weisen dafür aber bei nichtquadratischen Funktionen eine deutlich schnellere Konvergenz auf. Deshalb sollten Verfahren der konjugierten Gradienten nur für große Probleme eingesetzt werden.