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.)
Eine in der Praxis häufig auftretende Aufgabe ist es, eine Lösung
eines nichtlinearen Gleichungssystems

zu finden, wobei
eine offene Menge und
eine nichtlineare, einmal stetig differenzierbare Funktion mit Jacobi-Matrix

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

von
bei
zu ersetzen und die Nullstelle von
als neue Näherung
von
zu wählen. Dieses Vorgehen führt zu der bereits aus der Numerischen Mathematik bekannten Iterationsvorschrift des Newton-Verfahrens
- (6.1)
![{\displaystyle x^{k+1}:=x^{k}-\left[{\mathcal {J}}_{F}(x^{k})\right]^{-1}F(x^{k}),\quad k=0,1,....}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e465caee1273d30fb22ab3f7814ca13d753970cb)
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
die Matrix
nichtsingulär und it
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

Demnach erhält man
auch, indem man die eindeutige Lösung
des linearen Gleichungssystems
- (6.2)

bestimmt und man anschließend

setzt. (Den Variablenvektor in einem Gleichungssystem wie
in (6.2) schreiben wir ohne einen Index, während wir eine Lösung des Systems wie hier
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)
[Bearbeiten]
- (0) Wähle
und setze
.
- (1) Falls
ist, stop!
- (2) Bestimme die eindeutige Lösung
des linearen Gleichungssystems
- (6.3)

- und setze

- (3) Setze
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
wieder die Euklidische Norm auf dem
bzw. die durch sie induzierte Matrixnorm auf dem Raum
, die Spektralnorm, bezeichne (die Ergebnisse sind auch für jede andere Vektornorm und dadurch induzierte Matrixnorm gültig). Mit

für ein
bezeichnen wir wieder die offene
-Umgebung von
. 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.
- Sei
eine stetige vektorwertige Funktion, sei
für
und sei
der Vektor mit den Komponenten
. Dann gilt:

Es sei
das Standardskalarprodukt auf dem
aus (5.7) und es sei
. Dann gilt unter Verwendung der Cauchy-Schwarz-Ungleichung


- Es sei
offen und
sei einmal stetig differenzierbar. Ferner existiere ein
, für welches
gelte und
nichtsingulär sei. Dann gibt es eine Umgebung
von
für ein
, so dass Algorithmus 6.1 für jeden Startpunkt
durchführbar ist und er, sofern er nicht nach endlich vielen Schritten mit
abbricht, eine Folge
erzeugt, für welche gilt:
- (i)
konvergiert superlinear gegen
.
- (ii) Hat man mit einem
- (6.4)

- so konvergiert
quadratisch gegen
.
(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
eine reguläre Matrix. Dann ist die Matrix
für jede Matrix
mit
regulär und es gilt
- (6.5)

Wegen der Stetigkeit von
auf
können wir zunächst
so klein wählen, dass gilt:
![{\displaystyle \|{\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^{*})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/57a227d17a4e46b935d6a765ed1b7a006c37083a)
Für
ergibt sich damit aus der anfangs gegebenen Aussage die Invertierbarkeit der Matrix
![{\displaystyle {\mathcal {J}}_{F}(x)={\mathcal {J}}_{F}(x^{*})+[{\mathcal {J}}_{F}(x)-{\mathcal {J}}_{F}(x^{*})]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8ca710465d6fe585d6ee1ed8c2ed72cac7d88d0)
sowie mit (6.5) und
die Abschätzung
- (6.6)
![{\displaystyle \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 .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d32ebac8069bd8320d6e9196a675513cbcde60fa)
Sei nun
![{\displaystyle {\mathcal {N}}(x):=x-[{\mathcal {J}}_{F}(x)]^{-1}F(x),\quad x\in {\mathcal {U}}_{\eta }(x^{*})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25f0ae62767ec5bb6c8539cebdf17fc22e48d52b)
die Iterationsfunktion des lokalen Newton-Verfahrens, die nach dem Gezeigten auf
wohldefiniert ist. Mit
und den Identitäten

schließen wir als nächstes
![{\displaystyle {\mathcal {N}}(x)-x^{*}=x-x^{*}-[{\mathcal {J}}_{F}(x)]^{-1}[F(x)-F(x^{*})]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe996a39dfb55df6926e66952e24cf80140157bf)
![{\displaystyle =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\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af7bd4fa39314e3d326050c8e9cf01d957719463)
![{\displaystyle =-[{\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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c1c53fff3d1cd4d9d4db2681415e876b268e4015)
Für
- (6.7)

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

Wegen der Stetigkeit von
auf
existiert ein
, so dass
auf
ist und damit gilt:

Beginnend mit
liegt folglich mit
auch
in
und konvergiert die Folge
linear gegen
. Die Konvergenz von
impliziert weiter die Konvergenz
. Da gemäß (6.8)
- (6.9)

für alle
gilt, folgt schließlich die superlineare Konvergenz von
.
(ii) Gilt nun (6.4) auf
, dann liegt für jedes
mit
und
auch
für alle
in
und folgt somit

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

Letzteres zeigt zusammen mit (6.9) die quadratische Konvergenz der Folge
.
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
eine beliebige reguläre Matrix und
irgendein Vektor: ist
die durch das lokale Newton-Verfahren für den Startpunkt
erzeugte Iteriertenfolge zur Bestimmung einer Lösung des Gleichungssystems
, so erzeugt das Verfahren bei Anwendung auf das System

für den Startpunkt
die Iteriertenfolge
mit

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
eine vorgegebene Abbruchschranke, so gilt aufgrund der oben beschriebenen Invarianz gegenüber affin-linearen Transformationen und der sich daraus ergebenden Identitäten

die Äquivalenz

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
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.
Das lokale Newton-Verfahren kann offenbar zur Bestimmung eines kritischen Punktes
einer Funktion
eingesetzt werden. Da wir nur an kritischen Punkten von
interessiert sind, die das Optimierungsproblem

lösen, d. h., die lokale Minimierer von
sind, ist es sinnvoll anzunehmen, dass die hinreichenden Optimalitätsbedingungen zweiter Ordnung aus Satz 1.14 in
erfüllt sind, also
gilt und die Matrix
positiv definit ist. Letzteres impliziert aufgrund der Stetikeit von
in
die Existenz eines
, so dass auch die Hesse-Matrizen
![{\displaystyle \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^{*})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1567c084485349b7291c55aee3b8ec93a5b9ff42)
positiv definit sind. (Gemäß Satz 6.3 würde es in diesem Unterabschnitt genügen, nur die Nichtsingularität von
vorauszusetzen. Da wir aber nicht an beliebigen kritischen Punkten, sondern an lokalen Minimalpunkten von
interessiert sind, fordern wir hier, dass die Matrix
positiv definit ist.) Denn es gilt:
- Seien
und seien
und
symmetrische Matrizen. Ist
positiv definit und
der kleinste Eigenwert von
, dann ist auch
für jede Matrix
mit
positiv definit.
Mit Lemma 1.10 erschließt man:

Setzt man
für
, so folgt daraus

q.e.d.
Algorithmus 6.1 lautet dann wie folgt:
Algorithmus 6.5 (Lokales Newton-Verfahren)
[Bearbeiten]
- (0) Wähle
und setze
.
- (1) Falls
ist, stop! (
ist kritische Lösung von Problem
.)
- (2) Bestimme die eindeutige Lösung
des linearen Gleichungssystems
- (6.10)

- und setze

- (3) Setze
und gehe nach (1).
Das lokale Newton-Verfahren zur Bestimmung einer Lösung
von
kann man auch auf direkte Weise motivieren. Ist
eine aktuelle Näherung von
, wobei
wie oben definiert und somit
positiv definit ist, so ersetze man
näherungsweise bei
durch das quadratische Taylor-Polynom

Als neue Näherung
von
wähle man dann den eindeutigen Minimalpunkt der gleichmäßig konvexen, quadratischen Funktion
, d. h., man bestimme die eindeutige Lösung
des linearen Gleichungssystems

Da
positiv definit ist, lässt sich diese Lösung mit

angeben, wobei
- (6.11)
![{\displaystyle p^{k}:=-\left[\nabla ^{2}f(x^{k})\right]^{-1}\nabla f(x^{k})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/020390483301b6fa7172acd6095e9a12ab39d9e1)
die sog. Newton-Richtung ist. Diese Richtung lässt sich offenbar als eindeutige Lösung des linearen Gleichungssystems (6.10) gewinnen.
Ist die Matrix
, wie hier angenommen wurde, positiv definit, so ist auch ihre Inverse
positiv definit und folglich
- (6.12)
![{\displaystyle \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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/654fbd033048256d4f1745b46a97aea3c3223637)
Also ist die Newton-Richtung
in diesem Fall eine Abstiegsrichtung für
in
, die sich aus einem lokalen quadratischen Modell für
bei
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.
- Es sei
und
sei ein lokaler Minimalpunkt von
, für den die Hesse-Matrix
positiv definit ist. Dann existiert eine Umgebung
von
für ein
, so dass Algorithmus 6.5 für jeden Startpunkt
durchführbar ist und er, sofern er nicht nach endlich vielen Schritten mit
abbricht, eine Folge
erzeugt, für welche gilt:
- (i)
konvergiert superlinear gegen
.
- (ii) Hat man mit einem
- (6.13)

- so konvergiert
quadratisch gegen
.
6.2 Das globalisierte Newton-Verfahren
[Bearbeiten]
Das Newton-Verfahren lässt sich durch Einführung einer Schrittweite
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)
[Bearbeiten]
- (0) Wähle eine semieffiziente Schrittweitenregel und ein
. Setze
.
- (1) Falls
ist, stop! (
ist kritische Lösung von Problem
.)
- (2) Bestimme die eindeutige Lösung
des linearen Gleichungssystems

berechne
und setze

(3) Setze
und gehe nach (1).
Um insbesondere zu sichern, dass die Newton-Richtung
existiert und eine Abstiegsrichtung ist, setzen wir die gleichmäßige positive Definitheit der Hesse-Matrizen
auf der Menge
aus (2.9) voraus:
- (V5) Es ist
, die Menge
aus (2.9) ist konvex und es existieren Konstanten
mit
- (6.14)

(Die Voraussetzung (V5) wird an mehreren Stellen in diesem Kurs verwendet. Die Menge
darin ist dann durch den Startpunkt des jeweilig betrachteten Verfahrens definiert.)
Die Voraussetzung (V5) impliziert die Bedingungen (V1) - (V4). (Gemäß Satz 1.4 ist
auf
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
von
, welcher globaler Minimierer von
ist (vgl. Korollar 1.18).
Die Bedingung (6.14) ist ferner äquivalent mit der Bedingung
- (6.15)
![{\displaystyle 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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0455f6d75dee1fbd4c6e75da87fcbc5e88eca1c)
(s. Lemma 1.10). Letzteres wiederum impliziert gemäß Bemerkung 2.16
- (6.16)
![{\displaystyle m\leq \left\|\left[\nabla ^{2}f(x)\right]^{-1}\right\|\leq M,\quad x\in N_{0}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/297cb0eb6de67796e70698966b47c63f974938eb)
Man beachte, dass die Voraussetzung (V5) erzwingt, dass die Matrix
positiv definit ist und dass damit
eine Abstiegsrichtung ist und
gilt. Induktiv schließt man weiter, dass die Newton-Richtung
![{\displaystyle p^{k}=-\left[\nabla ^{2}f(x^{k})\right]^{-1}\nabla f(x^{k})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/16af590b91fc6e4539eee0eda854e673dbacf41f)
für jedes
eine Abstiegsrichtung für
in
ist, womit
gilt und die Matrix
gemäß (6.14) positiv definit ist. Also passt Algorithmus 6.7 in das Schema des Modellalgorithmus 2.5 und erfüllen die Matrizen
die Forderung in (2.35).
Darüber hinaus können wir mit dem unter der Voraussetzung (V5) existierenden eindeutigen globalen Minimierer
von
mittels (6.16) die folgende Abschätzung gewinnen:
- (6.17)
![{\displaystyle \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\|.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1a1fa4140ef8e6624b8cf4ddac497f81223d5517)
Im Fall der Konvergenz von
gegen
konvergiert also die Folge
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)).
- Es sei (V5) erfüllt und
sei die somit existierende eindeutige Lösung von
. Dann ist Algorithmus 6.7 durchführbar und gilt für die durch ihn erzeugten Folgen
und
, sofern er nicht schon nach endlich vielen Schritten mit
abbricht,
- (6.18)

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
für alle hinreichend großen 
gilt. Es lässt sich ferner vermuten, dass man für jede Schrittweitenregel, für die man

zeigen kann, ebenfalls schnelle Konvergenz hat. In diesem Zusammenhang können wir für die in Kapitel 3 eingeführten Schrittweitenregeln beweisen:
- Es sei (V5) erfüllt. Bricht Algorithmus 6.7 nicht nach endlich vielen Schritten ab, dann gilt für die durch ihn erzeugte Schrittweitenfolge
:
- (i) Wird im Algorithmus die Minimum- oder Curry-Schrittweitenregel verwendet, so ist
.
- (ii) Wird im Algorithmus die Armijo-Schrittweitenregel verwendet, so ist
für alle hinreichend großen
.
- (iii) Wird im Algorithmus die Wolfe-Powell- oder die strenge Wolfe-Powell-Schrittweitenregel verwendet, so ist
für alle hinreichend großen
eine entsprechende Schrittweite.
Für die Newton-Richtung
hat man
- (6.19)
![{\displaystyle -\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff5ffc808d36db96dde9d7cf677c3a6181c3d4cb)
(i) Für jede exakte Schrittweite
ist gemäß ihrer Definition

Durch eine Taylor-Entwicklung ergibt sich daher für ein

Folglich erhalten wir mit
und mit (6.19)
- (6.20)

Für alle
und
mit
schließen wir nun mit (6.14)
- (6.21)
![{\displaystyle \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 ).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b4e766df17c8b71f981497837539826ffc9c5db)
Da Satz 6.9
und damit
impliziert, folgt Aussage (i) aus (6.20).
(ii) Eine Taylor-Entwicklung wiederum liefert mit
unter Verwendung von (6.19), einer analogen Abschätzung zu (6.21) und der Konvergenz von
in (6.18)

![{\displaystyle ={\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 ).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/111e3cd398ecea1303a39511d35dd96bafe69d29)
Daher gilt mit
aus (3.9) für alle hinreichend großen

Letzteres bedeutet aber nach Definition 3.10 der Armijo-Schrittweitenregel, dass
für alle solche
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
für
erfüllt. Weiter schließt man nun ähnlich wie im Beweis von (ii), dass mit Zahlen
gilt:

![{\displaystyle =\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 ).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae9ac8307898d3ce4ee22178f31f591abf2289d1)
Für jedes
und
folgt daher für alle hinreichend großen

Letzteres impliziert, dass
für alle hinreichend großen
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
eine solche Schrittweite ist, und gegebenenfalls
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.
- Es sei (V5) erfüllt und
sei die dann existierende eindeutige Lösung von
. Weiter werde in Algorithmus 6.7 die Minimum-, Curry-, Armijo-, Wolfe-Powell- oder strenge Wolfe-Powell-Schrittweitenregel verwendet, wobei in letzteren beiden Fällen
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
:
- (i)
konvergiert superlinear gegen
.
- (ii) Hat man mit einem
und einem
- (6.22)

- so konvergiert
quadratisch gegen
.
(i) Es gilt

und folglich
![{\displaystyle x^{k+1}-x^{*}=x^{k}-x^{*}-t_{k}\left[\nabla ^{2}f(x^{k})\right]^{-1}\nabla f(x^{k})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f98703f128f3139f64a66c8a16fee19e22b7bec5)
![{\displaystyle =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\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d92fb645daef01473e7bca8b2f21fafad986a512)
![{\displaystyle =(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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bbfbe2bbeb475a06fb3315552acdbe815ccb2194)
Daraus ergibt sich mit (6.16)
- (6.23)
![{\displaystyle {\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\|.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d78508e9af8d36f77fc9a6d105a92d26415ccbd1)
Gemäß Satz 6.9 konvergiert
gegen
, so dass die rechte Seite im Fall der Konvergenz
gegen 0 strebt. Die superlineare Konvergenz der Folge
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
mit einem
- (6.24)

Wird insbesondere die Armijo-Schrittweitenregel angewendet, so folgt nach Satz 6.10
für alle
mit einem
und ist damit die quadratische Konvergenz von
bewiesen. Bei Verwendung der Minimum- oder Curry-Schrittweitenregel andererseits folgert man zunächst aus Satz 6.10, dass ein
existiert mit
- (6.25)

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


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
nach oben abschätzt.
q.e.d.
Im Fall der quadratischen Funktion

mit positiv definiter Matrix
ist die Newton-Richtung
für einen Startpunkt
gegeben durch

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

Demzufolge ergibt sich

Das lokale sowie das globalisierte Newton-Verfahren mit einer exakten Schrittweitenregel liefern also für eine quadratische Funktion mit positiv definiter Matrix
unabhängig von der Wahl des Startpunktes immer nach einem Schritt den globalen Minimalpunkt
. Anders als bei den CG-Verfahren, die nach spätestens
Schritten den Minimalpunkt finden, muss dazu aber ein lineares Gleichungssystem gelöst werden.
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
unterschiedliche Einträge (
Diagonalelemente und
Elemente oberhalb der Diagonale). Diese Einträge, die partiellen Ableitungen von
, 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
für ein
, welches weit entfernt von einem strikt lokalen Minimalpunkt
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
für alle
positiv definit ist, kann die dem Newton-Verfahren zugrunde liegende quadratische Approximation in Punkten
, die weit von einem strikt lokalen Minimalpunkt von
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
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.