Theorie und Numerik von ausgewählten Verfahren der nichtlinearen Optimierung


Bachelorarbeit, 2010
116 Seiten, Note: 1,3

Leseprobe

Universit¨
at Ulm
Fakult¨
at f¨
ur Mathematik und Wirtschaftswissenschaften
Theorie und Numerik von ausgew¨
ahlten
Verfahren der nichtlinearen Optimierung
Bachelorarbeit
in Wirtschaftsmathematik
vorgelegt von
Botschkarewa, Nadeshda
am 30.08.10


Inhaltsverzeichnis
Einleitung
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1
Mathematische Grundlagen
3
1.1
Grundlagen aus der Linearen Algebra
. . . . . . . . . . . . . . . . . . . .
3
1.2
Definitionen und Bezeichnungen der Optimierungstheorie
. . . . . . . . .
4
1.3
Optimalit¨
atsbedingungen
. . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.4
Das Konvergenzverhalten iterativer Verfahren
. . . . . . . . . . . . . . . .
8
2
Quasi-Newton-Verfahren zur L¨
osung von unrestringierten Optimierungspro-
blemen
12
2.1
Grundidee des Newton-Verfahrens
. . . . . . . . . . . . . . . . . . . . . .
12
2.2
Idee des BFGS-Verfahrens
. . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.3
Algorithmus und Konvergenz
. . . . . . . . . . . . . . . . . . . . . . . . .
18
2.3.1
Lokales BFGS-Verfahren
. . . . . . . . . . . . . . . . . . . . . . . .
18
2.3.2
Globalisiertes BFGS-Verfahren
. . . . . . . . . . . . . . . . . . . .
19
2.4
Effizienzanalyse
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
3
Penalty-Verfahren anhand der quadratischen Penalty-Funktion
28
3.1
Idee des Verfahrens und Konstruktion von Penalty-Funktionen
. . . . . .
28
3.2
Algorithmus und Konvergenz
. . . . . . . . . . . . . . . . . . . . . . . . .
31
3.3
Effizienzanalyse
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
4
Penalty-Lagrange-Methode
37
4.1
Exakte Penalty-Funktionen
. . . . . . . . . . . . . . . . . . . . . . . . . .
38
4.2
Idee des Verfahrens und Konstruktion von Penalty-Lagrange-Funktionen
.
40
4.3
Algorithmus und Konvergenz
. . . . . . . . . . . . . . . . . . . . . . . . .
41
4.4
Erweiterung auf Ungleichungsrestriktionen
. . . . . . . . . . . . . . . . . .
45
4.5
Effizienzanalyse
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
5
Barriere-Verfahren anhand der logaritmischen Barriere-Funktion
53
5.1
Idee des Verfahrens und Konstruktion von Barriere-Funktionen
. . . . . .
54
5.2
Algorithmus und Konvergenz
. . . . . . . . . . . . . . . . . . . . . . . . .
56
5.3
Effizienzanalyse
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
6
Innere-Punkte-Verfahren
61
6.1
Grundidee der Verfahren anhand linearer Probleme
. . . . . . . . . . . . .
63
6.1.1
Grundlagen der linearen Optimierung
. . . . . . . . . . . . . . . .
64
I

Inhaltsverzeichnis
6.1.2
Logarithmische Barriere, zentraler Pfad
. . . . . . . . . . . . . . .
64
6.1.3
Anwendung des Newton-Verfahrens in Innere-Punkte-Verfahren
. .
69
6.1.4
Allgemeiner Algorithmus
. . . . . . . . . . . . . . . . . . . . . . .
73
6.2
Pfad-Verfolgungs-Verfahren und Konvergenz
. . . . . . . . . . . . . . . . .
76
6.3
Grundz¨
uge der primal-dualen Innere-Punkte-Verfahren f¨
ur nichtlineare
Probleme
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81
6.3.1
Barriere-Problem und gest¨
orte Optimalit¨
atsbedingungen nichtli-
nearer primaler Probleme
. . . . . . . . . . . . . . . . . . . . . . .
82
6.4
Globalisierung des Verfahrens
. . . . . . . . . . . . . . . . . . . . . . . . .
87
6.4.1
Backtracking-Methode f¨
ur unrestringierte Probleme
. . . . . . . .
88
6.4.2
Backtracking-Schrittweitenbestimmung mit dem Filteransatz
. . .
88
6.4.3
Algorithmus mit Korrekturschritten
. . . . . . . . . . . . . . . . .
95
7
Numerische Fallstudie
97
7.1
Implementierung
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
97
7.2
Parameter
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98
7.3
Numerische Tests
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
8
ANHANG
103
A Anhang
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
B Anhang
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
C Anhang
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
II

Abbildungsverzeichnis
2.1
Graphische Darstellung des Newton-Verfahrens
. . . . . . . . . . . . . . .
14
2.2
Rosenbrock-Funktion
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.3
Log-Rosenbrock-Funktion
. . . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.4
Graphische Darstellung des Quasi-Newton-Verfahrens
. . . . . . . . . . .
26
2.5
Graphische Darstellung der Newton-und Quasi-Newton-Verfahren
. . . . .
27
3.1
Graphische Darstellung des Penalty-Verfahrens
. . . . . . . . . . . . . . .
30
3.2
Die Veranschaulichung einer Erh¨
ohung von im Penalty-Verfahren
. . . .
31
3.3
Die Veranschaulichung des Abbruchskriteriums im Penalty-Verfahren
. . .
31
4.1
Vergleich von quadratischer und l
1
Penalty-Funktion
. . . . . . . . . . . .
39
5.1
Iterierten des quadratischen Penalty-Verfahrens und des Barriere-Verfahrens
54
5.2
Verlauf des Barriere-Verfahrens
. . . . . . . . . . . . . . . . . . . . . . . .
56
6.1
Veranschaulichung eines Filters mit 7 Eintr¨
agen
. . . . . . . . . . . . . . .
92
6.2
Filter ohne Schranken
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
6.3
Obere Schranke f¨
ur die Verletzung der Nebenbedingungen
. . . . . . . . .
93
7.1
Leistungsprofil der behandelten Verfahren
. . . . . . . . . . . . . . . . . . 101
Tabellenverzeichnis
4.1
Numerisches Verhalten des quadratischen Penalty-Verfahrens
. . . . . . .
49
4.2
Numerisches Verhalten des Penalty-Lagrange-Verfahrens
. . . . . . . . . .
49
5.1
Verschlechterung der Kondition im Barriere-Verfahren
. . . . . . . . . . .
61
7.1
Vergleich der Algorithme
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
8.1
Ausgaben der Penalty-Verfahren-Implementierung f¨
ur das Testproblem 35
mit
k
+1
= 5
k
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
III

8.2
Ausgaben der Penalty-Lagrange-Verfahren-Implementierung f¨
ur das Test-
problem 35 mit
k
+1
= 5
k
. . . . . . . . . . . . . . . . . . . . . . . . . . 103
8.3
Ausgaben der Penalty-Verfahren-Implementierung f¨
ur das Testproblem 35
mit
k
+1
= 3
k
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
8.4
¨
Ubersicht der Steuer-und Abbruchsparameter der implementierten Algo-
rithmen
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
Algorithmenverzeichnis
1
Lokales Newton-Verfahren
. . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2
Lokales inverses BFGS-Verfahren
. . . . . . . . . . . . . . . . . . . . . . .
19
3
Allgemeines Abstiegsverfahren
. . . . . . . . . . . . . . . . . . . . . . . .
20
4
Globalisiertes inverses BFGS-Verfahren
. . . . . . . . . . . . . . . . . . .
23
5
Penalty-Verfahren
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
6
Penalty-Lagrange-Verfahren zur L¨
osung gleichungsrestringierter Probleme
43
7
Allgemeines Penalty-Lagrange-Verfahren
. . . . . . . . . . . . . . . . . . .
48
8
Barriere-Verfahren
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
9
Basis-Algorithmus der primal-dualen Innere-Punkte-Verfahren f¨
ur lineare
Probleme
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
10
Zul¨
assiges Pfad-Verfolgungs-Verfahren
. . . . . . . . . . . . . . . . . . . .
78
11
Basis-Algorithmus der primal-dualen Innere-Punkte-Verfahren
. . . . . . .
87
12
Backtracking-Verfahren f¨
ur unrestringierte Probleme
. . . . . . . . . . . .
88
13
Backtracking-Verfahren f¨
ur restringierte Probleme
. . . . . . . . . . . . .
91
14
Schrittweitenbestimmungs-Algorithmus mit einem Filteransatz
. . . . . .
94
15
Primal-duales Innere-Punkte-Verfahren
. . . . . . . . . . . . . . . . . . . .
95
IV

Einleitung
Die Arbeit befasst sich mit der nichtlinearen Optimierung, die das Problem der Minimie-
rung oder der Maximierung einer nichtlinearen Funktion unter Ber¨
ucksichtigung einer
endlichen Anzahl von Nebenbedingungen behandelt. Die Optimierung ist ein bedeu-
tendes Anwendungsgebiet der Mathematik. Sie wird regelm¨
aßig zur Unterst¨
utzung von
Entscheidungsprozessen in Wirtschaft und Industrie verwendet. Wegen der wachsenden
Leistungsf¨
ahigkeit moderner Rechner ist die Behandlung umfangreicher Optimierungs-
aufgaben aus der Praxis, die ohne dieses technischen Werkzeuges unm¨
oglich w¨
are, ein
Anwendungsgebiet der Numerik geworden.
Eine der bedeutenden Aufgaben der Numerik ist es, die Korrektheit von Algorithmen
zu ¨
uberpr¨
ufen, d.h. sicherzustellen, das unter gewissen Voraussetzungen an die Problem-
daten tats¨
achlich die richtige L¨
osung bzw. eine N¨
aherungsl¨
osung mit einer ben¨
otigten
osungsgenauigkeit bestimmt wird. Diese ¨
Uberpr¨
ufung soll mit mathematischen Techni-
ken durchgef¨
uhrt werden, d.h. am Ende steht ein formaler mathematischer Beweis, der
den korrekten Ablauf eines Algorithmus sicherstellt.
Hat man sich von der einwandfreien Funktion eines Algorithmus ¨
uberzeugt, so stellt sich
die Frage nach der Effizienz des Algorithmus, d.h. es muss der Rechenaufwand pro N¨
a-
herungsl¨
osung und die Konvergenzgeschwindigkeit gegen die exakte L¨
osung untersucht
werden. Die beiden Eigenschaften liefern Informationen dar¨
uber, wieviel Iterationen der
Algorithmus ben¨
otigt, um eine N¨
ahrungsl¨
osung auf eine bestimmte Genauigkeit zu be-
rechnen und wieviel Zeit jede Iteration der Berechnung in Anspruch nimmt.
Diese Arbeit besch¨
aftigt sich mit numerischen Verfahren zur L¨
osung nichtlinearer Op-
timierungsaufgaben. Es werden theoretische Grundlagen von mehreren Verfahren unter
den Gesicht
V
punkten der Korrektheit und der Effizienz ausgearbeitet und durch Beispiele
und mit Matlab R2008a erzeugten Abbildungen aufgelockert.
In dem folgenden einleitenden Kapitel sind Defin
L
tionen und S¨
atze aus Optimierungs-
theorie, Linearer Algebra, Analysis und Numerik zusammengestellt und Kriterien zur
Konvergenzanalyse erkl¨
art. Da die L¨
osung von drei der behandelten Verfahren auf die L¨
o-
sung von sogenannten unrestringierten Problemen oder eines Gleichungssystems zur¨
uck-
gef¨
uhrt wird, wird zuerst ein Newton-artiges Verfahren vorgestellt und w¨
unschenswerte
Eigenschaften, wie globale Konvergenz, hohe Konvergenzordnung des Verfahrens, er¨
or-
tert. Im n¨
achsten Kapitel wird das sogenannte Penalty-Verfahren anhand einer Penalty-
1

Algorithmenverzeichnis
Funktion mit einem Algorithmus f¨
ur eine numerische Behandlung vorgestellt und seine
Konvergenzeigenschaften anhand der im ersten Kapitel erkl¨
arten Konvergenzkriterien
analysiert. Die Nachteile des in dem Kapitel vorgestellten Verfahrens werden durch eine
Anwendung von sogenannten exakten Penalty-Funktionen aufgehoben, was auch kurz
erl¨
autert wird. Auf der Grundlage des Penalty-Verfahrens wird die Penalty-Lagrange-
Methode mit einer vollst¨
andigen algorithmischen Darstellung der theoretischen Herlei-
tung vorgestellt und eine Konvergenzanalyse durchgef¨
uhrt. Das sogenannte Barriere-
Verfahren wird nach dem gleichen Schema vorgestellt, basierend auf der Idee und eini-
gen im Rahmen des Barriere-Verfahrens getroffenen Aussagen wird eine Version aus der
Klasse der Innere-Punkte-Verfahren er¨
ortert. Diese Version bildet die mathematischen
Grundlagen f¨
ur den Open Source Solver IPOPT, der von Andreas W¨
achter und Lorez
T. Biegler entwickelt wurde.
Den Schlußpunkt der Arbeit setzen numerische Fallstudien im letzten Abschnitt, wo-
bei die Effizienz der Verfahren im Mittelpunkt der Untersuchung steht. Dabei wurde
der IPOPT als ein Werkzeug zur L¨
osung von Optimierungsaufgaben mit dem Innere-
Punkte-Verfahren eingesetzt. Alle anderen ausgearbeiteten Algorithmen wurden in der
Programmiersprache C++ unter Verwendung der numerischen Bibliothek FLENS im-
plementiert. Dies erm¨
oglicht eine nahezu unver¨
anderte ¨
Ubertragung der mathematischen
Notation der Algorithmen in ein aufgebautes Programm.
Der Inhalt der Arbeit basiert auf mehrere Literaturquellen, die in den entsprechenden
Kapitel spezifiziert werden, wobei [
7
], [
6
] und [
15
] die Hauptquellen sind.
2

1 Mathematische Grundlagen
1.1 Grundlagen aus der Linearen Algebra
Zur Herleitung der behandelten Methoden und f¨
ur die Konvergenzanalyse von Optimie-
rungsverfahren ben¨
otigt man einige Definitionen aus der Linearen Algebra und Resultate
¨
uber Matrizen und Vektoren, die wir in dem Abschnitt kurz zusammenstellen.
Ein Vektor x
R
n
ist grunds¨
atzlich als Spaltenvektor zu verstehen. Im Weiteren wenden
wir die drei Vektornormen an:
x
1
=
n
i
=1
|x
i
|,
x
2
=
x
T
x =
n
i
=1
x
2
i
1
2
,
x
= max
i
=1,...,n
{|x
i
|}.
Sei
· eine beliebige Norm auf R
n
, dann wird auf dem Raum der reellen n
×n-Matrizen
durch
A = sup
x
=0
Ax
x
eine Norm definiert, die man als zugeordnete Matrixnorm bezeichnet. F¨
ur diese Ma-
trixnormen gilt
Ax
A x x R
n
.
Außerdem ben¨
otigen wir die sogenannte Frobenius-Norm, die f¨
ur eine reelle Matrix
A
R
n
×n
durch
A
F
=
n
i,j
=1
a
2
ij
1
2
definiert wird.
Sei A
R
n
×n
eine reelle, symmetrische Matrix. Dann heißt A positiv definit, wenn
gilt
x
T
Ax > 0
x R
n
\{0}.
Die Matrix A wird als positiv semidefinit bezeichnet, wenn gilt
x
T
Ax
0 x R
n
.
3

1 Mathematische Grundlagen
Der Zahlwert k(A) :=
A
A
-1
wird als Konditionszahl der Matrix A bzgl. der
verwendeten Matrixnorm bezeichnet.
Ist die Matrix A symmetrisch, dann hat A nur reelle Eigenwerte
1
(A)
2
(A)
...
n
(A)
und es gilt
1
(A) = min
x
=0
x
T
Ax
x
T
x
,
n
(A) = max
x
=0
x
T
Ax
x
T
x
,
insbesondere gilt
1
(A) x
2
x
T
Ax
n
(A) x
2
x R
n
.
(1.1)
Setzen wir nun
n
(A) =
max
(A) und
1
(A) =
min
(A). Es gilt k(A) :=
max
(A)
min
(A)
ur eine
symmetrische positiv definite Matrix A
R
n
×n
.
Sei A
-1
die Inverse einer reellen invertierbaren symmetrischen positiv definiten Matrix
A
R
n
×n
, dann hat sie die Eigenwerte
0 <
-1
max
(A) < ... <
-1
min
(A).
Inbesondere ist A
-1
auch positiv definit und es gilt
-1
max
(A) x
2
=
-1
n
(A)x
T
x
x
T
A
-1
x
-1
1
(A)x
T
x =
-1
min
(A) x
2
(1.2)
und k(A
-1
) =
min
(A)
max
(A)
= k(A)
-1
.
(1.3)
1.2 Definitionen und Bezeichnungen der Optimierungstheorie
Den benutzten Begriffsapparat in dem Abschnitt kann man aus allen Literaturquellen zur
Optimierungstheorie entnehmen. Eine detailierte Behandlung von benutzten Definitio-
nen und Zusammenh¨
angen ist insbesondere in [
15
] und [
6
] nachzulesen, wir ¨
ubernehmen
aber nur die Ergebnisse. Diese Arbeit befasst sich mit numerischen Verfahren zur L¨
osung
nichtlinearer restringierter Optimierungsaufgaben der Gestalt
min
x
R
n
f (x)
u.d.N.
g(x)
0, h(x) = 0
(1.4)
mit der zumindest stetig differenzierbaren Zielfunktion f :
R
n
R und den zumindest
stetig differenzierbaren Restriktionsabbildungen g :
R
n
R
m
und h :
R
n
R
p
,
wobei u.d.N. unter der Nebenbedingung heißt. Alternativ kann man diese als
min f (x) u.d.N. x
X mit der zul¨assigen Menge X := {x R
n
: g(x)
0, h(x) = 0}
4

1.2 Definitionen und Bezeichnungen der Optimierungstheorie
darstellen. Wir setzen voraus, dass X =
ist. Ein Punkt x X heißt zul¨assiger Punkt.
Da Maximierungsaufgaben sich auch als eine Minimierung der Negation der Zielfunktion
f behandeln lassen, verzichten wir auf weitere Behandlung von Maximierungsaufgaben.
Die Idee aller hier behandelten Verfahren besteht darin, dass die Verfahren ein restrin-
giertes Optimierungsproblem (
1.4
) in Folgen von unrestringierten Teilproblemen der
Gestalt
min
x
R
n
(x) mit
(x) :
R
n
R
oder Gleichungssysteme
F
(x) = 0 mit F :
R
n
R
l
reformulieren und iterativ l¨
osen.
Definition 1.1.
Wir nennen x
X eine globale L¨osung von (
1.4
), wenn
f (x
)
f(x) x X gilt. Dagegen nennt man x
X eine lokale L¨osung von
(
1.4
), wenn es eine Umgebung U
von x
mit f (x
)
f(x) x X U
gibt.
Um weiter die Verfahren zur L¨
osung von restringierten Problem betrachten zu k¨
onnen,
ben¨
otigen wir die folgende Definition.
Definition 1.2.
Die Funktion L :
R
n
× R
m
× R
p
R
L(x, , ) = f (x) +
T
g(x) +
T
h(x)
heißt Lagrange-Funktion f¨
ur das Problem (
1.4
) und
R
m
,
R
p
heißen die
Lagrange-Multiplikatoren.
In dem Zusammenhang mit der Lagrange-Funktion wird dem Standartproblem (
1.4
) ein
anderes Problem zugeordnet, n¨
amlich das Lagrange-duale Problem. Das Ausgangspro-
blem (
1.4
) wird als primales Problem bezeichnet.
Definition 1.3.
Die Funktion
q(, ) := inf
x
X
L(x, , )
heißt die duale Funktion von (
1.4
), das Optimierungsproblem
max
(,)R
m
×R
p
q(, )
u.d.N.
0
das duale Problem oder Dualproblem zu (
1.4
). Die Lagrange-Multiplikatoren
R
m
und
R
p
heißen dann duale Variablen.
Man sieht, dass das duale Problem viel einfacher aussieht als das primale Problem und
auch der Gradient der dualen Zielfunktion ist sehr einfach zu berechnen. Es ist aber noch
zu beachten, dass man f¨
ur Paar (, ) den Wert q(, ) durch unrestringierte Minimie-
rung bestimmen muss, um q und
q zu erhalten.
5

1 Mathematische Grundlagen
ur eine reelle zweimal stetig differenzierbare Funktion f : U
R
n
R bezeichne
f(x)=
f
x
1
..
.
f
x
n
R
n
den Gradient von f und
2
f (x) =
2
f
x
2
1
(x)
2
f
x
1
x
2
(x)
...
2
f
x
1
x
n
(x)
2
f
x
2
x
1
(x)
2
f
x
2
2
(x)
...
2
f
x
2
x
n
(x)
..
.
..
.
...
..
.
2
f
x
n
x
1
(x)
2
f
x
n
x
2
(x)
...
2
f
x
2
n
(x)
R
n
×n
die Hesse-Matrix von f .
ur eine reelle zweimal stetig defferenzierbare Funktion g : U
R
n
R
m
bezeich-
ne g (x) =
g
1
x
1
(x)
g
1
x
2
(x)
...
g
1
x
n
(x)
g
2
x
2
(x)
g
2
x
2
(x)
...
g
2
x
n
(x)
..
.
..
.
...
..
.
g
m
x
1
(x)
g
m
x
2
(x)
...
g
m
x
n
(x)
R
m
×n
die Jacobi-Matrix von g, wobei
g
i
(x) bzw.
h
i
(x) die i-ten Spalten der transponierten Jacobi-Matrizen von g bzw. h
seien, d.h.
g(x) R
n
×m
bzw.
h(x) R
n
×p
.
1.3 Optimalit¨
atsbedingungen
Nachdem die un-/und restringierten Probleme definiert wurden, sind noch folgende De-
finitionen und S¨
atze von Bedeutung. Dabei stammen die S¨
atze aus [
15
] S.13-18 und
S.77-93, wo die Beweise der S¨
atze auch zu finden sind.
Satz 1.4.
(Vgl. Satz 2.1.1 [
15
] S. 13)(Notwendiges Optimalit¨
atskriterium erster Ordnung
- unrestringierter Fall)
Sei f : U
R
n
R stetig differenzierbar auf der offenen Menge U R
n
und x
U ein
lokales Minimum von f . Dann gilt
f(x
) = 0 und x
wird station¨
arer Punkt genannt.
Satz 1.5.
(Vgl. Satz 2.1.8 [
15
] S. 15)(Hinreichende Bedingung zweiter Ordnung - unre-
stringierter Fall)
Sei f : U
R
n
R zweimal stetig differenzierbar auf der offenen Menge U R
n
und
x
U ein Punkt, in dem gilt:
· f(x
) = 0,
· Die Hesse-Matrix
2
f (x
) = 0 ist positiv definit:
d
T
2
f (x
)d > 0
d R
n
\{0}.
Dann ist x
ein striktes lokales Minimum von f .
6

1.3 Optimalit¨
atsbedingungen
Nach diesen S¨
atzen erhalten wir ein lokales Minimum, falls in dem Punkt die Zielfunk-
tion verschwindet und die Hesse-Matrix der Zielfunktion positiv definit ist.
Im Vergeleich zu den unrestringierten F¨
allen wird nicht die Zielfunktion, sondern die
Lagrange-Funktion des Problems mit den Lagrange-Multiplikatoren bei restringierten
Problemen betrachtet, um die Existenz von Extrema zu ¨
uberpr¨
ufen. Dabei werden
gewisse Voraussetzungen (CQ) an die Nebenbedingungen gestellt, unter denen es die
Lagrange-Multiplikatoren (, )
R
m
× R
p
gibt.
Definition 1.6.
(Vgl. Definitionen 3.1.5, 3.1.7, 3.1.12 [
15
] S.78-80)
Eine Bedingung, die die Gleichung
T
l
(g, h, x) = T (X, x)
mit
T (X, x) :=
d
R
n
;
k
> 0, x
k
X = : lim
k
x
k
= x, lim
k
k
(x
k
- x) = d
und
T
l
(g, h, x) :=
d
R
n
;
g
i
(x)
T
d
0, i A(x), h(x)
T
d = 0
impliziert, wird als Contraint Qualification (CQ) f¨
ur x bezeichnet.
Die Gleichung T
l
(g, h, x) = T (X, x) stellt eine f¨
ur die Existenz der Lagrange-Multiplikatoren
in den KKT-Bedingungen hinreichende Bedingung dar (Vgl. die Zusammenh¨
ange bei [
15
]
S.78-80). Sie ist aber schwer ¨
uberpr¨
ufbar, deswegen werden wir ¨
aquivalente Bedingungen
(CQ) ¨
uberpr¨
ufen.
Definition 1.7.
(Vgl. Definition 3.1.2 und Definition 3.1.24 [
15
] S. 77, 84)
Der Punkt x
X heißt regul¨ar, wenn die Spalten der Matrix g
A(x)
(x),
h(x) mit
A(x) := {i; 1 i m, g(x) = 0}
linear unabh¨
angig sind.
Definition 1.8.
Die Indexmenge
A(x) bezeichnen wir als Indexmenge aktiver Un-
gleichungsnebenbedingungen und das Komplement davon mit
I(x) als Indexmenge
inaktiver Ungleichungsnebenbedingungen.
Lemma 1.9.
(Vgl. Lemma 3.1.25 [
15
] S. 84)
Die Regularit¨
at ist eine Constraint Qualification.
Satz 1.10.
(Vgl. Satz 3.1.14 [
15
] S. 80)(Notwendige Optimalit¨
atsbedingungen erster
Ordnung - restringerter Fall, Karush-Kuhn-Tucker-Bedingung, KKT-Bedingungen)
Sei x
R
n
eine lokale L¨
osung von (
1.4
), in der eine Constraint Qualification gilt.
Dann gelten die Karush-Kuhn-Tucker-Bedingungen:
Es gibt Lagrange-Multiplikatoren
R
m
und
R
p
mit:
7

1 Mathematische Grundlagen
1.
f(x
) +
g(x
)
+
h(x
)
= 0 (Multiplikatorregel),
2. h(x
) = 0,
3.
0, g(x
)
0,
T
g(x
) = 0 (Komplementarit¨
atsbedingungen).
Satz 1.11.
(Vgl. Definition 3.1.27 und Satz 3.1.32 [
15
] S. 85, 89)(Hinreichende Bedin-
gungen zweiter Ordnung)
Der Punkt x
R
n
gen¨
uge den KKT-Bedingungen
1.10
mit Multiplikatoren
R
m
und
R
p
. Seien die Zielfunktion f und die Restriktionsabbildungen g und h zweimal
stetig differenzierbar. Ferner gelte
d
T
2
xx
L(x
,
,
)d > 0, d
T
+
(g, h, x
,
)
\{0}
mit
T
+
(g, h, x, ) :=
d;
g
i
(x)
T
d
= 0,
falls i
A(x) und
i
> 0
0, falls i A(x) und
i
= 0
,
h(x)
T
d = 0 .
Dann ist x
eine isolierte lokale L¨
osung von (
1.4
).
1.4 Das Konvergenzverhalten iterativer Verfahren
Die Effizienz eines numerischen Verfahrens wird sehr stark durch die Anzahl der Itera-
tionsschritte, bis eine ben¨
otigte L¨
osungsgenauigkeit erzielt wird, beeinflusst. Basierend
auf den in dem zweiten Abschnitt zusammengefassten S¨
atzen lassen sich Konvergenzaus-
sagen f¨
ur behandelte Verfahren beweisen. Sie charakterisieren aber keine Konvergenzei-
genschaften der numerischen Verfahren, die gewissen Effizienzaussagen treffen lassen,
deswegen ben¨
otigen wir weitere Kriterien f¨
ur die Analyse der Konvergenzgeschwindig-
keit. Um die Konvergenzeigenschaften zu beschreiben und zu vergleichen, benutzt man
die Begriffe der Konvergenzordnung, des Konvergenzfaktors und des Einzugsbe-
reiches der Konvergenz
bzw. Konvergenzbereichs. Die hier vorgestellten Konzepte
zur Konvergenzanalyse beschr¨
anken sich nicht auf die Optimierung, sondern werden auch
in anderen Bereichen der Numerik angewandt, deswegen betrachten wir zun¨
achst allge-
meine Definitionen der Konvergenzgeschwindigkeiten. Die ausf¨
uhrlichen theoretischen
Herleitungen von den vorzustellenden Konzepten sind in [
2
] S.93-102, [
10
], [
11
] S.46-52
[
13
] S.196-228 nachzulesen.
Definition 1.12. (Lokale Konvergenz)
Die Iteration x
k
+1
= (x
k
) mit x
R
n
und :
R
n
R
n
heißt lokal konvergent,
wenn ein
> 0 existiert, so dass
x
0
U(x
, ) gilt
lim
k
x
k
= x
.
8

1.4 Das Konvergenzverhalten iterativer Verfahren
Definition 1.13. (Konvergenzordnung)
Eine Folge (x
k
)
R
n
konvergiert
1. linear gegen x
, falls ein k
0
existiert, so dass
k > k
0
x
k
+1
- x
c x
k
- x
mit einer Konstante c
(0, 1) gilt
2. superlinear gegen x
, falls ein k
0
existiert, so dass
k > k
0
x
k
+1
- x
c
k
x
k
- x
mit lim
k
(c
k
) = 0 gilt
3. von Ordnung p>1 gegen x
, falls ein k
0
existiert, so dass
k > k
0
x
k
+1
- x
x
k
- x
p
mit einer Konstante
(0, ) gilt.
Es wird demnach die Konvergenz von Ordnung p = 2 als quadratische Konvergenz
bezeichnet.
Definition 1.14.
Es gelte x
k
x
, dann definieren wir f¨
ur x
k
= x
den Q-Faktor mit
Q(x
k
) := lim sup
k
x
k
+1
- x
x
k
- x
.
Wir merken an, dass die hier eingef¨
uhrten Begriffe der linearen bzw. superlinearen Kon-
vergenz h¨
aufig auch als Q-lineare bzw. Q-superlineare Konvergenz benannt werden. Auf
die Behandlung der sogenannten R-linearen, R-superlinearen usw. Konvergenz verzich-
ten wir in der Arbeit.
Zur Beschreibung der Effizienz eines iterativen Verfahrens werden wir also die Konver-
genzfaktoren, Konvergezordnungen und Konvergenzbereiche U (x
, ) betrachten, welche
angeben, wie schnell N¨
aherungsl¨
osungen x
k
bei der Konvergenz des Fehlers x
k
-x
0
gegen exakte L¨
osungen konvergieren, und in welcher Umgebung die Geschwindigkeit
erreicht wird. Die Kriterien lassen sich allerdings nur unter zus¨
atzlichen Bedingungen
bestimmen. Ohne diese Voraussetzungen kann die Konvergenz der mit den iterativen
Verfahren bestimmten Folge der Iterierten (x
k
) gegen die gesuchte L¨
osung beliebig lang-
sam sein.
Als Teilaufgabe zur Behandlung nichtlinearer Optimierungsaufgaben mit den vorzustel-
lenden Verfahren sind die L¨
osungen einer nichtlinearen Gleichung oder eines Systems
von nichtlinearen Gleichungen zu bestimmen, deswegen spezifizieren wir die Kriterien
ur die Analyse der Geschwindigkeit von iterativen Verfahren zur L¨
osung von nichtlinea-
ren Gleichungen und Gleichungssystemen.
Als theoretische Grundlage f¨
ur das Studium der Konvergenzeigenschaften werden wir zu-
erst allgemeine iterative Verfahren betrachten, die auf dem Banachschen Fixpunktsatz
basieren, der ein mathematisches Hilfsmittel zur Bildung konvergierender Zahlenfolgen
9

1 Mathematische Grundlagen
darstellt. Dabei wird das vorliegende Gleichungssystem F (x) = 0 mit einer mindest ste-
tig differenzierbaren Funktion F :
R
n
R
n
in eine ¨
aquivalente Fixpunktform (x) = x
mit :
R
n
R
n
transformiert. Somit wird die Suche einer Nullstelle in die iterative
Suche eines Fixpunktes umformuliert. Man w¨
ahlt so, dass die Gleichung (x
) = x
gilt, wenn f¨
ur ein x
R
n
F (x
) = 0 auch erf¨
ullt ist, d.h. die Fixpunktiteration besitzt
die Form x
k
+1
= (x
k
), k
0.
Bei der Klasse von iterativen Verfahren wird voraussgesetzt, dass die Iterationsfunktion
eine Kontraktion ist, d.h.
I R
n
und L
(0, 1), so dass f¨ur : I I gilt
(x)
- (y) L x - y x, y I,
somit l¨
asst es sich beweisen, dass der sogenannte absolute Fehler
abs
:= x
k
- x
mit
wachsendem k kleiner wird, dadurch stellt er auf einer Umgebung von I das Konver-
genzverhalten der Folge (x
k
) dar. Aus dem Banachschen Fixpunktsatz (siehe z.B. bei [
2
]
S. 95) folgt, dass die Kontraktionskonstante L eine untere Schranke auf der Umgebung
I darstellt, um die sich der Fehler pro Iteration verkleinert, d.h. je kleiner die Konstante
L ist, desto besser ist die Konvergenz der Folge (x
k
) gegen x
.
Außerdem k¨
onnen wir das Konvergenzverhalten durch ein asymptotisches Verhalten des
Fehlers
lim
k
x
k
+1
- x
x
k
- x
charakterisieren. F¨
ur gen¨
ugend große k verh¨
alt sich also der Verfahrensfehler wie eine geo-
metrische Folge. Im Allgemeinen ergibt sich lineare Konvergenz der Fixpunktiterations-
Verfahren, weil der Fehler x
k
+1
- x
ausgehend aus x
k
- x
linear mit dem Faktor
(x
) abnimmt, d.h. die lineare Konvergenzrate ist asymptotisch gleich (x
) f¨
ur
k
lim
k
x
k
+1
- x
x
k
- x
= (x
) .
Dies l¨
asst sich durch eine einfache Anwendung des Mittelwertsatzes f¨
ur eine kontrahie-
rende Iterationsfunktion auf einer abgeschlossenen Menge I beweisen (siehe z.B. [
2
] S.95
ur I
R und z.B. bei [
13
] S.220 erweitert auf I
R
n
). Bei einer linearen Konvergenz
zeichnet sich eine schnell konvergente Iterationsfunktion dadurch aus, dass die Norm der
Jacobi-Matrix (x
) m¨
oglichst klein ist. Im Fall linearer Konvergenz werden asym-
ptotisch stets gleich viele Iterationsschritte ben¨
otigt, um den Betrag von x
k
- x
auf
den zehnten Teil zu reduzieren. Dies bedeutet, dass nach je m Iterationen je eine weitere
Deziamalstelle der Approximation richtig ist. Aus x
k
+m
-x
(x
)
x
k
-x
folgt
ur m die Bedingung
m
-1
log
10
(x
)
.
Man kann spezielle Iterationsverfahren entwickeln, die ¨
uberlineare - also mindestens qua-
dratische - Konvergenz besitzen.
Abschließend bemerken wir aber, dass eine Folge mit einer h¨
oheren Konvergenzordnung
10

grunds¨
atzlich ein besseres Konvergezverhalten hat, auch wenn die Konvergenzordnung
und der Konvergenzfaktor die Konvergenz beeinflussen.
Schließlich haben wir zwei Maße f¨
ur Konvergenzanalyse von iterativen Verfahren zur L¨
o-
sung nichtlinearer Gleichungen und Gleichungssysteme, n¨
amlich die Konvergenzordnung
und den Konvergenzfaktor (x
) . Da bei den iterativen Verfahren der Konvergenz-
faktor stark von der Kontraktionskonstante der Ableitung F abh¨
angt, sch¨
atzen wir im
Weiteren anstatt einer Norm der Jacobi-Matrix (x
) der Iterationsfunktion eine
Norm der Jacobi-Matrix F (x
) der behandelten Funktion F .
Um die Behandlung von dem Konvergenzfaktor zu vereinfachen, f¨
uhren wir noch die
folgende Absch¨
atzung f¨
ur eine Matrix A
R
n
×n
,
> 0 und eine induzierte Matrixnorm
· ein
(A)
A (A) + ,
wobei
(A) :=
max
i
=1,...,n
{|
i
(A)
|} der Spektralradius von A sei. Der Nachweis, dass der
Spektralradius die untere Schranke aller induzierten Matrixnormen bildet, ist sehr auf-
andig, deswegen verweisen wir auf die Literaturquelle [
8
]. Dank der Absch¨
atzung k¨
on-
nen wir den Konvergenzfaktor (x
) bzw. F (x
) durch den Spektralradius absch¨
at-
zen.
Da die Ermittlung des Radius des Konvergenzbereiches U (x
, ) in der Praxis im All-
gemeinen sehr schwer ist, verzichten wir auf allgemeine Betrachtung des Konvergenz-
bereiches der iterativen Verfahren. Man kann aber einen Zusammenhang zwischen dem
Konvergenzfaktor und dem Radius des Einzugsbereichs der Konvergenz bei einigen Itera-
tionsverfahren feststellen. Z.B. bei dem Newton-Verfahren mit (x) := x
- F (x)
-1
F (x)
ist sowohl der Konvergenzradius als auch der Konvergenzfaktor von der Kontraktions-
konstante L
(0, 1) der Ableitung F der zu untersuchenden Funktion F abh¨angig (siehe
bei [
10
] S.66). Wenn man keine Lipschitz-Stetigkeit voraussetzt, erh¨
alt man niedrigere
Konvergenzordnung mit einem anderen Konvergenzfaktor, aber einen ¨
ahnlichen Zusam-
menhang zwischen dem Konvergenzfaktor und dem Konvergenzbereich (siehe bei [
10
] S.
65-66). Aus den beiden S¨
atzen folgt, dass die Vergr¨
oßerung des Konvergenzfaktors nicht
nur zur Reduktion der Konvergenzgeschwindigkeit sondern auch zur Verkleinerung des
Konvergenzbereiches bei dem Newton-Verfahren f¨
uhrt.
Bemerkung 1.15.
Die definierte Kriterien zur Untersuchung des Konvergenzverhalten
beeinflussen lediglich die Anzahl der Iterationsschritte, d.h. das Konvergenzverhalten
kann kein alleiniges Kriterium f¨
ur die G¨
ute iterativer Verfahren darstellen, da hierf¨
ur
auch der m¨
oglicherweise unterschiedliche Rechenaufwand pro Iteration zu ber¨
ucksichti-
gen ist. Dabei sind die Rechenoperationen und Anzahl der Funktionauswertungen pro
Iteration ausschlaggebend.
Der vorgestellten Zusammenhang gilt sowohl zur L¨
osung von Gleichungenssystemen als
auch zur Minimierung einer zweimal stetig differenzierbaren Funktion, indem man Null-
stellen des Gradienten
f(x) mit den Fixpunktiterations-Verfahren approximiert. Eine
Norm der Hesse-Matrix
2
f (x
) bzw. der Spektralradius der Hesse-Matrix bildet in dem
Fall eine Absch¨
atzung des Konvergenzfaktors.
11

2 Quasi-Newton-Verfahren zur L¨
osung von unrestringierten Optimierungsproblemen
2 Quasi-Newton-Verfahren zur L¨
osung von
unrestringierten Optimierungsproblemen
Abgesehen von ihrer praktischen Bedeutung werden viele Verfahren zur L¨
osung von
unrestringierten Problemen ferner als Ansatzpunkt zur Entwicklung von Verfahren zur
restringierten Optimierung herangezogen. Außerdem kann die L¨
osung von restringierten
Problemen auf die von unrestringierten Problemen zur¨
uckgef¨
uhrt werden.
Deswegen besch¨
aftigt sich dieses Kapitel mit einem Newton-artigen Verfahren, das zur
osung nichtlinearer Gleichungen, kleiner und mittelgroßer Gleichungssysteme und unre-
stringierter Optimierungsprobleme verwendet wird. Die Verfahrensklasse der unrestrin-
gierten Minimierung wird derzeit als eine der effizientesten und zuverl¨
assigsten zur L¨
o-
sung von Problemen nicht zu hoher Dimension angesehen.
Die Ausarbeitung basiert auf den folgenden Literaturquellen [
7
] S.29-49 und S.57-64,
[
10
] S.144-197 und [
15
] S.129-182 und ist folgendermaßen gegliedert: Erst wird die Idee
des Newton-Verfahrens kurz skizziert, dann die Grundlagen eines der Quasi-Newton-
Verfahren vorgestellt und abschließend nach der vordefinierten Vorgehensweise die Kor-
rektheit und die Effizienz des hergeleiteten Algorithmus analysiert.
2.1 Grundidee des Newton-Verfahrens
Um die Idee und die Herleitung von Quasi-Newton-und Innere-Punkte-Verfahren ver-
st¨
andlich vorstellen zu k¨
onnen, betrachten wir die Grundidee und grundlegende Defini-
tionen des (lokalen) Newton-Verfahrens zur L¨
osung nichtlinearer Gleichungssysteme und
nichtlinearer unrestringierter Optimierungsprobleme. Wir behandeln zuerst ein nichtli-
neares Gleichungssystem der Gestalt
F (x) = 0,
(2.1)
wobei F :
R
n
R
n
eine zumindest stetig differenzierbare Funktion ist.
Wir gehen davon aus, dass x
k
eine aktuelle N¨
aherung f¨
ur die L¨
osung x
des Gleichungs-
systems (
2.1
) ist. Wir approximieren die Funktion F lokal durch die Linearisierung
F
k
(x) := F (x
k
) + F (x
k
)(x
- x
k
)
um die aktuelle N¨
aherung x
k
und bestimmen dann die n¨
achste N¨
aherung x
k
+1
ur die
gesuchte L¨
osung x
als Nullstelle der linearisierten Funktion F
k
. Dies f¨
uhrt auf die Vor-
12

2.1 Grundidee des Newton-Verfahrens
schrift
x
k
+1
:= x
k
- F (x
k
)
-1
F (x
k
)
mit der Inversen der Jacobi-Matrix F (x
k
)
-1
. Um die explizite Bestimmung der inversen
Matrix zu vermeiden, bestimmt man einen Korrekturvektor x
k
durch das L¨
osen des
Gleichungssystems
F (x
k
)x
k
=
-F (x
k
),
das als Newton-Gleichung bezeichnet wird. Die n¨
achste Iterierte erhalten wir anschlie-
ßend durch
x
k
+1
:= x
k
+ x
k
.
Der Korrekturvektor x
k
wird auch als Newton-Schritt bezeichnet. Die Idee des Ver-
fahrens zur L¨
osung eines nichtlinearen Gleichungssystems wird durch den folgenden Al-
gorithmus dargestellt.
Algorithmus 1
: Lokales Newton-Verfahren (in Anlehnung an [
15
] S.38)
ahle einen Startvektor x
0
R
n
, einen Toleranzwert
0.
1. Setze k
0.
2. Ist F (x
k
)
2
, STOP.
3. Bestimme
x
k
R
n
als L¨
osung des linearen Gleichungssystems
F (x
k
)
x
k
=
-F (x
k
).
4. Setze x
k
+1
= x
k
+
x
k
, k
k + 1, und gehe zu 2.
Um die Herleitung des Verfahrens verst¨
andlich darzustellen und graphisch zu illustrieren,
betrachten wir einen eindimensionalen Fall, d.h. wir behandeln eine nichtlineare Glei-
chung f (x) = 0, wobei f :
R R eine stetige differenzierbare Funktion ist. Wir approxi-
mieren die gesuchte Nullstelle durch eine Behandlung der Tangente p(x) im Startpunkt
x
0
. Das Tangentialpolynom hat die folgende Gestalt
p(x) = f (x
0
) + f (x
0
)(x
- x
0
).
(2.2)
Anstelle des Schnittpunktes x
des Graphen von f mit der x-Achse berechnen wir dann
den Schnittpunkt x
1
der Tangente mit der x-Achse (siehe Abbildung
2.1
). Der Schnitt-
punkt x
1
asst sich aus (
2.2
) wie folgt berechnen x
1
= x
0
-
f
(x
0
)
f
(x
0
)
. Die Grundidee des
Newton-Verfahrens besteht nun in der mehrfachen Anwendungen dieser Vorschrift
x
k
+1
= x
k
-
f (x
k
)
f (x
k
)
, k = 0, 1, 2, 3...,
was mit der Abbildung
2.1
gezeigt wird. Die lokale quadratische Konvergenz des Newton-
13

2 Quasi-Newton-Verfahren zur L¨
osung von unrestringierten Optimierungsproblemen
Abbildung 2.1: Graphische Darstellung des Newton-Verfahrens in dem eindimensionalen
Fall
Verfahrens nach dem Algorithmus
1
zum L¨
osen nichtlinearer Gleichungssysteme ist z.B.
bei [
15
] S.41-42 nachgewiesen.
Man kann das Newton Verfahren auch zur Behandlung von unrestringierten Optimie-
rungsaufgaben mit zweimal stetig differenzierbaren Funktion f :
R
n
R verwenden.
Falls die Hesse-Matrix
2
f (x)
R
n
×n
positiv definit ist, erhalten wir einen station¨
aren
Punkt durch das L¨
osen des Gleichungssystems
f(x) = 0, das die notwendige Optima-
lit¨
atsbedingung erster Ordnung f¨
ur unrestringierte Probleme darstellt. Das demnach zu
osende Gleichungssystem lautet
2
f (x
k
)x
k
=
-f(x
k
)
und die n¨
achste Iterierte erhalten wir durch
x
k
+1
:= x
k
+ x
k
bzw. x
k
+1
:= x
k
- (
2
f (x
k
))
-1
f(x
k
).
¨
Uber die Konvergenzresultate des Newton-Verfahrens f¨
ur Optimierungsprobleme kann
man bei [
15
] S.43-44 lesen.
2.2 Idee des BFGS-Verfahrens
In vielen Anwendungsf¨
allen ist die Berechnung der Hesse-Matrix
2
f (x) zeitintensiv
und die notwendige positive Definitheit der Hesse-Matrix ist im Allgemeinen auch nicht
gesichert. Andererseits ist das vereinfachte Newton-Verfahren wegen seiner Konvergen-
zeigenschaften meist nicht konkurrezf¨
ahig, deswegen betrachten wir in diesem Abschnitt
das sogenannte Quasi-Newton-Verfahren, das mit geringerem Funktionsaufwand eine
14

2.2 Idee des BFGS-Verfahrens
passable Approximation K
k
der Inverse der Hesse-Matrix
2
f (x) liefert und dennoch
lokal Q-superlinear konvergiert, dies wurde insbesondere in der Arbeit [
7
] S.148-164 ge-
zeigt.
In der vorliegenden Arbeit wird nur auf die gebr¨
auchlichste aus der Klasse der Quasi-
Newton-Verfahren Methode eingegagen, die als Broyden-Fletcher-Goldfarb-Shanno
(BFGS)-Verfahren bezeichnet wird. Das Verfahren benutzt die im k-ten Iterationsschritt
bestimmte Verfahrensgr¨
oßen, um eine Matrix K
k
als eine Approximation der Inversen
von der Hesse-Matrix
2
f (x) geeignet zur Matrix K
k
+1
des folgenden Schrittes aufzu-
datieren.
Um eine Aufdatierungsformel herzuleiten und die Eigenschaften von der gewonnenen
Matrix K
k
nachzuweisen, betrachten wir erst die Matrizen H
k
, die die Hesse-Matrizen
im k-ten Schritt approximieren und die n¨
achste Iterierte x
k
+1
im Newton-Schritt durch
die Vorschrift
x
k
+1
:= x
k
- H
-1
k
f(x
k
)
bestimmen lassen. Dies hat zun¨
achst den Vorteil, dass man die insgesamt n
2
partiel-
len Ableitungen in
2
f (x
k
) nicht zu berechnen braucht. Ferner wird sich sp¨
ater noch
herausstellen, dass man den Rechenaufwand von im Allgemeinen O(n
3
) Rechenopera-
tionen beim Newton-Verfahren auf lediglich O(n
2
) pro Iterationen beim Quasi-Newton-
Verfahren mittels Verwendung von K
k
reduzieren kann.
Eine notwendige Eigenschaft der gesuchten Approximation wird mit dem Korollar von
Dennis und Mor´
e (Vgl. Korollar 7.9 [
7
] S. 62) hergeleitet (siehe bei [
7
] S. 129-130). Es
handelt sich um die sogenannte Quasi-Newton-Bedingung
f(x
k
+1
)
- f(x
k
) = H
k
+1
(x
k
+1
- x
k
),
(2.3)
die eine Forderung an H
k
+1
stellt, so dass die superlineare Konvergenz des Verfahrens
nach dem Korollar Dennis und Mor´
e erreichbar ist. Im eindimensionalen Fall ist die
Quasi-Newton-Bedingung mit der Sekantenformel
H
k
+1
=
f(x
k
+1
)
- f(x
k
)
x
k
+1
- x
k
identisch, d.h. H
k
+1
stellt also die Steigung der Sekante von f durch die Punkte
(x
k
+1
, f (x
k
+1
)) und (x
k
, f (x
k
)) dar.
Die Quasi-Newton-Gleichung erfordert, dass die positiv definite und symmetrische Ma-
trix H
k
+1
(x
k
+1
- x
k
) in
f(x
k
+1
)
- f(x
k
)
abbildet. Dies ist nur m¨
oglich, wenn die Vektoren (x
k
+1
- x
k
) und
f(x
k
+1
)
- f(x
k
)
die Bedingung
(x
k
+1
- x
k
)
T
f(x
k
+1
)
- f(x
k
) > 0
(2.4)
15

2 Quasi-Newton-Verfahren zur L¨
osung von unrestringierten Optimierungsproblemen
erf¨
ullen. Dies sieht man leich, wenn man die Quasi-Newton-Gleichung mit (x
k
+1
- x
k
)
T
multipliziert. Somit hat die Quasi-Newton-Gleichung immer eine L¨
osung H
k
+1
, wenn die
Bedingung (
2.4
) erf¨
ullt ist.
Um die Schreibweise zu vereinfachen, nutzen wir im Weiteren die folgenden Abk¨
urzun-
gen:
d
k
:= x
k
+1
- x
k
, y
k
:=
f(x
k
+1
)
- f(x
k
),
somit lauten die Quasi-Newton-Bedingung H
k
+1
d
k
= y
k
und die zu (
2.4
) ¨
aquivalente
Bedingung d
T
k
y
k
T
= y
T
k
d
k
> 0. Der Vektor d
k
im k-ten Schritt ist im lokalen BFGS-
Verfahren mit dem Korrekturvektor x
k
identisch. Im Weiteren behandeln wir aber das
globalisierte BFGS-Verfahren, wo d
k
= x
k
im Allgemeinen sein kann. Um die Einheit-
liche Notation f¨
ur das BFGS-Verfahren zu behalten, bezeichnen wir x
k
+1
- x
k
= d
k
.
Da H
k
eine geeignete N¨
aherung der Hesse-Matrix
2
f (x
k
) darstellen soll, stellen wir
folgende Forderungen an die Updateformel:
1. Die resultierende H
k
ist symmetrisch und positiv definit, sofern H
0
diese Eigen-
schaften hat.
2. H
k
erf¨
ullt die Quasi-Newton-Bedingung (
2.3
).
3. H
k
entsteht aus den Daten: H
k
-1
, x
k
, x
k
-1
,
f(x
k
) und
f(x
k
-1
).
Es gibt mehrere Ans¨
atze f¨
ur eine symmetrische Quasi-Newton-Aufdatierung. Die bis heu-
te erfolgreichsten Quasi-Newton-Verfahren entstehen durch die sogenannte symmetrische
Rang-2-Aufdatierung:
H
k
+1
:= H
k
+ uu
T
+ vv
T
mit u, v
R
n
und ,
R.
Es ist offensichtlich, dass die durch die Rang-2-Aufdatierung gewonnene Matrix H
k
+1
symmetrisch ist.
Einsetzen in die Quasi-Newton-Gleichung liefert dann die zu l¨
osende Gleichung
H
k
d
k
+ uu
T
d
k
+ vv
T
d
k
!
= y
k
.
Seien
u := y
k
, v := H
k
d
k
, :=
1
y
T
k
d
k
, :=
-
1
d
T
k
H
k
d
k
,
dann erhalten wir
H
k
d
k
+
y
k
y
T
k
d
k
y
T
k
d
k
-
H
k
d
k
(H
k
d
k
)
T
d
k
d
T
k
H
k
d
k
= y
k
.
16

2.2 Idee des BFGS-Verfahrens
Nachdem in der Gleichung y
T
k
d
k
und d
T
k
H
k
d
k
sich dank der Symmetrie der Matrix H
k
urzen, erhalten wir die Quasi-Newton-Gleichung, d.h. die zweite Anforderung ist damit
erf¨
ullt.
Aus der Aufdatierung ergibt sich insbesondere die sogenannte Broyden-Fletcher-Goldfarb-
Shanno-Formel (BFGS)
H
k
+1
:= H
k
+
y
k
y
T
k
y
T
k
d
k
-
H
k
d
k
(H
k
d
k
)
T
d
T
k
H
k
d
k
,
(2.5)
die f¨
ur y
T
k
d
k
= 0 und d
T
k
H
k
d
k
= 0 wohldefiniert ist.
Die Matrix H
k
+1
ist symmetrisch und erf¨
ullt offensichtlich die Anforderungen 2 und 3,
falls die Matrix H
k
die Eigenschaften hat. Es bleibt nun die positive Definitheit der
Matrix H
k
+1
zu zeigen, die aus der positive Definitheit der Matrix H
k
bzw. H
0
folgen
soll.
Satz 2.1.
(Vgl. Satz 2.9.2 (1) [
15
] S.60)
Seien y
T
k
d
k
> 0, d
T
k
H
k
d
k
= 0 und H
k
positiv definit, dann ist die Matrix H
k
+1
positiv
definit.
Beweis:
Da positiv definite Matrizen sich faktorisieren lassen, betrachten wir eine Zerlegung
H
k
= R
T
k
R
k
, wobei R
k
R
n
×n
eine invertierbare Matrix ist. Es gilt
v R
n
\{0}
v
T
H
k
+1
v = v
T
H
k
v +
(v
T
y
k
)
2
y
T
k
d
k
-
(v
T
H
k
d
k
)
2
d
T
k
H
k
d
k
= R
k
v
2
2
+
(v
T
y
k
)
2
y
T
k
d
k
-
(R
k
v)
T
(R
k
d
k
)
2
R
k
d
k
2
2
Cauchy-Schwarz
-Ungleichung
R
k
v
2
2
+
(v
T
y
k
)
2
y
T
k
d
k
-
R
k
v
2
2
R
k
d
k
2
2
R
k
d
k
2
2
=
(v
T
y
k
)
2
y
T
k
d
k
0
Sind v und d
k
linear unabh¨
angig, dann gibt es t
R\{0} mit v = td
k
und daher ergibt
sich (v
T
y
k
)
2
= t
2
(d
T
k
y
k
) > 0 aus der Positivit¨
at von y
T
k
d
k
= (d
T
k
y
k
)
T
, d.h.
(v
T
y
k
)
2
y
T
k
d
k
0
gilt, somit ist H
k
+1
positiv definit.
Nach der bisherige Ausf¨
uhrung erf¨
ullt die Updateformel (
2.5
) alle gestellten Forderungen.
Unter der Verwendung solcher Aufdatierungsmatrizen kann man also die explizite Be-
rechnung der Hesse-Matrix vermeiden. Der Rechenaufwand betr¨
agt aber O(n
3
) Operati-
on pro Iteration, weil man bei der Quasi-Newton-Iteration in jedem Schritt ein lineares
Gleichungssystem der Gestalt
H
k
x
k
=
-f(x
k
)
17
Ende der Leseprobe aus 116 Seiten

Details

Titel
Theorie und Numerik von ausgewählten Verfahren der nichtlinearen Optimierung
Hochschule
Universität Ulm  (Numerische Mathematik)
Note
1,3
Autor
Jahr
2010
Seiten
116
Katalognummer
V274017
ISBN (eBook)
9783656659709
ISBN (Buch)
9783656659693
Dateigröße
3233 KB
Sprache
Deutsch
Schlagworte
nichtlinaere Optimierungsprobleme, Optimierungprobleme mit Nebenbedingungen, restringirte, Newton-artiges Verfahren, Penalty, Barriere, Barriereverfahren, Penaltyverfahren, Numerik, newtonartite, Optimierung, restringierte, unrestringierte, Optimierungprobleme, Nebenbedingungen
Arbeit zitieren
Nadeshda Botschkarewa (Autor), 2010, Theorie und Numerik von ausgewählten Verfahren der nichtlinearen Optimierung, München, GRIN Verlag, https://www.grin.com/document/274017

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Theorie und Numerik von ausgewählten Verfahren der nichtlinearen Optimierung


Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden