Download pdf - Nichtlineare Optimierung - unibas.ch

Nichtlineare Optimierung

Skript zur Vorlesung

im

Frühjahrsemester 2011

Helmut Harbrecht

Stand: 25. Mai 2011

3

Vorwort

Diese Mitschrift kann und soll nicht ganz den Wortlaut der Vorlesung wiedergeben. Sie sollals Lernhilfe dienen und das Nacharbeiten des Inhalts der Vorlesung erleichtern. Nebenden unten genannten Büchern, diente mir auch das Vorlesungsskript Numerik nichtlinearer

Optimierung von Gerhard Starke (Uni Hannover) als fruchtbare Quelle.

Literatur zur Vorlesung:

— C. Geiger und C. Kanzow: Numerische Verfahren zur Lösung unrestringierter Op-

timierungsaufgaben, Springer-Verlag

— C. Geiger und C. Kanzow: Theorie und Numerik restringierter Optimierungsaufga-

ben, Springer-Verlag

— F. Jarre und J. Stoer: Optimierung, Springer-Verlag

4 Inhaltsverzeichnis

Inhaltsverzeichnis

1 Grundlagen 5

1.1 Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Optimalitätskriterien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3 Konvexität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Gradientenverfahren 10

2.1 Idealisierte Variante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.2 Praktische Variante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 Newton-Verfahren 15

3.1 Lokales Newton-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.2 Globalisiertes Newton-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . 203.3 Inexaktes Newton-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . 223.4 Trust-Region-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4 Quasi-Newton-Verfahren 31

5 Verfahren der konjugierten Gradienten 37

5.1 CG-Verfahren für lineare Gleichungssysteme . . . . . . . . . . . . . . . . . 375.2 Nichtlineares CG-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . 405.3 Modifiziertes Verfahren von Polak und Ribière . . . . . . . . . . . . . . . . 43

6 Nichtlineare Ausgleichsprobleme 48

6.1 Gauß-Newton-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486.2 Levenberg-Marquardt-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . 51

7 Optimierungsprobleme mit Nebenbedingungen 56

7.1 Optimalitätsbedingungen erster Ordnung . . . . . . . . . . . . . . . . . . . 567.2 Optimalitätsbedingungen zweiter Ordnung . . . . . . . . . . . . . . . . . . 62

8 Projiziertes Gradientenverfahren 65

8.1 Konvergenzeigenschaften . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658.2 Affine Nebenbedingungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

9 SQP-Verfahren 76

9.1 Quadratische Minimierungsprobleme mit affinen Nebenbedingungen . . . . 769.2 Bestimmung aktiver Nebenbedingungen . . . . . . . . . . . . . . . . . . . . 78

5

1. Grundlagen

1.1 Einführung

Optimierungsaufgaben treten in zahlreichen Anwendungsproblemen in den Natur- undIngenieurwissenschaften, der Wirtschaft oder der Industrie auf. Beispielsweise versuchenTransportunternehmen, die Fahrt- oder Flugkosten zu minimieren und dabei sicherzustel-len, dass alle Aufträge ausgeführt werden. Ebenso führt die numerische Simulation vielerphysikalischer Vorgänge in den Naturwissenschaften auf Optimierungsprobleme, da daszugrundeliegende mathematische Modell oftmals auf dem Prinzip der Energieminimierungberuht.

Unter einem endlichdimensionalen Minimierungsproblem wird die folgende Aufgabe ver-standen: Gegeben sei eine Zielfunktion f : Rn → R. Gesucht ist ein Punkt x⋆ ∈ R, sodass

f(x⋆) ≤ f(x) für alle x ∈ Rn.

Dabei ist es ausreichend, sich nur mit Minimierungsproblemen zu beschäftigen, da einMaximierungsproblem für f immer einem Minimierungsproblem für −f entspricht.

Definition 1.1 Es sei f : Rn → R. Ein Punkt x⋆ ∈ Rn heißt globales Minimum, fallsgilt

f(x⋆) ≤ f(x) für alle x ∈ Rn.

Das Minimum ist ein lokales Minimum, wenn es eine Umgebung U ⊂ Rn von x⋆ gibt,so dass

f(x⋆) ≤ f(x) für alle x ∈ U.

Das Minimim heißt strikt, wenn im Fall x 6= x⋆ jeweils die strenge Ungleichung f(x⋆) <f(x) gilt.

In der Regel ist es mit vertretbarem Aufwand nur möglich, ein lokales Minimum von f ineiner Umgebung eines Startwertes x0 zu bestimmen.

1.2 Optimalitätskriterien

Um ein lokales Minimum numerisch zu finden, versucht man iterativ die Gleichung ∇f(x) =0 zu lösen.

6 Kapitel 1. Grundlagen

Definition 1.2 Seien U ⊂ Rn eine offene Menge und f : U → R eine stetig differenzier-bare Funktion. Ein Punkt x⋆ ∈ U heißt stationärer Punkt, falls gilt

∇f(x⋆) = 0.

Wir wiederholen einige bekannte Eigenschaften lokaler Minima aus der Analysis:

Satz 1.3 (notwendige Bedingung 1. Ordnung) Ist x⋆ ein lokales Minimum von f und istf stetig differenzierbar in einer Umgebung von x⋆, dann gilt ∇f(x⋆) = 0. Der Punkt x⋆

ist also ein stationärer Punkt.

Satz 1.4 (notwendige Bedingung 2. Ordnung) Ist x⋆ ein lokales Minimum von f undist die Hesse-Matrix ∇2f stetig in einer Umgebung von x⋆, dann gilt ∇f(x⋆) = 0 und∇2f(x⋆) ist eine positiv semidefinite Matrix.

Satz 1.5 (hinreichende Bedingung 2. Ordnung) Die Hesse-Matrix ∇2f sei stetig in einerUmgebung von x⋆ mit ∇f(x⋆) = 0. Ist ∇2f(x⋆) eine positiv definite Matrix, dann ist x⋆

ein striktes lokales Minimum.

1.3 Konvexität

Wir wenden uns einem wichtigen und in der Praxis oft auftretenden Spezialfall zu, bei demwir mit einem lokalen zugleich ein globales Minimum gefunden haben. Dazu sei angemerkt,dass eine Menge D ⊂ Rn konvex ist, falls aus x,y ∈ D auch λx+ (1− λ)y ∈ D folgt füralle λ ∈ (0, 1).

Definition 1.6 Es sei D ⊂ Rn eine konvexe Menge. Die Funktion f : D → R heißtkonvex auf D, wenn für alle λ ∈ (0, 1) und alle x,y ∈ D gilt

f(λx+ (1− λ)y

)≤ λf(x) + (1− λ)f(y).

Gilt für x 6= y sogar stets die strikte Ungleichung, dann heißt die Funktion strikt konvex.Gibt es ein µ > 0, so dass

f(λx+ (1− λ)y

)+ µλ(1− λ)‖x− y‖22 ≤ λf(x) + (1− λ)f(y)

für alle λ ∈ (0, 1) und alle x,y ∈ D, dann heißt die Funktion f gleichmäßig konvex.

Beispiele 1.7

1. Die Gerade f(x) := x ist konvex auf R, aber nicht strikt konvex.

1.3. Konvexität 7

2. Die Exponentialfunktion f(x) := exp(x) ist strikt konvex auf R, dort aber nichtgleichmäßig konvex.

3. Die Parabel f(x) := x2 ist gleichmäßig konvex auf R. Hingegen ist die sehr ähnlichaussehende Funktion f(x) := x4 zwar strikt konvex auf R, aber nicht gleichmäßigkonvex.

△

•

•

•

•

-x λx+ (1− λ)y y

6

f(λx+ (1− λ)y

)

f(x)

λf(x) + (1− λ)f(y)

f(y)

f

Bei einer eindimensionalen konvexen Funktion liegt die Verbindungslinie zweier Punkteoberhalb des Graphen.

Bemerkung Sei f : Rn → R eine quadratische Funktion, das heißt

f(x) =1

2xTAx+ bTx + c

mit einer symmetrischen Matrix A ∈ Rn×n, b ∈ Rn und c ∈ R. Die Funktion f ist genaudann konvex, wenn A positiv semidefinit ist. Ist die Matrix A sogar positiv definit, so istf sogar gleichmäßig konvex. △

Satz 1.8 Seien D ⊂ Rn eine offene und konvexe Menge und f : D → R stetig differen-zierbar. Die Funktion f ist genau dann konvex auf D, wenn für alle x,y ∈ D gilt

f(x)− f(y) ≥ ∇f(y)T (x− y). (1.1)

Ist diese Ungleichung strikt für alle x 6= y, dann ist f sogar strikt konvex. Die Funktionf ist genau dann gleichmäßig konvex, wenn ein µ > 0 existiert, so dass

f(x)− f(y) ≥ ∇f(y)T (x− y) + µ‖x− y‖22 (1.2)

für alle x,y ∈ D.

Beweis. Es gelte zuächst (1.2). Für x,y ∈ D und beliebiges λ ∈ (0, 1) ergibt sich dannmit z := λx + (1− λ)y

f(x)− f(z) ≥ ∇f(z)T (x− z) + µ‖x− z‖22,f(y)− f(z) ≥ ∇f(z)T (y − z) + µ‖y − z‖22.

8 Kapitel 1. Grundlagen

Multipliziert man diese Gleichungen mit λ beziehungsweise 1−λ und addiert sie anschlie-ßend, dann folgt

λf(x) + (1− λ)f(y)− f(λx+ (1− λ)y

)≥ 2µλ(1− λ)‖x− y‖22,

das heißt, f ist gleichmäßig konvex.

Sei f nun als gleichmäßig konvex auf D vorausgesetzt. Für alle x,y ∈ D und λ ∈ (0, 1)gilt dann mit einem µ > 0

f(y + λ(x− y)

)= f

(λx+ (1− λ)y

)

≤ λf(x) + (1− λ)f(y)− µλ(1− λ)‖x− y‖22

und daher

f(y + λ(x− y)

)− f(y)

λ≤ f(x)− f(y)− µ(1− λ)‖x− y‖22.

Aufgrund der stetigen Differenzierbarkeit von f folgt somit für λ→ 0+

∇f(y)T (x− y) ≤ f(x)− f(y)− µ‖x− y‖22,

dies bedeutet, es gilt (1.2). Da der soeben geführte Beweis auch im Fall µ = 0 seineGültigkeit behält, folgt die Äquivalenz von (1.1) zur Konvexität von f .

Es verbleibt zu zeigen, dass die strikte Konvexität von f die strikte Ungleichung

f(x)− f(y) > ∇f(y)T (x− y)

für alle x,y ∈ D mit x 6= y impliziert. Als strikt konvexe Funktion ist f insbesonderekonvex, das heißt, es gilt (1.1). Für

z :=1

2(x+ y) =

1

2x+

(1− 1

2

)y

ergibt sich daher

∇f(y)T (x− y) = 2∇f(y)T (z− y) ≤ 2{f(z)− f(y)

}. (1.3)

Ist x 6= y, dann folgt wegen der strikten Konvexität

f(z) <1

2f(x) +

1

2f(y).

Dies eingesetzt in (1.3) liefert die Behauptung

∇f(y)T (x− y) < f(x)− f(y).

Satz 1.9 Die Funktion f : D ⊂ Rn → R sei konvex. Dann ist jedes lokale Minimum x⋆

auch ein globales Minimum von f . Ist f zusätzlich differenzierbar, so ist jeder stationärePunkt x⋆ ein globales Minimum.

1.3. Konvexität 9

Beweis. Angenommen, der Punkt x⋆ ist ein lokales, aber kein globales Minimum. Danngibt es einen Punkt y⋆ ∈ Rn mit f(y⋆) < f(x⋆). Für alle

x = λx⋆ + (1− λ)y⋆, λ ∈ (0, 1) (1.4)

gilt aufgrund der Konvexität

f(x) ≤ λf(x⋆) + (1− λ)f(y⋆) < f(x⋆).

Da in jeder Umgebung von x⋆ Punkte der Form (1.4) liegen, steht dies im Widerspruchzur Annahme, dass x⋆ ein lokales Minimum ist. Folglich ist jedes lokale Minimum auchein globales Minimum.

Wir zeigen nun die zweite Aussage. Dazu sei f differenzierbar vorausgesetzt und x⋆ einstationärer Punkt. Wir führen den Beweis wieder per Widerspruch und nehmen an, dassx⋆ kein lokales Minimum ist. Dann können wir ein y⋆ wie oben wählen und erhaltenaufgrund der Konvexität

∇f(x⋆)T (y⋆ − x⋆) =d

dsf(x⋆ + t(y⋆ − x⋆)

)∣∣∣t=0

= limt→0+

f(x⋆ + t(y⋆ − x⋆)

)− f(x⋆)

t

≤ limt→0+

(1− t)f(x⋆) + tf(y⋆)− f(x⋆)

t

= f(y⋆)− f(x⋆) < 0.

Deshalb ist ∇f(x⋆) 6= 0 und folglich ist x⋆ kein stationärer Punkt.

10 Kapitel 2. Gradientenverfahren

2. Gradientenverfahren

2.1 Idealisierte Variante

Im folgenden setzen wir stets voraus, dass f : D ⊂ Rn → R stetig differenzierbar ist.Zunächst wollen wir das Gradientenverfahren betrachten, das auch Verfahren des steilsten

Abstiegs genannt wird. Die Idee dabei ist, die Iterierte xk in Richtung des Antigradienten−∇f(xk) aufzudatieren

xk+1 := xk − αk∇f(xk),

so dass f(xk+1) < f(xk) ist. Dass dies im Fall ∇f(xk) 6= 0 immer möglich ist, zeigt unsdas nächste Lemma.

Lemma 2.1 Vorausgesetzt es ist ∇f(xk) 6= 0, dann gibt es ein δ > 0, so dass dieFunktion

ϕ(α) = f(xk − α∇f(xk)

)

für alle 0 ≤ α ≤ δ streng monoton fällt. Insbesondere gilt

f(xk − δ∇f(xk)

)< ϕ(0) = f(xk).

Beweis. Die Funktion ϕ ist stetig differenzierbar und es gilt

ϕ′(0) =d

dαf(xk − α∇f(xk)

)∣∣∣α=0

= −‖∇f(xk)‖22 < 0.

Aus Stetigkeitsgründen folgt die Existenz eines δ > 0 mit ϕ′(α) < 0 für alle 0 ≤ α ≤ δund damit die Behauptung.

Algorithmus 2.2 (idealisiertes Gradientenverfahren)input: Funktion f : Rn → R und Startnäherung x0 ∈ Rn

output: Folge von Iterierten {xk}k∈N➀ Initialisierung: setze k := 0

➁ berechne den Antigradienten dk = −∇f(xk)

➂ löseαk = argmin

α∈Rf(xk + αdk) (2.1)

➃ setze xk+1 := xk + αkdk

2.1. Idealisierte Variante 11

➄ erhöhe k := k + 1 und gehe nach ➁

Satz 2.3 Die Funktion f : D ⊂ Rn → R sei gleichmäßig konvex. Weiter sei f differen-zierbar mit Lipschitz-stetigem Gradienten:

‖∇f(x)−∇f(y)‖2 ≤ L‖x− y‖2 für alle x,y ∈ D.

Dann konvergiert das idealisierte Gradientenverfahren für beliebige Startnäherungen x0 ∈D gegen das eindeutige globale Minimum x⋆ und es gilt

f(xk+1)− f(x⋆) ≤(1− µ2

L2

){f(xk)− f(x⋆)

}, k = 1, 2, . . . .

Beweis. Aufgrund von (2.1) gilt für ein beliebiges β > 0, dass

f(xk+1) ≤ f(xk − β∇f(xk)

)

= f(xk)− β

∫ 1

0

∇f(xk − tβ∇f(xk)

)T∇f(xk) dt

= f(xk)− β‖∇f(xk)‖22 − β

∫ 1

0

{∇f

(xk − tβ∇f(xk)

)−∇f(xk)

}T∇f(xk) dt

≤ f(xk)− β‖∇f(xk)‖22 + β

∫ 1

0

∥∥∇f(xk − tβ∇f(xk)

)−∇f(xk)

∥∥2︸︷︷︸

≤tβL‖∇f(xk)‖2

‖∇f(xk)‖2 dt

≤ f(xk)−(β − β2L

2

)‖∇f(xk)‖22.

Für β = 1/L schließen wir also

f(xk+1)− f(x⋆) ≤ f(xk)− f(x⋆)− 1

2L‖∇f(xk)−∇f(x⋆)︸︷︷︸

=0

‖22. (2.2)

Die gleichmäßige Konvexität impliziert

µ‖xk − x⋆‖22 ≤{∇f(xk)−∇f(x⋆)

}T(xk − x⋆) ≤ ‖∇f(xk)−∇f(x⋆)‖2‖xk − x⋆‖2.

Dies eingesetzt in (2.2) liefert

f(xk+1)− f(x⋆) ≤ f(xk)− f(x⋆)− µ2

2L‖xk − x⋆‖22.


Weiterhin erhalten wir aus der Lipschitz-Bedingung

f(xk)− f(x⋆) =

∫ 1

0

∇f(x⋆ + t(xk − x⋆)

)T(xk − x⋆) dt

=

∫ 1

0

{∇f

(x⋆ + t(xk − x⋆)

)−∇f(x⋆)

}T(xk − x⋆) dt

≤∫ 1

0

∥∥∇f(x⋆ + t(xk − x⋆)

)−∇f(x⋆)

∥∥2︸︷︷︸

≤tL‖xk−x⋆‖2

‖xk − x⋆‖2 dt

=L

2‖xk − x⋆‖22,

womit sich die gewünschte Abschätzung ergibt.

Bemerkung Im obigen Beweis haben wir

f(xk)− f(x⋆) ≤ L

2‖xk − x⋆‖22

gezeigt. Umgekehrt folgt aus der gleichmäßigen Konvexität aber auch

f(xk)− f(x⋆) ≥∫ 1

0

∇f(x⋆ + t(xk − x⋆)

)T(xk − x⋆) dt

≥∫ 1

0

tµ‖xk − x⋆‖22 dt

=µ

2‖xk − x⋆‖22.

Daher folgt aus Satz 2.3, dass der Fehler des idealisierten Gradientenverfahrens

‖xk − x⋆‖22 ≤2

µ

{f(xk)− f(x⋆)

}

≤ 2

µ

(1− µ2

L2

)k{f(x0)− f(x⋆)

}

≤ L

µ

(1− µ2

L2

)k

‖x0 − x⋆‖22.

Wir erhalten demnach eine lineare Konvergenzordnung

‖xk − x⋆‖2 ≤ cρk‖x0 − x⋆‖2mit ρ =

√1− µ2/L2 < 1. △

2.2 Praktische Variante

Um einen praktikablen Algorithmus für das Gradientenverfahren zu erhalten, müssen wirnoch das eindimensionale Minimierungsproblem (2.1) lösen. Die Bedingung

d

dαf(xk + αdk) = ∇f(xk + αdk)

Tdk = 0

stellt eine nichtlineare Gleichung für α ∈ R dar, deren exaktes Lösen viel zu teuer ist.Daher halbiert man die Schrittweite ausgehend von αk = 1 solange, bis ein Abstieg erzieltwurde.

2.2. Praktische Variante 13

Bemerkung Ist f(x) = 12xTAx+ bTx + c eine quadratische Funktion, dann kann (2.1)

exakt gelöst werden:

αk =dTkdk

dkAdk, wobei dk := b−Axk.

In diesem Fall ist das idealisierte Gradientenverfahren leicht durchführbar und konvergiertgemäß Satz 2.3 linear. Der Kontraktionsfaktor ρ hängt dabei stark von der Kondition derMatrix A ab, denn es gilt

ρ =cond2(A)− 1

cond2(A) + 1.

△

Algorithmus 2.4 (Gradientenverfahren)input: Funktion f : Rn → R und Startnäherung x0 ∈ Rn

output: Folge von Iterierten {xk}k∈N➀ Initialisierung: wähle σ ∈ (0, 1) und setze k := 0

➁ berechne den Antigradienten dk := −∇f(xk) und setze αk := 1

➂ solangef(xk + αkdk) > f(xk)− σαk‖dk‖22 (2.3)

setze αk := αk/2

➃ setze xk+1 := xk + αkdk


Bemerkung Die Liniensuche ➂ wird als Armijo-Schrittweitenregel bezeichnet. Sie ga-rantiert nicht nur Abbruchbedingung f(xk+1) < f(xk), sondern die Armijo-Goldstein-

Bedingung

f(xk − αk∇f(xk)

)≤ f(xk)− σαk‖∇f(xk)‖22. (2.4)

Dabei bricht die Liniensuche mit einem αk > 0 ab, denn für ϕ(α) = f(xk − α∇f(xk)

)

gilt nämlich

f(xk − α∇f(xk)

)= ϕ(α) = ϕ(0) + αϕ′(0) + O(α) = f(xk)− α‖∇f(xk)‖22 + O(α).

△Der nachfolgende Satz liefert ein globales Konvergenzresultat für das Gradientenverfah-ren unter der Verwendung der Armijo-Schrittweitenregel. Er benötigt nur die Lipschitz-stetigkeit von f , aber keine Konvexität.

Satz 2.5 Es sei D ⊂ Rn eine offene Menge, in der f stetig differenzierbar, nach untenbeschränkt und ∇f zudem Lipschitz-stetig ist. Ferner sei neben x0 auch die gesamteNiveaumenge {x ∈ Rn : f(x) ≤ f(x0)} in D enthalten. Dann gilt für die Iterierten{xk}k≥0 aus Algorithmus 2.4

∇f(xk)k→∞−→ 0.


Beweis. Da D die gesamte Niveaumenge enthält, ist sichergestellt, dass die Iterierten{xk}k≥0 alle in D enthalten sind. Nach Konstruktion ist dann die Folge {f(xk)}k≥0 mono-ton fallend und nach unten beschränkt. Daher folgt aus der Armijo-Goldstein-Bedingung(2.4), dass

f(x0) ≥ f(x1) + σα0‖∇f(x0)‖22 ≥ · · · ≥ f(xk+1) + σ

k∑

ℓ=0

αℓ‖∇f(xℓ)‖22 ≥ 0.

Da die Reihe auf der rechten Seite notwendigerweise für k → ∞ konvergent ist, folgt

αk‖∇f(xk)‖22k→∞−→ 0. (2.5)

Es verbleibt zu zeigen, dass αk > ε für ein ε > 0.

Für festes k ist aufgrund von Algorithmus 2.4 αk = 1 oder die Armijo-Goldstein-Bedingungist für 2αk verletzt:

2σαk‖∇f(xk)‖22 > f(xk)− f(xk − 2αk∇f(xk)

)= 2αk‖∇f(xk)‖22 − R2(xk, 2αk)

mit dem Taylor-Restglied

R2(xk, 2αk) = 2αk

(‖∇f(xk)‖22 −∇f

(xk − ξ∇f(xk)

)T∇f(xk)), ξ ∈ (0, 2αk).

Da ∇f Lipschitz-stetig ist, ist das Taylor-Restglied R2(xk, 2αk) durch να2k‖∇f(xk)‖22 für

ein geeignetes ν > 0 beschränkt. Daher ist

σα2k‖∇f(xk)‖22 > 2αk‖∇f(xk)‖22 − 2ναk‖∇f(xk)‖22 = 2αk(1− ν)‖∇f(xk)‖22,

dies bedeutet

αk >2(1− ν)

σ=: ε > 0.

Somit bleibt αk für alle k ≥ 0 größer als min{1, ε} und daher folgt die Behauptung aus(2.5).

Beachte: Satz 2.5 besagt nicht, dass die Folge {xk}k≥0 selber konvergiert. Selbst wenndie Folge {xk}k≥0 konvergiert, braucht der Grenzwert darüberhinaus kein Minimum vonf zu sein.

Beispiel 2.6 Gegeben sei die Funktion

f(ξ, η) = ξ2 + (η2 − 1)2 + ξ2(η2 − 1)2 → min .

Das Minimum von f ist 0 und wird offensichtlich für ξ = 0 und η = ±1 angenommen.Hat eine Iterierte xk von Algorithmus 2.4 die Form xk = [ξk, 0]

T , dann gilt

∇f(xk) =

[2ξ + 2ξ(η2 − 1)2

2η(η2 − 1)(1 + ξ2)

] ∣∣∣∣(ξ,η)=(ξk ,0)

=

[4ξk0

].

Daher hat die nächste Iterierte zwangsläufig wieder die Form xk+1 = [ξk+1, 0]T und nach

Satz 2.5 konvergiert ∇f(xk) = [4ξk, 0]T gegen Null. Deshalb streben auch ξk und xk gegen

Null für k → ∞. Dennoch ist [0, 0]T lediglich ein Sattelpunkt von f , da f(0, η) für η = 0ein lokales Maximum aufweist. △

15

3. Newton-Verfahren

3.1 Lokales Newton-Verfahren

Sei f : Rn → R zweimal stetig differenzierbar. Beim Newton-Verfahren wird das Mini-mierungsproblem f(x) → min gelöst, indem sukzessive die quadratischen Näherungen

qk(x) := f(xk) +∇f(xk)T (x− xk) +

1

2(x− xk)

T∇2f(xk)(x− xk)

minimiert. Ist die Hesse-Matrix ∇2f(xk) positiv definit, so ist die neue Iterierte xk+1

genau die Lösung der Gleichung

∇qk(x) = ∇f(xk) +∇2f(xk)(x− xk)!= 0.

Hieraus ergibt sich die Iterationsvorschrift

xk+1 = xk −(∇2f(xk)

)−1∇f(xk), k = 0, 1, 2, . . . . (3.1)

Algorithmus 3.1 (Newton-Verfahren)input: Funktion f : Rn → R und Startnäherung x0 ∈ Rn


➁ berechne die Newton-Richtung durch Lösen des linearen Gleichungssystems

∇2f(xk)dk = −∇f(xk) (3.2)

➂ setze xk+1 := xk + dk

➃ erhöhe k := k + 1 und gehe nach ➁

Der mächtigste Satz zum Newton-Verfahren ist der Satz von Newton-Kantorovich. Erliefert nicht nur die Konvergenz des Newton-Verfahrens, sondern auch die Existenz einesstationären Punkts.

Satz 3.2 (Newton-Kantorovich) Sei D ⊂ Rn offen und konvex und f : D ⊂ Rn → R

zweimal stetig differenzierbar mit

‖∇2f(x)−∇2f(y)‖2 ≤ L‖x− y‖2

16 Kapitel 3. Newton-Verfahren

1x

0x

2 x

f’(x)

Abbildung 3.1: Geometrische Interpretation des Newton-Verfahrens.

für alle x,y ∈ D. Für ein gegebenes x0 ∈ D nehmen wir an, dass die Hesse-Matrix∇2f(x0) invertierbar ist mit α :=

∥∥(∇2f(x0

)−1∥∥2. Ferner gelte

β :=∥∥(∇2f(x0)

)−1∇f(x0)∥∥2≤ 1

2αL

und für

γ± :=1

αL

(1±

√1− 2αβL

)≥ 0

sei S := {x ∈ Rn : ‖x−x0‖2 ≤ γ−} ⊂ D. Dann sind die Iterierten des Newton-Verfahrens(3.1) wohldefiniert, liegen alle in S und konvergieren gegen ein x⋆ ∈ S mit ∇f(x⋆) = 0,welches eindeutig ist in D ∩ {x ∈ Rn : ‖x− x0‖2 ≤ γ+}. Insbesondere ist die Konvergenzquadratisch, falls 2αβL < 1 ist. Dies bedeutet, es existiert ein c > 0 so dass gilt

‖x⋆ − xk+1‖2 ≤ c‖x⋆ − xk‖22.

Bevor wir den Beweis dieses Satzes erbringen, stellen wir drei hilfreiche Lemmata zurVerfügung. Dabei gelten stets die Voraussetzungen des Satzes von Newton-Kantorovich.

Lemma 3.3 Sei {yk}k≥0 eine Folge im Rn und {tk}k≥0 eine Folge nichtnegativer, monotonwachsender, reeller Zahlen mit tk → t⋆ <∞. Gilt

‖yk+1 − yk‖2 ≤ tk+1 − tk, k = 0, 1, . . . ,

dann existiert ein eindeutig bestimmtes y⋆ ∈ Rn mit yk → y⋆ und

‖y⋆ − yk‖2 ≤ t⋆ − tk, k = 0, 1, . . . .

Dies bedeutet, die Folge {tk}k≥0 majorisiert {yk}k≥0.

3.1. Lokales Newton-Verfahren 17

Beweis. Es gilt

‖yk+p − yk‖2 =∥∥∥∥

k+p−1∑

ℓ=k

(yℓ+1 − yℓ)

∥∥∥∥2

≤k+p−1∑

ℓ=k

‖yℓ+1 − yℓ‖2

≤k+p−1∑

ℓ=k

tℓ+1 − tℓ

︸︷︷︸=tk+p−tk

≤ t⋆ − tk.

Folglich ist {yk}k≥0 eine Cauchy-Folge im Rn, woraus die Behauptung folgt.

Lemma 3.4 Für alle x ∈ T := {x ∈ Rn : ‖x − x0‖2 < 1/(αL)} ist die Hesse-Matrix∇2f(x) invertierbar mit

∥∥(∇2f(x))−1∥∥

2≤ α

1− αL‖x− x0‖2. (3.3)

Ist außerdem N(x) := x−(∇2f(x)

)−1∇f(x) ∈ T , dann gilt

∥∥N(N(x)

)−N(x)

∥∥2≤ 1

2

αL‖x−N(x)‖21− αL‖x0 −N(x)‖2

.

Beweis. Für x ∈ T gilt

∥∥(∇2f(x0))−1(∇2f(x0)−∇2f(x)

)∥∥2≤

∥∥(∇2f(x0))−1∥∥

2︸︷︷︸≤α

‖∇2f(x0)−∇2f(x)∥∥2︸︷︷︸

≤L‖x0−x‖2

< 1.

Die Satz von der Neumann-Reihe liefert daher die Existenz von

{I −

(∇2f(x0)

)−1(∇2f(x0)−∇2f(x))}−1

=

∞∑

k=0

{(∇2f(x0)

)−1(∇2f(x0)−∇2f(x))}k

.

Speziell folgt die Anschätzung

∥∥{I−(∇2f(x0)

)−1(∇2f(x0)−∇2f(x))}−1∥∥

2≤

∞∑

k=0

{αL‖x0−x‖2

}k=

1

1− αL‖x0 − x‖2.

Die Abschätzung (3.3) ergibt sich nun aus der Identität

(∇2f(x)

)−1=

{I −

(∇2f(x0)

)−1(∇2f(x0)−∇2f(x))}−1∇2f(x0).


Die zweite Aussage des Lemmas sieht man wie folgt. Mit dem soeben gezeigten gilt

∥∥N(N(x)

)−N(x)

∥∥2=

∥∥∥N(x)−(∇2f

(N(x)

))−1

∇f(N(x)

)−N(x)

∥∥∥2

≤∥∥∥(∇2f

(N(x)

))−1∥∥∥2

∥∥∇f(N(x)

)∥∥2

≤ α

1− αL‖N(x)− x0‖2∥∥∇f

(N(x)

)∥∥2.

Wir müssen also nur noch∥∥∇f

(N(x)

)∥∥2

abschätzen. Aufgrund der Identität

∇f(x)−∇2f(x)(N(x)− x

)= 0

schließen wir∥∥∇f

(N(x)

)∥∥2=

∥∥∇f(N(x)

)−∇f(x)−∇2f(x)

(N(x)− x

)∥∥2.

Mit

∇f(y)−∇f(x) =∫ 1

0

∇2f(x+ t(y − x)

)(y− x) dt

und y := N(x) folgt

∥∥∇f(N(x)

)∥∥2=

∥∥∥∥∫ 1

0

{∇2f(x+ t(y − x)

)−∇2f(x)

}(y − x) dt

∥∥∥∥2

≤∫ 1

0

‖∇2f(x+ t(y − x))−∇2f(x)

∥∥2︸︷︷︸

≤Lt‖y−x‖2

‖y − x‖2 dt

≤ L

2‖N(x)− x‖22.

Damit ergibt sich schließlich die Behauptung.

Lemma 3.5 Die Folge der Newton-Iterierten {xk}k≥0 ist wohldefiniert und durch dieFolge {tk}k≥0 mit

t0 := 0, tk+1 :=β − αL

2t2k

1− αLtk, k = 1, 2, . . . (3.4)

majorisiert. Insbesondere konvergiert tk monoton von unten gegen t⋆ := γ−.

Beweis. Wir zeigen zunächst induktiv, dass 0 = t0 < t1 < · · · < tk < t⋆ gilt. Da für k = 0nichts zu zeigen ist, können wir annehmen, dass die Aussage für ein k ∈ N0 bewiesen ist.Mit quadratischer Ergänzung folgt die Gleichung

tk+1 − tk =β − αL

2t2k − tk + αLt2k1− αLtk

=αL2(tk − tk−1)

2 +

=0︷︸︸︷β − αL

2t2k−1 − (1− αLtk−1)tk

1− αLtk

=1

2

αL(tk − tk−1)2

1− αLtk.

3.1. Lokales Newton-Verfahren 19

Wegen 1 − αLtk > 0 und tk−1 < tk schließen wir tk < tk+1. Um tk+1 < t⋆ zu zeigen,betrachten wir das Polynom p(t) := αL

2t2− t+β, welches die zwei Nullstellen γ− = t⋆ und

γ+ besitzt. Wegen

t⋆ − tk+1 =t⋆ − αLtkt

⋆ − β + αL2t2k

1− αLtk

=αL2(t⋆ − tk)

2 −=0︷︸︸︷p(t⋆)

1− αLtk

=1

2

αL(t⋆ − tk)2

1− αLtk︸︷︷︸>0

> 0

ist in der Tat tk+1 < t⋆, womit ist der Induktionsschritt k 7→ k + 1 erbracht ist. Ins-besondere folgt zwingend die Konvergenz tk → t⋆, da Fixpunkte der Iteration (3.4) derBedingung 0 = p(t) genügen müssen und t⋆ = γ− < γ+ gilt.

Wir zeigen nun, dass alle xk existieren, in S liegen und jeweils ‖xk − xk−1‖2 ≤ tk −tk−1 erfüllen. Für k = 0 ist dies sicherlich richtig. Es möge also die Folge x1, . . . ,xk

das Behauptete erfüllen. Wegen S ⊂ T folgt der Induktionsschritt k 7→ k + 1 dann ausLemma 3.4 gemäß

‖xk+1 − xk‖2 =∥∥N

(N(xk−1)

)−N(xk−1)

∥∥2

≤ 1

2

αL‖xk − xk−1‖21− αL‖xk − x0‖2

≤ 1

2

αL(tk − tk−1)

1− αLtk= tk+1 − tk

und

‖xk+1 − x0‖2 ≤k∑

ℓ=0

‖xℓ+1 − xℓ‖2 ≤k∑

ℓ=0

tℓ+1 − tℓ = tk+1 − t0 ≤ t⋆ = γ−.

Wir sind nun in der Lage, den Satz von Newton-Kantorovich beweisen zu können, wobeiwir nur die Existenz eines stationären Punktes x⋆ nachweisen und nicht dessen Eindeu-tigkeit.

Beweis des Satzes von Newton-Kantorovich. Nach Lemma 3.5 werden die Newton-Iterierten{xk}k≥0 von {tk}k≥0 majorisiert und konvergieren gemäß Lemma 3.3 gegen ein eindeutigbestimmtes x⋆ ∈ S. Wegen

‖∇f(xk)‖2 = ‖∇2f(xk)(xk+1 − xk)‖2≤

∥∥{∇2f(xk)−∇2f(x0)}(xk+1 − xk)

∥∥2+ ‖∇2f(x0)(xk+1 − xk)‖2

≤{Lt⋆ + ‖∇2f(x0)‖2

}︸︷︷︸

<∞

‖xk+1 − xk‖2︸︷︷︸→0

→ 0


und der Stetigkeit von ∇f , ist auch die Gleichung ∇f(x⋆) = 0 erfüllt. Ist ferner 2αβL < 1,dann konvergiert aufgrund der Abschätzung

t⋆ − tk =αL2(t⋆ − tk−1)

2

1− αLtk−1≤ αL

2− 2αLt⋆(t⋆ − tk−1)

2

die Folge {tk}k≥0 quadratisch. Dies impliziert sofort die quadratische Konvergenz derdurch {tk}k≥0 majorisierten Folge {xk}k≥0. �

Bemerkungen

1. Die Konvergenz des Newton-Verfahrens ist im allgemeinen nur lokal.

2. Der Satz von Newton-Kantorovich benutzt nirgendwo Konvexität. Das Newton-Verfahren konvergiert folglich auch im Fall von Sattelpunkten.

△

3.2 Globalisiertes Newton-Verfahren

Um das Newton-Verfahren zu globalisieren, müssen wir sicherstellen, dass die Suchrich-tung auch dann wohldefiniert ist, wenn sich das Gleichungssystem (3.2) nicht lösen lässtoder es gar keine Abstiegsrichtung beschreibt. In beiden Fällen machen wir dann einfacheinen Gradientenschritt:

Algorithmus 3.6 (globalisiertes Newton-Verfahren)input: Funktion f : Rn → R und Startnäherung x0 ∈ Rn

output: Folge von Iterierten {xk}k∈N➀ Initialisierung: wähle σ ∈ (0, 1), ρ > 0 und setze k := 0

➁ berechne, falls möglich, die Newton-Richtung durch Lösen des linearen Gleichungs-systems

∇2f(xk)dk = −∇f(xk)

➂ ist das Gleichungssystem nicht lösbar oder ist die Bedingung

∇f(xk)Tdk ≤ −ρ‖∇f(xk)‖22 (3.5)

nicht erfüllt, dann setze dk := −∇f(xk)

➃ setze αk := 1

➄ solangef(xk + αkdk) > f(xk) + σαk∇f(xk)

Tdk (3.6)

setze αk := αk/2

➅ setze xk+1 := xk + αkdk

➆ erhöhe k := k + 1 und gehe nach ➁

Die Bedingungen (3.5) und (3.6) garantieren zusammen die Armijo-Goldstein-Bedingung(2.4) und somit einen hinreichenden Abstieg. Die Konvergenz ∇f(xk) → 0 folgt daheranalog zum entsprechenden Satz 3.6 über das Gradientenverfahren. Aus dem nachfol-

3.2. Globalisiertes Newton-Verfahren 21

genden Satz ergibt sich, dass das globalisierte Newton-Verfahren in der Umgebung einesMinimums zum lokalen Newton-Verfahren wird.

Satz 3.7 Seien f : Rn → R zweimal stetig differenzierbar und x⋆ ∈ Rn ein stationärerPunkt, an dem die Hesse-Matrix ∇2f(x⋆) positiv definit ist. Konvergiert die Folge {xk}k≥0

der Newton-Iterierten gegen x⋆, dann exitistiert ein k0 ∈ N mit

f(xk + dk) > f(xk) + σ∇f(xk)T∇2f(xk)∇f(xk) (3.7)

für alle k ≥ k0 und jedes feste σ ∈ (0, 1/2).

Beweis. Aus den Voraussetzung folgt aus Stetigkeitsgründen zunächst

‖∇f(xk)‖2 k→∞−→ 0. (3.8)

Ferner ist ∇2f(x⋆) invertierbar und aufgrund der Stetigkeit schließen wir auf die Existenzeiner Umgebung U ⊂ Rn von x⋆ mit

∥∥(∇2f(x))−1∥∥

2≤ c für alle x ∈ U.

Daher existiert ein k0 ∈ N, so dass

∥∥(∇2f(xk))−1∥∥

2≤ c für alle k ≥ k0.

Aus der Newton-Gleichung dk := −(∇2f(xk)

)−1∇f(xk) folgt deshalb

‖dk‖2 ≤∥∥(∇2f(xk)

)−1∥∥2‖∇f(xk)‖2 ≤ c‖∇f(xk)‖2 k→∞−→ 0.

Da mit ∇2f(x⋆) auch(∇2f(x⋆)

)−1positiv definit ist, können wir k0 vergrößern, so dass

∇f(xk)T(∇2f(xk)

)−1∇f(xk) ≥ c‖∇f(xk)‖22 für alle k ≥ k0. (3.9)

Nach dem Taylorschen Satz exitiert ein ξk auf der Verbindungsstrecke von xk und xk+dk,so dass gilt

f(xk + dk) = f(xk) +∇f(xk)Tdk +

1

2dTk∇2f(ξk)dk.

Wegen xk → x⋆ und dk → 0 gilt auch ξk → x⋆ und folglich

‖∇2f(ξk)−∇2f(xk)‖2 k→∞−→ 0.

Wegen σ ∈ (0, 1/2) ist daher

(σ − 1

2

)c

︸︷︷︸<0

+1

2c2‖∇2f(ξk)−∇2f(xk)‖2 ≤ 0 (3.10)


für alle k genügend groß. Für großes k folgt die Behauptung nun aus der Cauchy-SchwarzschenUngleichung, (3.8),(3.9) und (3.10):


1

2dTk∇2f(xk)dk︸︷︷︸=−∇f(xk)Tdk

+1

2dTk

{∇2f(ξk)−∇2f(xk)

}dk

≤ f(xk) +1

2∇f(xk)

Tdk +1

2‖dk‖22‖∇2f(ξk)−∇2f(xk)‖2

= f(xk) + σ∇f(xk)Tdk +

(σ − 1

2

)dTk∇2f(xk)dk︸︷︷︸

=∇f(xk)T (∇2f(xk))−1∇f(xk)

+1

2‖dk‖22‖∇2f(ξk)−∇2f(xk)‖2

≤ f(xk) + σ∇f(xk)Tdk

+

{(σ − 1

2

)c +

1

2c2‖∇2f(ξk)−∇2f(xk)‖2

︸︷︷︸≤0

}‖∇f(xk)‖22

≤ f(xk) + σ∇f(xk)Tdk.

Sind die Voraussetzungen des Satzes 3.7 erfüllt, dann zeigt Abschätzung (3.10), dass (3.5)für ein genügend kleines ρ erfüllt ist. Daher folgt dann aus (3.7), dass (3.6) stets gilt.

3.3 Inexaktes Newton-Verfahren

Beim inexakten Newton-Verfahren wird das Gleichungssystem (3.2) nicht exakt, sondernnur näherungsweise gelöst. Dies entspricht natürlich der numerischen Praxis.

Algorithmus 3.8 (inexaktes lokales Newton-Verfahren)input: Funktion f : Rn → R und Startnäherung x0 ∈ Rn


➁ wähle eine Toleranz ηk > 0 und bestimme eine Suchrichtung dk mit

‖∇f(xk) +∇2f(xk)dk‖2 ≤ ηk‖∇f(xk)‖2 (3.11)



Die Konvergenzrate des inexakten Newton-Verfahrens ergibt sich aus dem nachfolgendenSatz. Speziell gibt er uns eine Bedingung an die Wahl der Toleranzen {ηk} an, so dass dasVerfahren dennoch quadratisch konvergiert.

3.3. Inexaktes Newton-Verfahren 23

Satz 3.9 Seien f : Rn → R zweimal stetig differenzierbar und x⋆ ∈ Rn ein stationärerPunkt, an dem die Hesse-Matrix ∇2f(x⋆) positiv definit ist. Dann existiert eine UmgebungU ⊂ Rn von x⋆, so dass für alle x0 ∈ U gelten:

(i.) Ist ηk ≤ η für ein hinreichend kleines η, dann ist Algorithmus 3.8 wohldefiniert unddie durch ihn erzeugte Folge {xk}k≥0 konvergiert mindestens linear gegen x⋆.

(ii.) Die Konvergenzrate ist superlinear, falls ηk → 0 gilt.

(iii.) Die Konvergenzrate ist quadratisch, falls ηk = O(‖∇f(xk)‖2) gilt und ∇2f lokalLipschitz-stetig ist.

Beweis. Da f zweimal stetig differenzierbar ist, ist ∇f lokal Lipschitz-stetig. Daher exis-tiert eine Umgebung U ⊂ Rn von x⋆ und ein L > 0 derart, dass

‖∇f(x)‖2 = ‖∇f(x)−∇f(x⋆)‖2 ≤ L‖x− x⋆‖2 für alle x ∈ U.

Da ∇2f(x⋆) invertierbar ist, folgt, indem wir U eventuell verkleinern, aufgrund der Ste-tigkeit ∥∥(∇2f(x)

)−1∥∥2≤ c für alle x ∈ U.

Aus der Definition der Ableitung einer Funktion schließen wir, indem wir wieder U even-tuell verkleinern, dass

‖∇f(x⋆)−∇f(x)−∇2f(x)(x− x⋆)‖2︸︷︷︸=O(‖x−x⋆‖2)

≤ 1

4c‖x− x⋆‖2.

Setze nun η := 1/(4cL) und wähle x0 ∈ U . Dann ist ∇2f(x0) regulär und es lässt sich eind0 mit (3.11) berechnen. Somit ist x1 wohldefiniert und wegen

‖x1 − x⋆‖2 =∥∥x0 − x⋆ −

(∇2f(x0)

)−1∇f(x0) +(∇2f(x0)

)−1{∇2f(x0)d0 +∇f(x0)}∥∥

2

≤∥∥(∇2f(x0)

)−1∥∥2

{∥∥∇2f(x0)(x0 − x⋆)−∇f(x0) +∇f(x⋆)∥∥2

+∥∥∇2f(x0)d0 +∇f(x0)

∥∥2︸︷︷︸

≤η‖∇2f(x0)‖2

}

≤ c

(1

4c+ ηL

)‖x0 − x⋆‖2

=1

2‖x0 − x⋆‖2

wieder in U enthalten. Mit vollständiger Induktion schließen wir

‖xk − x⋆‖2 ≤1

2k‖x0 − x⋆‖2,

was die lineare Konvergenz xk → x⋆ nachweist.

Zum Nachweis von (ii.) bemerken wir, dass analog zur obigen Ungleichungskette auch

‖xk+1 − x⋆‖2 ≤ c{∥∥∇2f(xk)(xk − x⋆)−∇f(xk) +∇f(x⋆)

∥∥2+ ηk‖∇2f(xk)‖2

}

≤ c{∥∥∇2f(xk)(xk − x⋆)−∇f(xk) +∇f(x⋆)

∥∥2+ ηkL‖xk − x⋆‖2

}


bewiesen werden kann. Für ηk → 0 ist daher

‖xk+1 − x⋆‖2 = O(‖xk − x⋆‖2),das heißt, {xk}k≥0 konvergiert superlinear gegen x⋆.

Die lokal quadratische Konvergenz wird ganz ähnlich nachgewiesen: Mit

∇f(xk)−∇f(x⋆) =

∫ 1

0

∇2f(x⋆ + t(xk − x⋆)

)(xk − x⋆) dt

folgt mittels der lokalen Lipschitzstetigkeit∥∥∇2f(xk)(xk − x⋆)−∇f(xk) +∇f(x⋆)

∥∥2

=

∥∥∥∥∫ 1

0

{∇2f(xk)− f

(x⋆ + t(xk − x⋆)

)}(xk − x⋆) dt

∥∥∥∥2

≤∫ 1

0

∥∥∇2f(xk)−∇2f(x⋆ + t(xk − x⋆)

)∥∥2︸︷︷︸

≤tL‖xk−x⋆‖2

‖xk − x⋆‖2 dt

≤ L

2‖xk − x⋆‖22.

Setzt man dies zusammen mit ηk = O(‖∇f(xk)‖2) = O(‖xk−x⋆‖2) in die obige Abschät-zung ein, dann ergibt sich

‖xk+1 − x⋆‖2 = O(‖xk − x⋆‖22),das ist Aussage (iii.).

3.4 Trust-Region-Verfahren

Die quadratische Approximation

f(xk + d) ≈ f(xk) +∇f(xk)Td+

1

2dT∇2f(xk)d = qk(d)

ist nur für kleines ‖d‖2 genau. Man schränkt daher den Bereich ein, in dem man derquadratischen Approximation qk(d) vertraut. Dies erklärt den Begriff trust region. ImZusammenhang mit dem Newton-Verfahren wird das Update dk beispielsweise aus

mind∈Rn

qk(d) unter der Nebenbedingung ‖d‖2 ≤ ∆k (3.12)

bestimmt, wobei der Radius ∆k noch geeignet zu bestimmen ist. Wir haben also in jedemSchritt ein quadratisches Minimierungsproblem mit Nebenbedingungen zu lösen.

Wir wenden uns der Wahl des Radius ∆k zu. Dieser wird so gesteuert, dass eine mög-lichst gute Übereinstimmung der quadratischen Näherung qk mit der Funktion f(xk + ·)sichergestellt ist. Liegt das Qualitätsmaß

ρk =f(xk)− f(xk + dk)

qk(0)− qk(dk)

nahe bei 1, stimmt die tatsächliche Reduktion (Zähler) mit der vorhergesagten Reduktion(Nenner) gut überein und der Radius ∆k kann sogar vergrößert werden. Ist das Quali-tätsmaß klein, dann sollte der Radius ∆k verkleinert und der Schritt wiederholt werden.Ansonsten behält man ∆k bei.

3.4. Trust-Region-Verfahren 25

Algorithmus 3.10 (Trust-Region-Verfahren)input: Funktion f : Rn → R und Startnäherung x0 ∈ Rn

output: Folge von Iterierten {xk}k∈N➀ Initialisierung: wähle 0 < ρ− < ρ+ < 1 und setze ∆0 := 1 und k := 0

➁ bestimme dk durch näherungsweise Lösung von (3.12) und berechne

ρk :=f(xk)− f(xk + dk)

qk(0)− qk(dk)

➂ falls ρk > ρ− setze xk+1 := xk + dk, sonst setze ∆k := ∆k/2 und gehe nach ➁

➃ falls ρk > ρ+ setze ∆k+1 := 2∆k, sonst setze ∆k+1 := ∆k


Ausgangspunkt zur näherungsweisen Lösung von (3.12) ist der Cauchy-Punkt, dessenKonstruktion in zwei Schritten erfolgt.

1. Bestimme dk aus

mind∈Rn

f(xk) +∇f(xk)Td unter der Nebenbedingung ‖d‖2 ≤ ∆k.

Dieser Richtungsvektor lässt sich explizit angeben:

dk = − ∆k

‖∇f(xk)‖2∇f(xk).

2. Bestimme τk aus

minτ>0

qk(τdk) unter der Nebenbedingung ‖τdk‖2 ≤ ∆k

und setze d⋆k := τkdk. Für die Berechnung von τk sind zwei Fälle zu unterscheiden.

Falls ∇f(xk)T∇2f(xk)∇f(xk) ≤ 0 gilt, so folgt τk = 1. Ansonsten ist

τk = min

{1,

1

∆k

‖∇f(xk)‖32∇f(xk)T∇2f(xk)∇f(xk)

}.

Unser Ziel ist es nun, eine Kombination zu finden, die für kleine Werte ∆k mit dem Cauchy-Punkt übereinstimmt und für größere Werte ∆k in das Newton-Verfahren übergeht. Wirstellen dazu die sogenannte Dogleg-Strategie vor und verwenden zur Abkürzung statt(3.12)

q(d) := f + gTd+1

2dTHd unter der Nebenbedingung ‖d‖2 ≤ ∆k.

Für kleine Werte ∆k fällt der quadratische Term nicht ins Gewicht und wir gehen inRichtung des Cauchy-Punktes dC := − ‖g‖2

2

gTHgg, für große Werte ∆k wollen wir hingegen

die Newton-Richtung dN := −H−1g verwenden:

d(τ) =

{τdC , falls 0 ≤ τ ≤ 1,

dC + (τ − 1)(dN − dC), falls 1 ≤ τ ≤ 2.


Lemma 3.11 Es sei H postitiv definit und g 6= 0. Dann ist

(i.) die Funktion ‖d(τ)‖2 streng monoton wachsend in τ , falls dN 6= dC , und

(ii.) die Funktion q(d(τ)

)monoton fallend in τ .

Beweis. Beide Aussagen im Fall 0 ≤ τ ≤ 1 offensichtlich.

Für 1 ≤ τ := σ + 1 ≤ 2 betrachten wir die Funktion

ϕ(σ) =1

2‖d(1 + σ)‖22

=1

2‖dC + σ(dN − dC)‖22

=1

2‖dC‖22 + σdT

C(dN − dC) +1

2σ2‖dN − dC‖22

und zeigen ϕ′(σ) > 0 für alle σ ∈ (0, 1):

ϕ′(σ) = dTC(dN − dC) + σ ‖dN − dC‖22︸︷︷︸

>0 da dN 6=dC

> dTC(dN − dC)

=gTg

gTHggT

(H−1g − gTg

gTHgg

)

=gTg

gTHggTH−1g

(1− (gTg)2

(gTHg)(gTH−1g)

)

≥ 0,

wobei sich die letzte Ungleichung aus

(gTg)2 = (gTH1/2H−1/2g)2 ≤ ‖H1/2g‖22‖H−1/2g‖22 = (gTHg)(gTH−1g)

ergibt. Damit ist Aussage (i.) gezeigt.

Um Aussage (ii.) nachzuweisen, bilden wir ψ(σ) = q(d(1 + σ)

)und erhalten

ψ′(σ) = (g +HdC)T (dN − dC) + σ (dN − dC)

TH(dN − dC)︸︷︷︸≥0

≤{g +HdC +H(dN − dC)

}T(dN − dC)

= (g +HdN)T (dN − dC) = 0.

Bemerkung Aus diesem Lemma folgt, dass es genau einen Punkt gibt, an dem derDogleg-Pfad den Kreis mit Radius ∆k schneidet, falls ‖dN‖2 ≥ ∆k. Da q

(d(τ)

)monoton

fällt, nimmt man diesen Schittpunkt als Update. Ist hingegen ‖dN‖2 ≤ ∆k, dann verläuftder Pfad ganz im Innern des Trust-Region-Bereichs. Folglich wählt man als Update

dk =

dN , falls ‖dN‖2 ≤ ∆k,

dS, falls ‖dC‖2 < ∆k < ‖dN‖2,∆k

‖dC‖2dC , falls ‖dC‖2 ≥ ∆k,


wobei

dS := dC + (τ ⋆ − 1)(dN − dC) mit τ ⋆ = argminτ>0

{(‖dC + (τ − 1)(dN − dC)‖2 −∆k)

2}.

Bei Implementierung muss man jedoch zuallererst überprüfen, ob überhaupt

qk(dN ) < qk(0)

gilt. Denn ist ∇2f(xk) nicht positiv definit, muss dem nicht so sein. In diesem Fall ist dieNewton-Richtung von vornherein zu verwerfen und der Cauchy-Punkt zu nehmen. △Unser Ziel ist der Nachweis globaler Konvergenz des Newton-Verfahrens mit der vorge-stellten Trust-Region-Technik. Ausgangspunkt dafür ist die Reduktion des Funktionalsdurch die Verwendung des Cauchy-Punktes.

Lemma 3.12 Für den Cauchy-Punkt d⋆k gilt

qk(d⋆k) ≤ qk(0)−

1

2‖∇f(xk)‖2min

{∆k,

‖∇f(xk)‖2‖∇2f(xk)‖2

}.

Beweis. Wir müssen drei Fälle unterscheiden.

(i.) Falls ∇f(xk)T∇2f(xk)∇f(xk) ≤ 0 folgt

qk(d⋆k)− qk(0) = − ∆k

‖∇f(xk)‖2‖∇f(xk)‖22 +

1

2

∆2k∇f(xk)

T∇2f(xk)∇f(xk)

‖∇f(xk)‖22≤ −∆k‖∇f(xk)‖2

≤ −1

2‖∇f(xk)‖2min

{∆k,

‖∇f(xk)‖2‖∇2f(xk)‖2

}.

(ii.) Im Fall 0 < ∇f(xk)T∇2f(xk)∇f(xk) ≤ ‖∇f(xk)‖32/∆k ergibt sich

qk(d⋆k)− qk(0) = − ∆k

‖∇f(xk)‖2‖∇f(xk)‖22 +

1

2

∆2k∇f(xk)

T∇2f(xk)∇f(xk)

‖∇f(xk)‖22≤ −∆k‖∇f(xk)‖2 +

1

2

∆2k

‖∇f(xk)‖22‖∇f(xk)‖32

∆k

= −1

2∆k‖∇f(xk)‖2

≤ −1

2‖∇f(xk)‖2min

{∆k,

‖∇f(xk)‖2‖∇2f(xk)‖2

}.

(iii.) Ist schließlich ∇f(xk)T∇2f(xk)∇f(xk) > ‖∇f(xk)‖32/∆k, so liegt der Cauchy-Punkt

im Innern des Trust-Region-Bereichs und ist durch

d⋆k = − ‖∇f(xk)‖22

∇f(xk)T∇2f(xk)∇f(xk)∇f(xk)


gegeben. Somit gilt

qk(d⋆k)− qk(0) = − ‖∇f(xk)‖42

∇f(xk)T∇2f(xk)∇f(xk)

+1

2

‖∇f(xk)‖42(∇f(xk)T∇2f(xk)∇f(xk))2

∇f(xk)T∇2f(xk)∇f(xk)

= −1

2

‖∇f(xk)‖42∇f(xk)T∇2f(xk)∇f(xk)

≤ −1

2

‖∇f(xk)‖42‖∇f(xk)‖22‖∇2f(xk)‖2

≤ −1

2‖∇f(xk)‖2min

{∆k,

‖∇f(xk)‖2‖∇2f(xk)‖2

}.

Bemerkung Mit der Dogleg-Strategie erreicht man mindestens eine Reduktion des Funk-tionals qk(d) durch den Cauchy-Punkt, das heißt, es gilt

qk(dk) ≤ qk(0)−1

2‖∇f(xk)‖2min

{∆k,

‖∇f(xk)‖2‖∇2f(xk)‖2

}.

△

Satz 3.13 Auf der Niveaumenge N := {x ∈ Rn : f(x) ≤ f(x0)} sei f zweimal stetig dif-ferenzierbar und nach unten beschränkt. Ist ∇2f(x) beschränkt auf der gesamten Niveau-menge N , dann erfüllen die vom Trust-Region-Verfahren 3.10 mit der Dogleg-Strategieberechneten Iterierten {xk}k≥0

∇f(xk)k→∞−→ 0.

Beweis. Wir vollziehen den Beweis des Satzes in vier Schritten.

(i.) Für das Maß ρk zur Anpassung des Trust-Region-Radius gilt

|ρk − 1| =∣∣∣∣f(xk)− f(xk + dk)− {qk(0)− qk(dk)}

qk(0)− qk(dk)

∣∣∣∣ =∣∣∣∣f(xk + dk)− qk(dk)

qk(0)− qk(dk)

∣∣∣∣.

Die Taylor-Entwicklung von f um xk liefert


1

2dTk∇2f(xk + ξdk)dk

für ein ξ ∈ (0, 1). Damit ergibt sich

|qk(dk)− f(xk + dk)| =∣∣∣∣1

2dTk∇2f(xk)dk −

1

2dTk∇2f(xk + ξdk)dk

∣∣∣∣

≤ 1

2

{‖∇2f(xk)‖2 + max

0≤t≤1‖∇2f(xk + tdk)‖2

}‖dk‖22

≤ c‖dk‖22,


wobei c > 0 eine obere Schranke für ∇2f(x) auf der Niveau-Menge N sei. Da nachLemma 3.12 gilt

qk(dk) ≤ qk(0)−1

2‖∇f(xk)‖2min

{∆k,

‖∇f(xk)‖2c

}, (3.13)

erhalten wir folglich die Abschätzung

|ρk − 1| ≤ c‖dk‖22‖∇f(xk)‖2min{∆k,

‖∇f(xk)‖2c

}≤ 2c∆2

k

‖∇f(xk)‖2{∆k,‖∇f(xk)‖2

c}. (3.14)

(ii.) Bei erfolgreichem Iterationsschritt ist f(xk)− f(xk + dk) ≥ ρ−{qk(0)− qk(dk)

}, das

heißt, gemäß (3.13) gilt

f(xk)− f(xk + dk) ≥ρ−

2‖∇f(xk)‖2min

{∆k,

‖∇f(xk)‖2c

}. (3.15)

Da die Folge {f(xk)}k≥0 nach Konstruktion streng monoton fällt und nach unten be-schränkt ist, muss gelten

min

{∆k,

‖∇f(xk)‖2c

}k→∞−→ 0. (3.16)

(iii.) Wir zeigen nun, dass {‖∇f(xk)‖2}k≥0 für eine unendliche Teilfolge {kℓ}ℓ≥0 gegenNull konvergiert. Angenommen, die Behauptung gilt nicht, dann folgt

‖∇f(xk)‖2 ≥ ε > 0 für alle k ≥ K(ε).

Aus (3.16) ergibt sich unmittelbar

∆kk→∞−→ 0,

weshalb (3.14) impliziert |ρk − 1| → 0 für k → ∞, beziehungsweise

ρkk→∞−→ 1.

Demnach existiert ein M(ε) ≥ K(ε), so dass ρk ≥ ρ+ für alle k ≥M(ε). Ab dem M(ε)-tenSchritt wird folglich ∆k in jedem Schritt von Algorithmus 3.10 verdoppelt, was jedoch imWiderspruch zu (3.16) steht.

(iv.) Wir beweisen nun die Aussage des Satzes. Dazu nehmen wir an, dass eine Teilfolgevon {‖∇f(xk)‖2}k≥0 nicht gegen Null konvergiert. Nach Aussage (iii.) existiert dann einε > 0 und zwei Indizes ℓ < m, so dass

‖∇f(xℓ)‖2 ≥ 2ε, ‖∇f(xm)‖2 ≤ ε, ‖∇f(xk)‖2 > ε, k = ℓ+ 1, . . . , m− 1.

Da {f(xk)}k≥0 eine Cauchy-Folge ist, kann ℓ dabei so groß gewählt werden, dass

f(xℓ)− f(xm) <ε2ρ−

2c. (3.17)

Wegen ‖xk+1 − xk‖2 = ‖dk‖2 ≤ ∆k, folgt aus (3.15), dass

f(xk)− f(xk+1) ≥ερ−

2min

{‖xk+1 − xk‖2,

ε

c

}, k = ℓ, ℓ+ 1, . . . , m− 1.


Summation ergibt wegen (3.17)

ερ−

2

m−1∑

k=ℓ

min

{‖xk+1 − xk‖2,

ε

c

}≤ f(xℓ)− f(xm) <

ε2ρ−

2c,

was nur erfüllt sein kann, wenn

min

{‖xk+1 − xk‖2,

ε

c

}= ‖xk+1 − xk‖2, k = ℓ, ℓ+ 1, . . . , m− 1,

und insgesamtm−1∑

k=ℓ

‖xk+1 − xk‖2 <ε

c

gilt. Da ∇f(x) auf der Niveaumenge N Lipschitz-stetig zur Konstante c ist, ergibt diesschließlich

‖∇f(xm)−∇f(xℓ)‖2 ≤ c‖xm − xℓ‖2 ≤ c

m−1∑

k=ℓ

‖xk+1 − xk‖2 < ε

im Widerspruch zur Annahme. Damit ist der Satz bewiesen.

31

4. Quasi-Newton-Verfahren

Beim Newton-Verfahren ist das Update dk durch die Newton-Gleichung ∇2f(xk)dk =−∇f(xk) gegeben. Da das Berechnen der Hesse-Matrix und das Lösen dieses Gleichungs-systems oftmals zu teuer ist, versucht man,

(∇2f(xk)

)−1durch einfach zu berechnende

Matrizen Hk zu ersetzen und die Suchrichtung

dk := −Hk∇f(xk)

zu benutzen. Man spricht von einem Quasi-Newton-Verfahren, wenn für alle k ≥ 0 dieMatrix Hk+1 der Quasi-Newton-Gleichung

Hk+1

{∇f(xk+1)−∇f(xk)

}= xk+1 − xk (4.1)

genügt. Diese Bedingung stellt sicher, dass sich Hk+1 in der Richtung xk+1 − xk ähnlichwie die Newton-Matrix

(∇2f(xk)

)−1verhält, für die gilt

∇f(xk+1)−∇f(xk) = ∇2f(xk)(xk+1 − xk) +O(‖xk+1 − xk‖22).Für eine quadratische Funktion q(x) = 1

2xTAx+ bTx+ c mit positiv definiter Matrix A

gilt (4.1) wegen ∇q(x) = Ax + b sogar exakt. Ferner erscheint es sinnvoll, als Hk nurpositiv definite Matrizen zu wählen. Dies garantiert, dass für ∇f(xk) 6= 0 die Richtungdk = −Hk∇f(xk) eine Abstiegsrichtung von f wird

∇f(xk)Tdk = −∇f(xk)

THk∇f(xk) < 0.

Beide Forderungen lassen sich erfüllen: Mit den Abkürzungen

pk = xk+1 − xk, qk = ∇f(xk+1)−∇f(xk)

und frei wählbaren Parameternγk > 0, νk ≥ 0

ist Hk+1 rekursiv gegeben durch

Hk+1 := Φ(Hk,pk,qk, γk, νk),

Φ(H,p,q, γ, ν) := γH+

(1 + γν

qTHq

pTq

)ppT

pTq− γ

1− ν

qTHqHqqTH (4.2)

− γν

pTq(pqTH+HqpT ).

Die Update-Funktion Φ ist nur für pTq 6= 0 und qTHq 6= 0 erklärt. Man beachte, dassman Hk+1 aus Hk dadurch erhält, dass man zur Matrix γkHk eine Korrekturmatrix vomRang ≤ 2 addiert:

rang(Hk+1 − γkHk) ≤ 2.

Man nennt dieses Verfahren daher auch Rang-2-Verfahren.

Folgende Spezialfälle sind in (4.2) enthalten:

32 Kapitel 4. Quasi-Newton-Verfahren

1. γk ≡ 1, νk ≡ 0: Verfahren von Davidon, Fletcher und Powell (DFP-Verfahren).

2. γk ≡ 1, νk ≡ 1: Rang-2-Verfahren von Broydon, Fletcher, Goldfarb und Shanno(BFGS-Verfahren).

3. γk ≡ 1, νk = pTk qk/(p

Tk qk − pT

kHkqk): symmetrisches Rang-1-Verfahren von Broy-

don.

Letzteres Verfahren ist nur für pTk qk 6= pT

kHkqk definiert; νk < 0 ist möglich: in diesem Fallkann Hk+1 auch indefinit werden, auch wenn Hk positiv definit ist (vergleiche Satz 4.2).Setzt man den gewählten Wert in (4.2) ein, erhält man für Hk eine Rekursionformel, dieden Namen Rang-1-Verfahren erklärt:

Hk+1 := Hk +zkz

Tk

αk, zk := pk −Hkqk, αk := pT

k qk − qTkHkqk.

Algorithmus 4.1 (Quasi-Newton-Verfahren)input: Funktion f : Rn → R und Startnäherung x0 ∈ Rn

output: Folge von Iterierten {xk}k∈N➀ Initialisierung: setze H0 := I und k := 0

➁ berechne die Quasi-Newton-Richtung dk = −Hk∇f(xk)

➂ löseαk ≈ argmin

α∈Rf(xk + αdk)

➃ setze xk+1 := xk + αkdk, pk := xk+1 − xk und qk := ∇f(xk+1)−∇f(xk)

➄ wähle γk > 0, νk ≥ 0 und berechne Hk+1 := Φ(Hk,pk,qk, γk, νk) gemäß (4.2)

➅ erhöhe k := k + 1 und gehe nach ➁

Das Verfahren ist eindeutig durch die Wahl der Parameter γk, νk und die Minimierung inSchritt ➂ fixiert. Die Minimierung xk 7→ xk+1 und ihre Qualität kann man mit Hilfe einesParameters σk beschreiben, der durch

∇f(xk+1)Tdk = σk∇f(xk)

Tdk = −σk∇f(xk)THk∇f(xk)

definiert ist. Falls dk eine Abstiegsrichtung ist, das heißt ∇f(xk)Tdk < 0, dann ist σk

eindeutig bestimmt. Bei exakter Liniensuche ist σk = 0 wegen

∇f(xk+1)Tdk = ϕ′

k(αk) = 0, wobei ϕk(α) := f(xk + αdk).

Wir setzen für das folgendeσk < 1 (4.3)

voraus. Falls ∇f(xk) 6= 0 und Hk positiv definit ist, folgt aus (4.3) αk > 0 und deshalb

qTkpk = αk{∇f(xk+1)−∇f(xk)}Tdk

= αk(σk − 1)∇f(xk)Tdk

= −αk(σk − 1)∇f(xk)THk∇f(xk)

> 0,

also auch qk 6= 0 und qTkHkqk > 0. Die Matrix Hk+1 ist damit durch (4.2) wohldefiniert.

33

Die Forderung (4.3) kann nur dann nicht erfüllt werden, wenn

ϕ′k(α) = ∇f(xk + αdk)

Tdk ≤ ∇f(xk)Tdk = ϕ′

k(0) < 0

für alle α ≥ 0 gilt. Dann ist aber

f(xk + αdk)− f(xk) =

∫ α

0

ϕ′k(t) dt ≤ α∇f(xk)

Tdk < 0 für alle α ≥ 0,

so dass f(xk +αdk) für α → ∞ nicht nach unten beschränkt ist. Die Forderung (4.3) be-deutet also keine wesentliche Einschränkung. Damit ist bereits der erste Teil des folgendenSatzes gezeigt, der besagt, dass das Quasi-Newton-Verfahren 4.1 unsere oben aufgestelltenForderungen erfüllt.

Satz 4.2 Falls im Quasi-Newton-Verfahren 4.1 die Matrix Hk für ein k ≥ 0 positivdefinit ist, ∇f(xk) 6= 0 und σk < 1 ist, dann ist für alle γk > 0, νk ≥ 0 die MatrixHk+1 := Φ(Hk,pk,qk, γk, νk) wohldefiniert und wieder positiv definit. Insbesondere erfülltsie die Quasi-Newton-Gleichung

Hk+1qk = pk.

Beweis. Die Wohldefiniertheit von Hk+1 haben wir bereits gezeigt, so dass wir nur nochdie positive Definitheit nachweisen müssen. Sei y ∈ Rn \ {0} ein beliebiger Vektor undHk = LLT die Cholesky-Zerlegung von Hk. Mit Hilfe der Vektoren

u := LTy, v := LTqk

lässt sich yTHk+1y wegen (4.2) so schreiben:

yTHk+1y = γkuTu+

(1 + γkνk

vTv

pTk qk

)(pT

k y)2

pTk qk

− γk1− νkvTv

(uTv)2 − 2γkνkpTk qk

(pTk y)(u

Tv)

= γk

(uTu− (uTv)2

vTv

)+

(pTk y)

2

pTk qk

+ γkνk

(√vTv

pTk y

pTk qk

− uTv√vTv

)2

≥ γk

(uTu− (uTv)2

vTv

)+

(pTk y)

2

pTk qk

.

Die Cauchy-Schwarzsche Ungleichung ergibt

uTu− (uTv)2

vTv≥ 0,

mit Gleichheit genau dann, wenn u = λv für ein λ 6= 0 (wegen y 6= 0). Für u 6= λvist also yHk+1y > 0. Für u = λv folgt aus der Nichtsingularität von Hk und L auch0 6= y = λqk, so dass

yHk+1y ≥ (pTk y)

2

pTk qk

= λ2pTk qk > 0.

Da y ∈ Rn \ {0} beliebig war, muss Hk+1 positiv definit sein.

Die Quasi-Newton-Gleichung Hk+1qk = pk verifiziert man schließlich sofort mittels (4.2).


Ein wesentliches Resultat ist, dass das Quasi-Newton-Verfahren im Fall einer quadrati-schen Funktion f : Rn → R das Minimum nach höchstens n Schritten liefert, sofern dieMinimierung in ➂ exakt sind. Da sich jede genügend oft differenzierbare Funktion f inder Nähe ihres Minimums beliebig genau durch eine quadratische Funktion approximierenlässt, lässt diese Eigenschaft vermuten, dass das Verfahren auch bei der Anwendung aufnichtquadratische Funktionen rasch konvergiert.

Satz 4.3 Sei

f(x) =1

2xTAx+ bTx + c

eine quadratische Funktion mit einer positiv definiten Matrix A ∈ Rn×n. Wendet mandas Quasi-Newton-Verfahren 4.1 zur Minimierung von f mit den Startwerten x0 und H0

an, wobei man die Minimierungen in ➂ exakt durchführt, so liefert das Verfahren Folgen{xk}k≥0, {Hk}k≥0, {∇f(xk)}k≥0, {pk}k≥0 und {qk}k≥0 mit den Eigenschaften:

(i.) Es gibt ein kleinstes m ≤ n mit xm = x⋆ = −A−1b, das heißt, xm ist das eindeutigeMinimum von f , insbesondere gilt also ∇f(xm) = 0.

(ii.) Es ist pTk qk > 0 und pT

k qℓ = pTkApℓ = 0 für alle 0 ≤ k 6= ℓ < m. Die Vektoren pk

sind demnach A-konjugiert.

(iii.) Es gilt pTk∇f(xℓ) = 0 für alle 0 ≤ k < ℓ ≤ m.

(iv.) Es ist Hℓqk = λk,ℓpk für alle 0 ≤ k < ℓ ≤ m mit

γk,ℓ :=

{γkγk+1 · · · γℓ−1, für k < ℓ− 1,

1, für k = ℓ− 1.

(v.) Falls m = n, so gilt zusätzlich

Hm = Hn = PDP−1A−1,

wobeiD = diag(γ0,n, γ1,n, . . . , γn−1,n), P = [p0,p1, . . . ,pn−1].

Für γk ≡ 1 folgt Hn = A−1.

Beweis. Wir zeigen zunächst induktiv, dass die Bedigungen (ii.)–(iv.) für ein beliebigesm ≥ 0 gelten, falls für alle j < m Hj positiv definit und ∇f(xj) 6= 0 ist. Da die Aussagenfür m = 0 trivialerweise erfüllt sind, können wir annehmen, dass sie für ein beliebigesm ≥ 0 gelten. Der Induktionsschritt m 7→ m+ 1 ergibt sich nun wie folgt.

Da Hm positiv definit ist, folgt aus ∇f(xm) 6= 0 sofort dm = −Hm∇f(xm) 6= 0 und∇f(xm)

THm∇f(xm) > 0. Weil exakt minimiert wird, ist αm die Nullstelle von

0 = ∇f(xm+1)Tdm =

{∇f(xm) + αmAdm

}Tdm, αm =

∇f(xm)Hm∇f(xm)

dTAdm,

also pm = αmdm und

∇f(xm+1)Tpm = αm∇f(xm+1)

Tdm = 0. (4.4)

35

Deshalb gilt

pTmqm = αmd

Tm

{∇f(xm+1)−∇f(xm)

}

= −αmdTm∇f(xm)

= αm∇f(xm)THm∇f(xm)

> 0

und folglich ist Hm+1 nach Satz 4.2 positiv definit. Weiter ist für k < m wegen Apk = qk

pTk qm = pT

kApm = qTkpm = −αmq

TkHm∇f(xm)

(iv.)= −αmγk,mp

Tk∇f(xm)

(iii.)= 0. (4.5)

Das ist der Induktionsschritt für Aussage (ii.).

Weiter gilt für k < m

pTk∇f(xm+1) = pT

k

(∇f(xk+1) +

m∑

j=k+1

qj

)= 0

nach dem eben bewiesenen und Aussage (iii.). Zusammen mit (4.4) ergibt dies Aussage(iii.) für m+ 1.

Den Induktionsschritt für Aussage (iv.) sieht man wie folgt ein. Anhand von (4.2) verifi-ziert man sofort

Hm+1qm = pm.

Wegen Aussage (ii.) für m+1 und der Induktionsvoraussetzung hat man ferner für k < m

pTmqk

(ii.)= 0, qT

mHmqk(iv.)= γk,mq

Tmpm

(ii.)= 0,

so dass für k < m aus (4.2) folgt

Hm+1qk = γmHmqk(iv.)= γmγk,mpk = γk,m+1pk.

Der restliche Beweis ist nun einfach. Die Aussagen (ii.)–(iv.) können nur für m ≤ nrichtig sein, da die Vektoren p0,p1, . . . ,pm−1 linear unabhängig sind. Aus 0 =

∑m−1ℓ=0 λℓpℓ

folgt nämlich durch Multiplikation mit pTkA, k = 0, 1, . . . , m − 1, wegen Aussage (ii.)

λkpTkApk = 0, das heißt, λk = 0.

Da wir bewiesen haben, dass die Aussagen (ii.)–(iv.) für beliebiges m gelten, solange∇f(xm) 6= 0 ist, muss es also einen ersten Index m ≤ n geben mit

∇f(xm) = 0, xm = −A−1b,

dies bedeutet, es gilt Aussage (i.).

Für den Fall m = n gilt wegen Aussage (iv.) zusätzlich HnQ = PD für die Matrizen

D = diag(γ0,n, γ1,n, . . . , γn−1,n), P = [p0,p1, . . . ,pn−1], Q = [q0,q1, . . . ,qn−1].

Wegen AP = Q ergibt sich schließlich wegen der Nichtsingularität der Matrix P dieBeziehung

Hn = PDP−1A−1,

Damit ist der Satz vollständig bewiesen.


Es stellt sich nun die Frage, wie man die Parameter γk und νk wählen soll, um ein mög-lichst gutes Verfahren zu erhalten. Aussage (v.) aus Satz 4.3 legt die Wahl γk ≡ 1 nahe,weil dies D = I und folglich limm Hm =

(∇2f(x⋆)

)−1vermuten lässt, weshalb das Verfah-

ren voraussichtlich ähnlich schnell wie ein Newton-Verfahren konvergiert. Im allgemeinenist diese Vermutung für nichtquadratische Funktionen aber nur unter zusätzlichen Vor-raussetzungen richtig. Nach praktischen Erfahrungen ist die Wahl

γk ≡ 1, νk ≡ 1 (BFGS-Verfahren)

am besten.

Bemerkungen

1. Sowohl das DFP-Verfahren als auch das BFGS-Verfahren konvergieren superline-ar in der Umgebung eines lokalen Minimus x⋆, falls f : Rn → R zweimal stetigdifferenzierbar ist und die Hesse-Matrix in der Umgebung von x⋆ Lipschitz-stetigist.

2. Eine andere Startmatrix H0 6= I ist denkbar, solange sie symmetrisch und positivdefinit ist.

3. In der Praxis macht man gelegentlich Restarts, setzt also Hk := H0, falls k ∈ mZ

mit festem m ∈ N, beispielsweise m = 100.

4. Gerade bei großen Optimierungsproblemen stellt man die Matrix Hk nicht direktauf, sondern berechnet sie rekursiv aus den Vektoren {(γk, νk,pk,qk)}k≥0. Damitauch bei vielen Schritten der Speicherplatz nicht überhand nimmt, speichert mannur die höchstens letzten m Vektoren. Man erlaubt also ein “Gedächtnis” von mUpdates und ersetzt die unbekannte Matrix Hk−m durch H0. Man spricht von einemLimited-Memory-Quasi-Newton-Verfahren.

△

37

5. Verfahren der konjugierten Gradi-

enten

5.1 CG-Verfahren für lineare Gleichungssysteme

Es sei A ∈ Rn×n eine symmetrische und positive definite Matrix und b ∈ Rn. Das Verfah-

ren der konjugierten Gradienten oder CG-Verfahren zur Lösung des linearen Gleichungs-systems Ax = b geht davon aus, dass die Lösung x⋆ eindeutiges Minimum φ(x⋆) = 0 desFunktionals

φ(x) =1

2(b−Ax)TA−1(b−Ax) =

1

2xTAx− xTb+

1

2bTA−1b ≥ 0

ist.

Ausgehend von einer Startnäherung x wollen wir φ in die Richtung d minimieren

φ(x+ αd) = φ(x) +α2

2dTAd− αdT (b−Ax) → min

α∈R.

Aus∂φ(x + αd)

∂α= αdTAd− dT (b−Ax)

!= 0

folgt daher

α =dT (b−Ax)

dTAd. (5.1)

Lemma 5.1 Die Vektoren d0,d1, . . . ,dk seien A-konjugiert , das heißt, es gelte dTi Adj =

0 für alle i 6= j. Istxk = arg min

x∈x0+span{d0,d1,...,dk−1}φ(x)

und setzt man

xk+1 = xk + αkdk, αk =dTk rk

dTkAdk

, rk = b−Axk, (5.2)

so folgtxk+1 = arg min

x∈x0+span{d0,d1,...,dk}φ(x).

Beweis. Die A-Konjugiertheit der Vektoren {dℓ} impliziert dTkA(xk − x0) = 0. Daher

38 Kapitel 5. Verfahren der konjugierten Gradienten

folgt

φ(xk + αdk) = φ(xk) +α2

2dTkAdk − αdT

k (b−Axk)

= φ(xk) +α2

2dTkAdk − αdT

k (b−Ax0)

=: φ(xk) + ϕ(α),

das heißt, das Minimierungsproblem entkoppelt. Da nach Voraussetzung xk das Funktio-nal φ über x0+span{d0,d1 . . . ,dk−1} minimiert, wird das eindeutige Minimum angenom-men, wenn ϕ(α) minimal ist. Dies ist aber nach (5.1) genau dann der Fall, wenn

αk =dTk (b−Axk)

dTkAdk

=dTk (b−Ax0)

dTkAdk

. (5.3)

Die Idee des CG-Verfahrens ist es nun, ausgehend von einer Startnäherung x0, sukzessiveüber die konjugierten Richtungen dk zu minimieren. Die Folge der Residuen

r0 = b−Ax0, rk+1 = b−Axk+1(5.2)= rk − αkAdk, k ≥ 0, (5.4)

erfüllt dann für alle ℓ < k

dTℓ rk = dT

ℓ (b−Axk) = dTℓ

(b−Ax0−

k−1∑

i=0

αiAdi

)= dT

ℓ (b−Ax0)−αℓdTℓ Adℓ

(5.3)= 0. (5.5)

Da die Richtungen dk paarweise A-konjugiert und folglich linear unabhängig sind, ergibtsich rn = 0, das heißt, das CG-Verfahren liefert die Lösung A−1b nach höchstens nSchritten. Zu beantworten bleibt daher nur die Frage, wie die Suchrichtungen dk geschicktgewählt werden können.

Lemma 5.2 Für beliebiges d0 = r0 erzeugt die Rekursion

rk+1 = rk − αkAdk, dk+1 = rk+1 − βkdk, βk =dTkArk+1

dTkAdk

(5.6)

solange eine Folge nichtverschwindender A-konjugierter Vektoren d0,d1, . . . ,dk+1 bisrk+1 = 0 ist.

Beweis. SeiKk(A, r0) := span{r0,Ar0, . . . ,A

k−1r0}.Wir zeigen zunächst induktiv, dass stets gilt

Kk(A, r0) = span{r0, r1, . . . , rk−1} = span{d0,d1, . . . ,dk−1}.

Da für k = 1 die Aussage klar ist, nehmen wir an, sie gilt für ein k ≥ 1. Dann folgt

rk(5.6)= rk−1︸︷︷︸

∈Kk(A,r0)

−αk Adk︸︷︷︸∈Kk+1(A,r0)

∈ Kk+1(A, r0).

5.1. CG-Verfahren für lineare Gleichungssysteme 39

Gemäß (5.5) ist rk ⊥ span{d0,d1, . . . ,dk−1} = Kk(A, r0), dies bedeutet

Kk(A, r0) ( span{r0, r1, . . . , rk} ⊆ Kk+1(A, r0).

Da die Dimension von Kk+1(A, r0) höchstens um 1 höher ist als die von Kk(A, r0), mussgelten

Kk+1(A, r0) = span{r0, r1, . . . , rk}.

Aus rk(5.6)= dk + βk−1dk−1 folgt

span{d0,d1, . . . ,dk} = span{d0,d1, . . . ,dk−1, rk}= span{r0, r1, . . . , rk−1, rk} = Kk+1(A, r0).

Insbesondere muss aus Dimensionsgründen dk 6= 0 sein.

Es verbleibt, die A-Konjugiertheit zu zeigen: Angenommen, d0,d1, . . . ,dk sind A-konjugiert.Der Induktionsschritt folgt dann aus

dTkAdk+1

(5.6)= dT

kA(rk+1 − βkdk)(5.6)= dT

kArk+1 −dTkArk+1

dTkAdk

dTkAdk = 0

und für alle ℓ < k

dTℓ Adk+1

(5.6)= dT

ℓ Ark+1 −dTkArk+1

dTkAdk

dTℓ Adk︸︷︷︸=0

= (Adℓ)T rk+1 = 0

wegen Adℓ ∈ Kk+1(A, r0) ⊥ rk+1.

Bemerkung Der Raum Kk(A, r0) heißt Krylov-Raum. Die Iterierte xk des CG-Verfahrensminimiert demnach das Funktional φ(x) unter allen x aus dem verschobenen Krylov-Raumx0 +Kk(A, r0). △Um den CG-Algorithmus endgültig zu formulieren, bemerken wir zunächst, dass gilt

αk(5.3)=

dTk rk

dTkAdk

(5.6)=

(rk − βk−1dk−1)T rk

dTkAdk

(5.5)=

‖rk‖22dTkAdk

. (5.7)

Wegen rk ∈ Kk+1(A, r0) ⊥ rk+1 folgt ferner

dTkArk+1 = (Adk)

T rk+1(5.6)=

1

αk

(rk − rk+1)T rk+1

(5.7)= −dT

kAdk

‖rk‖22‖rk+1‖22

und damit

βk(5.6)=

dTkArk+1

dTkAdk

= −‖rk+1‖22‖rk‖22

. (5.8)

Die Kombination von (5.2) und (5.6)–(5.8) liefert schließlich:

Algorithmus 5.3 (CG-Verfahren)input: Matrix A ∈ Rn×n, rechte Seite b ∈ Rn und Startnäherung x0 ∈ Rn

output: Folge von Iterierten {xk}k∈N➀ Initialisierung: setze d0 = r0 := b−Ax0 und k := 0


➁ berechne

αk :=‖rk‖22dTkAdk

xk+1 := xk + αkdk

rk+1 := rk − αkAdk

βk :=‖rk+1‖22‖rk‖22

dk+1 := rk+1 + βkdk

➂ falls ‖rk+1‖2 > ε erhöhe k := k + 1 und gehe nach ➁

Das CG-Verfahren wird generell als Iterationsverfahren verwendet, das heißt, man brichtdie Iteration ab, falls die Residuennorm ‖rk‖2 kleiner als eine Fehlertoleranz ε ist. ProIterationsschritt wird nur eine Matrix-Vektor-Multiplikation benötigt. Allerdings hängtdie Konvergenz des Verfahrens stark von der Kondition der Matrix ab. Man kann zeigen,dass die Iterierten {xk} des CG-Verfahrens bezüglich der Energienorm

‖x‖A :=√

〈x,x〉A =√xTAx

der Fehlerabschätzung

‖xk − x⋆‖A ≤ 2

(√cond2A− 1√cond2A+ 1

)k

‖x0 − x⋆‖A

genügen.

5.2 Nichtlineares CG-Verfahren

In Anlehnung an das CG-Verfahren 5.3 ist das nichtlineare CG-Verfahren zur Lösung vonnichtlinearen Optimierungsproblemen f(x) → min definiert.

Algorithmus 5.4 (Nichtlineares CG-Verfahren)input: Funktion f : Rn → R und Startnäherung x0 ∈ Rn

output: Folge von Iterierten {xk}k∈N➀ Initialisierung: setze d0 = −∇f(x0) und k := 0

➁ löseαk ≈ argmin

α∈Rf(xk + αdk)

➂ berechne

xk+1 := xk + αkdk

βk :=‖∇f(xk+1)‖22‖∇f(xk)‖22︸︷︷︸

Verfahren von Fletcher und Reeves

oder βk :=∇f(xk+1)

T{∇f(xk+1)−∇f(xk)}‖∇f(xk)‖22︸︷︷︸

Verfahren von Polak und Ribière

dk+1 := −∇f(xk+1) + βkdk

5.2. Nichtlineares CG-Verfahren 41


Bemerkung Ist f(x) = 12xTAx − bTx + c eine quadratische Funktion, dann fallen bei

exakter Minimierung in ➁ sowohl das Verfahren von Fletcher und Reeves als auch dasVerfahren von Polak und Ribière mit dem CG-Verfahren zusammen. Ersteres folgt aus∇f(xk) = Axk − b = −rk, zweiteres aus ∇f(xk)

T∇f(xk+1) = rTk rk+1 = 0. △

Lemma 5.5 Die Funktion f : D ⊂ Rn → R sei gleichmäßig konvex. Weiter sei fdifferenzierbar mit Lipschitz-stetigem Gradienten:


Dann gilt für das Verfahren von Polak und Ribière bei exakter Liniensuche in ➁

−dTk∇f(xk) ≥

µ

µ+ L‖∇f(xk)‖2‖dk‖2.

Beweis. Bei exakter Liniensuche gilt im k-ten Schritt des Verfahrens von Polak und Ri-bière

0 = ∇f(xℓ + αℓdℓ)Tdℓ = ∇f(xℓ+1)

Tdℓ für alle ℓ ≤ k. (5.9)

Daher können wir den Nenner in

βk =∇f(xk+1)

T{∇f(xk+1)−∇f(xk)}‖∇f(xk)‖22

folgendemaßen umformen:

‖∇f(xk)‖22 = (βk−1dk−1 − dk)T∇f(xk)

(5.9)= −dT

k∇f(xk)

(5.9)= dT

k

{∇f(xk+1)−∇f(xk)

}

=1

αk

(xk+1 − xk)T{∇f(xk+1)−∇f(xk)

}.

Aufgrund der gleichmäßigen Konvexität und der Lipschitz-Bedingung erhalten wir

|βk| ≤L

µ|αk|

‖∇f(xk+1)‖2‖xk+1 − xk‖2‖xk+1 − xk‖22

=L

µ

‖∇f(xk+1)‖2‖dk‖2

.

Dies führt auf

‖dk+1‖2 ≤ ‖∇f(xk+1)‖2 + |βk|‖dk‖2 ≤(1 +

L

µ

)‖∇f(xk+1)‖2,


woraus dann die Behauptung folgt

− dTk+1∇f(xk+1)

‖dk+1‖2‖∇f(xk+1)‖2=

{∇f(xk+1)− βkdk}T∇f(xk+1)

‖dk+1‖2‖∇f(xk+1)‖2(5.9)=

‖∇f(xk+1)‖22‖dk+1‖2‖∇f(xk+1)‖2

≥ µ

µ+ L.

Bemerkung Die geometrische Interpretation von Lemma 5.5 ist, dass beim Verfah-ren von Polak und Ribière die Suchrichtung dk und die Richtung des steilsten Abstiegs−∇f(xk) stets den Winkel θ mit cos θ > µ/(µ+ L) einschließen. △

Satz 5.6 Die Funktion f : D ⊂ Rn → R sei gleichmäßig konvex. Weiter sei f differen-zierbar mit Lipschitz-stetigem Gradienten:


Dann konvergiert das Verfahren von Polak und Ribière mit exakter Liniensuche in ➁ fürbeliebige Startnäherungen x0 ∈ D gegen das eindeutige globale Minimum x⋆ und es gilt

f(xk+1)− f(x⋆) ≤(1− µ4

L2(µ+ L)2

){f(xk)− f(x⋆)

}, k = 1, 2, . . . .

Beweis. Der Beweis ist ähnlich zu dem von Satz 2.3. Aufgrund der Minimierungsbedin-gung gilt wieder für ein γ > 0

f(xk+1) ≤ f(xk + γdk)

= f(xk) + γ

∫ 1

0

∇f(xk + γtdk)Tdk dt

= f(xk) + γ∇f(xk)Tdk + γ

∫ 1

0

{∇f(xk + γtdk)−∇f(xk)

}Tdk dt

≤ f(xk) + γ∇f(xk)Tdk + γ

∫ 1

0

‖∇f(xk + γtdk) +∇f(xk)‖2︸︷︷︸≤tγL‖dk‖2

‖dk‖2 dt

≤ f(xk) + γ∇f(xk)Tdk + γ2

L

2‖dk‖22.

Für die Wahl

γ := −∇f(xk)Tdk

L‖dk‖22

5.3. Modifiziertes Verfahren von Polak und Ribière 43

folgern wir mit Lemma 5.5

f(xk+1)− f(x⋆) ≤ f(xk)− f(x⋆)− (∇f(xk)Tdk)

2

2L‖dk‖22≤ f(xk)− f(x⋆)− µ2

2L(µ+ L)2‖∇f(xk)−∇f(x⋆)︸︷︷︸

=0

‖22.

Aus der gleichmäßigen Konvexität ergibt sich

µ‖xk − x⋆‖22 ≤{∇f(xk)−∇f(x⋆)

}T(xk − x⋆) ≤ ‖∇f(xk)−∇f(x⋆)‖2‖xk − x⋆‖2,

während die Lipschitz-Stetigkeit impliziert

f(xk)− f(x⋆) =

∫ 1

0

∇f(txk + (1− t)x⋆

)T(xk − x⋆) dt ≤ L

2‖xk − x⋆‖22.

Setzen wir diese beiden Abschätzungen in die obige ein, so erhalten wir das Behauptete.

Bemerkungen

1. Die Konvergenzabschätzung aus Satz 5.6 ist schlechter als die das Gradientenver-fahren betreffende aus Satz 2.3. Dies spiegelt jedoch nicht die Tatsache wieder, dassdas CG-Verfahren im Fall quadratischer Funktionen viel schneller konvergiert alsdas Gradientenverfahren. Die Ursache liegt in der Beweistechnik begründet, die dasVerfahren von Polak und Ribière als Störung des Gradientenverfahrens auffasst.

2. Das Verfahren von Polak und Ribière konvergiert im allgemeinen schneller als dasVerfahren von Fletcher und Reeves.

3. In der Praxis verwendet man Restarts: Wird der Winkel zwischen dem Antigradi-enten und der Suchrichtung zu groß, etwa

− ∇f(xk)Tdk

‖∇f(xk)‖2‖dk‖2< γ

für kleines γ ∈ (0, 1), dann startet das Verfahren durch einen Gradientenschritt neu.

△

5.3 Modifiziertes Verfahren von Polak und Ribière

Nichtlineare CG-Verfahren fallen, wie auch das BFGS-Verfahren, im Fall einer konvexenquadratischen Funktion mit dem CG-Verfahren zusammen. Allerdings sind die Quasi-Newton-Verfahren robuster hinsichtlich der Schrittweitensteuerung. Die nichtlinearen CG-Verfahren funktionieren umso besser, je genauer die Liniensuche in ➁ von Algorithmus 5.4durchgeführt wird. Eine direkt zu implementierende Schrittweitensteuerung stellen wir imfolgenden modifizierten Verfahren von Polak und Ribière vor.

Algorithmus 5.7 (modifiziertes Verfahren von Polak und Ribière)input: Funktion f : Rn → R und Startnäherung x0 ∈ Rn

output: Folge von Iterierten {xk}k∈N


➀ Initialisierung: wähle σ ∈ (0, 1), 0 < γ < 1 < γ und setze d0 = −∇f(x0), k := 0

➁ setze

αk :=|∇f(xk)

Tdk|‖dk‖22

➂ berechne

xk+1 := xk + αkdk

βk :=∇f(xk+1)

T{∇f(xk+1)−∇f(xk)}‖∇f(xk)‖22

dk+1 := −∇f(xk+1) + βkdk

➃ ist eine der Bedingungen

f(xk+1) ≤ f(xk)− σα2k‖dk‖22 (5.10)

−γ‖∇f(xk+1)‖22 ≤ ∇f(xk+1)Tdk+1 ≤ −γ‖∇f(xk+1)‖22 (5.11)

verletzt, dann halbiere αk und gehe nach ➂

➄ ist ∇f(xk+1) 6= 0, dann erhöhe k := k + 1 und gehe nach ➁

Lemma 5.8 Ist f : Rn → R stetig differenzierbar, so ist Algorithmus 5.7 wohldefiniert.

Beweis. Wir bemerken zunächst, dass stets dk 6= 0 ist und somit der Faktor αk in ➁ exis-tiert. Wäre nämlich dk = 0 für ein k ∈ N0, so würde aus ➁ im Fall k = 0 beziehungsweiseaus (5.11) im Fall k > 0 sofort ∇f(xk) = 0 folgen.

Es ist also nur zu zeigen, dass die Liniensuche ➁–➃ in jedem Iterationschritt k ∈ N0

erfolgreich ist. Zu diesem Zweck nehmen wir an, dass k ∈ N0 ein fester Iterationsindexmit ∇f(xk)

Tdk < 0 ist. Als erstes stellen wir fest, dass die Bedingung (5.10) wegen

f(xk + αdk) = f(xk) + α∇f(xk)Tdk + O(α)

nach endlich vielen erfolglosen Schritten der Liniensuche immer erfüllt ist.

Als nächstes zeigen wir, dass die Bedingung (5.11) ebenfalls nach endlich vielen erfolglosenSchritten stets erfüllt ist. Denn angenommen, dem ist nicht so. Dann gibt es eine Teilfolge{kℓ}ℓ>0, so dass für jedes

yℓ = xk + 2−kℓ|∇f(xk)

Tdk|‖dk‖22

dk, ℓ ∈ N

zumindest eine der beiden Bedingungen

∇f(yℓ)T

{−∇f(yℓ) +

∇f(yℓ)T{∇f(yℓ)−∇f(xk)}‖∇f(xk)‖22

dk

}> −γ‖∇f(yℓ)‖22,

∇f(yℓ)T

{−∇f(yℓ) +

∇f(yℓ)T{∇f(yℓ)−∇f(xk)}‖∇f(xk)‖22

dk

}< −γ‖∇f(yℓ)‖22


nicht erfüllt ist. Der Grenzübergang ℓ→ ∞ liefert yℓ → xk und folglich gilt

−‖∇f(xk)‖22 ≥ −γ‖∇f(xk)‖22 oder − ‖∇f(xk)‖22 ≤ −γ‖∇f(xk)‖22.

Aus 0 < γ < 1 < γ folgt dann aber ‖∇f(xk)‖2 = 0 im Widerspruch zu unserer Voraus-setzung ∇f(xk)

Tdk < 0.

Damit ist gezeigt, dass Algorithmus 5.7 wohldefiniert ist, sofern die Abstiegsbedingung∇f(xk)

Tdk < 0 für alle k ∈ N0 erfüllt ist. Für k = 0 gilt sie aber nach Definition von d0

und für k > 0 folgt sie dann aus Bedingung (5.11).

Lemma 5.9 Es sei D ⊂ Rn eine offene, beschränkte und konvexe Menge, in der f stetigdifferenzierbar, nach unten beschränkt und ∇f zudem Lipschitz-stetig ist. Ferner sei nebenx0 auch die gesamte Niveaumenge N := {x ∈ Rn : f(x) ≤ f(x0)} in D enthalten. Danngelten die folgenden Aussagen:

(i.) Alle Iterierten xk liegen in der Niveaumenge N .

(ii.) Die Folge {f(xk)}k∈N ist konvergent.

(iii.) Es gilt limk→∞ αk‖dk‖2 = 0.

(iv.) Es ist αk‖dk‖22 ≤ γc2, wobei c < ∞ eine obere Schranke von ‖∇f(x)‖2 auf derNiveaumenge N sei.

(v.) Es existiert eine Konstante θ > 0 mit

αk ≥ θ|∇f(xk)

Tdk|‖dk‖22

für alle k ∈ N0.

Beweis.

(i.) Diese Aussage ergibt sich unmittelbar aus der Bedingung (5.10).

(ii.) Die Folge {f(xk)}k∈N ist streng monoton fallend und aufgrund der Voraussetzungnach unten beschränkt. Hieraus ergibt sich das Behauptete.

(iii.) Aus (5.10) folgtσα2

k‖dk‖22 ≤ f(xk)− f(xk+1)

für alle k ∈ N0. Der Grenzübergang k → ∞ liefert daher unter Berücksichtigungder schon bewiesenen Aussage (ii.) die Behauptung.

(iv.) Aus den Schritten ➁–➃ von Algorithmus 5.7 folgt

αk‖dk‖22 ≤|∇f(xk)

Tdk|‖dk‖22

‖dk‖22 ≤ γ‖∇f(xk)‖22 ≤ γc2

für alle k ∈ N0.

(v.) Zum Nachweis dieser Aussage führen wir eine Fallunterscheidung durch.

Fall 1: αk = |∇f(xk)Tdk|/‖dk‖22.

Dann ist offensichtlich

αk ≥|∇f(xk)

Tdk|‖dk‖22

. (5.12)

Fall 2: αk < |∇f(xk)Tdk|/‖dk‖22.


Dann verletzt die Schrittweite 2αk zumindest eine der Bedingungen in ➃. Der Punktzk := xk + 2αkdk genügt also (5.10) oder (5.11) nicht. Nach Aussage (iii.) existiertein K ∈ N, so dass zk ∈ D für alle k ≥ K. Im folgenden zeigen wir Aussage (v.)zunächst nur für solche k.

Fall 2A: Der Punkt zk ∈ D verletzt (5.10).

Dann giltf(zk) > f(xk)− σ(2αk)

2‖dk‖22. (5.13)

Aufgrund des Mittelwertsatzes existiert ein ξk auf der Verbindungsstrecke von xk

und zk, so dass

f(zk) = f(xk) +∇f(ξk)T (zk − xk) = f(xk) + 2αk∇f(ξk)Tdk. (5.14)

Aus (5.13) und (5.14) folgt daher

f(xk) + 2αk∇f(xk)Tdk + 2αk

{∇f(ξk)Tdk −∇f(xk)

Tdk

}> f(xk)− σ(2αk)

2‖dk‖22.

Aus der Lipschitz-Stetigkeit von ∇f in D ergibt sich

2αk∇f(xk)Tdk + 2αkL ‖ξk − xk‖2︸︷︷︸

=2αk‖dk‖2

‖dk‖2 > −σ(2αk)2‖dk‖22.

Dies liefert unmittelbar

αk ≥1

2(L+ σ)

|∇f(xk)Tdk|

‖dk‖22. (5.15)

Fall 2B: Der Punkt zk ∈ D verletzt die linke Ungleichung in (5.11).

Wegen

∇f(zk)T{−∇f(zk) +

∇f(zk)T{∇f(zk)−∇f(xk)}‖∇f(xk)‖22

dk

}< −γ‖∇f(zk)‖22

ergibt sich mit Hilfe der Cauchy-Schwarzschen Ungleichung

−‖∇f(zk)‖22 − ‖∇f(zk)‖22‖∇f(zk)−∇f(xk)‖2

‖∇f(xk)‖22‖dk‖2 < −γ‖∇f(zk)‖22,

das heißt, es ist

1 +‖∇f(zk)−∇f(xk)‖2

‖∇f(xk)‖22‖dk‖2 > γ.

Aus der Lipschitz-Stetigkeit von ∇f und der Tatsache, dass die Schrittweite αk derBedingung (5.11) genügt, folgt daher nach kurzer Rechnung

αk ≥(γ − 1)‖∇f(xk)‖22

2L‖dk‖22≥ γ − 1

2γL

|∇f(xk)Tdk|

‖dk‖22. (5.16)

Fall 2C: Der Punkt zk ∈ D verletzt die linke Ungleichung in (5.11). Es ist

∇f(zk)T{−∇f(zk) +

∇f(zk)T{∇f(zk)−∇f(xk)}‖∇f(xk)‖22

dk

}> −γ‖∇f(zk)‖22.


Analog zum Fall 2B erhält man hieraus

αk ≥1− γ

2γL

|∇f(xk)Tdk|

‖dk‖22. (5.17)

Wegen (5.12), (5.15), (5.16), (5.17) folgt Aussage (v.) mit

θ := min

{1,

1

2(L+ σ),γ − 1

2γL,1− γ

2γL

},

und zwar zunächst für alle k ≥ K. Da nur endlich viele k übrigbleiben, folgt Aussage(v.) nach eventueller Verkleinerung von θ aber auch für alle k ∈ N0.

Satz 5.10 Unter den Voraussetzungen von Lemma 5.9 gilt für die Iterierten {xk}k≥0 desmodifizierten Verfahren von Polak und Ribière 5.7

∇f(xk)k→∞−→ 0.

Beweis. Angenommen, die Aussage des Satzes ist falsch. Dann existieren ein ε > 0 undeine Teilfolge {xkℓ}, so dass

‖∇f(xkℓ−1)‖2 > ε

für alle ℓ ∈ N. Aus der Aufdatierungsvorschrift für dkℓ und Lemma 5.9 (iv.) folgt dann

‖dkℓ‖2 ≤ ‖∇f(xkℓ)‖2 +‖∇f(xkℓ)‖2‖∇f(xkℓ)−∇f(xkℓ−1)‖2

‖∇f(xkℓ−1)‖22‖dkℓ−1‖2 ≤ c + γ

Lc3

ε2

für alle ℓ ∈ N. Zusammen mit Lemma 5.9 (iii.) ergibt sich hieraus

limℓ→∞

αkℓ‖dkℓ‖22 = 0

und weiter aus Lemma 5.9 (v.)

limℓ→∞

|∇f(xkℓ)Tdkℓ| = 0.

Die rechte Ungleichung in (5.11) liefert daher

limℓ→∞

‖∇f(xkℓ)‖2 = 0.

Weil nach Lemma 5.9 (iii.) gilt

limℓ→∞

‖xkℓ − xkℓ−1‖2 = limℓ→∞

αkℓ−1‖dkℓ−1‖2 = 0,

schließen wir

‖∇f(xkℓ−1)‖2 ≤ ‖∇f(xkℓ)−∇f(xkℓ−1)‖2 + ‖∇f(xkℓ)‖2≤ L‖xkℓ − xkℓ−1‖2 + ‖∇f(xkℓ)‖2ℓ→∞−→ 0.

Dies steht aber im Widerspruch zur Annahme, dass {‖∇f(xkℓ−1)‖2}ℓ>0 nicht nach Nullkonvergiert.

48 Kapitel 6. Nichtlineare Ausgleichsprobleme

6. Nichtlineare Ausgleichsprobleme

6.1 Gauß-Newton-Verfahren

Ein nichtlineares Ausgleichsproblem liegt vor, falls zu gegebenen Daten und Funktionen

y =

y1y2...ym

∈ Rm, f(x) =

f1(x1, x2, . . . , xn)f2(x1, x2, . . . , xn)

...fm(x1, x2, . . . , xn)

: Rn → Rm

dasjenige x⋆ = [x⋆1, x⋆2, . . . , x

⋆n]

T gesucht wird, das die Minimierungsaufgabe

φ(x) :=1

2‖y− f(x)‖22 =

m∑

i=1

|yi − fi(x1, x2, . . . , xn)|2 → minx∈Rn

(6.1)

löst.

Nichtlineare Ausgleichsprobleme können im allgemeinen nur iterativ gelöst werden. Dahierzu Gradienteninformationen benötigt wird, setzen wir f als stetig differenzierbar vor-aus. Die Ableitung f ′ sei zusätzlich sogar Lipschitz-stetig.

Natürlich kann man das nichtlineare Ausgleichsproblem (6.1) mit dem Gradientenverfah-ren oder dem Quasi-Newton-Verfahren zu lösen. Besser ist es jedoch, es mit dem Newton-Verfahren zu lösen, was auf die Iteration

xk+1 = xk − φ′′(xk)∇φ(xk), k = 0, 1, 2, . . .

führt. Hierzu wird jedoch neben dem Gradienten

∇φ(x) = −(f ′(x)

)T (y − f(x)

), f ′(x) =

∂f1∂x1

(x) ∂f1∂x2

(x) . . . ∂f1∂xn

(x)∂f2∂x1

(x) ∂f2∂x2

(x) . . . ∂f2∂xn

(x)...

......

∂fm∂x1

(x) ∂fm∂x2

(x) . . . ∂fm∂xn

(x)

auch die Hesse-Matrix benötigt, das ist

φ′′(x) =(f ′(x)

)Tf ′(x)−

(y − f(x)

)Tf ′′(x).

In der Praxis will man die Berechnung des Tensors f ′′(x) ∈ Rm×(n×n) jedoch vermei-den. Daher vernachlässigt man den Term

(y− f(x)

)Tf ′′(x) und erhält das Gauß-Newton-

Verfahren.

6.1. Gauß-Newton-Verfahren 49

Zu dessen Herleitung linearisieren wir die Funktion f

f(x + d) = f(x) + f ′(x)d+ O(‖d‖2).

Ist nun xk eine Näherungslösung des Ausgleichsproblems (6.1), so erwartet man, dass dieOptimallösung xk+1 = xk + dk des linearisierten Problems

mind∈Rn

‖y− f(xk)− f ′(xk)d‖22 = ‖rk − f ′(xk)dk‖22, rk := y− f(xk)

eine bessere Lösung des Ausgleichsproblems ist. Gemäß Definition muss das Update dk

die Normalengleichungen(f ′(xk)

)Tf ′(xk)dk =

(f ′(xk)

)Trk

lösen. Dies führt auf folgenden Algorithmus:

Algorithmus 6.1 (Gauß-Newton–Verfahren)input: Funktion f : Rn → Rm, Datenvektor y ∈ Rm und Startnäherung x0 ∈ Rn

output: Folge von Iterierten {xk}k∈N➀ Initialisierung: setze k = 0

➁ löse die Normalengleichungen

(f ′(xk)

)Tf ′(xk)dk =

(f ′(xk)

)T (y− f(xk)

)(6.2)



Satz 6.2 Sei D ⊂ Rn offen und f : D → Rm eine stetig differenzierbare Abbildung. DasMinimierungsproblem (6.1) habe eine Lösung x⋆ ∈ D mit rang

(f ′(x⋆)

)= n ≤ m. Sei

λ > 0 der kleinste Eigenwert von(f ′(x⋆)

)Tf ′(x⋆). Ferner gelte die Lipschitz-Bedingung

‖f ′(x)− f ′(z)‖2 ≤ α‖x− z‖2 (6.3)

und ∥∥(f ′(x)− f ′(x⋆))T (

y − f(x⋆))∥∥

2≤ β‖x− x⋆‖2 (6.4)

mit β < λ für alle x, z aus einer Umgebung von x⋆. Dann existiert ein ε > 0, so dassfür jeden Startvektor x0 ∈ Bε(x

⋆) := {x ∈ Rn : ‖x − x⋆‖2 < ε} die Folge der Iterierten{xk}k≥0 mindestens linear gegen x⋆ konvergiert.

Beweis. Nach Voraussetzung gibt es ein ε1 > 0, so dass (6.3) und (6.4) für alle x ∈ Bε1(x⋆)

gelten. Aus Stetigkeitsgründen folgt außerdem die Existenz von γ > 0, so dass

‖f ′(x)‖2 ≤ γ für alle x ∈ Bε1(x⋆).

Wegen rang(f ′(x⋆)

)= n, ist die Matrix

(f ′(x⋆)

)Tf ′(x⋆) regulär mit

∥∥∥∥((

f ′(x⋆))T

f ′(x⋆))−1

∥∥∥∥2

=1

λ. (6.5)


Daher gibt es zu beliebigem δ > 1 ein ε2 > 0 derart, dass(f ′(x)

)Tf ′(x) regulär ist und

∥∥∥∥(f ′(x)

)Tf ′(x)

)−1∥∥∥∥2

≤ δ

λfür alle x ∈ Bε2(x

⋆). (6.6)

Wir wählen δ > 1 so, dass zusätzlich gilt

δ <λ

β. (6.7)

Weiter gibt es ein ε3 > 0, so dass für jedes xk ∈ Bε3(x⋆) folgt

‖f(x⋆)− f(xk)− f ′(xk)(x⋆ − xk)‖2

=

∥∥∥∥∫ 1

0

f ′(xk + t(x⋆ − xk)

)(x⋆ − xk) dt− f ′(xk)(x

⋆ − xk)

∥∥∥∥2

=

∥∥∥∥∫ 1

0

(f ′(xk + t(x⋆ − xk)

)− f ′(xk)

)(x⋆ − xk) dt

∥∥∥∥2

≤∫ 1

0

∥∥∥f ′(xk + t(x⋆ − xk)

)− f ′(xk)

∥∥∥2︸︷︷︸

≤αt‖xk−x⋆‖2

‖xk − x⋆‖2 dt

≤ α

2‖xk − x⋆‖22.

Wir setzen nun

ε := min

{ε1, ε2, ε3,

λ− βδ

αγδ

}> 0.

Aus (6.2) folgt dann für xk ∈ Bε(x⋆) dass

xk+1 − x⋆ = xk + dk − x⋆

=((

f ′(xk))T

f ′(xk))−1[(

f ′(xk))T (

y − f(xk))−(f ′(xk)

)Tf ′(xk)(x

⋆ − xk)]

=((

f ′(xk))T

f ′(xk))−1[(

f ′(xk))T (

y − f(x⋆))

+(f ′(xk)

)T (f(x⋆)− f(xk)− f ′(xk)(x

⋆ − xk))].

Hieraus folgt dann mit (6.5) und (6.6)

‖xk+1 − x⋆‖2 ≤∥∥∥∥((

f ′(xk))T

f ′(xk))−1

∥∥∥∥2

[∥∥(f ′(xk))T (

y− f(x⋆))∥∥

2

+ ‖f ′(xk)‖2‖f(x⋆)− f(xk)− f ′(xk)(x⋆ − xk)‖2

]

≤ δ

λ

[∥∥(f ′(xk))T (

y − f(x⋆))∥∥

2+αγ

2‖xk − x⋆‖22

]. (6.8)

Wegen 0 = ∇φ(x⋆) = −(f ′(x⋆)

)T (y − f(x⋆)

)ergibt sich mit (6.4)

∥∥(f ′(xk))T (

y − f(x⋆))∥∥

2=

∥∥(f ′(xk)− f ′(x⋆))T (

y − f(x⋆))∥∥

2≤ β‖xk − x⋆‖2,

dies bedeutet,

‖xk+1 − x⋆‖2 ≤δ

λ

[β +

αγ

2‖xk − x⋆‖2︸︷︷︸

≤ε≤(λ−βδ)/(αγδ)

]‖xk − x⋆‖2 ≤

[βδ

λ+λ− βδ

2λ︸︷︷︸=(λ+βδ)/(2λ)

]‖xk − x⋆‖2.

6.2. Levenberg-Marquardt-Verfahren 51

Wegen (6.7) ist die Konstante (λ+ βδ)/(2λ) < 1, das heißt, alle Iterierten {xk}k≥0 liegenin Bε(x

⋆) und konvergieren mindestens linear gegen x⋆.

Bemerkung Die Voraussetzung (6.4) besagt im Prinzip, dass das Residuum r(x⋆) =y − f(x⋆) klein genug sein soll. Dies sieht man insbesondere, wenn man sie durch diestärkere Bedingung

‖y − f(x⋆)‖2 ≤λ

α

ersetzt. Dann folgt nämlich (6.4):∥∥(f ′(x)− f ′(x⋆)

)T (y − f(x⋆)

)∥∥2≤ ‖f ′(x)− f ′(x⋆)‖2︸︷︷︸

≤α‖x−x⋆‖2

‖y − f(x⋆)‖2︸︷︷︸≤λ/α

≤ λ‖x− x⋆‖2.

△

Korollar 6.3 Zusätzlich zu den Voraussetzungen aus Satz 6.2 gelte f(x⋆) = y. Dannexistiert ein ε > 0, so dass für jeden Startvektor x0 ∈ Bε(x

⋆) die Folge der Iterierten{xk}k≥0 quadratisch gegen x⋆ konvergiert.

Beweis. Aus Satz 6.2 folgt die lineare Konvergenz der Iterierten {xk}k≥0 gegen x⋆. ZumNachweis der quadratischen Konvergenz bemerken wir, dass aufgrund der Voraussetzung(6.4) mit β = 0 gilt. Daher folgt aus (6.8)

‖xk+1 − x⋆‖2 ≤αγδ

2λ‖xk − x⋆‖22.

6.2 Levenberg-Marquardt-Verfahren

Das Levenberg-Marquardt-Verfahren ist ein Trust-Region-Verfahren, also ein Verfahren,bei dem der Linearisierung nur im Bereich ‖dk‖2 ≤ ∆k vertraut wird. Demnach wollenwir das restringierte Optimierungsproblem

mind∈Rn:‖d‖2≤∆k

ψ(d) = mind∈Rn:‖d‖2≤∆k

1

2‖rk − f ′(xk)d‖22, (6.9)

lösen, um die Iterierte dann mit der Lösung dk aufzudatieren: xk+1 = xk + dk.

Da die Menge B∆k(0) kompakt ist, existiert ein Minimum dk. Es treten dabei zwei Fälle

auf:

1. Das Minimum dk liegt im Inneren der Kugel B∆k(0) und erfüllt

∇ψ(dk) =(f ′(xk)

)T (f ′(xk)dk − rk

)= 0. (6.10)

2. Das Minimum liegt auf dem Rand, erfüllt also ‖dk‖2 = ∆k. In diesem Fall muss dieHöhenlinie von ψ in dk genau den Kreis ∂B∆k

(0) tangieren, das heißt, der Gradient∇ψ(dk) zeigt in Richtung des Nullpunkts:

∇ψ(dk) =(f ′(xk)

)T (f ′(xk)dk − rk

)= −λkdk für ein λk ≥ 0. (6.11)


Der Parameter λk wird Lagrange-Parameter genannt. Da die Gleichung (6.10) als Spezi-alfall λk = 0 von (6.11) angesehen werden kann, erhalten wir:

Lemma 6.4 Die Lösung dk des restringierten Problems (6.9) genügt der Gleichung((

f ′(xk))T

f ′(xk) + λkI)dk =

(f ′(xk)

)Trk (6.12)

für ein λk ≥ 0. Dabei ist der Wert λk genau dann positiv, wenn ∇ψ(dk) 6= 0 und daherdie Nebenbedingung ‖dk‖2 = ∆k > 0 gilt.

Der Vorteil des regularisierten Systems (6.12) liegt darin, dass es stets eindeutig lösbarist, sofern λk > 0 ist. Die zugehörige Lösung

dk =((

f ′(xk))T

f ′(xk) + λkI)−1(

f ′(xk))T

rk = −((

f ′(xk))T

f ′(xk) + λkI)−1

∇φ(xk)

erfüllt offenbar die Abstiegsbedingung dTk∇φ(xk) < 0, es sei denn, der Punkt xk ist

stationär.

Bemerkung Ist λk = 0, dann ergibt sich ein Gauß-Newton-Schritt, während dk fürλk → ∞ der Richtung des steilsten Abstiegs entspricht. △Wir müssen uns noch ein Kriterium überlegen, wie wir ∆k wählen. Eine neue Näherungxk+1 = xk + dk können wir anhand der Armijo-Goldstein-Bedingung (vergleiche (2.4))bewerten:

ρ =φ(xk + dk)− φ(xk)

dTk∇φ(xk)

=1

2

‖y − f(xk)‖22 − ‖y− f(xk + dk)‖22dTk

(f ′(xk)

)T (y− f(xk)

) .

Wir wählen zwei Toleranzgrenzen 0 < ρ− < ρ+ < 1 und akzeptieren den Iterationsschritt,wenn ρ > ρ− gilt. Dann war der Trust-Region-Radius ∆k geeignet gewählt. Ist ρ ≥ρ+, so können wir ∆k sogar vergrößern. Ist hingegen ρ ≤ ρ−, dann verwerfen wir denIterationsschritt und verkleinern ∆k. Dies führt auf den folgenden Algorithmus:

Algorithmus 6.5 (Levenberg-Marquardt-Verfahren)input: Funktion f : Rn → Rm, Datenvektor y ∈ Rm und Startnäherung x0 ∈ Rn

output: Folge von Iterierten {xk}k∈N➀ Initialisierung: wähle 0 < ρ− < ρ+ < 1 und setze ∆0 := 1 und k := 0

➁ bestimme die Lösung dk des restringierten Optimierungsproblems (6.9)

➂ berechne

ρk =1

2

‖y− f(xk)‖22 − ‖y − f(xk + dk)‖22dTk

(f ′(xk)

)T (y − f(xk)

) (6.13)

➃ falls ρk > ρ− setze xk+1 := xk + dk, sonst setze ∆k := ∆k/2 und gehe nach ➁

➄ falls ρk > ρ+ setze ∆k+1 := 2∆k, sonst setze ∆k+1 := ∆k

➅ erhöhe k := k + 1 und gehe nach ➁


Satz 6.6 Es sei D ⊂ Rn eine kompakte Menge, in der f stetig differenzierbar und f ′

zudem Lipschitz-stetig ist. Ferner sei neben x0 auch die gesamte Niveaumenge {x ∈ Rn :φ(x) ≤ φ(x0)} in D enthalten. Dann gilt für die Iterierten {xk}k≥0 aus Algorithmus 6.5

∇φ(xk)k→∞−→ 0.

Beweis. (i) Zunächst beweisen wir eine obere Schranke für den Lagrange-Parameter λkaus (6.12). Dazu nehmen wir ohne Beschränkung der Allgemeinheit an, dass λk > 0 unddaher ‖dk‖2 = ∆k ist. Aus (6.12) folgt

dTk

((f ′(xk)

)Tf ′(xk) + λkI

)dk = dT

k

(f ′(xk)

)Trk ≤ ‖dk‖2

∥∥(f ′(xk))T

rk∥∥2.

Da(f ′(xk)

)Tf ′(xk) positiv semidefinit ist, kann die linke Seite nach unten durch λk abge-

schätzt werden, so dass folgt

λk ≤∥∥(f ′(xk)

)Trk∥∥2

∆k

=‖∇φ(xk)‖2

∆k

. (6.14)

(ii) Als nächstes leiten wir eine untere Schranke für den Nenner νk in (6.13) her. Im Fallλk > 0 ist

(f ′(xk)

)Tf ′(xk) + λkI positiv definit, weshalb eine Cholesky-Zerlegung LLT

existiert. Dabei gilt

‖LTL‖2 = ‖LLT‖2 =∥∥(f ′(xk)

)Tf ′(xk) + λkI

∥∥2= ‖f ′(xk)‖22︸︷︷︸

≤c für alle x∈D

+λk(6.14)

≤ c+‖∇φ(xk)‖2

∆k.

Setzen wir w = L−1∇φ(xk), so folgt unter Beachtung von (6.12) hieraus

νk =(∇φ(xk)

)T(LLT )−1∇φ(xk) = wTw

‖∇φ(xk)‖22(∇φ(xk)

)T∇φ(xk)=

‖w‖22‖∇φ(xk)‖22wTLTLw

≥ ‖w‖22‖∇φ(xk)‖22‖w‖22

(c+ ‖∇φ(xk)‖2/∆k

) ≥ ‖∇φ(xk)‖21 + c

min{∆k, ‖∇φ(xk)‖2}. (6.15)

Im Fall λk = 0 folgtνk = rTk f

′(xk)(f ′(xk)

)+rk = ‖Pkrk‖22,

wobei Pk = f ′(xk)(f ′(xk)

)+den Orthogonalprojektor auf img

(f ′(xk)

)bezeichnet. Wegen

img(f ′(xk)

)= kern

((f ′(xk)

)T)⊥

folgt daher

‖∇φ(xk)‖22 =∥∥(f ′(xk)

)Trk∥∥2

2=

∥∥(f ′(xk))T

Pkrk∥∥2

2≤

∥∥(f ′(xk))T∥∥2

2‖Pkrk‖22 ≤ cνk,

das heißt, (6.15) ist auch im Fall λk = 0 gültig.

(iii) Wir beweisen nun, dass die rechte Seite von (6.15) gegen Null konvergiert. Bei er-folgreichem Iterationsschritt ist ρk > ρ− und aus (6.13) und (6.15) folgt

φ(xk)− φ(xk+1) > ρ−νk ≥ ρ−‖∇φ(xk)‖21 + c

min{∆k, ‖∇φ(xk)‖2}. (6.16)


Da nach Konstruktion {φ(xk)}k≥0 eine monoton fallende, nach unten beschränkte Folgeist, muss gelten

min{∆k, ‖∇φ(xk)‖2} k→∞−→ 0. (6.17)

(iv) Als nächstes zeigen wir, dass ‖∇φ(xk)‖2 für eine Teilfolge {kn}n∈N mit kn → ∞ gegenNull konvergiert. Angenommen, die Behauptung gilt nicht, dann folgt

‖∇φ(xk)‖2 ≥ ε > 0 für alle k ≥ K(ε).

Aus (6.17) ergibt sich damit unmittelbar

∆kk→∞−→ 0. (6.18)

Taylor-Entwicklung von ρk liefert jedoch

ρk =φ(xk+1)− φ(xk)

dTk∇φ(xk)

=dTk∇φ(xk) +O(‖dk‖22)

dTk∇φ(xk)

= 1 +O(∆2

k

νk

)(6.15)= 1 +O

(∆k

‖∇φ(xk)‖2︸︷︷︸≥ε>0

)= 1 +O(∆k) für k → ∞.

Demnach existiert ein M(ε) ≥ K(ε), so dass ρk > ρ+ für alle k ≥M(ε). Ab dem M(ε)-tenSchritt wird folglich ∆k in jedem Schritt von Algorithmus 6.5 verdoppelt, was jedoch imWiderspruch zu (6.18) steht.

(v) Wir beweisen nun die Aussage des Satzes. Dazu nehmen wir an, dass eine Teilfolgevon {‖∇φ(xk)‖2}k≥0 nicht gegen Null konvergiert. Nach Aussage (iv) existiert dann einε > 0 und zwei Indizes ℓ < m, so dass

‖∇φ(xℓ)‖2 ≥ 2ε, ‖∇φ(xm)‖2 ≤ ε, ‖∇φ(xk)‖2 > ε, k = ℓ+ 1, . . . , m− 1.

Da {φ(xk)}k≥0 eine Cauchy-Folge ist, kann ℓ dabei so groß gewählt werden, dass

φ(xℓ)− φ(xm) <ε2ρ−

(1 + c)L, (6.19)

wobei L > 1 eine Lipschitz-Konstante von ∇φ in D bezeichne. Wegen ‖xk+1−xk‖2 ≤ ∆k

folgt aus (6.16) dass

φ(xk)− φ(xk+1) ≥ερ−

1 + cmin{‖xk+1 − xk‖2, ε}, k = ℓ, ℓ+ 1, . . . , m− 1.

Summation ergibt

ερ−

1 + c

m−1∑

k=ℓ

min{‖xk+1 − xk‖2, ε} ≤ φ(xℓ)− φ(xm)(6.19)<

ε2ρ−

(1 + c)L,

was wegen L > 1 nur erfüllt sein kann, wenn

min{‖xk+1 − xk‖2, ε} = ‖xk+1 − xk‖2, k = ℓ, ℓ+ 1, . . . , m− 1,

und insgesamtm−1∑

k=ℓ

‖xk+1 − xk‖2 <ε

L


gilt. Dies ergibt

‖∇φ(xm)−∇φ(xℓ)‖2 ≤ L‖xm − xℓ‖2 ≤ L

m−1∑

k=ℓ

‖xk+1 − xk‖2 < ε

im Widerspruch zur Annahme. Damit ist der Satz bewiesen.

Wir kommen nun zur Implementierung. Um das restringierte Minimierungsproblem (6.9)zu lösen, berechnen wir zunächst die Lösung dk bezüglich des unrestringierten Minimie-rungsproblems und akzeptieren den Schritt, falls ‖dk‖2 ≤ ∆k. Ist hingegen ‖dk‖2 > ∆k,so wissen wir, dass das Minimum von (6.9) auf dem Rand liegt. Wir suchen dann dasjenigeTupel (λk,dk), das (6.12) und ‖dk‖2 = ∆k löst.

Es bezeichne z1 ≥ · · · ≥ zn ≥ 0 die Eigenwerte von(f ′(xk)

)Tf ′(xk) und {vi}ni=1 die

zugehörigen orthonormalen Eigenvektoren. Entwickeln wir die rechte Seite von (6.12) indiese Eigenbasis

(f ′(xk)

)Trk =

n∑

i=1

ξivi,

dann folgt

dk(λk) =((

f ′(xk))T

f ′(xk) + λkI)−1

n∑

i=1

ξivi =

n∑

i=1

ξizi + λk

vi.

Die Forderung ‖dk(λk)‖2 = ∆k führt auf die nichtlineare Gleichung

r(λk) :=n∑

i=1

|ξi|2|zi + λk|2

!= ∆2

k.

Diese kann mit dem Hebden-Verfahren gelöst werden, einem Newton-Verfahren für dieGleichung

1√r(λ)

− 1

∆k

!= 0.

Ausgehend vom Startwert λ(0) = 0 konvergiert die zugehörige Iteration

λ(i+1) = λ(i) + 2r3/2(λ(i))

r′(λ(i))

(r−1/2(λ(i))− 1

∆k

), i = 0, 1, 2, . . . .

sehr schnell gegen die Lösung λk. Die explizite Spektralzerlegung kann vermieden werden,indem man r(λ) = ‖dk(λ)‖22 und

r′(λ) = −2rTk f′(xk)

((f ′(xk)

)Tf ′(xk) + λI

)−3(f ′(xk)

)Trk = −2dk(λ)

Tg(λ)

mit((

f ′(xk))T

f ′(xk) + λI)g(λ) = dk(λ)

benutzt.

Für jede Hebden-Iterierte sind zwei Gleichungssysteme mit derselben Systemmatrix zulösen. Diese entsprechen genau den Normalengleichungen zu den Ausgleichsproblemen

∥∥∥∥[f ′(xk)√λI

]dk(λ)−

[rk0

]∥∥∥∥2

2

→ min,

∥∥∥∥[f ′(xk)√λI

]g(λ)−

[0

dk(λ)/√λ

]∥∥∥∥2

2

→ min .

Verwendet man die QR-Zerlegung QR = f ′(xk), so können letztere durch Anwendungvon jeweils n(n + 1)/2 Givens-Rotationen effizient gelöst werden.

56 Kapitel 7. Optimierungsprobleme mit Nebenbedingungen

7. Optimierungsprobleme mit Neben-

bedingungen

7.1 Optimalitätsbedingungen erster Ordnung

Wir betrachten im folgenden Optimierungsprobleme mit Nebenbedingungen, das heißt,Probleme der Form

minx∈Rn

f(x) unter den Nebenbedingungen

ci(x) = 0 für alle i ∈ JG,

ci(x) ≥ 0 für alle i ∈ JU .

(7.1)

Dabei seien JG und JU Indexmengen für Gleichungs- und Ungleichungsnebenbedingun-gen.

Definition 7.1 Es bezeichne

G := {x ∈ Rn : ci(x) = 0 für i ∈ JG und ci(x) ≥ 0 für i ∈ JU} ⊂ Rn

die Menge der zulässigen Punkte des Minimierungsproblems unter Nebenbedingungen(7.1). Dann verstehen wir unter einem lokalen Minimum des Problems (7.1) einen Punktx⋆ ∈ G, für den für alle x ∈ U ∩ G gilt f(x⋆) ≤ f(x) mit einer Umgebung U ⊂ Rn vonx⋆.

Als generelle Voraussetzung für das folgende seien sowohl f als auch ci für alle i ∈ JG∪JU

stetig differenzierbar im betrachteten Bereich.

Definition 7.2 Es sei x⋆ ∈ G ein lokales Minimum des Minimierungsproblems (7.1).Die Folge {xk}k∈N ⊂ Rn heißt zulässige Folge für das Problem (7.1), falls folgendeEigenschaften erfüllt sind:

(i.) Es gilt limk→∞ xk = x⋆ ∈ G.

(ii.) Es ist xk 6= x⋆ für alle k ∈ N.

(iii.) Es existiert ein K ∈ N, so dass xk ∈ G für alle k ≥ K.

Die Richtung d ∈ Rn heißt Grenzrichtung einer zulässigen Folge, falls

limℓ→∞

xkℓ − x⋆

‖xkℓ − x⋆‖2= d (7.2)

7.1. Optimalitätsbedingungen erster Ordnung 57

für eine Teilfolge {xkℓ}ℓ∈N gilt.

Satz 7.3 Ist x⋆ ∈ G ein lokales Minimum des Minimierungsproblems (7.1), so gilt

∇f(x⋆)Td ≥ 0

für alle Grenzrichtungen d ∈ Rn zu zulässigen Folgen mit Grenzwert x⋆.

Beweis. Angenommen, es gibt eine zulässige Folge {xk}k∈N mit ∇f(x⋆)Td < 0 für eineGrenzrichtung d. Es sei {xkℓ}ℓ∈N eine zur Grenzrichtung gehörende Teilfolge mit (7.2).Dann gilt

f(xkℓ) = f(x⋆) +∇f(x⋆)T (xkℓ − x⋆) + O(‖xkℓ − x⋆‖2)= f(x⋆) + ‖xkℓ − x⋆‖2∇f(x⋆)Td+ O(‖xkℓ − x⋆‖2).

Wegen ∇f(x⋆)d < 0 gibt es ein L ∈ N, so dass

f(xkℓ) < f(x⋆) +1

2‖xkℓ − x⋆‖2∇f(x⋆)Td

für alle ℓ ≥ L gilt. In jeder Umgebung von x⋆ finden wir daher ein xkℓ mit f(xkℓ) < f(x⋆)im Widerspruch zur Voraussetzung.

Mit Hilfe dieses Satzes können wir den Begriff des stationären Punktes auf das Minimie-rungsproblem mit Nebenbedingungen (7.1) verallgemeinern.

Definition 7.4 Der Punkt x⋆ ∈ G wird als stationärer Punkt des Minimierungspro-blems mit Nebenbedingungen (7.1) bezeichnet, falls

∇f(x⋆)Td ≥ 0 (7.3)

für alle Grenzrichtungen d ∈ Rn zulässiger Folgen mit Grenzwert x⋆ gilt.

Man beachte, dass die Bedingung (7.3) im Fall eines unrestringierten Minimierungspro-blems mit der üblichen Bedingung ∇f(x⋆) = 0 zusammenfällt.

Definition 7.5 Zu gegeben Punkt x⋆ ∈ G sei

JA(x⋆) := JG ∪ {i ∈ JU : ci(x

⋆) = 0}.

die Menge der aktiven Nebenbedingungen. Sind die zu dieser Menge gehörigenGradienten

{∇ci(x⋆) : i ∈ JA(x⋆)}

linear unabhängig, so sagen wir, der Punkt x⋆ erfüllt die LICQ-Bedingung.


Bemerkung LICQ steht abkürzend für linear independence constraint qualification. △

Lemma 7.6 Sei x⋆ ein lokales Minimum des Minimierungsproblems (7.1). Ist d ∈ Rn

eine Grenzrichtung einer zulässigen Folge, so gilt

∇ci(x⋆)Td = 0 für alle i ∈ JG,

∇ci(x⋆)Td ≥ 0 für alle i ∈ JU ∩ JA.

Gelten umgekehrt für eine Richtung d ∈ Rn mit ‖d‖2 = 1 diese beiden Bedingungen undist zusätzlich die LICQ-Bedingung für x⋆ erfüllt, dann ist d eine Grenzrichtung zu x⋆.

Beweis. (i.) Es sei {xk}k∈N eine zulässige Folge, für die d eine Grenzrichtung ist. Wirerhalten, gegebenfalls durch Übergang zu einer Teilfolge,

limk→∞

xk − x⋆

‖xk − x⋆‖2= d.

Daraus folgtxk = x⋆ + ‖xk − x⋆‖2d+ O(‖xkℓ − x⋆‖2).

Ist i ∈ JG, so haben wir für alle k ≥ K

0 =ci(xk)

‖xk − x⋆‖2=ci(x

⋆) + ‖xk − x⋆‖2∇ci(x⋆)Td+ O(‖xk − x⋆‖2)‖xk − x⋆‖2

= ∇ci(x⋆)Td+O(‖xk − x⋆‖2)‖xk − x⋆‖2

.

Durch den Grenzübergang k → ∞ schließen wir in diesem Fall ∇ci(x⋆)Td = 0.

Ist i ∈ JU ∪ JA(x⋆), dann erhalten wir für alle k ≥ K

0 ≤ ci(xk)

‖xk − x⋆‖2=

O(‖xk − x⋆‖2)‖xk − x⋆‖2

und analog zum obigen Vorgehen ∇ci(x⋆)Td ≥ 0. Damit ist die erste Aussage des Satzesgezeigt.

(ii.) Wir setzen A := [∇ci(x⋆)T ]i∈JA(x⋆) und beachten, dass diese Matrix aufgrund derLICQ-Bedingung vollen Rang m := |JA(x

⋆)| ≤ n besitzt. Ohne Beschränkung der Allge-meinheit können wir annehmen, dass alle Nebenbedingungen aktiv sind, also JG ∪ JU =JA(x

⋆) ist. Zur Matrix A ∈ Rm×n können wir eine Matrix B ∈ Rn×(n−m) mit vollem Randn−m finden, so dass AB = 0 gilt. Dabei bilden die Spalten von B eine Basis des Kernsvon A.

Für t > 0 und d ∈ Rn mit ‖d‖2 = 1 definieren wir die Abbildung φ : Rn ×R → Rn durch

φ(x, t) =

[c(x)− tAd

BT (x− x⋆ − td)

]mit c(x) = [ci(x)]i∈JA(x⋆)


und betrachten die Lösung des Gleichungssystems φ(x, t) = 0. Für t = 0 ist x = x⋆ dieLösung dieses Gleichungssystems und die Jakobi-Matrix

∇xφ(x⋆, 0) =

[∇c(x⋆)T

BT

]=

[A

BT

]∈ Rn×n

ist nichtsingulär. Nach dem Satz über implizite Funktionen besitzt dieses Gleichungssys-tem also für hinreichend kleines t > 0 eine eindeutige Lösung x = x(t).

Sei {tk}k∈N ⊂ (0, 1] eine Folge mit tk → 0 und für k ≥ K sei xk die eindeutige Lsoungvon φ(x, tk) = 0. Wir zeigen, dass {xk}k∈N eine zulässige Folge mit Grenzrichtung d ist.Zunächst folgern wir xk ∈ G für alle k ∈ N aus

i ∈ JG ⇒ ci(xk) = tk∇ci(x⋆)Td = 0,

i ∈ JU ∩ JA ⇒ ci(xk) = tk∇ci(x⋆)Td ≥ 0.

Aufgrund des Satzes über implizite Funktionen hängt die Lösung xk des Gleichungssys-tems φ(x, t) = 0 stetig von tk ab. Dies impliziert

limk→∞

xk = x⋆.

Als nächstes zeigen wir, dass xk 6= x⋆ gilt. Angenommen, es ist xk = x⋆ für ein k ∈ N,dann würde gelten

φ(x⋆, tk) =

[c(x⋆)− tkAd

BT (x⋆ − x⋆ − tkd)

]= 0.

Da alle Nebenbedingungen als aktiv angenommen wurden, gilt c(x⋆) = 0 und es folgt[A

BT

]d = 0.

Daraus ergibt sich d = 0 im Widerspruch zu ‖d‖2 = 1. Folglich ist {xk}k∈N eine zulässigeFolge.

Wir müssen noch nachweisen, dass d eine Grenzrichtung ist.

0 = φ(xk, tk)

=

[c(xk)− tkAd

BT (xk − x⋆ − tkd)

]

=

[c(x⋆) +A(xk − x⋆) + O(‖xk − x⋆‖2)− tkAd

BT (xk − x⋆ − tkd)

]

=

[A

BT

](xk − x⋆ − tkd) + O(‖xk − x⋆‖2).

Durch die spezielle Wahl von

dk :=xk − x⋆

‖xk − x⋆‖2erhalten wir hieraus

limk→∞

{dk −

tkd

‖xk − x⋆‖2

}= 0.

Wegen ‖dk‖2 = 1 für alle k ∈ N und ‖d‖2 = 1 folgt

limk→∞

tk‖xk − x⋆‖2

= 1

und damit limk→∞ dk = d. Dies beweist die zweite Aussage des Satzes.


Definition 7.7 Zu einem Punkt x⋆ ∈ G und aktiven Nebenbedingungen JA(x⋆) bezeich-

nen wir

K(x⋆) := {d ∈ Rn : ∇ci(x⋆)Td = 0 für i ∈ JG und

∇ci(x⋆)Td ≥ 0 für i ∈ JU ∩ JA(x⋆)}

als Linearisierungskegel an x⋆.

Lemma 7.8 Genau dann gibt es keine Richtung d ∈ K(x⋆) mit ∇f(x⋆)Td < 0, wennein Vektor λ = [λi]i∈JA(x⋆) existiert mit

∇f(x⋆) =∑

i∈JA(x⋆)

λi∇ci(x⋆) = ATλ

und λi ≥ 0 für i ∈ JU ∩ JA(x⋆).

Beweis. (i.) Wir betrachten den Kegel

K :=

{y ∈ Rn : y =

∑

i∈JA(x⋆)

λi∇ci(x⋆), λi ≥ 0 für i ∈ JU ∩ JA(x⋆)

}.

Da K offensichtlich abgeschlossen ist, lautet die Aussage des Lemmas also:

∇f(x⋆)Td ≥ 0 für alle Richtungen d ∈ K(x⋆) ⇐⇒ ∇f(x⋆) ∈ K.

(ii.) Seien ∇f(x⋆) ∈ K und d ∈ K(x⋆), dann gilt

∇f(x⋆)Td =∑

i∈JA(x⋆)

λi∇ci(x⋆)Td

=∑

i∈JG

λi∇ci(x⋆)Td+∑

i∈JU∩JA(x⋆)

λi∇ci(x⋆)Td

≥ 0

wegen λi ≥ 0 und ∇ci(x⋆)Td ≥ 0 für alle i ∈ JU ∩ JA(x⋆).

(iii.) Angenommen, es gilt ∇f(x⋆) 6∈ K, dann sei y ∈ K der Punkt mit minimalenAbstand zu ∇f(x⋆), das heißt, die Lösung des Minimierungsproblems

miny∈Rn

‖y−∇f(x⋆)‖2 unter der Nebenbedingung y ∈ K.

Da K ein Kegel ist, liegt mit y auch ty für alle t ≥ 0 in K. Insbesondere muss y alsoerfüllen:

0 =d

dt‖ty −∇f(x⋆)‖22

∣∣∣∣t=1

= 2t‖y‖22 − 2yT∇f(x⋆)∣∣t=1

= 2yT(y −∇f(x⋆)

).


Für beliebiges y ∈ K folgt aus der Konvexität von K, dass

‖y + θ(y − y)−∇f(x⋆)‖22 ≥ ‖y −∇f(x⋆)‖22 für alle θ ∈ (0, 1).

Deshalb ist2θ(y − y)T

(y −∇f(x⋆)

)+ θ2‖y − y‖22 ≥ 0,

was für θ → 0 auf

0 ≤ (y− y)T(y −∇f(x⋆)

)= yT

(y −∇f(x⋆)

)(7.4)

führt.

Wir zeigen nun, dass d := y−∇f(x⋆) 6= 0 die Bedingungen d ∈ K(x⋆) und ∇f(x⋆)Td < 0erfüllt. Zweiteres folgt sofort aus

dT∇f(x⋆) = dT (y − d) =(y −∇f(x⋆)

)Ty − dTd = −‖d‖22 < 0.

Ersteres sieht man hingegen wie folgt ein. Durch geeignete Wahl von λi, i ∈ JA(x⋆),

erreicht man

i ∈ JG =⇒ ∇ci(x⋆) ∈ K und −∇ci(x⋆) ∈ K,

i ∈ JU ∩ JA(x⋆) =⇒ ∇ci(x⋆) ∈ K.

Setzen wir in (7.4) die spezielle Wahl y = ±∇ci(x⋆) falls i ∈ JG und y = ∇ci(x⋆) fallsi ∈ JU ∩ JA(x

⋆) ein, so erhalten wir

i ∈ JG =⇒ ±∇ci(x⋆)Td ≥ 0 also ∇ci(x⋆)Td = 0,

i ∈ JU ∩ JA(x⋆) =⇒ ∇ci(x⋆)Td ≥ 0.

Daraus folgt d ∈ K(x⋆).

Definition 7.9 Die zum Minmierungsproblem mit Nebenbedingungen (7.1) gehörigeLagrange-Funktion lautet

L(x,λ) := f(x)−∑

i∈JG∪JU

λici(x).

Die Parameter λ = [λi]i∈JG∪JGwerden Lagrange-Parameter genannt.

Mit Hilfe der Lagrange-Funktion kann man nur ein Minimium von (7.1) charakterisieren.

Satz 7.10 (Karush, Kuhn und Tucker) Es sei x⋆ ∈ G eine lokales Minimum des Minimie-rungsproblems mit Nebenbedingungen (7.1) und x⋆ erfülle die LICQ-Bedingung. Danngibt es genau einen Vektor von Lagrange-Parametern λ⋆, so dass die folgenden KKT-

Bedingungen erfüllt sind:

∇xL(x⋆,λ⋆) = 0,

ci(x⋆) = 0 für alle i ∈ JG,

ci(x⋆) ≥ 0 für alle i ∈ JU ,

λ⋆i ≥ 0 für alle i ∈ JU ,

λ⋆i ci(x⋆) = 0 für alle i ∈ JG ∪ JU .


Beweis. (i.) Angenommen, x⋆ ∈ G ist ein lokales Minimum von (7.1), an dem die LICQ-Bedingung erfüllt ist. Dann gilt nach Satz 7.3 ∇f(x⋆)Td ≥ 0 für alle dazugehörigenGrenzrichtungen d. Nach Lemma 7.6 sind alle Richtungen, für die die Bedingungen

∇ci(x⋆)Td = 0 für alle i ∈ JG,

∇ci(x⋆)Td ≥ 0 für alle i ∈ JU ∩ JA(x⋆).

efüllt sind, auch Grenzrichtungen und erfüllen somit ∇f(x⋆)Td ≥ 0. Mit anderen Worten,für alle d ∈ K(x⋆) gilt ∇f(x⋆)Td ≥ 0. Dies impliziert nach Lemma 7.8 die Existenz vonλi ∈ R, so dass

∇f(x⋆) =∑

i∈JA(x⋆)

λi∇ci(x⋆) mit λi ≥ 0 für i ∈ JU ∩ JA(x⋆).

Hierin sind die Lagrange-Parameter λi aufgrund der LICQ-Bedingung eindeutig be-stimmt.

(ii.) Wir definieren

λ⋆i :=

{λi, i ∈ JA(x

⋆)

0, sonst

und weisen nach, dass damit die KKT-Bedingungen erfüllt sind. Es gilt nach (i.)

∇xL(x⋆,λ⋆) = ∇f(x⋆)−

∑

i∈JG∪JU

λi∇ci(x⋆)

= ∇f(x⋆)−∑

i∈JA(x⋆)

λi∇ci(x⋆)

= 0.

Die Bedingungen ci(x⋆) = 0 für alle i ∈ JG und ci(x

⋆) ≥ 0 für alle i ∈ JU folgen ausx⋆ ∈ G. Weiter gilt λ⋆i = 0 für i ∈ JU \JA(x

⋆) und λ⋆i ≥ 0 für i ∈ JU ∩JA(x⋆), das heißt,

es ist λ⋆i ≥ 0 für i ∈ JU . Schließlich gilt λ⋆i = 0 für i ∈ JU \ JA(x⋆), sowie ci(x⋆) = 0 für

alle i ∈ JA(x⋆), und somit λ⋆i ci(x

⋆) = 0 für alle i ∈ JG ∪ JU . Weil ci(x⋆) > 0 ist für allei ∈ JU \ JA, folgt die Eindeutigkeit der λ⋆i aus der letzten KKT-Bedingung.

7.2 Optimalitätsbedingungen zweiter Ordnung

Wir wenden uns nun Bedingungen zweiter Ordnung zu, wobei wir voraussetzen, dass fund ci für alle i ∈ JG ∪ JU zweimal stetig differenzierbar seien.

Definition 7.11 Zu gegebenen Lagrange-Parametern λ⋆ sei

K(x⋆,λ⋆) = {d ∈ K(x⋆) : ∇ci(x⋆)Td = 0 für alle i ∈ JU ∩ IA(x⋆) mit λ⋆i > 0}.

7.2. Optimalitätsbedingungen zweiter Ordnung 63

Bemerkung Wegen K(x⋆,λ⋆) ⊂ K(x⋆) gilt offensichtlich

d ∈ K(x⋆,λ⋆) ⇐⇒

∇ci(x⋆)Td = 0, i ∈ JG,

∇ci(x⋆)Td = 0, i ∈ JU ∩ JA(x⋆) mit λ⋆i > 0,

∇ci(x⋆)Td ≥ 0, i ∈ JU ∩ JA(x⋆) mit λ⋆i = 0.

Deshalb folgt aus der ersten KKT-Bedingung aus Satz 7.10 die Aussage

d ∈ K(x⋆,λ⋆) =⇒ ∇f(x⋆)Td =∑

i∈JG∪JU

λ⋆i∇ci(x⋆)Td = 0.

△

Satz 7.12 (hinreichende Bedingung 2. Ordnung) Für einen zulässigen Punkt x⋆ ∈ G gebees einen Vektor von Lagrange-Parametern λ⋆, so dass die KKT-Bedingungen erfüllt sind.Weiter sei

dT∇2xL(x

⋆,λ⋆)d > 0 für alle d ∈ K(x⋆,λ⋆) \ {0}.Dann ist x⋆ Lösung des Minimierungsproblems mit Nebenbedingungen (7.1).

Beweis. Der Satz ist bewiesen, wenn wir zeigen können, dass zu jeder zulässigen Folge{xk} ein M ∈ N existiert, so dass f(xk) > f(x⋆) für alle k ≥M ist.

Zu einer beliebigen zulässigen Folge {xk} sei d eine beliebige Grenzrichtung. Nach Lem-ma 7.6 gilt d ∈ K(x⋆). Nach der Definition der Grenzrichtung gibt es eine Teilfolge {xkℓ},welche

xkℓ − x⋆ = ‖xkℓ − x⋆‖2d+ O(‖xkℓ − x⋆‖2) (7.5)

erfüllt. Wegen den KKT-Bedingungen gilt für die Lagrange-Funktion

L(xkℓ ,λ⋆) = f(xkℓ)−

∑

i∈JA(x⋆)

λ⋆i ci(xkℓ) ≤ f(xkℓ).

Taylor-Entwicklung ergibt

L(xkℓ ,λ⋆) = L(x⋆,λ⋆)︸︷︷︸

=f(x⋆)

+∇xL(x⋆,λ⋆)︸︷︷︸

=0

T (xkℓ − x⋆)

+1

2(xkℓ − x⋆)T∇2

xL(x⋆,λ⋆)(xkℓ − x⋆) + O(‖xkℓ − x⋆‖22)

= f(x⋆) +1

2(xkℓ − x⋆)T∇2

xL(x⋆,λ⋆)(xkℓ − x⋆) + O(‖xkℓ − x⋆‖22),

wobei wieder die KKT-Bedingungen verwendet wurden.

Wir unterscheiden nun zwei Fälle: d 6∈ K(x⋆,λ⋆) und d ∈ K(x⋆,λ⋆).

Für d 6∈ K(x⋆,λ⋆) gibt es ein i⋆ ∈ JU ∩ IA(x⋆), für welches

λ⋆i⋆∇ci⋆(x⋆)Td > 0

gilt. Eine Taylor-Entwicklung führt auf

λ⋆i⋆ci⋆(xkℓ) = λ⋆i⋆ci⋆(x⋆)︸︷︷︸

=0

+λ⋆i⋆∇ci⋆(x⋆)T (xkℓ − x⋆) + O(‖xkℓ − x⋆‖2)

(7.5)= λ⋆i⋆‖xkℓ − x⋆‖2∇ci⋆(x⋆)Td+ O(‖xkℓ − x⋆‖2).


Für die Lagrange-Funktion gilt somit

L(xkℓ ,λ⋆) = f(xkℓ)−

∑

i∈JA(x⋆)

λ⋆i ci(xkℓ)

≤ f(xkℓ)− λ⋆i⋆ci⋆(xkℓ)

= f(xkℓ)− λ⋆i⋆‖xkℓ − x⋆‖2∇ci⋆(x⋆)Td+ O(‖xkℓ − x⋆‖2).

Andererseits wurde oben gezeigt, dass

L(xkℓ ,λ⋆) = f(x⋆) + O(‖xkℓ − x⋆‖2).

Daraus ergibt sich nun

f(xkℓ) ≥ f(x⋆) + λ⋆i⋆‖xkℓ − x⋆‖2∇ci⋆(x⋆)Td+ O(‖xkℓ − x⋆‖2)

und wegen λi⋆∇ci⋆(x⋆)Td > 0 impliziert dies f(xkℓ) > f(x⋆), falls nur kℓ genügend großist.

Für d ∈ K(x⋆,λ⋆) erhalten wir direkt

f(xkℓ) ≥ L(xkℓ ,λ⋆)

= f(x⋆) +1

2(xkℓ − x⋆)T∇2

xL(x⋆,λ⋆)(xkℓ − x⋆) + O(‖xkℓ − x⋆‖22)

(7.5)= f(x⋆) +

1

2‖xkℓ − x⋆‖22dT∇2

xL(x⋆,λ⋆)d+ O(‖xkℓ − x⋆‖22),

woraus sich wegen dT∇2xL(x

⋆,λ⋆)d > 0 wiederum f(xkℓ) > f(x⋆) für genügend große kℓergibt.

Bemerkung Die notwendige Bedingung zweiter Ordnung für ein Minimum von (7.1)lautet: Ist x⋆ ∈ G ein Minimum von (7.1), an dem die LICQ-Bedingung erfüllt ist, undgenügen die zugehörigen Lagrange-Parameter λ⋆ den KKT-Bedingungen, dann gilt

dT∇2xL(x

⋆,λ⋆)d ≥ 0 für alle d ∈ K(x⋆,λ⋆).

△

65

8. Projiziertes Gradientenverfahren

8.1 Konvergenzeigenschaften

Ziel dieses Kapitels ist es, das Gradientenverfahren aus Kapitel 2 auf das Minimierungs-problem mit Nebenbedingungen (7.1) zu verallgmeinern. Dazu sei neben der stetigenDifferenzierbarkeit der Funktion f : Rn → R vorausgesetzt, dass die zulässige MengeG ⊂ Rn konvex ist.

Grundlage des projizierten Gradientenverfahren ist die orthogonale Projektion:

Definition 8.1 Es sei G ⊂ Rn eine abgeschlossene, konvexe Menge. Dann ist die ortho-

gonale Projektion PG : Rn → G definiert durch die Bedingung

‖PG(x)− x‖2 = miny∈G

‖y − x‖2.

Der Punkt PG(x) ∈ G besitzt also die Eigenschaft, den kürzesten Abstand zu einemgegebenen Punkt x ∈ Rn zu besitzen.

Die Berechnung des projizierten Punktes PG(x) lässt sich für viele spezielle Nebenbedin-gungen relativ einfach umsetzen. Beispielsweise gilt dies für affine Nebenbedingungen, diespäter genauer behandelt werden.

Die Grundversion des projizierten Gradientenverfahren ist im folgenden Algorithmus be-schrieben:

Algorithmus 8.2 (projiziertes Gradientenverfahren)input: Funktion f : Rn → R, konvexe zulässige Menge G ⊂ Rn und

Startnäherung x0 ∈ Goutput: Folge von Iterierten {xk}k∈N

➀ Initialisierung: wähle σ ∈ (0, 1) und setze k := 0

➁ berechne den Antigradienten dk := −∇f(xk) und setze αk := 1

➂ solangef(PG(xk + αkdk)

)> f(xk)− σdT

k

(PG(xk + αkdk)− xk

)(8.1)

setze αk := αk/2

➃ setze xk+1 := PG(xk + αkdk)


66 Kapitel 8. Projiziertes Gradientenverfahren

Für den Fall der Minimierung ohne Nebenbedingungen, das heißt G = Rn, stellt obi-ger Algorithmus genau das bekannte Gradientverfahren 2.4 dar. Insbesondere geht dieBedingung an die Reduktion des Funktionals über in die Armijo-Goldstein-Bedingung

f(xk+1) ≤ f(xk)− σαk‖∇f(xk)‖22.

Ähnlich wie früher kann man zeigen, dass auch für das projizierte Gradientenverfahrenein αk > 0 existiert, für das die Reduktionsbedingung erfüllt ist.

Lemma 8.3 Ist die zulässige Menge G ⊂ Rn konvex, so erfüllt die orthogonale ProjektionPG die folgenden Eigenschaften:

(i.) Es gilt(PG(x)− x

)T (PG(x)− y

)≤ 0 für alle x ∈ Rn, y ∈ G.

(ii.) Es gilt(PG(y)−PG(x)

)T(y − x) ≥ ‖PG(y)−PG(x)‖22 ≥ 0 für alle x,y ∈ Rn, das

heißt, PG ist monoton.

(iii.) Es gilt ‖PG(y) − PG(x)‖2 ≤ ‖y − x‖2 für alle x,y ∈ Rn, das heißt, PG ist nichtexpandierend.

Beweis. (i.) Wegen der Konvexität folgt aus y ∈ G auch y := (1− t)PG(x) + ty ∈ G füralle t ∈ [0, 1]. Aus

‖y − x‖22 = ‖y −PG(x) +PG(x)− x‖22= ‖y −PG(x)‖22 + ‖PG(x)− x‖22 − 2

(PG(x)− x

)T (PG(x)− y

)

folgt aufgrund der Minimierungseigenschaft von PG, dass

‖y −PG(x)‖22 − 2(PG(x)− x

)T (PG(x)− y

)= ‖y− x‖22 − ‖PG(x)− x‖22 ≥ 0.

Einsetzen von PG(x)− y = t(PG(x)− y

)führt auf

t2‖y −PG(x)‖22 − 2t(PG(x)− x

)T (PG(x)− y

)≥ 0,

was für t→ 0 die gewünschte Aussage liefert.

(ii.) Die bereits bewiesene Aussage (i.) impliziert(PG(x)− x

)T (PG(x)−PG(y)

)≤ 0,

(PG(y)− y

)T (PG(y)−PG(x)

)≤ 0.

Zusammen führt dies auf(PG(y)− y + x−PG(x)

)T (PG(y)−PG(x)

)≤ 0,

das ist Aussage (ii.).

(iii.) Diese Aussage folgt sofort aus Aussage (ii.) durch Anwenden der Cauchy-Schwarz-schen Ungleichung.

Bemerkung Aus der Monotonieeigenschaft (ii.) folgt wegen xk = PG(xk) für die neueIterierte xk+1 = PG

(xk − αk∇f(xk)

)des projizierten Gradientenverfahrens, dass

‖xk+1 − xk‖22 ≤ (xk+1 − xk)T (xk − αk∇f(xk)− xk

).

8.1. Konvergenzeigenschaften 67

Wir erhalten daher

−∇f(xk)T (xk+1 − xk) ≥

1

αk‖xk+1 − xk‖22. (8.2)

Dies bedeutet, dass durch die Abstiegsbedingung (8.1) des Algorithmus 8.2 tatsächlichf(xk+1) < f(xk) erreicht wird. △

Lemma 8.4 Ist die zulässige Menge G ⊂ Rn konvex, so ist für beliebige x ∈ Rn undd ∈ Rn die Funktion

ϕ(α) :=‖PG(x + αd)− x‖2

α

für alle α > 0 monoton fallend.

Beweis. (i.) Für 0 < α < β setzen wir

u := PG(x + αd)− x, v := PG(x + βd)− x

und erhalten unter Verwendung von Lemma 8.3 (i.)

uT (u− v) = {PG(x+ αd)− (x+ αd) + αd}T{PG(x+ αd)−PG(x+ βd)}≤ αdT{PG(x+ αd)−PG(x + βd)}

und analogvT (v − u) ≤ βdT{PG(x + βd)−PG(x+ αd)}.

Zusammen ergibt diesuT (u− v)

α≤ vT (u− v)

β. (8.3)

(ii.) Weiter erhalten wir mit Lemma 8.3 (ii.)

uT (u− v) ≤ αdT{PG(x+ αd)−PG(x+ βd)}= − α

β − α(βd− αd)T{PG(x + βd)−PG(x+ αd)}

≤ − α

β − α‖PG(x+ βd)−PG(x+ αd)‖22

≤ 0.

Aus der Cauchy-Schwarzschen Ungleichung ergibt sich

uTv(‖u‖2 + ‖v‖2) ≤ ‖u‖2‖v‖2(‖u‖2 + ‖v‖2),

woraus

‖u‖2vT (u− v) = ‖u‖2(uTv − ‖v‖22) ≤ ‖v‖2(‖u‖22 − uTv) = ‖v‖2uT (u− v) (8.4)

folgt.

(iii.) Wir unterscheiden nun zwei Fälle: Für uT (u−v) = 0 gilt PG(x+αd) = PG(x+βd)und somit u = v. Hieraus folgt unmittelbar auch

ϕ(α) =‖u‖2α

≥ ‖v‖2β

= ϕ(β).


Für den Fall uT (u− v) < 0 folgt aus (8.3)

β

α≥ vT (u− v)

uT (u− v)

und aus (8.4)

‖v‖2 ≤ ‖u‖2vT (u− v)

uT (u− v).

Kombiniert man diese zwei Ungleichungen, so erhält man wieder

ϕ(α) =‖u‖2α

≥ ‖v‖2β

= ϕ(β).

Satz 8.5 Die zulässige Menge G ⊂ Rn sei konvex und die Funktion f : Rn → R seiauf G stetig differenzierbar und nach unten beschränkt. Weiter sei ∇f auf G gleichmäßigstetig. Dann gilt für die Iterierten {xk}k∈N des projizierten Gradientenverfahrens

limk→∞

‖xkℓ+1 − xk‖2αk

= 0.

Beweis. Wir führen einen Widerspruchsbeweis. Angenommen, es existiert zu jedem ε > 0eine unendliche Teilfolge {kℓ}ℓ∈N, so dass

‖xkℓ+1 − xkℓ‖2αkℓ

≥ ε.

Dann gilt insbesondere auch


≥ εmax{εαkℓ, ‖xkℓ+1 − xkℓ‖2}. (8.5)

Da die Folge {f(xkℓ)}ℓ∈N monoton fallend und nach unten beschränkt ist, folgt aus derAbstiegsbedingung (8.1) des projizierten Gradientenverfahrens

limℓ→∞

∇f(xkℓ)T (xkℓ+1 − xkℓ) = 0,

was wiederum gemäß (8.2)

limℓ→∞


= 0.

nach sich zieht. Aufgrund von (8.5) erhalten wir hieraus

limk→∞

αkℓ = 0 und limk→∞

‖xkℓ+1 − xkℓ‖2 = 0.

Für ykℓ+1 := PG(xkℓ + 2αkℓdkℓ) gilt aufgrund der algorithmischen Umsetzung des proji-zierten Gradientenverfahrens

f(ykℓ+1) > f(xkℓ) + σ∇f(xkℓ)T (ykℓ+1 − xkℓ),


also auchf(xkℓ)− f(ykℓ+1) < σ∇f(xkℓ)

T (xkℓ − ykℓ+1). (8.6)

Aus Lemma 8.4 folgt


≥ ‖xkℓ+1 − xkℓ‖2‖ykℓ+1 − xkℓ‖2

2αkℓ

≥ αkℓε‖ykℓ+1 − xkℓ‖2

2αkℓ

=ε

2‖ykℓ+1 − xkℓ‖2.

Weiter ergibt sich mit Lemma 8.3 (ii.)

(xkℓ+1 − xkℓ)T{xkℓ − αkℓ∇f(xkℓ)− xkℓ︸︷︷︸

=−αkℓ∇f(xkℓ

)

}≥ ‖xkℓ+1 − xkℓ‖22,

(ykℓ+1 − xkℓ+1)T{xkℓ − 2αkℓ∇f(xkℓ)−

(xkℓ − αkℓ∇f(xkℓ)

)︸︷︷︸

=−αkℓ∇f(xkℓ

)

}≥ 0.

Zusammen führt dies auf

(xkℓ − ykℓ+1)T∇f(xkℓ) ≥ (xkℓ − xkℓ+1)

T∇f(xkℓ)

≥ ‖xkℓ+1 − xkℓ‖22αkℓ

≥ ε

2‖ykℓ+1 − xkℓ‖2,

woraus sich speziell auch ‖ykℓ+1−xkℓ‖2 → 0 für ℓ→ ∞ ergibt. Die gleichmäßige Stetigkeitvon ∇f impliziert nun

∣∣∣∣1−f(xkℓ)− f(ykℓ+1)

(xkℓ − ykℓ+1)T∇f(xkℓ)

∣∣∣∣ =O(‖ykℓ+1 − xkℓ‖2)

(xkℓ − ykℓ+1)T∇f(xkℓ)

≤ 2

ε

O(‖ykℓ+1 − xkℓ‖2)‖xkℓ − ykℓ+1‖2

ℓ→∞−→ 0.

Dies steht jedoch im Widerspruch zu der aus (8.6) folgenden Abschätzung

f(xkℓ)− f(ykℓ+1)

(xkℓ − ykℓ+1)T∇f(xkℓ)< σ < 1.

Bemerkung Da αk ≤ 1 ist, folgt aus Satz 8.5 speziell ‖xk+1−xk‖2 → 0 für k → ∞, dasheißt, die Iterierten aus Algorithmus 8.2 konvergieren gegen einen Punkt x⋆ ∈ G. △

Definition 8.6 Die zulässige Menge G ⊂ Rn sei konvex. Für jeden Punkt x ∈ G ist derTangentialkegel TG(x) definiert als kleinster abgeschlossener Kegel, der die Menge

{d = y − x : y ∈ G}

enthält.


Bemerkung Der Tangentialkegel TG(x⋆) ist die Menge aller Grenzrichtungen zulässigerFolgen für das Minimierungsproblem (7.1), skaliert mit einem beliebigen positiven Faktor.Wir erinnern an den Begriff des Linearisierungskegels K(x⋆) aus dem vorigen Kapitel. Erbesteht aus allen Richtungen d ∈ Rn mit dT∇ci(x⋆) = 0 für i ∈ JG und dT∇ci(x⋆) ≥ 0für i ∈ JU ∩ JA(x

⋆). Nach Lemma 7.6 gilt TG(x⋆) ⊂ K(x⋆) und für den Fall, dass dieLICQ-Bedingung erfüllt ist, sogar TG(x⋆) = K(x⋆). △

Lemma 8.7 Die zulässige Menge G ⊂ Rn sei konvex. Für jeden Punkt x ∈ G erfülltdie orthogonale Projektion PTG(x)

(−∇f(x)

)der Richtung des steilsten Abstiegs auf den

Tangentialkegel TG(x) die folgenden Eigenschaften:

(i.) Es gilt∇f(x)TPTG(x)

(−∇f(x)

)= −

∥∥PTG(x)

(−∇f(x)

)∥∥2

2.

(ii.) Es ist

min{∇f(x)Td : d ∈ TG(x),∥∥d‖2 ≤ 1} = −‖PTG(x)

(−∇f(x)

)∥∥2.

(iii.) Der Punkt x ist genau dann ein stationärer Punkt des Minimierungsproblems mitNebenbedingungen (7.1), wenn PTG(x)

(−∇f(x)

)= 0.

Beweis. (i.) Nach Definition der Orthogonalprojektion besitzt die Funktion

g(λ) :=1

2

∥∥λPTG(x)

(−∇f(x)

)+∇f(x)

∥∥2

2

ein Minimum bei λ = 1. Daher gilt

g′(1) :=∥∥PTG(x)

(−∇f(x)

)∥∥2

2+∇f(x)TPTG(x)

(−∇f(x)

)= 0.

(ii.) Wegen Aussage (i.) gilt

∥∥PTG(x)

(−∇f(x)

)+∇f(x)

∥∥2

2= ‖∇f(x)‖22 −

∥∥PTG(x)

(−∇f(x)

)∥∥2

2.

Für alle d ∈ TG(x) mit ‖d‖2 ≤∥∥PTG(x)

(−∇f(x)

)∥∥2

gilt nach Definition der orthogonalenProjektion

∥∥PTG(x)

(−∇f(x)

)+∇f(x)

∥∥2

2≤ ‖d+∇f(x)‖22≤

∥∥PTG(x)

(−∇f(x)

)∥∥2

2+ 2∇f(x)Td+ ‖∇f(x)‖22.

Zusammen ergibt dies

∇f(x)Td ≥ −∥∥PTG(x)

(−∇f(x)

)∥∥2

2.

Das Behauptete erhält man, indem man d = d/∥∥PTG(x)

(−∇f(x)

)∥∥2

setzt.

(iii.) Definitionsgemäß ist x ∈ G genau dann ein stationärer Punkt, wenn ∇f(x)Td ≥ 0ist für alle Grenzrichtungen zulässiger Folgen mit Grenzwert x. Dies ist gleichbedeutenddamit, dass ∇f(x)Td ≥ 0 für alle d ∈ TG(x) ist. Aussage (ii.) impliziert, dass dies genaudann der Fall ist, wenn PTG(x)

(−∇f(x)

)= 0 erfüllt ist.


Bemerkung Aussage (ii.) des obigen Lemmas kann auch als

min{∇f(x⋆)Td : d ∈ TG(x⋆),

∥∥d‖2 = 1} = −‖PTG(x⋆)

(−∇f(x⋆)

)∥∥2. (8.7)

geschrieben werden, da das Minimum für ‖d‖2 = 1 angenommen wird. △

Satz 8.8 Die zulässige Menge G ⊂ Rn sei konvex und die Funktion f : Rn → R seiauf G stetig differenzierbar und nach unten beschränkt. Weiter sei ∇f auf G gleichmäßigstetig. Dann gilt für die Iterierten {xk}k∈N des projizierten Gradientenverfahrens

limk→∞

PTG(xk)

(−∇f(xk)

)= 0.

Beweis. Zu beliebigen ε > 0 gibt es nach Lemma 8.7 (ii.) zu jeder Iterierten xk eindk ∈ TG(xk) mit ‖dk‖2 = 1, so dass

∇f(xk)Tdk ≤ −

∥∥PTG(xk)

(−∇f(xk)

)∥∥2+ ε (8.8)

gilt. Da dk Grenzrichtung einer zulässigen Folge ist, gibt es ein yk ∈ G mit∥∥∥∥

yk − xk

‖yk − xk‖2− dk

∥∥∥∥2

≤ ε.

Aus Lemma 8.3 (i.) folgt{xk+1 −

(xk − αk∇f(xk)

)}T(xk+1 − yk+1)

={PG

(xk − αk∇f(xk)

)−(xk − αk∇f(xk)

)}T{PG

(xk − αk∇f(xk)

)− yk+1

}

≤ 0,

was aufαk∇f(xk)

T (xk+1 − yk+1) ≤ ‖xk+1 − xk‖2‖xk+1 − yk+1‖2,beziehungsweise

−∇f(xk)T (yk+1 − xk+1)

‖xk+1 − yk+1‖2≤ ‖xk+1 − xk‖2

αk,

führt. Insgesamt erhalten wir deshalb

−∇f(xk)Tdk+1 ≤ ‖∇f(xk)‖2

∥∥∥∥yk+1 − xk+1

‖yk+1 − xk+1‖2− dk+1

∥∥∥∥2

− ∇f(xk)T (yk+1 − xk+1)

‖yk+1 − xk+1‖2≤ ε‖∇f(xk)‖2 +

‖xk+1 − xk‖2αk

.

Die Kombination mit (8.8) ergibt∥∥PTG(xk+1)

(−∇f(xk+1)

)∥∥2

≤ −∇f(xk+1)Tdk+1 + ε

≤ −∇f(xk)Tdk+1 + ‖∇f(xk+1)−∇f(xk)‖2 ‖dk+1‖2︸︷︷︸

=1

+ε

≤ ε‖∇f(xk)‖2 +‖xk+1 − xk‖2

αk+ ‖∇f(xk+1)−∇f(xk)‖2 + ε.


Weil ε > 0 beliebig war, folgt hieraus schließlich

limk→∞

∥∥PTG(xk+1)

(−∇f(xk+1)

)∥∥2≤ lim

k→∞

‖xk+1 − xk‖2αk

+ limk→∞

‖∇f(xk+1)−∇f(xk)‖2 = 0

wobei Satz 8.5 und die gleichmäßige Stetigkeit von ∇f zur Anwendung kommt.

In der Regel folgt aus der Stetigkeit von ∇f nicht, dass auch PTG(x)

(−∇f(x)

)stetig ist.

Um sicherzustellen, dass die Iterierten des projizierten Gradientenverfahrens tatsächlichgegen einen stationären Punkt konvergieren, benötigen wir daher das folgende Resultat.

Satz 8.9 Die zulässige Menge G ⊂ Rn sei konvex und die Funktion f : Rn → R sei aufG stetig differenzierbar. Dann folgt für jede Folge {xk}k∈N ⊂ G mit xk → x⋆ ∈ G

∥∥PTG(x⋆)

(−∇f(x⋆)

)∥∥2≤ lim inf

k→∞

∥∥PTG(xk)

(−∇f(xk)

)∥∥2.

Beweis. Aus Lemma 8.7 (ii.) folgt für jedes y ∈ G

−∇f(xk)T (y− xk) ≤

∥∥PTG(xk)

(−∇f(xk)

)∥∥2‖y− xk‖2,

woraus sich für k → ∞ die Ungleichung

−∇f(x⋆)T (y − x⋆) ≤∥∥PTG(xk)

(−∇f(xk)

)∥∥2‖y− x⋆‖2

ergibt. Jedes d ∈ TG(x⋆) mit ‖d‖2 = 1 ist Grenzrichtung einer zulässigen Folge {yk}k∈N ⊂

G, das heißt, es gilt

d = limk→∞

yk − x⋆

‖yk − x⋆‖2und lim

k→∞yk = x⋆.

Somit erhalten wir

−∇f(x⋆)Td ≤ lim infk→∞

∥∥PTG(xk)

(−∇f(xk)

)∥∥2

und daraus wegen (8.7) die Behauptung:∥∥PTG(x⋆)

(−∇f(x⋆)

)∥∥2= max{−∇f(x⋆)Td : d ∈ TG(x

⋆),∥∥d‖2 = 1}

≤ lim infk→∞

∥∥PTG(xk)

(−∇f(xk)

)∥∥2.

Bemerkung Die Kombination der Sätze 8.5, 8.8 und 8.9 liefert die folgende Aussage:Ist die zulässige Menge G ⊂ Rn konvex und ist die Funktion f : Rn → R auf G stetigdifferenzierbar mit gleichmäßig stetigem Gradienten und nach unten beschränkt, dannkonvergieren die Iterierten {xk}k∈N des projizierten Gradientenverfahrens 8.2 gegen einx⋆ ∈ G mit

PTG(x⋆)

(−∇f(x⋆)

)= 0.

Gemäß Lemma 8.7 (iii.) bedeutet dies, dass x⋆ ein stationärer Punkt ist. △

8.2. Affine Nebenbedingungen 73

8.2 Affine Nebenbedingungen

Bei Anwendungsproblemen treten häufig affine Ungleichungsnebenbedingungen auf, wes-halb wir diesen Spezialfall eingehender untersuchen wollen. Wir nehmen demnach an, dassdas Minimierungsproblem unter Nebenbedingungen von der speziellen Form

minx∈Rn

f(x) unter den Nebenbedingungen

aTi x ≤ bi für alle i = 1, 2, . . . , m

(8.9)

mit ai ∈ Rn und bi ∈ R für alle i = 1, 2, . . . , m ist. Dies ist also ein Spezialfall von (7.1),für den JG = ∅, JU = {1, 2, . . . , m} und ci(x) := bi − aT

i x gesetzt wird. Die Menge derzulässigen Punkte ist in diesem Fall gegeben durch

G = {x ∈ Rn : aTi x ≤ bi für alle i = 1, 2, . . . , m}.

Für x ∈ G betrachten wir die Menge der aktiven Indizes

JA(x) :={i ∈ {1, 2, . . . , m} : aT

i x = bi}.

Die LICQ-Bedingung bedeutet hier gerade die lineare Unabhängigkeit der Vektoren ai füri ∈ JA(x).

Wir wenden uns der Charakterisierung von stationären Punkten zu, die für den Spezialfallaffiner Nebenbedingungen besonders handlich ist.

Lemma 8.10 Für den Punkt x⋆ ∈ G sei die Menge {ai : i ∈ JA(x⋆)} linear unabhängig.

Dann ist x⋆ genau dann ein stationärer Punkt für das Minimierungsproblem unter affinenNebenbedingungen (8.9), wenn es für jedes i ∈ JA(x

⋆) eine eindeutige Zahl λ⋆i ≥ 0 gibt,so dass

∇f(x⋆) +∑

i∈JA(x⋆)

λ⋆iai = 0 (8.10)

gilt.

Beweis. Nach Lemma 8.7 (iii.) ist x⋆ ∈ G genau dann ein stationärer Punkt des Problems(8.9), wenn für die orthogonale Projektion auf den Tangentialkegel PTG(x⋆)

(−∇f(x⋆)

)= 0

gilt. Dies ist nach Lemma 8.7 (ii.) genau dann der Fall, wenn

−∇f(x⋆)Td ≤ 0 für alle d ∈ TG(x⋆).

gilt. Da die LICQ-Bedingung erfüllt ist, gilt nun nach Lemma 7.6

TG(x⋆) = K(x⋆) = {d ∈ Rn : dTai ≤ 0 für alle i ∈ JA(x

⋆)}.Schließlich ist nach Lemma 7.8 die Aussage

−∇f(x⋆)Td ≤ 0 für alle d ∈ K(x⋆)

äquivalent zur Existenz und Eindeutigkeit nichtnegativer Zahlen λ⋆i ∈ R, i ∈ JA(x⋆), mit

∇f(x⋆) = −∑

i∈JA(x⋆)

λ⋆iai.


Bemerkung Die Notwendigkeit der Bedingung (8.10) ergibt sich auch direkt aus denKKT-Bedingungen (vergleiche Satz 7.10). Lemma 8.10 sagt jedoch zusätzlich aus, dassdiese Bedingung bei Vorliegen affiner Nebenbedingungen auch hinreichend für das Vorlie-gen eines stationären Punktes ist. △

Definition 8.11 Ein stationärer Punkt heißt nicht entartet, wenn die Menge {ai : i ∈JA(x

⋆)} linear unabhängig ist und für die Lagrange-Parameter in (8.10) λ⋆i > 0 für allei ∈ JA(x

⋆) gilt.

Satz 8.12 Die Funktion f : Rn → R sei stetig differenzierbar auf der zulässigen Menge

G = {x ∈ Rn : aTi x ≤ bi für alle i = 1, 2, . . . , m}.

Die Folge {xk}k∈N ∈ G konvergiere gegen den nicht entarteten stationären Punkt x⋆ ∈ Gund es gelte

limk→∞

PTG(xk)

(−∇f(xk)

)= 0.

Dann gibt es ein L ∈ N mit JA(xk) = JA(x⋆) für alle k ≥ L, das heißt, die Menge der

aktiven Indizes ändert sich für genügend große k nicht mehr.

Beweis. Aus xk → x⋆ und xk ∈ G folgt JA(xk) = JA(x⋆) für genügend große k. Wir neh-

men nun das Gegenteil der Aussage des Satzes an, nämlich dass eine unendliche Teilfolge{xkℓ}ℓ∈N und ein Index p ∈ JA(x

⋆) existieren, so dass p 6∈ JA(xkℓ) für alle ℓ ∈ N. Wirverwenden den orthogonalen Projektor PH auf den Unterraum

H :={x ∈ Rn : aT

i x = 0 für alle i ∈ JA(x⋆) \ {p}

}.

Für i ∈ JA(x⋆) \ {p} gilt insbesondere aT

i PHai = 0, woraus PHai = 0 folgt.

Aufgrund der Eigenschaft der orthogonalen Projektion steht ap − PHap senkrecht aufdem Unterraum H , was wiederum bedeutet, dass ap − PHap im Raum span

{ai : i ∈

JA(x⋆) \ {p}

}enthalten ist. Angenommen, es würde PHap = 0 gelten, dann ließe sich ap

als Linearkombination der Vektoren ai, i ∈ JA(x⋆) \ {p}, schreiben. Die Menge {ai : i ∈

JA(x⋆)} ist aber linear unabhängig, da der stationäre Punkt x⋆ nicht entartet ist. Somit

muss PHap 6= 0 gelten.

Wegen PHap ∈ H , das heißt, aTi PHap = 0 für i ∈ JA(x

⋆) \ {p} ⊃ JA(xkℓ) schließen wirinsbesondere PHap ∈ TG(xkℓ) für alle ℓ ∈ N. Aus Lemma 8.7 (ii.) erhalten wir

∇f(xk)TPHap ≥ −

∥∥PTG(xk)

(−∇f(xk)

)∥∥2‖PHap‖2.

Für k → ∞ ergibt sich wegen xk → x⋆ damit

∇f(x⋆)TPHap ≥ 0. (8.11)

Andererseits gilt, da der stationäre Punkt x⋆ nicht entartet ist,

∇f(x⋆) +∑

i∈JA(x⋆)

λ⋆iai = 0

8.2. Affine Nebenbedingungen 75

mit λ⋆i > 0 für i ∈ JA(x⋆). Dies impliziert

∇f(x⋆)TPHap =(PH∇f(x⋆)

)Tap

= −( ∑

i∈JA(x⋆)

λ⋆iPHai

)T

ap

= −λ⋆p(PHap)Tap

= −λ⋆p‖PHap‖22< 0

im Widerspruch zur Abschätzung (8.11).

76 Kapitel 9. SQP-Verfahren

9. SQP-Verfahren

9.1 Quadratische Minimierungsprobleme mit affinen Ne-

benbedingungen

Das Prinzip des SQP-Verfahrens (kurz für sequential quadratic programs) ist die Rück-führung allgemeiner Minimierungsprobleme auf eine Folge von Minimierungsproblemenmit quadratischer Zielfunktion und affinen Nebenbedingungen.

Ersetzen wir das allgemeine Minimierungsproblem (7.1) durch eine quadratische Zielfunk-tion und affine Nebenbedingungen, so erhalten wir folgende Aufgabenstellung:

minx∈Rn

1

2xTHx+ gTx unter den Nebenbedingungen

aTi x = bi für alle i ∈ JG, (9.1)

aTi x ≤ bi für alle i ∈ JU .

Dabei wird die quadratische Zielfunktion durch die quadratische Matrix H ∈ Rn×n undden Vektor g ∈ Rn beschrieben. Eine eventuell hinzukommende additive Konstante hatkeine Konstante auf das Minimierungsproblem. Für i ∈ JG ∪JU sind weiter ai ∈ Rn undbi ∈ R vorgegeben, um die Nebenbedingungen festzulegen.

Um (9.1) zu lösen, wird zunächst iterativ die Menge der aktiven Indizes bestimmt. Hierzuwerden im nächsten Abschnitt geeignete Techniken vorgestellt. Als Teilaufgabe resultie-ren quadratische Minimierungsprobleme mit affinen Gleichungsnebenbedingungen. Wirbetrachten also zuerst im Detail die Lösung solcher Probleme:

minx∈Rn

1


aTi x = bi für alle i = 1, 2, . . . , m.

(9.2)

Um (9.2) zu lösen, stellen wir die KKT-Bedingungen auf. Die Lagrange-Funktion lautet

L(x,λ) :=1

2xTHx+ gTx−

m∑

i=1

λi(bi − aTi x).

Zur Abkürzung schreiben wir

A =[a1 a2 · · · am

]∈ Rn×m, b =

b1b2...bm

∈ Rm, λ =

λ1λ2...λm

∈ Rm

9.1. Quadratische Minimierungsprobleme mit affinen Nebenbedingungen 77

und erhalten

L(x,λ) :=1

2xTHx+ gTx− λT (b−ATx).

Als notwendige Bedingung ergibt sich gemäß Satz 7.10

∇xL(x,λ) = Hx+ g +Aλ = 0,

∇yL(x,λ) = ATx− b = 0.

Daher erfüllt die Lösung (x⋆,λ⋆) der notwendigen Bedingung erster Ordnung das Sattel-punktproblem [

H A

AT 0

] [x⋆

λ⋆

]=

[−g

b

]. (9.3)

Wir wenden uns nun der Frage zu, wann dieses lineare Gleichungssystem eindeutig lösbarist.

Wir stellen fest, dass A ∈ Rn×m vollen Rang besitzen muss. Wegen m < n ist jedochkern(AT ) 6= {0}. Sei p ∈ Rn ein solcher Vektor, für den ATp = 0 gilt. Dann ist fürbeliebiges q ∈ Rm

[pT qT

] [ H A

AT 0

] [p

q

]= pTHp+ qTATp+ pTAq

= pTHp+ qTATp︸︷︷︸=0

+(ATp︸︷︷︸=0

)Tq

= pTHp. (9.4)

Folglich müssen wir vermeiden, dass der Nullraum der Matrix H einen Vektor des Null-raums von der Matrix AT enthält, was die Voraussetzungen des nachfolgenden Satzesmotiviert.

Satz 9.1 Es sei H ∈ Rn×n und A ∈ Rn×m, wobei m < n. Besitzt A vollen Rangm und ist H auf dem Kern von AT positiv definit, das heißt, ist pTHp > 0 für allep ∈ kern(AT ) \ {0}, so ist die KKT-Matrix

K :=

[H A

AT 0

]

regulär und folglich (9.3) eindeutig lösbar.

Beweis. Sei p ∈ Rn und q ∈ Rm derart, dass

K

[p

q

]=

[H A

AT 0

] [p

q

]= 0

gilt. Aus der zweiten Zeile folgt ATp = 0 und daher ist

0 =[pT qT

] [ H A

AT 0

] [p

q

](9.4)= pTHp.

Dies kann aber nach Voraussetzung nur für p = 0 erfüllt sein. Wegen Hp+Aq = 0 folgtschließlich Aq = 0 und aufgrund des vollen Spaltenrangs von A ist auch q = 0. Folglichist K regulär und das Behauptete bewiesen.


Bemerkung Man kann sogar zeigen, dass die Matrix K genau n positive und m negativeEigenwerte besitzt. Die Lösung indefiniter Systeme kann mit geeigneten Erweiterungender Cholesky-Zerlegung oder aber bei sehr großen Systemen auch iterativ, etwa mit demMINRES-Verfahren oder dem Bramble-Pasciak-CG, geschehen. △Der nächste Satz besagt, dass die Lösung von (9.3) die Lösung von (9.2) liefert.

Satz 9.2 Es gelten die Voraussetzungen von Satz 9.1. Dann ist die Lösung x⋆ ∈ Rn von(9.3) die eindeutige Lösung von (9.2).

Beweis. Sei x 6= x⋆ derart, dass ATx = b und setze p := x⋆ − x. Dann ist ATp = 0 undp 6= 0. Für q(x) := 1

2xTHx+ gTx gilt dann offensichtlich mit x = x⋆ − p

q(x) =1

2pTHp− pTHx⋆ − gTp+ q(x⋆). (9.5)

Aus (9.3) folgt, dass −Hx⋆ = Aλ+ g, so dass

−pTHx⋆ = pT (Aλ+ g) = gTp

ist. Eingesetzt in (9.5) ergibt sich

q(x) =1

2pTHp+ q(x⋆) > q(x⋆),

dies bedeutet, x⋆ ist das eindeutige Minimum von (9.2).

9.2 Bestimmung aktiver Nebenbedingungen

Wir wenden uns nun der Lösung der Minimierungsaufgabe (9.1) zu, wobei wir annehmen,dass die Vektoren ai linear unabhängig sind. Indem wir wie bisher für jeden Punkt x ∈ Rn

die Menge der aktiven Indizes bezeichnen als

JA(x) = {i ∈ JG ∪ JU : aTi x = bi} = JG ∪ {i ∈ JU : aT

i x = bi},

können wir (9.1) umschreiben gemäß

minx∈Rn

1


aTi x = bi für alle i ∈ JA(x),

aTi x ≤ bi für alle i ∈ JU \ JA(x).

Für jede lokale Lösung x⋆ ∈ Rn des Minimierungsproblems (9.1) gelten somit nachSatz 7.10 die folgenden KKT-Bedingungen

Hx⋆ + g +∑

i∈JA(x⋆)

λ⋆iai = 0,

aTi x

⋆ = bi für i ∈ JA(x⋆),

aTi x

⋆ ≤ bi für i ∈ JU \ JA(x⋆),

λi ≥ 0 für i ∈ JU \ JA(x⋆).

9.2. Bestimmung aktiver Nebenbedingungen 79

Die Grundidee des folgenden Vorgehens ist die Beobachtung, dass bei Kenntnis der IndizesJA(x

⋆) der aktiven Nebenbendigungen am Lösungspunkt die Lösung von (9.1) gleichzeitigdie Lösung des quadratischen Minimierungsproblem unter Gleichungsnebenbedingungen

minx∈Rn

1


aTi x = bi für alle i ∈ JA(x

⋆)

ist. Die aktiven Indizes werden über ein iteratives Vorgehen gefunden, ausgehend von ei-nem Sattelpunkt x0, der zulässiger Punkt für das Problem (9.1) ist, und einer IndexmengeJ0 mit JG ⊂ J0 ⊂ JA(x0).

Ausgehend von einem zulässigem Punkt xk und einer aktuellen Indexmenge Jk mit JG ⊂Jk ⊂ JA(xk) besteht ein Schritt dieses iterativen Vorgehens aus den folgenden beidenHalbschritten:

1. Löse das quadratische Minimierungsproblem mit Gleichungsnebenbedingungen ander aktuellen Indexmenge:

mind∈Rn

1

2(xk + d)TH(xk + d) + gT (xk + d) unter den Nebenbedingungen

aTi (xk + d) = bi für alle i ∈ Jk.

(9.6)

2. Konstruiere aus dem aus dem ersten Halbschritt erhaltenen Punkt xk + dk einenPunkt xk+1, der in der zulässigen Menge

G = {x ∈ Rn : aTi x = bi für alle i ∈ JG und aT

i x ≤ bi für alle i ∈ JU}enthalten ist.

Die Lösung von (9.6) ist offenbar äquivalent zu

mind∈Rn

1

2dTHd+ (g +Hxk)

Td+1

2xTkHxk + gTxk unter den Nebenbedingungen

aTi d = bi − aT

i xk für alle i ∈ Jk.

Mit gk := g + Hxk und unter der Beachtung von aTi xk = bi sowie der Tatsache, dass

Konstanten in der zu minimierenden Funktion keine Rolle spielen, lässt sich dies auchumschreiben in

mind∈Rn

1

2dTHd+ gT

k d unter den Nebenbedingungen

aTi d = 0 für alle i ∈ Jk.

(9.7)

Dieses quadratische Minimierungsproblem unter Gleichungsnebenbedingungen hat dieForm (9.2) und kann entsprechend gelöst werden.

Bei der Durchführung des zweiten Halbschritts wird wie folgt vorgegangen. Erfüllt xk+dk

auch die Nebenbedingungen

aTi (xk + dk) ≤ bi für alle i ∈ JU \ Jk,

dann wird xk+1 := xk + dk gesetzt. Falls nicht alle Nebenbedingungen erfüllt sind, be-stimmen wir xk+1 := xk + αkdk mit αk ∈ [0, 1) größtmöglich, so dass noch alle Nebenbe-dingungen

aTi (xk + αkdk) ≤ bi für alle i ∈ JU \ Jk

erfüllt sind. Die Bestimmung von αk geschieht durch eine Fallunterscheidung:


1. Für alle i ∈ JU \ Jk mit aTi dk ≤ 0 gilt

aTi (xk + αkdk) ≤ aT

i xk ≤ bi

für alle αk ≥ 0. Somit verursachen diese Nebenbedingungen keine Einschränkungan αk.

2. Für alle i ∈ JU \ Jk mit aTi dk > 0 haben wir jedoch die Einschränkung

αk ≤bi − aT

i xk

aTi dk

.

Insgesamt erhalten wir daher

αk = min

{1, min

i 6∈Jk,aTi dk>0

bi − aTi xk

aTi dk

}.

Alle Nebenbedingungen, für die das Minimum angenommen wird, bezeichnen wir als blo-

ckierende Nebenbedingungen. Falls αk < 1, legen wir zu xk+1 := xk + αkdk eine neueIndexmenge Jk+1 fest, indem wir eine oder mehrere blockierende Nebenbedingungen hin-zufügen.

Diese Iteration wird solange durchgeführt, bis wir an einem Punkt x angelangt sind, derdas quadratische Minimierungsproblem mit Gleichungsnebenbedingungen an der aktuel-len Indexmenge J löst. Dies ist leicht daran zu erkennen, dass das zugehörige quadratischeMinimierungsproblem (9.7) die Lösung d = 0 besitzt.

Aufgrund der Minimierungseigenschaft gilt nach Satz 7.10 für das Problem (9.7) die ersteKKT-Bedingung

Hx+ g +∑

i∈J

λiai = 0

mit Lagrange-Parametern λi, über deren Vorzeichen aber keine Aussage möglich ist. Set-zen wir λi = 0 für i ∈ JU \ J , so haben wir auch die erste KKT-Bedingung für dasMinimierungsproblem (9.1) erfüllt:

Hx+ g +∑

i∈JG∪JU

λiai = 0.

Die zweite und dritte KKT-Bedingungen lauten

aTi x = bi für i ∈ JG,

aTi x ≤ bi für i ∈ JU .

Sie sind nach Konstruktion ebenfalls erfüllt. Ferner ist λi = 0 für alle i ∈ JU \ J , weshalbauch die fünfte KKT-Bedingung

λi(bi − aTi x) = 0 für i ∈ JG ∪ JU

gilt.

Für die vierte KKT-Bedingung ist noch das Vorzeichen der Lagrange-Parameter λi füri ∈ J ∩ JU zu bestimmen. Sind diese sämtlich nichtnegativ, dann ist auch die vierteKKT-Bedingung erfüllt und es gelten alle für das Minimierungsproblem (9.1) notwendigen

9.2. Bestimmung aktiver Nebenbedingungen 81

Bedingungen aus Satz 7.10. Für den Fall, dass H positiv definit ist, folgt insbesonderesogar, dass x tatsächlich eine lokale Lösung des Minimierungsproblems (9.1) ist.

Tritt dagegen ein negativer Lagrange-Parameter λj mit j ∈ J ∩ JU auf, so ist die vierteKKT-Bedingung verletzt. Daher kann x keine Lösung des Minimierungsproblems (9.1)sein. In diesem Fall lässt sich der Wert des quadratischen Funktionals verkleinern, indemman die zu j gehörige Nebenbedingung aus der Indexmenge J streicht. Dies folgt aus demBeweis von Lemma 7.8. Man kann zeigen, dass sich auf diese Weise alle Nebenbedingungenmit negativen Lagrange-Parametern entfernen lassen und am Ende ein Punkt x resultiert,der alle KKT-Bedingungen erfüllt.

Beispiel 9.3 Wir illustrieren das beschriebene Vorgehen an folgendem konkreten Mini-mierungsproblem

min(x1,x2)∈R2

(x1 − 1)2 +

(x2 −

5

2

)2

unter den Nebenbedingungen

x1 − 2x2 + 2 ≥ 0

−x1 − 2x2 + 6 ≥ 0

−x1 + 2x2 + 2 ≥ 0

x1 ≥ 0

x2 ≥ 0.

In der Notation (9.1) haben wir also

H =

[2 00 2

], g =

[−2−5

], x =

[x1x2

]

a1 =

[−12

], a2 =

[12

], a3 =

[1−2

], a4 =

[−10

], a5 =

[0−1

]

b1 = 2, b2 = 6, b3 = 2, b4 = 0, b5 = 0.

Wir starten das Verfahren mit

x0 =

[20

]und J0 = {3, 5}.

Das Minimierungsproblem (9.6) liefert für k = 0 als Lösung x1 = x0, da nur dieser Punktin der zulässigen Menge liegt und die beiden Gleichungsnebenbedingungen erfüllt. Diezugehörigen Lagrange-Parameter erhalten wir aus dem linearen Gleichungssystem

0 = Hx1 + g + λ3a3 + λ5a5 =

[2 + λ3

−5 − 2λ3 − λ5

],

dessen Lösung λ3 = −2 und λ5 = −1 ist. Wir streichen die Nebenbedingungen zumkleineren Lagrange-Parameter und erhalten J1 = {5}.Das Minimierungsproblem (9.6) für k = 1 liefert als Lösung

x2 =

[10

]


und der Lagrange-Parameter λ5 errechnet sich aus

0 = Hx2 + g + λ5a5 =

[0

−5− λ5

],

das heißt, λ5 = −5. Wir streichen folglich auch diese Nebenbedingung und landen beiJ2 = ∅.Nun lösen wir das Minimierungsproblem (9.7) für k = 2, das heißt, ein Minimierungspro-blem ohne Nebenbedingungen, was auf

d2 =

[05/2

]und somit x3 = x2 +

3

5d2 =

[13/2

]

führt. Wir addieren die blockierende Nebenbedingung zu unserer leeren Indexmenge J2

hinzu und erhalten J3 = {1}.Die Lösung des Minimierungsproblems (9.7) für k = 3 ergibt

d3 =

[2/51/5

]und somit x4 = x3 + d3 =

[7/517/10

],

wobei keine weitere blockierende Nebenbedingung auftritt. Der zugehörige Lagrange-Parameter folgt aus

0 = Hx4 + g + λ1a1 =

[4/5− λ1

−8/5 + 2λ1

],

also λ1 = 4/5. Folglich erfüllt x4 alle KKT-Bedingungen des Minimierungsproblems (9.1)und ist die gesuchte Lösung. △

Index

AlgorithmusCG-Verfahren, 39Gauß-Newton–Verfahren, 49Gradientenverfahren, 10, 13, 65Levenberg-Marquardt-Verfahren, 52modifiziertes Verfahren von Polak und

Ribière, 43Newton-Verfahren, 15, 20, 22nichtlineares CG-Verfahren, 40, 43Quasi-Newton-Verfahren, 32Trust-Region-Verfahren, 25Verfahren von Fletcher und Reeves,

40Verfahren von Polak und Ribière, 40

Armijo-Goldstein-Bedingung, 13, 66Armijo-Schrittweitenregel, 13

BFGS-Verfahren, 32

Cauchy-Punkt, 25CG-Verfahren, 39

nichtlineares, 40, 43

DFP-Verfahren, 32Dogleg-Strategie, 25

Energienorm, 40

Folgezulässige, 56

Funktionkonvexe, 6Lagrange-, 61quadratische, 7

Gauß-Newton-Verfahren, 48Gradientenverfahren, 10Grenzrichtung, 56

Hebden-Verfahren, 55

KKT-Bedingungen, 61

Konvexität, 6gleichmäßige, 6strikte, 6

Krylov-Raum, 39

Lagrange-Funktion, 61-Parameter, 52, 61

LICQ-Bedingung, 57Linearisierungskegel, 60

Minimumglobales, 5lokales, 5, 56striktes, 5

Nebenbedingung, 56affine, 73aktive, 57blockierende, 80Gleichungs-, 56Ungleichungs-, 56

Newton-Verfahren, 15globalisiertes, 20inexaktes, 22

NormEnergie-, 40

Projektionorthogonale, 65

PunktCauchy-, 25stationärer, 6, 57

nicht entarteter, 74zulässiger, 56

Quasi-Newton-Gleichung, 31Quasi-Newton-Verfahren

BFGS-Verfahren, 32DFP-Verfahren, 32Limited-Memory-, 36

83

84 Index

Rang-2-Verfahren, 31symmetrisches Rang-1-Verfahren von

Broydon, 32

Satzvon Karush, Kuhn und Tucker, 61von Newton-Kantorovich, 15

SQP-Verfahren, 76

Tangentialkegel, 69Trust-Region-Verfahren, 25, 51

Vektorenkonjugierte, 34, 37

Verfahrender konjugierten Gradienten, 39des steilsten Abstiegs, 10Gauß-Newton-, 48globalisiertes Newton-, 20Gradienten-, 10Hebden-, 55inexaktes Newton-, 22Levenberg-Marquardt-, 52modifiziertes Verfahren von Polak und

Ribière, 43Newton-, 15Quasi-Newton-, 31

BFGS-Verfahren, 32DFP-Verfahren, 32Limited-Memory-, 36Rang-2-Verfahren, 31symmetrisches Rang-1-Verfahren von

Broydon, 32SQP-, 76Trust-Region-, 25, 51von Fletcher und Reeves, 40von Polak und Ribière, 40

Zielfunktion, 5