Benutzer:Stepri2005/Kurs:Optimierung II/Das Newton-Verfahren

Wir wollen als nächstes das aus der Numerischen Mathematik bekannte Newton-Verfahren für die unrestringierte Optimierung diskutieren. Wir beginnen in Abschnitt 6.1 damit, das auch als lokales oder ungedämpftes Newton-Verfahren bezeichnete Verfahren zur Bestimmung einer Lösung eines nichtlinearen Gleichungssystems, welches aus der Numerischen Mathematik I bekannt ist, nochmals zu beschreiben. Für dieses Verfahren geben wir dann einen Konvergenzsatz mit Aussagen zur Konvergenzgeschwindigkeit an. Im Anschluss daran werden wir die Ergebnisse auf das aktuelle Problem der Lösung des unrestringierten Optimierungsproblems übertragen.

Bei Anwendung auf letzteres Problem ist das Newton-Verfahren unter geeigneten Voraussetzungen ein Verfahren vom Typ des Modellalgorithmus 2.5, wobei in jeder Iteration die Schrittweite 1 gewählt wird. Für diese spezielle Wahl der Schrittweiten kann aber auch nur lokale Konvergenz, d. h. Konvergenz in dem Fall gesichert werden, dass der Startpunkt für das Verfahren schon nahe genug bei der angestrebten Lösung gewählt wird. Um den Einzugsbereich für die Wahl des Startpunktes bei Erhaltung der Konvergenz zu erweitern, kann man das Newton-Verfahren globalisieren, d. h., mit einer semieffizienten oder effizienten Schrittweitenregel versehen. Konvergenzresultate für dieses globalisierte oder gedämpfte Newton-Verfahren werden in Abschnitt 6.2 entwickelt. Einige abschließende Hinweise zu den genannten Verfahren findet man in Abschnitt 6.3. (Wenn wir Aussagen machen, die sowohl auf das lokale als auch auf das globalisierte Newton-Verfahren zutreffen, sprechen wir auch kurz vom Newton-Verfanren.)

6.1 Das lokale Newton-Verfahren

6.1.1 Nichtlineare Gleichungssysteme

Eine in der Praxis häufig auftretende Aufgabe ist es, eine Lösung $x^{*}\in D$ eines nichtlinearen Gleichungssystems

$F_{i}(x_{1},...,x_{n})=0\quad (i=1,...,n)\Leftrightarrow F(x)=0$

zu finden, wobei $D\subseteq \mathbb {R} ^{n}$ eine offene Menge und $F:D\to \mathbb {R} ^{n}$ eine nichtlineare, einmal stetig differenzierbare Funktion mit Jacobi-Matrix

${\mathcal {J}}_{F}(x):=\left({\frac {\partial F_{i}}{\partial x_{j}}}(x)\right)_{i,j=1,...,n}\in \mathbb {R} ^{n\times n}$

ist. Vorausgesetzt, es gibt eine solche Nullstelle $x^{*}$, so besteht eine auf Newton zurückgehende Idee zur näherungsweisen Berechnung von $x^{*}$ darin $F$ in einer aktuellen Näherung $x^{k}$ von $x^{*}$ durch die lineare Approximation

$F_{k}(x):=F(x^{k})+{\mathcal {J}}_{F}(x^{k})\left(x-x^{k}\right)$

von $F$ bei $x^{k}$ zu ersetzen und die Nullstelle von $F_{k}$ als neue Näherung $x^{k+1}$ von $x^{*}$ zu wählen. Dieses Vorgehen führt zu der bereits aus der Numerischen Mathematik bekannten Iterationsvorschrift des Newton-Verfahrens

(6.1) $x^{k+1}:=x^{k}-\left[{\mathcal {J}}_{F}(x^{k})\right]^{-1}F(x^{k}),\quad k=0,1,....$

Wir gehen dabei davon aus, was unter geeigneten Voraussetzungen gesichert werden muss, dass das Newton-Verfahren durchführbar ist, d. h., dass für jedes $k$ die Matrix ${\mathcal {J}}_{F}(x^{k})$ nichtsingulär und it $x^{k+1}$ in (6.1) definiert ist.

Die Berechnung der Inversen einer Matrix kann man fast immer durch die weniger aufwändige Lösung eines linearen Gleichungssystems "ersetzen". So ist (6.1) äquivalent mit der Gleichung

${\mathcal {J}}_{F}(x^{k})(\underbrace {x^{k+1}-x^{k}} _{=:h^{k}})=-F(x^{k}).$

Demnach erhält man $x^{k+1}$ auch, indem man die eindeutige Lösung $h^{k}$ des linearen Gleichungssystems

(6.2) ${\mathcal {J}}_{F}(x^{k})h=-F(x^{k})$

bestimmt und man anschließend

$x^{k+1}:=x^{k}+h^{k}$

setzt. (Den Variablenvektor in einem Gleichungssystem wie $h$ in (6.2) schreiben wir ohne einen Index, während wir eine Lösung des Systems wie hier $h^{k}$ mit einem Index versehen.) Das (lokale oder ungedämpfte) Newton-Verfahren lautet somit unter den angegebenen Bedingungen wie folgt:

Algorithmus 6.1 (Lokales Newton-Verfahren für Gleichungssysteme)

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

(1) Falls $F(x^{k})=0$ ist, stop!

(2) Bestimme die eindeutige Lösung $h^{k}$ des linearen Gleichungssystems

(6.3) ${\mathcal {J}}_{F}(x^{k})h=-F(x^{k})$

und setze

$x^{k+1}:=x^{k}+h^{k}.$

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

Die Durchführbarkeit des lokalen Newton-Verfahrens sowie dessen lokale Konvergenz sind, wie aus der Numerischen Mathematik 1 bekannt ist, unter geeigneten Voraussetzungen garantiert. So kann man für Algorithmus 6.1 z. B. den unten stehenden Konvergenzsatz beweisen, wobei hier $\|\cdot \|$ wieder die Euklidische Norm auf dem $\mathbb {R} ^{n}$ bzw. die durch sie induzierte Matrixnorm auf dem Raum $\mathbb {R} ^{n\times n}$, die Spektralnorm, bezeichne (die Ergebnisse sind auch für jede andere Vektornorm und dadurch induzierte Matrixnorm gültig). Mit

${\mathcal {U}}_{\delta }(x^{*}):=\{x\in \mathbb {R} ^{n}{\big |}\|x-x^{*}\|<\delta \}$

für ein $\delta >0$ bezeichnen wir wieder die offene $\delta$-Umgebung von $x^{*}$. Wegen der Aussage zur superlinearen Konvergenz, die üblicherweise in der Numerischen Mathematik nicht gegeben wird, geben wir einen vollständigen Beweis für den Satz an. Dazu und für spätere Zwecke benötigen wir das folgende Lemma.

Lemma 6.2

Sei $v:[a,b]\to \mathbb {R} ^{n}$ eine stetige vektorwertige Funktion, sei $v(t):=(v_{1}(t),...,v_{n}(t))^{T}$ für $t\in [a,b]$ und sei $u:=\int _{a}^{b}v(t)\,dt$ der Vektor mit den Komponenten $u_{i}:=\int _{a}^{b}v_{i}(t)\,dt$. Dann gilt:

$\left\|\int _{a}^{b}v(t)\,dt\right\|\leq \int _{a}^{b}\|v(t)\|\,dt.$

Beweis.

Es sei $\langle \cdot ,\cdot \rangle$ das Standardskalarprodukt auf dem $\mathbb {R} ^{n}$ aus (5.7) und es sei $K:=\|u\|$. Dann gilt unter Verwendung der Cauchy-Schwarz-Ungleichung

$K^{2}=\langle u,u\rangle =\left\langle \int _{a}^{b}v(t)\,dt,u\right\rangle =\sum _{i=1}^{n}u_{i}\int _{a}^{b}v_{i}(t)\,dt=\int _{a}^{b}\sum _{i=1}^{n}u_{i}v_{i}(t)\,dt=\int _{a}^{b}\langle u,v(t)\rangle \,dt$

$\leq \int _{a}^{b}\|u\|\|v(t)\|\,dt=K\int _{a}^{b}\|v(t)\|\,dt.$

Satz 6.3

Es sei $D\subset \mathbb {R} ^{n}$ offen und $F:D\to \mathbb {R} ^{n}$ sei einmal stetig differenzierbar. Ferner existiere ein $x^{*}\in D$, für welches $F(x^{*})=0$ gelte und ${\mathcal {J}}_{F}(x^{*})$ nichtsingulär sei. Dann gibt es eine Umgebung ${\mathcal {U}}_{\delta }(x^{*})$ von $x^{*}$ für ein $\delta >0$, so dass Algorithmus 6.1 für jeden Startpunkt $x^{0}\in {\mathcal {U}}_{\delta }(x^{*})$ durchführbar ist und er, sofern er nicht nach endlich vielen Schritten mit $x^{*}$ abbricht, eine Folge $\left\{x^{k}\right\}$ erzeugt, für welche gilt:

(i) $\left\{x^{k}\right\}$ konvergiert superlinear gegen $x^{*}$.

(ii) Hat man mit einem $L>0$

(6.4) $\|{\mathcal {J}}_{F}(x)-{\mathcal {J}}_{F}(x^{*})\|\leq L\|x-x^{*}\|,\quad x\in {\mathcal {U}}_{\delta }(x^{*}),$

so konvergiert $\left\{x^{k}\right\}$ quadratisch gegen $x^{*}$.

Beweis.

(i) Die folgende Aussage ist aus der Numerischen Mathematik im Zusammenhang mit Störungssätzen für lineare Gleichungssysteme bekannt (s. auch [Pla00, S. 80]):

Sei $A\in \mathbb {R} ^{n\times n}$ eine reguläre Matrix. Dann ist die Matrix $A+\Delta A$ für jede Matrix $\Delta A\in \mathbb {R} ^{n\times n}$ mit $\|\Delta A\|<1/\|A^{-1}\|$ regulär und es gilt

(6.5) $\left\|(A+\Delta A)^{-1}\right\|\leq {\frac {\|A^{-1}\|}{1-\|A^{-1}\|\|\Delta A\|}}.$

Wegen der Stetigkeit von ${\mathcal {J}}_{F}(x)$ auf $D$ können wir zunächst $\eta >0$ so klein wählen, dass gilt:

$\|{\mathcal {J}}_{F}(x)-{\mathcal {J}}_{F}(x^{*})\|\leq {\frac {1}{2\left\|[{\mathcal {J}}_{F}(x^{*})]^{-1}\right\|}},\quad x\in {\mathcal {U}}_{\eta }(x^{*})$

Für $x\in {\mathcal {U}}_{\eta }(x^{*})$ ergibt sich damit aus der anfangs gegebenen Aussage die Invertierbarkeit der Matrix

${\mathcal {J}}_{F}(x)={\mathcal {J}}_{F}(x^{*})+[{\mathcal {J}}_{F}(x)-{\mathcal {J}}_{F}(x^{*})]$

sowie mit (6.5) und $\beta :=\left\|[{\mathcal {J}}_{F}(x^{*})]^{-1}\right\|$ die Abschätzung

(6.6) $\left\|[{\mathcal {J}}_{F}(x)]^{-1}\right\|\leq {\frac {\left\|[{\mathcal {J}}_{F}(x^{*})]^{-1}\right\|}{1-\left\|[{\mathcal {J}}_{F}(x^{*})]^{-1}\right\|\|{\mathcal {J}}_{F}(x)-{\mathcal {J}}_{F}(x^{*})\|}}\leq 2\beta .$

Sei nun

${\mathcal {N}}(x):=x-[{\mathcal {J}}_{F}(x)]^{-1}F(x),\quad x\in {\mathcal {U}}_{\eta }(x^{*})$

die Iterationsfunktion des lokalen Newton-Verfahrens, die nach dem Gezeigten auf ${\mathcal {U}}_{\eta }(x^{*})$ wohldefiniert ist. Mit $F(x^{*})=0$ und den Identitäten

$\int _{0}^{1}{\mathcal {J}}_{F}(x^{*}+s(x-x^{*}))(x-x^{*})\,ds=F(x^{*}+s(x-x^{*})){\big |}_{0}^{1}=F(x)-F(x^{*})=F(x)$

schließen wir als nächstes

${\mathcal {N}}(x)-x^{*}=x-x^{*}-[{\mathcal {J}}_{F}(x)]^{-1}[F(x)-F(x^{*})]$

$=x-x^{*}-[{\mathcal {J}}_{F}(x)]^{-1}\left\{{\mathcal {J}}_{F}(x^{*})(x-x^{*})+\int _{0}^{1}[{\mathcal {J}}_{F}(x^{*}+s(x-x^{*}))-{\mathcal {J}}_{F}(x^{*})](x-x^{*})\,ds\right\}$

$=-[{\mathcal {J}}_{F}(x)]^{-1}[{\mathcal {J}}_{F}(x^{*})-{\mathcal {J}}_{F}(x)](x-x^{*})-[{\mathcal {J}}_{F}(x)]^{-1}\int _{0}^{1}[{\mathcal {J}}_{F}(x^{*}+s(x-x^{*}))-{\mathcal {J}}_{F}(x^{*})](x-x^{*})\,ds.$

Für

(6.7) $\varepsilon (x):=2\beta \left\{\|{\mathcal {J}}_{F}(x^{*})-{\mathcal {J}}_{F}(x)\|+\int _{0}^{1}\|{\mathcal {J}}_{F}(x^{*}+s(x-x^{*}))-{\mathcal {J}}_{F}(x^{*})\|\,ds\right\}$

leiten wir daraus unter Anwendung von Lemma 6.2 mit (6.6) die folgende Abschätzung ab:

(6.8) $\|{\mathcal {N}}(x)-x^{*}\|\leq \varepsilon (x)\|x-x^{*}\|.$

Wegen der Stetigkeit von ${\mathcal {J}}_{F}(x)$ auf ${\mathcal {U}}_{\eta }(x^{*})$ existiert ein $\delta \in (0,\eta ]$, so dass $\varepsilon (x)\leq 1/2$ auf ${\mathcal {U}}_{\delta }(x^{*})$ ist und damit gilt:

$\|{\mathcal {N}}(x)-x^{*}\|\leq {\frac {1}{2}}\|x-x^{*}\|,\quad x\in {\mathcal {U}}_{\delta }(x^{*}).$

Beginnend mit $x^{0}\in {\mathcal {U}}_{\delta }(x^{*})$ liegt folglich mit $x^{k}\in {\mathcal {U}}_{\delta }(x^{*})$ auch $x^{k+1}:={\mathcal {N}}(x^{k})$ in ${\mathcal {U}}_{\delta }(x^{*})$ und konvergiert die Folge $\left\{x^{k}\right\}$ linear gegen $x^{*}$. Die Konvergenz von $\left\{x^{k}\right\}$ impliziert weiter die Konvergenz $\varepsilon (x^{k})\to 0$ $(k\to \infty )$. Da gemäß (6.8)

(6.9) $\left\|x^{k+1}-x^{*}\right\|\leq \varepsilon (x^{k})\left\|x^{k}-x^{*}\right\|$

für alle $k$ gilt, folgt schließlich die superlineare Konvergenz von $\left\{x^{k}\right\}$.

(ii) Gilt nun (6.4) auf ${\mathcal {U}}_{\delta }(x^{*})$, dann liegt für jedes $k$ mit $x^{*}$ und $x^{k}$ auch $x^{*}+s(x^{k}-x^{*})$ für alle $s\in [0,1]$ in ${\mathcal {U}}_{\delta }(x^{*})$ und folgt somit

$\left\|{\mathcal {J}}_{F}(x^{*}+s(x^{k}-x^{*}))-{\mathcal {J}}_{F}(x^{*})\right\|\leq L\left\|x^{k}-x^{*}\right\|.$

Aus (6.7) gewinnt man damit für alle $k$ die Abschätzung

$\varepsilon (x^{k})\leq 2\beta \{L+L\}\left\|x^{k}-x^{*}\right\|=4\beta L\left\|x^{k}-x^{*}\right\|.$

Letzteres zeigt zusammen mit (6.9) die quadratische Konvergenz der Folge $\left\{x^{k}\right\}$.

q.e.d.

Für Algorithmus 6.1 hat man also unter den im Satz 6.3 genannten Voraussetzungen lokale Konvergenz, weswegen man ihn auch als lokales Newton-Verfahren bezeichnet. (Im Unterschied dazu meint man mit globaler Konvergenz eines Verfahrens, dass dessen Konvergenz unter gewissen Bedingungen für jeden beliebigen Startpunkt gesichert ist.)

Das lokale Newton-Verfahren ist invariant gegenüber affin-linearen Transformationen (Übung!). Dies bedeutet, wenn $A\in \mathbb {R} ^{n\times n}$ eine beliebige reguläre Matrix und $c\in \mathbb {R} ^{n}$ irgendein Vektor: ist $\left\{x^{k}\right\}$ die durch das lokale Newton-Verfahren für den Startpunkt $x^{0}$ erzeugte Iteriertenfolge zur Bestimmung einer Lösung des Gleichungssystems $F(x)=0$, so erzeugt das Verfahren bei Anwendung auf das System

$G(z):=F(Az+c)=0$

für den Startpunkt $z^{0}:=A^{-1}(x^{0}-c)$ die Iteriertenfolge $\left\{x^{k}\right\}$ mit

$z^{k}:=A^{-1}\left(x^{k}-c\right)\Leftrightarrow x^{k}=Az^{k}+c.$

Verfahren, die invariant gegenüber affin-linearen Transformationen sind, gelten gegenüber Verfahren, die diese Eigenschaft nicht besitzen, insofern als robuster, als ihre Konvergenzgeschwindigkeit weit weniger von den gerade vorliegenden speziellen Daten abhängt. Anders als bei CG-Verfahren (vgl. Abschnitt 5.5) ändert sich beim lokalen Newton-Verfahren insbesondere durch eine (affin-)lineare Transformation der Variablen die Konvergenzgeschwindigkeit des Verfahrens nicht. Denn ist $\varepsilon >0$ eine vorgegebene Abbruchschranke, so gilt aufgrund der oben beschriebenen Invarianz gegenüber affin-linearen Transformationen und der sich daraus ergebenden Identitäten

$\left\|G(z^{k})\right\|=\left\|F(Az^{k}+c)\right\|=\left\|F(x^{k})\right\|$

die Äquivalenz

$\left\|F(x^{k})\right\|\leq \varepsilon \Leftrightarrow \left\|G(z^{k})\right\|\leq \varepsilon .$

Bei Verfahren, die wie die CG-Verfahren nicht invariant gegenüber affin-linearen Transformationen sind, kann man zwar möglicherweise die Konvergenzgeschwindigkeit durch eine geeignete Wahl der Matrix $A$ erheblich beschleunigen, ist es aber häufig nicht vorhersehbar, ob das Verfahren für die aktuellen Daten langsam konvergiert oder ist es nicht klar, ob gegebenenfalls eine geeignete Transformation zur Konvergenzbeschleunigung gefunden werden kann.

6.1.2 Minimierungsprobleme

Das lokale Newton-Verfahren kann offenbar zur Bestimmung eines kritischen Punktes $x^{*}$ einer Funktion $f\in C^{2}(\mathbb {R} ^{n})$ eingesetzt werden. Da wir nur an kritischen Punkten von $f$ interessiert sind, die das Optimierungsproblem

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

lösen, d. h., die lokale Minimierer von $f$ sind, ist es sinnvoll anzunehmen, dass die hinreichenden Optimalitätsbedingungen zweiter Ordnung aus Satz 1.14 in $x^{*}$ erfüllt sind, also $\nabla f(x^{*})=0$ gilt und die Matrix $\nabla ^{2}f(x^{*})$ positiv definit ist. Letzteres impliziert aufgrund der Stetikeit von $\nabla ^{2}f(x)$ in $x$ die Existenz eines $\eta >0$, so dass auch die Hesse-Matrizen

$\nabla ^{2}f(x^{k})=\nabla ^{2}f(x^{*})+\left[\nabla ^{2}f(x^{k})-\nabla ^{2}f(x^{*})\right],\quad x^{k}\in {\mathcal {U}}_{\eta }(x^{*})$

positiv definit sind. (Gemäß Satz 6.3 würde es in diesem Unterabschnitt genügen, nur die Nichtsingularität von $\nabla ^{2}f(x^{*})$ vorauszusetzen. Da wir aber nicht an beliebigen kritischen Punkten, sondern an lokalen Minimalpunkten von $f$ interessiert sind, fordern wir hier, dass die Matrix $\nabla ^{2}f(x^{*})$ positiv definit ist.) Denn es gilt:

Lemma 6.4

Seien $A,\Delta A\in \mathbb {R} ^{n\times n}$ und seien $A$ und $A+\Delta A$ symmetrische Matrizen. Ist $A$ positiv definit und $\lambda _{\min(}A)$ der kleinste Eigenwert von $A$, dann ist auch $A+\Delta A$ für jede Matrix $\Delta A$ mit $\|\Delta A\|<\lambda _{\min(}A)$ positiv definit.

Beweis.

Mit Lemma 1.10 erschließt man:

$y^{T}(A+\Delta A)y=y^{T}Ay+y^{T}\Delta Ay\geq \lambda _{\min(}A)-\|\Delta A\|>0,\quad y\in \mathbb {R} ^{n},\quad \|y\|=1.$

Setzt man $y:=x/\|x\|$ für $x\in \mathbb {R} ^{n}\setminus \{0\}$, so folgt daraus

$x^{T}(A+\Delta A)x>0,\quad x\in \mathbb {R} ^{n}\setminus \{0\}.$

q.e.d.

Algorithmus 6.1 lautet dann wie folgt:

Algorithmus 6.5 (Lokales Newton-Verfahren)

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

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

(2) Bestimme die eindeutige Lösung $p^{k}$ des linearen Gleichungssystems

(6.10) $\nabla ^{2}f(x^{k})p=-\nabla f(x^{k})$

und setze

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

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

Das lokale Newton-Verfahren zur Bestimmung einer Lösung $x^{*}$ von $(P)$ kann man auch auf direkte Weise motivieren. Ist $x^{k}\in {\mathcal {U}}_{\eta }(x^{*})$ eine aktuelle Näherung von $x^{*}$, wobei $\eta$ wie oben definiert und somit $\nabla ^{2}f(x^{k})$ positiv definit ist, so ersetze man $f$ näherungsweise bei $x^{k}$ durch das quadratische Taylor-Polynom

$f_{k}(x):=f(x^{k})+\nabla f(x^{k})^{T}(x-x^{k})+{\frac {1}{2}}(x-x^{k})^{T}\nabla ^{2}f(x^{k})(x-x^{k}).$

Als neue Näherung $x^{k+1}$ von $x^{*}$ wähle man dann den eindeutigen Minimalpunkt der gleichmäßig konvexen, quadratischen Funktion $f_{k}$, d. h., man bestimme die eindeutige Lösung $x^{k+1}$ des linearen Gleichungssystems

$0=\nabla f_{k}(x)=\nabla f(x^{k})+\nabla ^{2}f(x^{k})\left(x-x^{k}\right).$

Da $\nabla ^{2}f(x^{k})$ positiv definit ist, lässt sich diese Lösung mit

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

angeben, wobei

(6.11) $p^{k}:=-\left[\nabla ^{2}f(x^{k})\right]^{-1}\nabla f(x^{k})$

die sog. Newton-Richtung ist. Diese Richtung lässt sich offenbar als eindeutige Lösung des linearen Gleichungssystems (6.10) gewinnen.

Ist die Matrix $\nabla ^{2}f(x^{k})$, wie hier angenommen wurde, positiv definit, so ist auch ihre Inverse $\nabla ^{2}f(x^{k})^{-1}$ positiv definit und folglich

(6.12) $\nabla f(x^{k})^{T}p^{k}=-\nabla f(x^{k})^{T}\left[\nabla ^{2}f(x^{k})\right]^{-1}\nabla f(x^{k})<0.$

Also ist die Newton-Richtung $p^{k}$ in diesem Fall eine Abstiegsrichtung für $f$ in $x^{k}$, die sich aus einem lokalen quadratischen Modell für $f$ bei $x^{k}$ ergibt.

Eine Aussage über die lokale Konvergenz des ungedämpften oder lokalen Newton-Verfahrens für Minimierungsprobleme können wir unmittelbar aus Satz 6.3 ableiten.

Satz 6.6

Es sei $f\in C^{2}(\mathbb {R} ^{n})$ und $x^{*}$ sei ein lokaler Minimalpunkt von $f$, für den die Hesse-Matrix $\nabla ^{2}f(x^{*})$ positiv definit ist. Dann existiert eine Umgebung ${\mathcal {U}}_{\eta }(x^{*})$ von $x^{*}$ für ein $\eta >0$, so dass Algorithmus 6.5 für jeden Startpunkt $x^{0}\in {\mathcal {U}}_{\eta }(x^{*})$ durchführbar ist und er, sofern er nicht nach endlich vielen Schritten mit $x^{*}$ abbricht, eine Folge $\left\{x^{k}\right\}$ erzeugt, für welche gilt:

(i) $\left\{x^{k}\right\}$ konvergiert superlinear gegen $x^{*}$.

(ii) Hat man mit einem $L>0$

(6.13) $\left\|\nabla ^{2}f(x)-\nabla ^{2}f(x^{*})\right\|\leq L\|x-x^{*}\|,\quad x\in {\mathcal {U}}_{\eta }(x^{*}),$

so konvergiert $\left\{x^{k}\right\}$ quadratisch gegen $x^{*}$.

6.2 Das globalisierte Newton-Verfahren

Das Newton-Verfahren lässt sich durch Einführung einer Schrittweite $t_{k}$ globalisieren, d. h. so modifizieren, dass man unter geeigneten Voraussetzungen auch zu globalen Konvergenzaussagen kommen kann. Man spricht in diesem Fall vom globalisierten oder gedämpften Newton-Verfahren. Mit einer semieffizienten Schrittweitenregel lautet es wie folgt.

Algorithmus 6.7 (Globalisiertes Newton-Verfahren)

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

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

(2) Bestimme die eindeutige Lösung $p^{k}$ des linearen Gleichungssystems

$\nabla ^{2}f(x^{k})p=-\nabla f(x^{k}),$

berechne $t_{k}>0$ und setze

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

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

Um insbesondere zu sichern, dass die Newton-Richtung $p^{k}$ existiert und eine Abstiegsrichtung ist, setzen wir die gleichmäßige positive Definitheit der Hesse-Matrizen $\nabla ^{2}f(x)$ auf der Menge $N_{0}$ aus (2.9) voraus:

(V5) Es ist $f\in C^{2}(\mathbb {R} ^{n})$, die Menge $N_{0}$ aus (2.9) ist konvex und es existieren Konstanten $0<m\leq M$ mit

(6.14) ${\frac {1}{M}}\|u\|^{2}\leq u^{T}\nabla ^{2}f(x)u\leq {\frac {1}{m}}\|u\|^{2},\quad u\in \mathbb {R} ^{n},\quad x\in N_{0}.$

(Die Voraussetzung (V5) wird an mehreren Stellen in diesem Kurs verwendet. Die Menge $N_{0}$ darin ist dann durch den Startpunkt des jeweilig betrachteten Verfahrens definiert.)

Bemerkung 6.8

Die Voraussetzung (V5) impliziert die Bedingungen (V1) - (V4). (Gemäß Satz 1.4 ist $f$ auf $N_{0}$ gleichmäßig konvex und nach Bemerkung 2.6 (iii) und (ii) sind (V2) und (V3) erfüllt.) Damit garantiert (V5) auch die Existenz genau eines kritischen Punktes $x^{*}$ von $f$, welcher globaler Minimierer von $f$ ist (vgl. Korollar 1.18).

Die Bedingung (6.14) ist ferner äquivalent mit der Bedingung

(6.15) $m\|u\|^{2}\leq u^{T}\left[\nabla ^{2}f(x)\right]^{-1}u\leq M\|u\|^{2},\quad u\in \mathbb {R} ^{n},\quad x\in N_{0}$

(s. Lemma 1.10). Letzteres wiederum impliziert gemäß Bemerkung 2.16

(6.16) $m\leq \left\|\left[\nabla ^{2}f(x)\right]^{-1}\right\|\leq M,\quad x\in N_{0}.$

Man beachte, dass die Voraussetzung (V5) erzwingt, dass die Matrix $\nabla ^{2}f(x^{0})$ positiv definit ist und dass damit $p^{0}$ eine Abstiegsrichtung ist und $x^{1}\in N_{0}$ gilt. Induktiv schließt man weiter, dass die Newton-Richtung

$p^{k}=-\left[\nabla ^{2}f(x^{k})\right]^{-1}\nabla f(x^{k})$

für jedes $k$ eine Abstiegsrichtung für $f$ in $x^{k}$ ist, womit $x^{k+1}\in N_{0}$ gilt und die Matrix $\nabla ^{2}f(x^{k+1})$ gemäß (6.14) positiv definit ist. Also passt Algorithmus 6.7 in das Schema des Modellalgorithmus 2.5 und erfüllen die Matrizen $H_{k}:=\left[\nabla ^{2}f(x^{k})\right]^{-1}$ die Forderung in (2.35).

Darüber hinaus können wir mit dem unter der Voraussetzung (V5) existierenden eindeutigen globalen Minimierer $x^{*}$ von $f$ mittels (6.16) die folgende Abschätzung gewinnen:

(6.17) $\left\|p^{k}\right\|=\left\|-\left[\nabla ^{2}f(x^{k})\right]^{-1}\nabla f(x^{k})\right\|\leq M\left\|\nabla f(x^{k})-\nabla f(x^{*})\right\|.$

Im Fall der Konvergenz von $\left\{x^{k}\right\}$ gegen $x^{*}$ konvergiert also die Folge $\left\{p^{k}\right\}$ der Newton-Richtungen gegen 0. Folglich können wir aus Satz 2.17 für das mit einer beliebigen semieffizienten Schrittweitenregel versehene globalisierte Newton-Verfahren die nachstehende Konvergenzaussage ableiten (die Voraussetzung (V5) impliziert ja (V1) - (V4)).

Satz 6.9

Es sei (V5) erfüllt und $x^{*}$ sei die somit existierende eindeutige Lösung von $(P)$. Dann ist Algorithmus 6.7 durchführbar und gilt für die durch ihn erzeugten Folgen $\left\{x^{k}\right\}$ und $\left\{p^{k}\right\}$, sofern er nicht schon nach endlich vielen Schritten mit $x^{*}$ abbricht,

(6.18) $\lim _{k\to \infty }x^{k}=x^{*},\quad \lim _{k\to \infty }p^{k}=0.$

Der letzte Satz liefert noch keine Aussage über die Konvergenzgeschwindigkeit des globalisierten Newton-Verfahrens. Eine solche Konvergenzaussage erhielte man sofort mit Satz 6.6, wenn man zeigen könnte, dass das globalisierte Newton-Verfahren nach endlich vielen Iterationen in das lokale Newton-Verfahren übergeht. Letzteres ist der Fall, wenn für die verwendete Schrittweitenregel

$t_{k}:=1$ für alle hinreichend großen $k$

gilt. Es lässt sich ferner vermuten, dass man für jede Schrittweitenregel, für die man

$\lim _{k\to \infty }t_{k}=1$

zeigen kann, ebenfalls schnelle Konvergenz hat. In diesem Zusammenhang können wir für die in Kapitel 3 eingeführten Schrittweitenregeln beweisen:

Satz 6.10

Es sei (V5) erfüllt. Bricht Algorithmus 6.7 nicht nach endlich vielen Schritten ab, dann gilt für die durch ihn erzeugte Schrittweitenfolge $\{t_{k}\}$:

(i) Wird im Algorithmus die Minimum- oder Curry-Schrittweitenregel verwendet, so ist $\lim _{k\to \infty }t_{k}=1$.

(ii) Wird im Algorithmus die Armijo-Schrittweitenregel verwendet, so ist $t_{k}:=1$ für alle hinreichend großen $k$.

(iii) Wird im Algorithmus die Wolfe-Powell- oder die strenge Wolfe-Powell-Schrittweitenregel verwendet, so ist $t_{k}:=1$ für alle hinreichend großen $k$ eine entsprechende Schrittweite.

Beweis.

Für die Newton-Richtung $p^{k}$ hat man

(6.19) $-\nabla f(x^{k})^{T}p^{k}=-\nabla f(x^{k})^{T}\left[\nabla ^{2}f(x^{k})\right]^{-1}\nabla ^{2}f(x^{k})p^{k}=(p^{k})^{T}\nabla ^{2}f(x^{k})p^{k}.$

(i) Für jede exakte Schrittweite $t_{k}$ ist gemäß ihrer Definition

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

Durch eine Taylor-Entwicklung ergibt sich daher für ein $\vartheta _{k}\in (0,1)$

$0=\nabla f(x^{k}+t_{k}p^{k})^{T}p^{k}=\nabla f(x^{k})^{T}p^{k}+t_{k}(p^{k})^{T}\nabla ^{2}f(x^{k}+\vartheta _{k}(x^{k+1}-x^{k}))p^{k}.$

Folglich erhalten wir mit $\xi ^{k}:=x^{k}+\vartheta _{k}(x^{k+1}-x^{k})\in N_{0}$ und mit (6.19)

(6.20) $t_{k}=-{\frac {\nabla f(x^{k})^{T}p^{k}}{(p^{k})^{T}\nabla ^{2}f(\xi ^{k})p^{k}}}={\frac {(p^{k})^{T}\nabla ^{2}f(x^{k})p^{k}}{(p^{k})^{T}\nabla ^{2}f(\xi ^{k})p^{k}}}=1+{\frac {(p^{k})^{T}\left(\nabla ^{2}f(x^{k})-\nabla ^{2}f(\xi ^{k})\right)p^{k}}{(p^{k})^{T}\nabla ^{2}f(\xi ^{k})p^{k}}}.$

Für alle $y^{k}\in \mathbb {R} ^{n}$ und $z^{k}\in N_{0}$ mit $\lim _{k\to \infty }\left\|y^{k}-z^{k}\right\|=0$ schließen wir nun mit (6.14)

(6.21) $\left|{\frac {(p^{k})^{T}\left[\nabla ^{2}f(y^{k})-\nabla ^{2}f(z^{k})\right]}{(p^{k})^{T}\nabla ^{2}f(z^{k})p^{k}}}\right|\leq M\left\|\nabla ^{2}f(y^{k})-\nabla ^{2}f(z^{k})\right\|\to 0\quad (k\to \infty ).$

Da Satz 6.9 $\lim _{k\to \infty }\left\|x^{k+1}-x^{k}\right\|=0$ und damit $\lim _{k\to \infty }\left\|\xi ^{k}-x^{k}\right\|=0$ impliziert, folgt Aussage (i) aus (6.20).

(ii) Eine Taylor-Entwicklung wiederum liefert mit $\eta _{k}\in (0,1)$ unter Verwendung von (6.19), einer analogen Abschätzung zu (6.21) und der Konvergenz von $\left\{p^{k}\right\}$ in (6.18)

${\frac {f(x^{k})-f(x^{k}+p^{k})}{-\nabla f(x^{k})^{T}p^{k}}}={\frac {-\nabla f(x^{k})^{T}p^{k}-{\frac {1}{2}}(p^{k})^{T}\nabla ^{2}f(x^{k}+\eta _{k}p^{k})p^{k}}{-\nabla f(x^{k})^{T}p^{k}}}=1-{\frac {(p^{k})^{T}\nabla ^{2}f(x^{k}+\eta _{k}p^{k})p^{k}}{2(p^{k})^{T}\nabla ^{2}f(x^{k})p^{k}}}$

$={\frac {1}{2}}-{\frac {1}{2}}{\frac {(p^{k})^{T}\left[\nabla ^{2}f(x^{k}+\eta _{k}p^{k})-\nabla ^{2}f(x^{k})\right]p^{k}}{(p^{k})^{T}\nabla ^{2}f(x^{k})p^{k}}}\to {\frac {1}{2}}\quad (k\to \infty ).$

Daher gilt mit $\zeta \in (0,1/2)$ aus (3.9) für alle hinreichend großen $k$

${\frac {f(x^{k})-f(x^{k}+p^{k})}{-\nabla f(x^{k})^{T}p^{k}}}>\zeta .$

Letzteres bedeutet aber nach Definition 3.10 der Armijo-Schrittweitenregel, dass $t_{k}:=1$ für alle solche $k$ ist.

(iii) Die erste Ungleichung in den Definitionen 3.13 und 3.18 der Wolfe-Powell- bzw. strengen Wolfe-Powell-Schrittweitenregel entspricht ja der Ungleichung (3.9) aus der Armijo-Schrittweitenregel und ist somit, wie der Beweis von Aussage (ii) zeigt, für alle hinreichend großen $k$ für $t_{k}:=1$ erfüllt. Weiter schließt man nun ähnlich wie im Beweis von (ii), dass mit Zahlen $\zeta _{k}\in (0,1)$ gilt:

$\left|{\frac {\nabla f(x^{k}+p^{k})^{T}p^{k}}{-\nabla f(x^{k})^{T}p^{k}}}\right|=\left|{\frac {-\nabla f(x^{k})^{T}p^{k}-(p^{k})^{T}\nabla ^{2}f(x^{k}+\zeta _{k}p^{k})p^{k}}{-\nabla f(x^{k})^{T}p^{k}}}\right|$

$=\left|{\frac {(p^{k})^{T}\left[\nabla ^{2}f(x^{k})-\nabla ^{2}f(x^{k}+\zeta _{k}p^{k})\right]p^{k}}{(p^{k})^{T}\nabla ^{2}f(x^{k})p^{k}}}\right|\leq M\left\|\nabla ^{2}f(x^{k})-\nabla ^{2}f(x^{k}+\zeta _{k}p^{k})\right\|\to 0\quad (k\to \infty ).$

Für jedes $\tau \in (0,1/2)$ und $\sigma \in [\tau ,1)$ folgt daher für alle hinreichend großen $k$

${\frac {-\nabla f(x^{k}+p^{k})^{T}p^{k}}{-\nabla f(x^{k})^{T}p^{k}}}\leq {\frac {\left|-\nabla f(x^{k}+p^{k})^{T}p^{k}\right|}{-\nabla f(x^{k})^{T}p^{k}}}\leq \left|{\frac {-\nabla f(x^{k}+p^{k})^{T}p^{k}}{-\nabla f(x^{k})^{T}p^{k}}}\right|\leq \tau \leq \sigma .$

Letzteres impliziert, dass $t_{k}:=1$ für alle hinreichend großen $k$ auch der zweiten Ungleichung in der Wolfe-Powell- und der strengen Wolfe-Powell-Schrittweitenregel genügt.

q.e.d.

Bei Verwendung der Wolfe-Powell- oder der strengen Wolfe-Powell-Schrittweitenregel sollte man also immer als erstes testen, ob $t_{k}:=1$ eine solche Schrittweite ist, und gegebenenfalls $t_{k}:=1$ setzen. Damit sind wir nun in der Lage, Aussagen über die Konvergenzgeschwindigkeit des globalisierten Newton-Verfahrens zu machen, wobei im Verfahren jede Schrittweitenregel aus Kapitel 3 verwendet werden kann.

Satz 6.11

Es sei (V5) erfüllt und $x^{*}$ sei die dann existierende eindeutige Lösung von $(P)$. Weiter werde in Algorithmus 6.7 die Minimum-, Curry-, Armijo-, Wolfe-Powell- oder strenge Wolfe-Powell-Schrittweitenregel verwendet, wobei in letzteren beiden Fällen $t_{k}:=1$ zu wählen ist, wenn dies eine entsprechende Schrittweite ist. Bricht dann der Algorithmus nicht nach endlich vielen Schritten ab, so gilt für die durch ihn erzeugte Folge $\left\{x^{k}\right\}$:

(i) $\left\{x^{k}\right\}$ konvergiert superlinear gegen $x^{*}$.

(ii) Hat man mit einem $L>0$ und einem $\varepsilon >0$

(6.22) $\left\|\nabla ^{2}f(x)-\nabla ^{2}f(x^{*})\right\|\leq L\|x-x^{*}\|,\quad x\in {\mathcal {U}}_{\varepsilon }(x^{*}),$

so konvergiert $\left\{x^{k}\right\}$ quadratisch gegen $x^{*}$.

Beweis.

(i) Es gilt

$\int _{0}^{1}\nabla ^{2}f\left(x^{*}+s(x^{k}-x^{*})\right)\left(x^{k}-x^{*}\right)\,ds=\nabla f\left(x^{*}+s(x^{k}-x^{*})\right){\big |}_{0}^{1}=\nabla f(x^{k})-\nabla f(x^{*})=\nabla f(x^{k})$

und folglich

$x^{k+1}-x^{*}=x^{k}-x^{*}-t_{k}\left[\nabla ^{2}f(x^{k})\right]^{-1}\nabla f(x^{k})$

$=x^{k}-x^{*}-t_{k}\left[\nabla ^{2}f(x^{k})\right]^{-1}\nabla f(x^{k})\left\{\nabla ^{2}f(x^{*})\left(x^{k}-x^{*}\right)+\int _{0}^{1}\left[\nabla ^{2}f\left(x^{*}+s(x^{k}-x^{*})\right)-\nabla ^{2}f(x^{*})\right]\left(x^{k}-x^{*}\right)\,ds\right\}$

$=(1-t_{k})\left(x^{k}-x^{*}\right)-t_{k}\left[\nabla ^{2}f(x^{k})\right]^{-1}\left[\nabla ^{2}f(x^{*})-\nabla ^{2}f(x^{k})\right]\left(x^{k}-x^{*}\right)-t_{k}\left[\nabla ^{2}f(x^{k})\right]^{-1}\int _{0}^{1}\left[\nabla ^{2}f\left(x^{*}+s(x^{k}-x^{*})\right)-\nabla ^{2}f(x^{*})\right]\left(x^{k}-x^{*}\right)\,ds.$

Daraus ergibt sich mit (6.16)

(6.23) ${\frac {\left\|x^{k+1}-x^{*}\right\|}{\|x^{k}-x^{*}\|}}\leq |1-t_{k}|+M|t_{k}|\left\|\nabla ^{2}f(x^{*})-\nabla ^{2}f(x^{k})\right\|+|t_{k}|M\max _{s\in [0,1]}\left\|\nabla ^{2}f\left(x^{*}+s(x^{k}-x^{*})\right)-\nabla ^{2}f(x^{*})\right\|.$

Gemäß Satz 6.9 konvergiert $\left\{x^{k}\right\}$ gegen $x^{*}$, so dass die rechte Seite im Fall der Konvergenz $t_{k}\to 1$ $(k\to \infty )$ gegen 0 strebt. Die superlineare Konvergenz der Folge $\left\{x^{k}\right\}$ für die genannten Schrittweitenregeln folgt nun aus Satz 6.10.

(ii) Gilt nun die Ungleichung in (6.22), so impliziert die Abschätzung (6.23) für alle $k\geq k_{1}$ mit einem $k_{1}\in \mathbb {N}$

(6.24) $\left\|x^{k+1}-x^{*}\right\|\leq |1-t_{k}|\left\|x^{k}-x^{*}\right\|+2ML|t_{k}|\left\|x^{k}-x^{*}\right\|^{2}.$

Wird insbesondere die Armijo-Schrittweitenregel angewendet, so folgt nach Satz 6.10 $t_{k}:=1$ für alle $k\geq k_{2}$ mit einem $k_{2}\geq k_{1}$ und ist damit die quadratische Konvergenz von $\left\{x^{k}\right\}$ bewiesen. Bei Verwendung der Minimum- oder Curry-Schrittweitenregel andererseits folgert man zunächst aus Satz 6.10, dass ein $k_{3}\geq k_{1}$ existiert mit

(6.25) $|t_{k}|\leq 2,\quad k\geq k_{3}.$

Schätzt man nun ferner den Bruch in (6.20) im Beweis von Satz 6.10 weiter ab und zwar hintereinander mit (6.21), (6.22), (6.25), (6.17) und (2.10), so erhält man für alle $k\geq k_{3}$

$|1-t_{k}|\leq M\left\|\nabla ^{2}f(x^{k})\nabla ^{2}f(\xi ^{k})\right\|\leq LM\left\|x^{k}-\xi ^{k}\right\|=LM\left\|\vartheta _{k}\left(x^{k+1}-x^{k}\right)\right\|=LM\left\|\vartheta _{k}t_{k}p^{k}\right\|$

$\leq 2LM\left\|p^{k}\right\|\leq 2LM^{2}\left\|\nabla f(x^{k})-\nabla f(x^{*})\right\|\leq 2\gamma LM^{2}\left\|x^{k}-x^{*}\right\|.$

Die für die quadratische Konvergenz zu zeigende Ungleichung bekommt man schließlich, indem man die rechte Seite in (6.24) mittels letzterer Abschätzung und mittels (6.25) für $k\geq k_{3}$ nach oben abschätzt.

q.e.d.

Bemerkung 6.12

Im Fall der quadratischen Funktion

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

mit positiv definiter Matrix $Q$ ist die Newton-Richtung $p^{0}$ für einen Startpunkt $x^{0}$ gegeben durch

$p^{0}:=-\nabla ^{2}f(x^{0})^{-1}\nabla f(x^{0})=-Q^{-1}\left(Qx^{0}+c\right)=-x^{0}-Q^{-1}c.$

Bei Verwendung einer exakten Schrittweite erhält man weiter gemäß (3.5)

$t_{0}:=-{\frac {\nabla f(x^{0})^{T}p^{0}}{(p^{0})^{T}Qp^{0}}}={\frac {\nabla f(x^{0})^{T}Q^{-1}\nabla f(x^{0})}{\nabla f(x^{0})^{T}Q^{-1}QQ^{-1}\nabla f(x^{0})}}=1.$

Demzufolge ergibt sich

$x^{1}:=x^{0}+t_{0}p^{0}=x^{0}+p^{0}=-Q^{-1}c.$

Das lokale sowie das globalisierte Newton-Verfahren mit einer exakten Schrittweitenregel liefern also für eine quadratische Funktion mit positiv definiter Matrix $Q$ unabhängig von der Wahl des Startpunktes immer nach einem Schritt den globalen Minimalpunkt $x^{*}:=-Q^{-1}c$. Anders als bei den CG-Verfahren, die nach spätestens $n$ Schritten den Minimalpunkt finden, muss dazu aber ein lineares Gleichungssystem gelöst werden.

6.3 Bemerkungen und Hinweise

Ein Iterationsschritt des lokalen und globalisierten Newton-Verfahrens ist numerisch sehr aufwändig, da u. a. die Hesse-Matrix der Zielfunktion ausgewertet werden muss. Als symmetrische Matrix besitzt sie im Extremfall $(n^{2}+n)/2$ unterschiedliche Einträge ($n$ Diagonalelemente und $(n^{2}-n)/2$ Elemente oberhalb der Diagonale). Diese Einträge, die partiellen Ableitungen von $f$, müssen entweder zunächst analytisch bestimmt oder numerisch berechnet werden. Zur Bestimmung der Newton-Richtung muss dann anschließend noch ein lineares Gleichungssystem gelöst werden.

Die Voraussetzung (V5) ist in der Praxis im Allgemeinen nicht nachprüfbar, so dass die Hesse-Matrix $\nabla ^{2}f(x^{k})$ für ein $x^{k}$, welches weit entfernt von einem strikt lokalen Minimalpunkt $x^{*}$ liegt, indefinit oder singulär sein kann. In einem solchen Fall liefert das Verfahren keine Abstiegsrichtung und ist es damit möglicherweise nicht konvergent bzw. ist es - im singulären Fall - überhaupt nicht durchführbar. Aber selbst wenn $\nabla ^{2}f(x^{k})$ für alle $k$ positiv definit ist, kann die dem Newton-Verfahren zugrunde liegende quadratische Approximation in Punkten $x^{k}$, die weit von einem strikt lokalen Minimalpunkt von $f$ entfernt sind, so schlecht sein, dass verglichen mit dem Aufwand pro Iteration ein zu geringer Fortschritt erzielt wird. Wir erinnern in diesem Zusammenhang daran, dass die quadratische Konvergenz erst zum Tragen kommt, wenn $\left\|x^{k}-x^{*}\right\|<1$ ist (vgl. Abschnitt 1.4).

Eine Teillösung für die genannten Schwierigkeiten bringen die inexakten Newton-Verfahren. Bei diesen benötigt man zwar auch die Hesse-Matrix in der aktuellen Iterierten, aber man muss bei ihnen nur eine im gewissen Sinne "inexakte" Lösung des im Verfahren auftretenden linearen Gleichungssystems bestimmen. Eine solche Näherungslösung kann auch existieren, wenn der Startpunkt zu weit entfernt von einem lokalen Minimalpunkt gewählt wurde und daher das System selbst keine Lösung besitzt.

Um mindestens eine superlineare Konvergenzrate für ein inexaktes Newton-Verfahren zu erzielen, muss jedoch die Genauigkeit der Näherungslösungen im Laufe des Iterationsprozesses zunehmen und im Grenzwert die exakte Lösung gefunden werden. Die inexakten Lösungen der linearen Gleichungssysteme selbst werden dabei z. B. mit einem CG-Verfahren berechnet, wobei man häufig einen Präkonditionierer zur Erzielung einer guten Konvergenzrate einsetzt (siehe z. B. [GeiKa99] für Details).

Das Newton-Verfahren selbst sollte man aus den genannten Gründen bei Zielfunktionen, die nicht gleichmäßig konvex sind, nur dann anwenden, wenn man eine gute Startnäherung für eine Lösung des Problems kennt. Eine solche kann man mit einem anderen global konvergierenden Verfahren gewinnen, wie z. B. auch dem Gradientenverfahren, welches häufig in den ersten Iterationen gute Fortschritte macht. Da man nicht weiß, ob man sich beim Übergang zum Newton-Verfahren bereits im Konvergenzbereich des lokalen Newton-Verfahrens befindet, sollte man dann aber auf jeden Fall das globalisierte Newton-Verfahren z. B. mit der Armijo-Schrittweitenregel verwenden.

Diesen Übergang vom Gradientenverfahren zum Newton-Verfahren leisten die im folgenden Kapitel diskutierten Quasi-Newton-Verfahren "automatisch", wenn man dort die Einheitsmatrix als Startmatrix wählt. Gegenüber dem Newton-Verfahren haben sie darüber hinaus den Vorteil, einen wesentlich geringeren numerischen Aufwand pro Iteration zu erfordern, wobei sie unter geeigneten Voraussetzungen ebenfalls zumindest superlinear konvergieren.