Kapitel 1

Teil I
Unrestringierte Probleme
2
Geg.: f : Rn → R, f ∈ C 1 (Rn ; R)
Ziel: suche Minimierer von f
3
Kapitel 1
Abstiegsverfahren
1.1 Allgemeine Abstiegsverfahren
Definition 1.1:
Sei x ∈ Rn . d ∈ Rn heißt Abstiegsrichtung für f bei x, falls ∃t > 0 s.d.
f (x + td) < f (x)
∀t ∈ (0, t)
Satz 1.2:
Sei f ∈ C 1 (Rn , R), d ∈ Rn mit ∇ f (x) · d < 0.
Dann gilt: d ist Abstiegsrichtung.
Beweis:: X
2
Algorithmus 1.3 (allgemeines Absteigsverfahren):
(S0) wähle x0 , setze k := 0
(S1) while (xk erfüllt nicht Abbruchkrit.) do {
(S2)
wähle Abstiegsrichtung dk von f in xk
(S3)
wähle Schrittweite tk > 0 mit f (xk + tk dk ) < f (xk )
(S4)
xk+1 := xk + tk dk ; k := k + 1
}
Beobachtung:
Eine von Algorithmus 1.3 erzeugte Folge muss nicht gegen Minimierer von f
4
konvergieren.
~ Konvergenz könnte dadurch erreicht werden, dass die tk schnell klein werden!
Es ist also nötig, das Konzept des “hinreichend großen Abstiegs” einzuführen.
Definition 1.4 (Schrittweitenstrategie, Effizienz):
Rn | d ist in Abstiegsrichtung für f in x }
• Sei A := {(x, d) ∈ Rn ×
• Für jedes (x, d) ∈ A sei T (x, d) ∈ R+ nicht leer. Wir nennen T “Schrittweitenregel”.
• Eine Schrittweitenregel T heißt effizient, falls es θ > 0 gibt, sodass ∀(x, d) ∈
A
∇ f (x)d
f (x + td) ≤ f (x) − θ
kdk
!2
∀t ∈ T (x, d)
Beispiel 1.5 (Armijo-Regel):
Sei σ ∈ (0, 1). Dann ist für (x, d) ∈ A
T Armi jo (x, d) := {t > 0 | f (x + td) ≤ f (x) + σt∇ f (x)d} , ∅
Der Einsatz effizienter Schrittweitenregeln bei Abstiegsverfahren führt auf (lokale) Minima:
Satz 1.6:
Sei f ∈ C 1 (Rn ; R) und (xk )∞
k=0 eine von Algorithmus 1.3 erzeugte Folge. Es gelte
zudem:
(i)
−
∇ f (xk ) · dk
≥c>0
k∇ f (xk )k kdk k
∀k
(1.1)
~ “Winkelbedingung”
(ii) die Schrittweiten tk sind effizient, d.h.
∇ f (xk ) · dk
f (xk+1 ) ≤ f (xk ) − θ
kdk k
!2
∀k
Dann gilt: Jeder Häufungspunkt von (xk )k ist stationärer Punkt von f .
5
(1.2)
Beweis:
• Sei x∗ Häufungspunkt von (xk )∞
k=0
∗
• Weil ( f (xk ))∞
k=0 monoton ↓ und eine TF gegen f (x ) konvergiert, konvergiert
die gesamte Folge:
lim f (xk ) = f (x∗ )
k→∞
• aus Effizienz und Winkelbedingung folgt
!2
∇ f (xk ) · d x
f (xk+1 ) ≤ f (xk ) − θ
kdk k
|∇ f (xk ) · dk |2
= f (xk ) − θ
kdk k2
| {z
}
≥c2 k∇ f (xk )k2
≤ f (xk ) − θc2 k∇ f (xk )k2
⇒ 0 ≤ θc2 k∇ f (xk )k2 ≤
f (x ) − f (x )
| k {z k+1}
→ f (x∗ )− f (x∗ )=0 für k→∞
⇒ lim k∇ f (xk )k2 = 0 ⇒ ∇ f (x∗ ) = 0
k→∞
2
Bemerkung 1.7:
Die Effizienzbedingung stellt den maximalen Abstieg dar, den man realistischerweise erwarten kann. Um das zu sehen, betrachte ein quadratisches f :
1 T
x Qx + cT x + γ mit Q S PD, c ∈ Rn , γ ∈ R
2
Sei d eine Abstiegsrichtung für f ∈ x
Dann gilt:
1
f (x + td) = f (x) + t ∇ f (x) · d + t2d T Qd, t ∈ R
| {z } 2
f (x) :=
<0
Der maximale Abstieg ergibt sich für t mit ϕ′ (t) = 0, wobei ϕ(t) = f (x + td). Also
2
2
0 = ∇ f (x) · d + td T Qd ⇒ f (x + td) = f (x) − 12 t d T Qt = f (x) − 12 ∇dfT(x)·d
Qd
weil Q SPD ist, gilt für den extremen Eigenwert von Q λmin kdk2 ≤ d T Qd ≤
λmax kdk2 . Damit folgt, dass man nicht mehr als Abstieg erwarten kann als das,
was die Effizienzabschätzung gibt.
6
1.2 Schrittweitenstrategien
Sei d Abstiegsrichtung für f bei x. Die nächstliegenden Wahlen für Schrittweiten
t > 0 sind:
1. “Minimierungsregel”: wähle tmin so, dass f (x + tmin d) = mint≥0 f (x + td)
~ globales Minimum auf Strahl {x + td | t ≥ 0}
2. “Curry-Regel”: wähle tc als tc := min{t > 0 | ∇ f (x + td) · d = 0}
~ x + tc d ist also das erste Minimum von f auf den Strahl {x + td | t > 0}
Diese Regeln sind in der Praxis nicht einfach realisierbar. Oft werden deshalb die
folgenden Strategien verwendet.
Definition 1.8 (Armijo-Regel):
Sei β ∈ (0, 1), σ ∈ (0, 1), d Abstiegsrichtung von f bei x. Dann ist die ArmijoSchrittweite t definiert als
T Ami jo (x, d) = max{βl | l ∈ N0 und f (x + βl d) ≤ f (x) + σβl ∇ f (x) · d}
Bemerkung:
• in der obigen Notation ist T Armi jo(x, d) eindeutig
• T Armi jo ist numerisch einfach zu bestimmen: man probiert l = 0, 1, . . . aus
bis man βl gefunden hat, welches f (x + βl d) ≤ f (x) + σβl∇ f (x) · d liefert.
Wegen σ < 1 und ∇ f (x) · d < 0 gibt es ein solches l.
Illustration:
• die Armijo-Regel erzwingt Abstieg, dies ist aber nicht notwendig effizient
im Sinne von Definition 1.4.
Sei ϕ(t) := f (x + td). Die Armijo-Regel sucht t > 0, sodass ϕ(t) ≤ ϕ(0) + tσϕ′(0).
Im Hinblick auf die Minimierungsregel bzw. Curry-Regel, scheint es sinnvoll,
t > 0 so zu bestimmen, dass |ϕ′ (t)| klein ist.
Definition 1.9 (Strenge Wolfe-Powell-Regel):
Sei d Abstiegsrichtung von f in x. Sei σ ∈ (0, 12 ), ρ ∈ (σ, 1).
7
hier kommt die
Illustration her
T S W P (x, d) := {t > 0| f (x+td) ≤ f (x)+tσ∇ f (x)·d und |∇ f (x+td)·d| ≤ −ρ∇ f (x)·d}
Illustration:
hier kommt die
Illustration her
Satz 1.10 (Wohldefiniertheit und Effizienz von SWP):
Sei f ∈ C 1 (Rn , R), σ ∈ (0, 21 ), ρ ∈ (σ, 1). Sei x0 ∈ Rn und L(x0 ) := {x ∈ Rn | f (x) ≤
f (x0 )}. Sei d Abstiegsrichtung von f in x ∈ L(x0 ) und
T S W P (x, d) = {t > 0 | f (x+td) ≤ f (x)+tσ∇ f (x)·d und |∇ f (x+td)·d| ≤ −ρ∇ f (x)·d}
Dann gilt:
(i) Ist f nach unten beschränkt, dann ist T S W P (x, d) , ∅
(ii) Ist ∇ f auf L(x0 ) Lipschitzstetig, so existiert θ > 0 (unabhängig von x ∈
L(x0 ) und d) mit
∇ f (x) · d
f (x + td) ≤ f (x) − θ
kdk
!2
∀t ∈ T S W P (x, d)
Beweis: ad(i):
Sei ϕ(t) := f (x + td) und ψ(t) := f (x) + tσ∇ f (x) · d.
z.z.: ∃t > 0 mit ϕ(t) ≤ ψ(t) ∧ |ϕ′ (t)| ≤ −ρϕ′ (0)
1. Schritt:
wegen ϕ′ (0) < ψ′ (0), limt→∞ ψ(t) = −∞, ϕ nach unten beschränkt, existiert t∗ > 0
mit
a) ϕ(t) ≤ ψ(t)
∀t ∈ [0, t∗]
b) ϕ(t∗ ) = ψ(t∗ )
Insbesondere folgt ϕ′ (t∗ ) − ψ′ (t∗ ) ≥ 0
2. Schritt:
betrachte die Fälle ϕ′ (t∗ ) < 0 und ϕ′ (t∗ ) > 0
Schritt 2a: Sei ϕ′ (t∗ ) < 0. Dann gilt:
• ϕ(t∗ ) = ψ(t∗ )
• |ϕ′ (t∗ )| = −ϕ′ (t∗ ) ≤ −ψ′ (t∗ ) = −σϕ′ (0) ≤ −ρϕ′ (0) also ist t∗ ∈ T S W P (x, d)
8
hier
kommt
eine Illustration
her
Schritt 2b: Sei ϕ′ (t∗ ) ≥ 0. Wegen ϕ′ (0) < 0 existiert dann t∗∗ ∈ (0, t∗ ) mit ϕ′ (t∗∗ ) =
0 und, nach 1. Schritt, ϕ(t∗∗ ) ≤ ψ(t∗∗ ). Also ist t∗ ∈ T S W P (x, d).
ad(ii): Sei t ∈ T S W P (x, d). Dann gilt:
• f (x + td) ≤ f (x) + tσ∇ f (x) · d ≤ f (x) ⇒ x + td ∈ L(x0 )
• ρ∇ f (x) · d ≤ −|∇ f (x + td) · d)| ≤ +∇ f (x + td) · d ⇒ (ρ − 1)∇ f (x) · d ≤
(∇ f (x + td) − ∇ f (x)) · d ≤ k∇ f (x + td) − ∇ f (x)k ||d||
bezeichnet L die Lipschitzkonstante von ∇ f auf L(x0 ), so folgt wg x, x + td ∈
L(x0 ):
(ρ − 1)∇ f (x) · d ≤ Lktdk kdk,
das heißt
t≥
(ρ − 1)∇ f (x) · d
Lkdk2
und somit
∇ f (x) · d
σ
(1 − ρ)
f (x + td) ≤ f (x) + σ∇ f (x) · dt ≤ f (x) −
L
kdk
|{z}
!2
=:θ>0
2
Bemerkung 1.11:
Warum σ ∈ (0, 21 )? Auf diese Weise wird garantiert, dass für quad. ϕ (also z.B.
für quad. f ) das exakte Minimum in T S W P liegt: Es gilt für t : ϕ′ (t) = 0, das heißt
ϕ′ (0) + tϕ′′(0) = 0
=
die “kritische” Gerade geht durch (0, ϕ(0)) und (t, ϕ(t)). Ihre Steigung ist ϕ(t)−ϕ(0)
t
1 ′
1 ′′
1
′
ϕ (0) + 2 tϕ (0) = 2 ϕ (0). Damit muss σ < 2 sein.
1.3 Numerische Realisierung der Schrittweitenregel
Laut Definition 1.8 ist die Armijo-Regel bereits realisierbar.
Ziel einer alg. Realisierung der strengen Wolfe-Powell-Regel ist die Konstruktion
eines t ∈ T S W P (x, d).
Der Erfolg der Algorithmen basiert auf folgendem Lemma:
9
hier
kommt
eine Illustration
her
Lemma 1.12:
Bezeichne ha, bi = [min{a, b}, max{a, b}] ein Interval mit Endpunkten a und b und
a , b. Es gelte
ϕ′ (a)(b − a) ≤ 0.
Dann gilt: Es gibt t ∈ ha, bi mit |ϕ′ (t)| < σ|ϕ′(0)|, falls eine der folgenden zwei
Bedingungen erfüllt ist:
(i) ϕ(a) ≤ ϕ(b)
(ii) ϕ(a) ≤ ϕ(0) + aσϕ′ (0) UND ϕ(b) ≥ ϕ(0) + bσϕ′(0)
Beweis: Im Fall (i) sieht man elementar, daß es sogar ein t ∈ ha, bi gibt mit ϕ′ (t) =
0 (Fallunterscheidung a < b und b > a!; BILD).
Im Fall (ii) mit b < a (BILD), folgt aus ϕ′ (a)(b − a) ≤ 0, daß ϕ′ (a) ≤ 0. Weiters
ist, weil ϕ′ (0) < 0, ϕ(b) > ϕ(a). Damit muß es ein t ∈ (b, a) geben mit ϕ′ (t) = 0.
Im Fall (ii) mit a < b (BILD), folgt aus ϕ′ (a)(b − a) ≤ 0, daß ϕ′ (a) < 0. Aus
ϕ(a) ≤ ϕ(0) + aσϕ′ (0) und ϕ(b) ≥ ϕ(0) + bσϕ′(0) folgt, daß es einen Schnittpunkt
t′ ∈ [a, b] von ϕ mit der Gerade gibt. Damit muß es zwischen a und t′ einen Punkt
t geben, für den |ϕ′ (t)| < σ|ϕ′(0)| ist.
2
Algorithmus 1.13 (Realisierung der SWP-Regel, I):
% input: σ ∈ (0, 1), ρ ∈ (σ, 1), γ > 1, x ∈ Rn , d ∈ Rn Abstiegsrichtung
% output: t∗ > 0 mit t ∈ T S W P (x, d)
t0 := 0, wähle tmax > 0 und t1 ∈ (0, tmax ); i := 1
% z.B. tmax so, daß ϕ(tmax ) ≥ ϕ(0) + tmax σϕ′(0)
while (TRUE) {
if (ϕ(ti ) ≥ ϕ(0) + σti ϕ′ (0)) or (ϕ(ti ) ≥ ϕ(ti−1 ) and i > 1) then {
t∗ := zoom(ti−1 , ti ); stop}
if |ϕ′ (ti )| ≤ −ρϕ′ (0) then { t∗ := ti ; stop}
if ϕ′ (ti ) ≥ 0 then { t∗ := zoom(ti , ti−1 ); stop}
wähle ti+1 ∈ (ti , tmax ); i := i + 1 % z.B. ti+1 := Mittelwert oder was Besseres
}
Algorithmus 1.14 (Realisierung der SWP-Regel, II):
% input: intervall ha, bi, welches die Voraussetzungen von Lemma 1.12 erfüllt.
function t∗ = zoom(a, b)
while (TRUE) {
10
wähle t ∈ ha, bi
if ϕ(t) ≥ ϕ(0) + σtϕ′ (0) or ϕ(t) ≥ ϕ(a) then { b := t }
else
if |ϕ′(t)| ≤ −ρϕ′ (0) then { t∗ := t; stop }
if ϕ′ (t)(b − a) < 0 then { b := a }
a := t }
}
% z.B. Mittelwert
Lemma 1.15:
Sei f ∈ C 1 (Rn , R) nach unten beschränkt. Sei d ∈ Rn Absteigsrichtung von f in x.
Dann gilt: Algorithmus 1.13 ist wohldefiniert, das heißt liefert ein Ergebnis, falls
tmax > 0 so gewählt wird, daß ϕ(tmax )−(ϕ(0)+tmax σϕ′ (0)) ≥ 0 und wenn die Punkte
t in Alg. 1.14 im Nichtabbruchfall immer so gewählt werden, daß die entstehenden
Intervalle ha, bi schnell schrumpfen.
Beweis: Wir skizzieren nur den Beweis. Die Beweisidee ist, daß mittels Alg. 1.13
ein Intervall ha, bi gefunden wird, welches die Voraussetzungen von Lemma 1.12
erfüllt. Die Anwendung der Funktion zoom (Alg. 1.14) findet dann eine hinreichend genaue Approximation durch eine Art Bisektionsverfahren.
1. Schritt: Alg. 1.13 erzeugt eine monoton wachsende Folge ti .
2. Schritt: Alg. 1.13 erzeugt ein Intervall ha, bi, welches die Vorausetzungen von
Lemma 1.12 erfüllt. Zudem ist a so, daß ϕ(a) ≤ ϕ(0) + aσϕ′ (0).
Wir gehen die verschiedenen Fälle durch:
• i = 1 und ϕ(t1 ) ≥ ϕ(0) + t1 σϕ′ (0): dann ist a = t0 = 0 und b = t1 > 0 sowie
ϕ′ (a)(b − a) ≤ 0.
• i > 1 und ϕ(ti ) ≥ ϕ(ti−1 ): Dann ist a = ti−1 und b = ti . Wegen ϕ′ (ti−1 ) < 0
(kein Abbruch im vorangegangen Schritt!) ist also ϕ′ (a)(b − a) < 0.
• i > 1 und ϕ(ti ) ≥ ϕ(0) + ti σϕ′(0): Es muss gelten ϕ(ti−1 ) < ϕ(0) + ti−1 σϕ′(0)
und ϕ′ (ti−1 ) < 0 (kein Abbruch im vorangegangen Schritt!). Damit wieder
die Voraussetzungen von Lemma 1.12 mit a = ti−1 und b = ti .
• i ≥ 1 und ϕ′ (ti ) ≥ 0: Wegen ϕ′ (ti−1 ) < 0 (kein Abbruch!) sowie ϕ(ti ) <
ϕ(ti−1 ) leistet die Wahl a = ti und b = ti−1 auch hier das Gewünschte.
3. Schritt: Wir analysieren die Funktion zoom: Wir behaupten: in jedem Schritt
(der nicht zum Abbruch führt) wir ein Intervall ha, bi erzeugt, welches die Voraussetzungen von Lemma 1.12 erfüllt. Da die entstehende Folge von Intervallen
gegen einen Punkt konvergiert (zumindest, wenn die Punkte t immer so gewählt
11
werden, daß die Intervallänge signifikant schrumpft) ergibt sich damit aus Lemma 1.12 die Existenz von t∗ mit der gewünschten SWP-Eigenschaft.
Sei ha, bi so, daß ϕ′ (a)(b − a) < 0, ϕ(a) ≤ ϕ(0) + aσϕ′ (0). Gelte zusätzlich einer
beiden Fälle in Lemma 1.12. Wir betrachten die möglichen Fälle:
• ϕ(t) > ϕ(0) + tσϕ′ (0): dann ist die neue Wahl ha, ti OK.
• ϕ(t) ≥ ϕ(a): Dann ist die neue Wahl ha, ti OK.
• ϕ(t) ≤ ϕ(0) + tσϕ′ (0) UND ϕ(t) < ϕ(a):
– für ϕ′ (t)(b − a) ≥ 0 ist dann das Intervall ht, ai OK,
– für ϕ′ (t)(b − a) < 0 ist dann das Intervall ht, bi OK.
2
Bemerkung: Die Aussage “wähle” in Alg. 1.13 und 1.14 kann z.B. einfach durch
Mittelwertbildung bestimmt werden. Cleverer sind geeignete Extrapolationen.
1.4 Gradientenverfahren (“steepest descent”)
Das “klassische” Gradientenverfahren wählt als Suchrichtung dk := −∇ f (xk ) und
verwendet die Armijo-Regel aus Definition 1.8. Diese Kombination führt bereits
auf “Konvergenz”:
Satz 1.16 (Gradientenverfahren):
Sei f ∈ C 1 (Rn , R). Sei (xk )∞
k=0 durch Algorithmus 1.3 mit dk := −∇ f (xk ) und
Armijo-Regel (Def. 1.8) erzeugt. Dann gilt: Jeder Häufungspunkt von (xk ) ist stationärer Punkt von f .
Beweis:
∗
′ ′
′
• Sei x∗ = Häufungspunkt von (xk )∞
k=0 , (xk )k TF mit xk → x
• limk→∞ f (xk ) = f (x∗ ) : ( f (xk ))∞
k=0 ist monoton fallend und eine TF konvergiert gegen f (x∗ )
• limk→∞ tk k∇ f (xk )k2 = 0: folgt aus Armijo-Regel:
f (xk+1 ) ≤ f (xk ) + σtk ∇ f (xk ) · dk ⇒
σtk k∇ f (xk )k2 ≤ f (xk ) − f (xk+1 ) → 0
12
(1.3)
• Annahme: ∇ f (x∗ ) , 0. Dann folgt aus (1.3) tk → 0. Da bei der Armijoregel
tk = βl für ein l ∈ N0 , folgt also l ≥ 1 für hinreichend große k. Insbesondere
impliziert damit die Wahl von tk in der Armijoregel, daß für hinreichend
große k′ :
f (xk′ + β−1 tk′ dk′ )
Armijo: tk′ β−1 < 1 wurde abgelehnt!
>
f (xk′ ) + σtk′ β−1 ∇ f (xk′ ) · dk′ ,
Taylor
f (xk′ + β−1 tk′ dk′ ) = f (xk′ ) + β−1 tk′ ∇ f (xk′ ) · dk′ + o(tk′ ).
Kombination der beiden Aussagen liefert wegen dk′ = −∇ f (xk′ ) und ∇ f (xk′ ) ,
0, weil ∇ f (x∗ ) , 0 und xk′ nahe bei x∗ :
β−1 σtk′ ∇ f (xk′ ) · dk′ > f (xk′ + β−1 tk′ dk′ ) − f (xk′ )
= β−1 tk′ ∇ f (xk′ ) · dk′ + o(tk′ ).
Wegen ∇ f (xk′ ) , 0 und dk′ = −∇ f (xk′ ) ergibt sich
k′ → ∞,
σ > 1 + o(1),
Widerspruch!
2
1.5 Gradientenverfahren bei quadratischen Zielfunktionen
Ziel: Abschätzen der Konvergenzgeschwindigkeit des Gradientenverfahrens
Idee:
• Betrachte quadratisches f :
1
f (x) = γ + cT x + xT Qx
2
(1.4)
für geg. γ ∈ R, c ∈ Rn , Q S PD
~ beachte: in der Nähe des Minimums von f ist f nach Taylor in guter
Näherung quadratisch
• Verwende die Minimierungsregel anstelle von Armijo, weil das Minimum
bestimmt werden kann:
der Minimierer t von t 7→ π(t) := f (x + td) für eine Abstiegsrichtung d ist:
t=−
∇ f (x) · d
d T Qd
13
denn
1
π(t) = f (x + td) = f (x) + t∇ f (x) · d + t2 d T Qd
2
π′ (t) = ∇ f (x) · d + td T Qd
→ Minimum t ist t = − ∇dfT(x)·d
Qd
damit ist ein Schritt des Gradientenverfahrens:
xk+1 = xk + tdk = xk −
∇ f (xk ) · dk
· dk
dkT Qdk
Satz 1.17:
Sei f gegeben durch (1.4). Es werde xk+1 aus xk mit Minimierungsregel und
dk := −∇ f (xk ) bestimmt. Sei x∗ das globale Minimum von f . Seien 0 <
λmin < λmax der extremalen Eigenwerte von Q. Dann gilt:
−λ 2
max
min
( f (xk ) − f (x∗ ))
(i) f (xk+1 ) − f (x∗ ) ≤ λλmax
+λmin
−λ 2
min
kxk − x∗ k2Q mit kzk2Q = zT Qz
(ii) kxk+1 − x∗ k2Q ≤ λλmax
max +λmin
Für den Beweis benötigen wir
Lemma 1.18 (Kantorovitch):
Sei Q SPD mit extremalen Eigenwerten λmin , λmax . Dann gilt
4λmin λmin
(xT x)2
≥
T
T
−1
x Qx x Q x (λmax + λmin )2
Beweis:
siehe Literatur (z.B. Buch von Dietrich Braess)
Beweis von Satz 1.17:
– Erinnerung: dk := −∇ f (xk )
– x∗ ist gegeben durch −c = Qx∗
– −dk = ∇ f (xk ) = Qxk + c
14
– Taylor liefert:
Taylor
f (x) − f (x∗ ) =
1
1
(x − x∗ )T ∇2 f (x∗ )(x − x∗ ) = kx − x∗ k2Q ∀x
| {z }
2
2
=Q
(1.5)
1
Taylor
f (x∗ ) − f (xk ) = ∇ f (xk ) · (x∗ − xk ) + (x∗ − xk )T ∇2 f (xk )(x∗ − xk )
| {z }
2
=Q
1
= −dk · (x∗ − xk ) + kx∗ − xk k2Q
2
(1.6)
– (1.5), (1.6) liefern f (xk ) − f (x∗ ) = 21 dk · (x∗ − xk )
– aus x∗ = −Q−1 c und xk = Q−1 (−dk − c) folgt x∗ − xk = Q−1 dk
– daraus folgt f (xk ) − f (x∗ ) = 21 dkT Q−1 dk
– mit tk = |dk |2 /(dkT Qdk ) ist
xk+1 = xk +
|dk |2
dk
dkT Qdk
1
1 |dk |4
f (xk+1 ) = f (xk + tk dk ) = f (xk ) − tk |dk |2 + tk2 dkT Qdk = f (xk ) −
2
2 dkT Qdk
⇒
1 |dk |4
=
2 dkT Qdk
1 |dk |4 2( f (xk ) − f (x∗ ))
f (xk ) − f (x∗ ) −
2 dkT Qdk dkT Q−1 dk
!
|dk |4
( f (xk ) − f (x∗ ))
1− T
dk Qdk dkT Q−1 dk
!!
4λmin λmax
( f (xk ) − f (x∗ ))
1−
λmin + λmax
!2
λmax − λmin
( f (xk ) − f (x∗ ))
λmax + λmin
f (xk+1 ) − f (x∗ ) = f (xk ) − f (x∗ ) −
=
=
≤
=
Beweis von (ii) folgt aus (i) und (1.5)
Bemerkungen
1. Konv. linear
2.
λmax −λmin
λmax +λmin
=
κ−1
κ+1
mit κ =
λmax
λmin
15
3. Obwohl Satz 1.17 eine Abschätzung nach oben liefert, spiegelt sie das Verhalten in der Praxis gut wider
4. “Vorkond.” Gradientenverfahren: Wählt man als Suchrichtung dk = −H −1 ∇ f (xk ),
so kann man zeigen:
!
λmax (H −1 Q) − λmin (H −1 Q)
∗
kxk − x∗ kQ
kxk+1 − x kQ ≤
λmax (H −1 Q) + λmin (H −1 Q)
5. Optimale Wahl von H ist H = Q = ∇2 f (xk ). Dann ist dk = −H −1 ∇ f (xk )
gerade die Newtonsuchrichtung.
16

Download Report