Nichtglatte Optimierung


Bachelorarbeit, 2010

104 Seiten, Note: 1,7


Leseprobe

Universität Augsburg
Institut für Mathematik
Diskrete Mathematik, Optimierung und Operations Research
Nichtglatte Optimierung
Bachelorarbeit
im Studiengang Mathematik zur Erreichung des akademischen
Grades des Bachelor of Science
vorgelegt von
Irene Filipiak
Augsburg, 21. Dezember 2010

Inhaltsverzeichnis
1. Einleitung
3
2. Grundlagen
4
2.1. Konvexe Mengen und Funktionen . . . . . . . . . . . . . . . . . . . . . .
4
2.1.1. Konvexe Mengen . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.1.2. Konvexe Funktionen . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2. Lokale Lipschitz-Stetigkeit . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.3. Subdierential und Richtungsableitung . . . . . . . . . . . . . . . . . . .
7
2.4. Konvexe Optimierungsprobleme . . . . . . . . . . . . . . . . . . . . . . . 13
2.5. Abstiegsrichtungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.6. Lagrange-Multiplikatoren . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3. Das Gradientenverfahren
17
3.1. Das Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2. Schrittweitenbestimmung . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.1. Armijo-Regel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.2. Wolfe-Powell-Regel . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.3. Bisektion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3. Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3.1. Bananen-Funktion . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3.2. Himmelblau-Funktion . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.3. Wolfe-Funktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4. Das Subgradientenverfahren
28
4.1. Das Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2. Konvergenzbetrachtungen . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.3. Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.3.1. Betragsfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.3.2. Wolfe-Funktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5. Approximatives Abstiegsverfahren
36
6. Bundle-Verfahren
44
6.1. Verwendung eines Bundles . . . . . . . . . . . . . . . . . . . . . . . . . . 44
6.2. Verfahren mit approximativer Suchrichtung . . . . . . . . . . . . . . . . 47
6.3. Das Schrittweitenverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.4. Konstruktion des Bundles . . . . . . . . . . . . . . . . . . . . . . . . . . 51
6.5. Ein implementierbares Abstiegsverfahren . . . . . . . . . . . . . . . . . . 54
6.6. Allgemeiner Ablauf des Bundle-Verfahrens . . . . . . . . . . . . . . . . . 59
6.7. Wolfe-Funktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
7. Schlussbemerkung
61
A. Anhang
62
Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Notationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Quellcode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2

1. Einleitung
Die Optimierung ist ein sehr wichtiger Bestandteil unserer heutigen Gesellschaft gewor-
den. Sie ist in allen Lebens- und Geschäftsbereichen wieder zu erkennen. Es wird immer
danach gestrebt den Lebensstandard der Menschen zu verbessern bzw. zu optimieren.
Dies beginnt in kleinen Betrieben und endet in groÿen Konzernen und weltweit erfolgrei-
chen Unternehmen. So wird stets versucht den gröÿtmöglichen Gewinn zu erzielen und
die dabei entstehenden Kosten bestmöglichst zu minimieren. Dies gelingt am besten mit
verschiedenen Optimierungsmethoden.
Da die Optimierung immer stärker in Naturwissenschaften, Wirtschaftswissenschaften
und Technik vertreten ist, gewinnt diese immer mehr an Bedeutung. Demzufolge rei-
fen die mathematischen Theorien, sowie die Software zunehmend aus. Es wird versucht
anwendungsrelevante Probleme durch mathematische Formulierungen und die Imple-
mentierung von Optimierungsverfahren zu lösen.
Im Folgenden wird das Teilgebiet der konvexen, nichtglatten Optimierung behandelt. In
diesem Bereich der Optimierung werden Probleme betrachtet, bei denen das Minimum
einer konvexen Funktion berechnet werden soll, wobei diese Funktion aber nicht überall
dierenzierbar ist.
Ziel dieser Arbeit besteht darin, verschiedene Methoden zu untersuchen und zu imple-
mentieren, die solche Optimierungsprobleme lösen. Diese Arbeit orientiert sich haupt-
sächlich an dem Buch Numerische Verfahren der konvexen, nichtglatten Optimierung
von Walter Alt. Als Erstes werden ein paar Grundlagen der Konvexität gelegt, danach
wird neben dem Gradientenverfahren auch das Subgradientenverfahren vorgestellt und
als Letztes wird das Bundel-Verfahren behandelt. Die besprochenen Verfahren werden
durch programmierte Beispiele in C/C++ vertieft und mit Hilfe von Scilab graphisch
veranschaulicht. Im Anhang benden sich die Quellcodes der Beispiele.
Ich möchte mich bei Herrn Prof. Dr. Borgwardt für die ausgezeichnete Betreuung und
Unterstützung während der Erstellung dieser Arbeit bedanken.
3

2. Grundlagen
2.1. Konvexe Mengen und Funktionen
Optimierungsprobleme lassen sich oft als komplexe Probleme darstellen. Diese lassen
sich dann als Minimierung einer konvexen Zielfunktion mit konvexen Nebenbedingungen
formulieren. In der Mathematik gehören die konvexen Mengen und Funktionen zu den
sehr gut untersuchten Strukturen, weshalb diese Probleme relativ leicht gelöst werden
können. Daher lohnt es sich hier besonders, die Struktur konvexer Mengen und konvexer
Funktionen herauszuarbeiten und in die Problemlösung einieÿen zu lassen.
2.1.1. Konvexe Mengen
Denition 2.1.1.1.[6] Eine Menge X R
n
heiÿt konvex, falls mit x, y X auch die
Verbindungsstrecke
[x, y] := {(1 - )x + y | 0 1}
(2.1)
zu X gehört. Durch die Abbildung 2.1 wird diese Situation graphisch verdeutlicht.
Abbildung 2.1.: konvexe und nicht konvexe Mengen [6]
Beispiel 2.1.1.2.[6] Für x R
n
, r
0 und eine beliebige Norm · auf dem R
n
sind
die oene Kugel um x mit Radius r,
B
(x, r) = {y R
n
| x - y < r},
und die abgeschlossene Kugel um x mit Radius r,
B
(x, r) = {y R
n
| x - y r},
konvexe Mengen.
Denition 2.1.1.3.[6] Eine Konvexkombination von k Vektoren x
1
, . . . , x
k
R
n
ist ein
Vektor der Form
k
i=1
i
x
i
mit
k
i=1
i
= 1 und
i
0, i = 1, . . . , k.
4

2. Grundlagen
Satz 2.1.1.4.[6] Eine Menge X R
n
ist genau dann konvex, wenn sie alle Konvex-
kombinationen von Punkten in X enthält.
Beweis zu Satz 2.1.1.4.[2], [6]
Enthält eine Menge X alle Konvexkombinationen ihrer Punkte, so auch diejenigen
Punkte z X, die mit n = 2, [0, 1] und x, y X durch z = (1-)x+y dargestellt
werden können.
Oenbar enthält eine konvexe Menge alle Konvexkombinationen z aus n = 2
Vektoren x, y X für alle [0, 1] mit z = (1 - )x + y. Es gelte also die Aussage
für n = k. Sei
k+1
i=1
i
x
i
=
k
i=1
i
x
i
+
k+1
x
i+1
= (1 -
k+1
)
k
i=1
i
x
i
1 -
k+1
+
k+1
x
i+1
so ist dies eine Konvexkombination der beiden Punkte
k
i=1
i
x
i
1-
k+1
, x
k+1
X mit
=
k+1
[0, 1]
Denition 2.1.1.5.[6] Eine nichtleere Teilmenge K R
n
heiÿt Kegel, wenn mit x K
auch {x | > 0} K ist.
Satz 2.1.1.6.[6] Sind X
1
, X
2
R
n
nichtleere, konvexe Mengen mit intX
2
= und
X
1
intX
2
= , dann gibt es eine Hyperebene, die X
1
und X
2
trennt, d.h., es gibt ein
s
R
n
, s
= 0
n
und r R mit
sup
xX
1
s
T
x
r inf
yX
2
s
T
y.
Weiter gilt s
T
y > r
für alle y intX
2
, d.h., X
2
ist nicht in der Hyperebene enthalten.
2.1.2. Konvexe Funktionen
Denition 2.1.2.1.[6] Ist X R
n
eine nichtleere, konvexe Menge, dann heiÿt die
Funktion f : X R konvex, wenn
f
((1 - )x + y) (1 - )f(x) + f(y)
für alle x, y X und alle ]0, 1[ gilt.
Abbildung 2.2.: konvexe Funktion [6]
5

2. Grundlagen
Beispiel 2.1.2.2.[6] Die durch f(x) = x, f(x) = x
2
und f(x) = |x| denierten Funk-
tionen f : R R sind konvex. Die Funktion
f
: R
n
R, f(x) =
n
i=1
x
2
i
= x, x = x
2
ist konvex. Ist · eine beliebige Norm auf R
n
, dann ist die Funktion f : R
n
R mit
f
(x) = x konvex.
Lemma 2.1.2.3.[6] Sind f
1
, . . . , f
m
ConvR
n
, t
1
, . . . , t
m
positive, reelle Zahlen und
gibt es ein x R
n
mit f
j
(x) < +, j = 1, . . . , m, dann ist auch die Funktion f :=
m
j=1
t
j
f
j
konvex.
2.2. Lokale Lipschitz-Stetigkeit
Zu diesem Thema wird neben dem oben genannten Buch ebenfalls die Literatur von
Carl Geiger und Christian Kanzow: Theorie und Numerik restringierter Optimierungs-
aufgaben verwendet.
Denition 2.2.1.[6] Ist X R
n
nichtleer und f : R
n
R, dann heiÿt f lokal Lipschitz-
stetig auf X, wenn es zu jedem z X ein = (z) > 0 und ein L = L(z) 0 gibt, so
dass
|f(x) - f(y)| L x - y
x, y B(z, )
gilt, d.h., f ist Lipschitz-stetig auf B(z, ).
Falls X nicht oen ist, so kann die lokale Lipschitz-Stetigkeit nicht auf ganz X ausgesagt
werden. Man betrachte dazu das folgende Beispiel:
Beispiel 2.2.2.[2] f : [0, 1] R, f(x) :=
0, falls 0 x < 1,
1, falls x = 1.
Hier ist die Funktion f im Punkt x = 1 noch nicht einmal stetig.
Satz 2.2.3.[2] Seien X R
n
eine konvexe Menge und f : X R eine konvexe
Funktion. Dann ist f lokal Lipschitz-stetig auf dem Inneren von X.
Um dies zu zeigen, wird zunächst das folgende Hilfsresultat betrachtet:
Lemma 2.2.4.[6] Ist f ConvR
n
und gilt für z int(domf) und , m, M R
m
f(x) M x B(z, 2),
(2.2)
d.h., f ist auf B(z, 2) beschränkt, dann ist
|f(x) - f(y)|
M
- m
x
- y
x, y B(z, ),
(2.3)
d.h., f ist auf B(z, ) Lipschitz-stetig.
Beweis zu Lemma 2.2.4.[2], [6]
Es seien x, y B(z, ) mit x = y beliebig. Man deniere
v
:= y +
y
- x
y
- x
.
6

2. Grundlagen
Wegen v - z v - y + y - z < 2 ist v B(z, 2) und
y
=
y
- x
+ y - x
v
+
+ y - x
x,
d.h., y ist eine Konvexkombination der Vektoren v und x. Verwendet man die Konvexität
von f sowie (2.2), so erhält man
f
(y) - f(x)
y
- x
+ y - x
[f(v) - f(x)]
1
y
- x (M - m).
Vertauscht man x und y, so hat man entsprechend
f
(x) - f(y)
y
- x
+ y - x
[f(v) - f(y)]
1
y
- x (M - m).
Dies ergibt zusammen die gewünschte Ungleichung (2.3). Da x int(X) beliebig vor-
gegeben war, ist damit die lokale Lipschitz-Stetigkeit von f nachgewiesen.
Korollar 2.2.5.[6] Eine Funktion f ConvR
n
ist auf einer konvexen und kompakten
Menge S int(domf) Lipschitz-stetig, d.h., es gibt ein L = L(S) 0, so dass
|f(x) - f(y)| L x - y
x, y S
gilt.
2.3. Subdierential und Richtungsableitung
Bevor auf das konvexe Subdierential eingegangen werden kann, wird noch eine weitere
wichtige Eigenschaft einer konvexen Funktion behandelt: die Richtungsableitung bzw.
-dierenzierbarkeit.
Als Erstes wird gezeigt, dass für jede konvexe Funktion f die Richtungsableitung exis-
tiert. Dabei wird vorausgesetzt, dass die Menge X oen ist.
Denition 2.3.1.[2], [6] Die Richtungsableitung von f im Punkt x X in Richtung
d
R
n
ist deniert durch
f
(x, d) := lim
t0
f
(x + td) - f(x)
t
= inf
t>0
f
(x + td) - f(x)
t
,
(2.4)
sofern der rechts stehende Grenzwert existiert.
Lemma 2.3.2.[2] Seien X R
n
eine oene und konvexe Menge, f : X R eine
konvexe Funktion, x X und d R
n
. Dann gilt:
a) Der Dierenzenquotient
q
(t) :=
f
(x + td) - f(x)
t
ist monoton fallend für t 0, d.h., es ist q(t
1
) q(t
2
) für alle 0 < t
1
< t
2
mit
x
+ t
2
d
X.
b) Die Richtungsableitung von f im Punkt x in Richtung d existiert und es ist
f
(x, d) := inf
t>0
f
(x + td) - f(x)
t
.
7

2. Grundlagen
Beweis zu Lemma 2.3.2.[2]
a) Seien 0 < t
1
< t
2
mit x + t
2
d
X (und damit auch x + t
1
d
X). Wegen der
Konvexität von f gilt
f
(x + t
1
d
) = f
t
1
t
2
(x + t
2
d
) + (1 -
t
1
t
2
)x
t
1
t
2
f
(x + t
2
d
) + (1 -
t
1
t
2
)f(x).
Diese Ungleichung impliziert
q
(t
1
) =
f
(x + t
1
d
) - f(x)
t
1
f
(x + t
2
d
) - f(x)
t
2
= q(t
2
).
Dies ist die Behauptung.
b) Seien t, > 0 mit x - d X und x + td X gegeben. Da f konvex ist,gilt
f
(x) = f
t
t
+
(x - d) +
t
+
(x + td)
t
t
+
f
(x - d) +
t
+
f
(x + td).
also
q
(t) =
f
(x + td) - f(x)
t
f
(x) - f(x - d)
.
Daraus ergibt sich,dass der Dierenzenquotient q(t) für t 0 durch die konstan-
te Gröÿe
f (x)-f (x- d)
nach unten beschränkt ist. Andererseits ist q(t) nach (a)
monoton fallend für t 0. Hieraus kann man schlieÿlich die Existenz der Rich-
tungsableitung f (x, d) mit der Eigenschaft
f
(x, d) = lim
t0
f
(x + td) - f(x)
t
= inf
t>0
f
(x + td) - f(x)
t
folgern und damit ist auch b) bewiesen.
Da nun die Vorbereitungen abgeschlossen sind,kann jetzt auf das Subdierential einge-
gangen werden.
Denition 2.3.3.[2] Seien X R
n
eine oene und konvexe Menge, f : X R eine
konvexe Funktion und x X. Ein Vektor s R
n
heiÿt Subgradient von f in x,wenn
gilt
f
(y) f(x) + s
T
(y - x) y X.
(2.5)
Die Menge der Subgradienten von f in x heiÿt das (konvexe) Subdierential von f in
x
und wird mit f(x) bezeichnet. Geometrisch gesehen enthält der Subgradient jene
verallgemeinerten Tangenten,die unterhalb der Funktion liegen (vgl. Abb. 2.3).
Beispiel 2.3.4.[2] Die Funktion f : R R sei durch f(x) = |x| deniert.
f
(x) =
{1},
falls x > 0,
[-1, 1], falls x = 0,
{-1},
falls x < 0.
8

2. Grundlagen
Abbildung 2.3.: Subgradient einer konvexen Funktion
Ist die Funktion f in x dierenzierbar und ist s ein Subgradient von f in x X, so
folgt aus f(x + td) - f(x) ts
T
d
für alle d R
n
und alle t > 0 mit x + td X nach
Division durch t und Grenzübergang t 0
f(x)
T
d
s
T
d
d R
n
.
Speziell für d = s - f(x) ergibt dies
s
= f(x).
Das Subdierential f(x) enthält im dierenzierbaren Fall genau einen Vektor, nämlich
den Gradienten f(x).Daher kann das Subdierential f(x) als Verallgemeinerung des
üblichen Gradienten angesehen werden.
Wie man solch eine Funktion optimiert wird später in Kapitel 4erklärt.
Als Nächstes werden einige wichtige Eigenschaften des Subdierentials bewiesen, die
zeigen, wie das Subdierential und die Richtungsableitung zusammen hängen.
Satz 2.3.5.[2], [6] Seien X R
n
eine oene und konvexe Menge, f : X R eine
konvexe Funktion und x X.Dann besitzt das Subdierential von f in x folgende
Eigenschaften:
a) Das Subdierential f(x) ist eine nichtleere, konvexe und kompakte Menge.
b) Es gilt
f
(x) = {s R
n
|s
T
d
f (x, d) für alle d R
n
}
c) Für die Richtungsableitung von f in x gilt
f
(x, d) = max
sf (x)
s
T
d
für alle d R
n
.
Beweis von Satz 2.3.5.[2], [6]
b
)
Sei s f(x), dann gilt für beliebiges d R
n
f
(x + td) f(x) + t(s
T
d
) t 0,
also
f
(x + td) - f(x)
t
s
T
d
t > 0.
9

2. Grundlagen
Für t 0 folgt daraus s
T
d
f (x, d).
Ist s R
n
mit s
T
d
f (x, d) für alle d R
n
, dann gilt für eine beliebige Richtung
d
R
n
wegen der rechten Seite von (2.4)
s
T
d
f (x, d)
f
(x + td) - f(x)
t
t > 0.
Ist x + d domf, dann ist [x, x + d] domf und für t = 1 folgt
f
(x + d) f(x) + s
T
d.
Ist x + d / domf, so ist f(x + d) = +. Somit ist die obige Ungleichung auch hier
erfüllt. D.h., f(x + d) f(x) + s
T
d
gilt für alle d R
n
. Für beliebiges y R
n
folgt
jetzt mit d := y - x
f
(y) = f(x + d) f(x) + s
T
(y - x),
d.h. s f(x).
a
)
Nach (b) folgt, dass f(x) der Durchschnitt der abgeschlossenen Halbräume {s
R
n
| s
T
d
f (x, d)}, d R
n
und damit selbst abgeschlossen und konvex ist. Aus
(b) kann ebenso gefolgert werden, dass f(x) beschränkt ist. Dazu verwendet man den
i
-ten Einheitsvektor e
i
= (0, . . . , 0, 1, 0, . . . , 0)
T
,
dann gilt für jeden Vektor s f(x)
s
max
i=1,...,n
f
(x, ±e
i
).
die Menge f(x) ist kompakt.
Nun bleibt noch zu zeigen, dass die Menge f(x) nichtleer ist. Dies wird zusammen mit
(c) bewiesen.
c
)
Man betrachte die beiden konvexen, nichtleeren Mengen
K
1
:= {(y, z) X × R | z > f(y)},
K
2
:= {(y, z) X × R | y = x + td, z = f(x) + tf (x, d), t > 0},
x
X ist dabei der vorgegebene Punkt und d R
n
ist ein beliebiger Vektor. K
1
ist
eine Säule oberhalb des Graphen f und K
2
ist der vom Punkt (x, f(x)) ausgehende
Stahl in Richtung (d, f (x, d)). Um die Konvexität von K
1
nachzuweisen, folgert man
aus (y, z), (~y, ~z) K
1
mit (0, 1)
z
+ (1 - )~z > f(y) + (1 - )f(~y) f(y + (1 - )~y),
also (y, z) + (1 - )(~y, ~z) K
1
.
Weiter gilt
K
1
K
2
= .
Denn (y, z) K
1
K
2
bedeutet, dass es ein t > 0 gibt, so dass
f
(y) < z = f(x) + tf (x, d) mit y = x + td
gilt. Daraus erhält man
f
(x + td) - f(x)
t
< f
(x, d).
10

2. Grundlagen
Dies widerspricht jedoch Lemma 2.3.2. b).
Man kann zwei disjunkte nichtleere und konvexe Mengen mittels einer Hyperebene
trennen, d.h., es gibt einen Vektor 0
n
= (s, ) R
n
× R mit
s
T
y
+ z s
T
(x + td) + (f(x) + tf (x, d))
(2.6)
y X, z R mit z > f(y) und t > 0.
Nun werden drei Fälle betrachtet:
· Fall > 0 : Setzt man in (2.6) y := x ein und führt den Grenzübergang t 0
aus, so erhält man z f(x), z R mit z > f(y). Dies ist allerdings nicht
möglich.
· Fall = 0 : Die Bedingung (2.6) wird hier nach Grenzübergang t 0 zu
s
T
y
s
T
x
y X.
Für ein hinreichend kleines > 0 gehört auch y := x + s zu X, da x ein innerer
Punkt von X ist. Für dieses spezielle y ergibt sich die obige Ungleichung, jedoch
ist s
T
s
0, also s = 0. Dies ist allerdings ein Widerspruch zu der Voraussetzung
(s, ) = (0, 0). Aus diesem Grund kann auch dieser Fall nicht eintreten.
· Fall < 0 : Man setze o.B.d.A. = -1. Aus (2.6) erhält man hier nach dem
Grenzübergängen z f(y), t 0
s
T
y
- f(y) s
T
x
- f(x) y X,
d.h., es ist s f(x)
f(x) = .
Wenn man aber y := x in (2.6) einsetzt, so folgt
s
T
x
- z s
T
(x + td) - f(x) + tf (x, d)
z > f(x) und t > 0.
Der Grenzübergang z f(x) und t := 1 liefert
f
(x, d) s
T
d.
Allerdings gilt nach (b) s
T
d
f (x, d)
Beh.
Möchte man zur Lösung konvexer Optimierungsprobleme numerische Verfahren anwen-
den, auf die später noch genauer eingegangen werden, muss man zu einem gegebenen x
den Subgradienten s f(x) berechnen. Dazu wird nun noch eine einfache Rechenregel
für Subdierentiale bewiesen.
Satz 2.3.6.[6] Sind f
1
, f
2
: R
n
R konvexe, überall endliche Funktionen und t
1
, t
2
positive, reelle Zahlen, dann gilt
(t
1
f
1
+ t
2
f
2
)(x) = t
1
f
1
(x) + t
2
f
2
(x) x R
n
.
Beweis von Satz 2.3.6.[6] Die Funktion f := t
1
f
1
+ t
2
f
2
ist nach Lemma 2.1.2.3 konvex.
Weiter gilt für x R
n
(1)
f
(x, ·) = t
1
f
1
(x, ·) + t
2
f
2
(x, ·).
11

2. Grundlagen
Nach Satz 2.3.5. b) ist daher
(2)
f
(x) = {s R
n
| s
T
d
t
1
f
1
(x, d) + t
2
f
2
(x, d) für alle d R
n
}.
Wendet man Satz 2.3.5. b) auf f
1
und f
2
an, so folgt für beliebiges s
1
f
1
(x) und
s
2
f
2
(x)
t
1
s
1
, d
+ t
2
s
2
, d
t
1
f
1
(x, d) + t
2
f
2
(x, d) d R
n
,
also wegen (2) t
1
s
1
+ t
2
s
2
f(x). Damit folgt
F
:= t
1
f
1
(x) + t
2
f
2
(x) f(x).
Die umgekehrte Inklusion wird durch Widerspruch bewiesen. Dazu wird angenommen,
dass es ein s f(x) mit s / F gibt. Da die Menge F nichtleer, konvex und kompakt
ist, gibt es einen Vektor 0
n
= d R
n
mit
s
T
d >
max
sF
s
T
d.
Mit s
1
f
1
(x), s
2
f
2
(x) ist s = t
1
s
1
+ t
2
s
2
F . Dies gilt speziell für s
i
f
i
(x), i = 1, 2, mit
(s
i
)
T
d
= max
sf
i
(x)
s
T
d.
Daher ist
s
T
d >
max
sF
s
T
d
= t
1
max
sf
1
(x)
s
T
d
+ t
2
max
sf
2
(x)
s
T
d.
Nach Satz 2.3.5. c) folgt daraus wegen s f(x)
f
(x, d) s
T
d > t
1
f
1
(x, d) + t
2
f
2
(x, d)
im Widerspruch zu (1).
Beispiel 2.3.7.[6] Sind f
1
, f
2
: R
n
R konvexe, überall endliche Funktionen, dann gilt
nach Satz 2.3.6 (setze t
1
= t
2
= 1)
(f
1
+ f
2
)(x) = f
1
(x) + f
2
(x) x R
n
.
Sind allgemeiner f
i
: R
n
R, i = 1, . . . , m, konvexe Funktionen und ist f : R
n
R
durch f(x) =
m
i=1
f
i
(x) deniert, dann ist f nach Lemma 2.1.2.3 konvex und durch
wiederholte Anwendung von Satz 2.3.6 erhält man
f
(x) = f
1
(x) +
m
i=2
f
i
(x)
f(x) =
m
i=1
f
i
(x)
für alle x R
n
. Die Funktion
f
(x) =
m
i=1
t
i
f
i
(x)
ist mit positiven reellen Zahlen t
i
, i
= 1, . . . , m, nach Lemma 2.1.2.3 konvex und durch
wiederholte Anwendung von Satz 2.3.6 erhält man schlieÿlich
f
(x) = t
1
f
1
(x) +
m
i=2
t
i
f
i
(x)
12

2. Grundlagen
f(x) =
m
i=1
t
i
f
i
(x)
für alle x R
n
. Um einen speziellen Subgradienten s f(x) zu erhalten, kann man
also beliebige Subgradienten s
i
f
i
(x) wählen und dann s =
m
i=1
t
i
s
i
berechnen.
2.4. Konvexe Optimierungsprobleme
Wenn man von einem konvexen Optimierungsproblem spricht, dann ist sowohl die Ziel-
funktion f : X R als auch die zulässige Menge X R
n
konvex. Das Ziel hierbei ist
ein Minimum der Funktion f auf der zulässigen Menge X zu berechnen. Dies wird wie
folgt ausgedrückt
(P ) min
xX
f
(x)
Die Menge X kann Restriktionen denieren, die in der Regel durch Gleichungen und
Ungleichungen dargestellt werden.
(P L)
min
xR
n
f
(x)
unter g
i
(x) 0 i = 1, . . . , m
h
j
(x) = 0 j = 1, . . . , p.
Eine wichtige Eigenschaft der konvexen Optimierung im Unterschied zur nicht konvexen
Optimierung ist, dass jedes lokale Optimum auch ein globales Optimum ist.
Denition 2.4.1. [6] Ein Punkt x
X heiÿt (globaler) Minimalpunkt von f auf X,
falls
f
(x) f(x
) x X
gilt. Ist x
Lösung von (P ), dann heiÿt f(x
) Optimal- bzw. Minimalwert von f.
2.4.1. unrestringierte Optimierungsaufgaben
Ist die Menge X = R
n
, dann spricht man von einem Optimierungsproblem ohne Re-
striktionen oder von einem unrestringiertem Optimierungsproblem. Hierbei ist die Ziel-
funktion f : R
n
R konvex und endlich.
(P U)
min
xR
n
f
(x)
Aus der Denition der Richtungsableitung und des Subdierentials kann man nun die
folgende Charakterisierung einer Lösung von (P U) folgern
Satz 2.4.2. [6] Für eine konvexe Funktion f : R
n
R sind die folgenden Aussagen
äquivalent:
a) x
ist Lösung von (P U),
b) 0
n
f(x
),
c) f (x
, d
) 0 für alle d R
n
.
13

2. Grundlagen
Beweis zu Satz 2.4.2. [6]
(a) (b)
Es gilt f(x) f(x
) für alle x R
n
genau dann, wenn
f
(x) f(x
) + 0
n
, x
- x
x R
n
gilt. Dies ist äquivalent zu 0
n
f(x
).
(a) (c)
Auf Grund der Optimalität von x
ist f(x
+ td) - f(x
) 0 für al-
le t R und d R
n
beliebig gilt
1
t
(f(x
+ td) - f(x
)) 0 t > 0.
Für t 0 erhält man f (x
, d
) 0.
(c) (a)
Nach Denition der Richtungsableitung ist für ein beliebiges x R
n
0 f (x
, x
- x
)
f
(x
+ 1(x - x
)) - f(x
)
1
= f(x) - f(x
),
womit (a) folgt.
Wenn f konvex und dierenzierbar ist, so wird (b) die notwendige und hinreichend
Optimalitätsbedingung f(x
) = 0
n
. Der Ausgangspunkt für die Konstruktion vom
Optimierungsverfahren ist allerdings, wie im dierenzierbaren Fall, die Charakterisie-
rung eines Minimums von Satz 2.4.2.
2.5. Abstiegsrichtungen
Um am Bestmöglichsten ein Minimum einer Funktion berechnen zu können, ist es emp-
fehlenswert Optimierungsverfahren so zu konstruieren, dass eine iterative Folge x
(k)
mit
Startwert x
(0)
und
f
(x
(k+1)
) < f(x
(k)
), k = 0, 1, . . .
(2.7)
berechnet wird. Solche Verfahren nennt man Abstiegsverfahren. Ausgehend von dem
aktuellen Iterationspunkt x
(k)
wird eine Suchrichtung d
(k)
R
n
und eine Schrittweite
t
k
>
0 berechnet, so dass die Bedingung (2.7) mit x
(k+1)
:= x
(k)
+t
k
d
(k)
erfüllt ist, d.h.,
in Richtung d
(k)
müssen die Funktionswerte von f abnehmen, also monoton fallen.
Denition 2.5.1.[6] Für f : R
n
R und x R
n
heiÿt ein Vektor d R
n
Abstiegs-
richtung von f in x, wenn es ein t > 0 mit f(x + td) < f(x) gibt.
Satz 2.5.2.[6] Für eine konvexe Funktion f : R
n
R und x, d R
n
sind folgende
Aussagen äquivalent:
a) d ist Abstiegsrichtung von f in x,
b) f (x, d) < 0,
c) max
sf (x)
s, d <
0.
14

2. Grundlagen
Beweis zu Satz 2.5.2. [6]
(a) (b)
Ist d Abstiegsrichtung von f in x, d.h., es gibt ein t > 0 mit f(x + td) <
f
(x), dann folgt aus der Denition der Richtungsableitung
f
(x, d)
f
(x + td) - f(x)
t
<
0,
also gilt (b).
(b) (a) Ist f (x, d) < 0, d.h., es gilt
0 > f (x, d) = lim
t0
f
(x + td) - f(x)
t
,
dann muss f(x + td) - f(x) < 0 sein, wenn t > 0 hinreichend klein ist. Somit gilt (a).
(b) (c) folgt aus f (x, d) = max
sf (x)
s, d
(vgl. Satz 2.3.5. (c)).
Falls x
(k)
beim Iterationsverfahren nicht optimal ist, dann gibt es nach Satz (2.4.2.
(c)) eine Richtung d
(k)
mit f (x
(k)
, d
(k)
) < 0. Nach obigen Satz ist d
(k)
Abstiegsrich-
tung in x
(k)
. Um eine solche Richtung zu berechnen, sollte man zuerst die eindeutige
Projektion s
(k)
von 0
n
auf f(x
(k)
) bestimmen. Ist s
(k)
= 0
n
,
dann ist 0
n
f(x
(k)
),
d.h., x
(k)
ist Lösung von (P U). Andernfalls zeigt das folgende Resultat, dass s
(k)
eine
Abstiegsrichtung deniert.
Satz 2.5.3.[6] Ist s
(k)
= 0
n
die eindeutig bestimmte Projektion von 0
n
auf f(x
(k)
),
dann ist d
(k)
:= -s
(k)
/ s
(k)
eine Abstiegsrichtung von f in x
(k)
und es gilt
f
(x
(k)
, d
(k)
) = - s
(k)
,
f
(x
(k)
,
-s
(k)
) = - s
(k) 2
.
Um diesen Satz beweisen zu können, wird noch ein Satz eingeführt indem gezeigt wird,
wie die Lösungen von Projektionen charakterisiert werden. Dieses Ergebnis kann dann
in folgendem Beweis verwendet werden.
Satz 2.5.4.[6] Für eine nichtleere, abgeschlossene und konvexe Menge X R
n
und
Punkte z R
n
,
^x X ist ^x = P
C
(z) genau dann, wenn
z
- ^x, x - ^x 0 x X
gilt.
Beweis von Satz 2.5.3.[6] Da s
(k)
die Projektion von 0
n
auf f(x
(k)
) ist, folgt aus obigem
Satz
0
n
- s
(k)
, s
- s
(k)
0 s f(x
(k)
).
Deswegen ist s - s
(k)
, d
(k)
0 für s f(x
(k)
), oder äquivalent
s, d
(k)
s
(k)
, d
(k)
= - s
(k)
s f(x
(k)
).
Daraus ergibt sich wegen s
(k)
f(x
(k)
)
f
(x
(k)
, d
(k)
) = max
sf (x
(k)
)
s, d
(k)
= - s
(k)
<
0,
d.h., d
(k)
ist Abstiegsrichtung von f in x
(k)
.
f
(x
(k)
,
·) ist positiv homogen f (x
(k)
,
-s
(k)
) = - s
(k) 2
.
15

2. Grundlagen
Da man in der Regel das Subdierential nicht vollständig berechnen kann, bzw. eini-
ge Probleme dabei entstehen können, scheitert diese Vorgehensweise leider. Schlieÿlich
muss bei der Konstruktion von Verfahren nur davon ausgegangen werden, dass folgendes
gilt
(S1) Zu jedem Vektor x R
n
kann man (mindestens) einen Subgradienten s(x)
f
(x) berechnen.
Später werden noch zwei Verfahren behandelt, die zu ihrer Konstruktion mit (S1) aus-
kommen:
· Subgradientenverfahren: ein Subgradient s
(k)
f(x
(k)
) wird in der k-ten Itera-
tion berechnet und d
(k)
:= -s
(k)
wird als Suchrichtung verwendet. Normalerweise
erhält man dabei keine Abstiegsrichtung, aber bei geeigneter Wahl der Schrittwei-
ten zumindest schwache Konvergenzresultate.
· Bundle-Verfahren: Man berechnet approximative Abstiegsrichtungen und dazu
passende Schrittweiten, so dass man ein Abstiegsverfahren erhält.
2.6. Lagrange-Multiplikatoren
Um Optimierungsprobleme mit Nebenbedingungen umformulieren zu können, spielen
Lagrange-Multiplikatoren eine wichtige Rolle. Angenommen die Aufgabe ist es ein lo-
kales Extremum einer Funktion in mehreren Veränderlichen mit einer oder mehreren
Nebenbedingungen zu nden wobei die Nebenbedingungen durch Setzen von Funktio-
nen auf gegebene Werte deniert seien. Diese Methode führt eine neue unbekannte
skalare Variable für jede Nebenbedingung ein, die Lagrange Multiplikatoren, und de-
niert eine Linearkombination die die Multiplikatoren als Koezienten einbindet. Das
reduziert das Nebenbedingungsproblem auf ein Problem ohne Nebenbedingung. Damit
kann es dann durch die gewöhnliche Gradientenmethodemethode gelöst werden.
Denition 2.6.1.[4] Die Vektoren R
m
und R
p
heiÿen Lagrange-Multiplikatoren,
wenn
(x, , ) L(x, , ) := f(x) +
m
i=1
i
g
i
(x) +
p
j=1
j
h
j
(x)
gilt, wobei g
i
(x) und h
i
(x) Restriktionen sind.
Satz 2.6.2.[6] Ein Punkt x
X ist genau dann Lösung von (P L), wenn es Lagrange-
Multiplikatoren R
m
und R
p
zu x
gibt.
16

3. Das Gradientenverfahren
In diesem Kapitel wird als erstes konkretes Verfahren, das sogenannte Gradientenver-
fahren, häug auch das Verfahren des steilsten Abstiegs bezeichnet, untersucht.Bei
diesem Verfahren bestimmt man im Punkt x
(k)
diejenigen Richtungen d
(k)
, in der f am
stärksten abnimmt.Auÿerdem bedarf es dazu einer stetig dierenzierbaren Zielfunktion.
Um dies zu verdeutlichen wurde dieses Verfahren in C/C++ implementiert und auf ein
Beispiel, auf das später genauer eingegangen wird, angewendet.
3.1. Das Verfahren
Algorithmus 3.1.1.[6] (Gradientenverfahren)
Wähle einen Startpunkt x
(0)
R
n
und setze k := 0.
1.Berechne f(x
(k)
).
2.Abbruchkriterium: Falls f(x
(k)
) = 0
n
, dann stoppe das Verfahren.
3.Berechne zu d
(k)
= -f(x
(k)
) eine Schrittweite t
k
>
0 durch Lösung des eindi-
mensionalen Minimierungsproblems min
t0
h
(t) := f(x
(k)
+ td
(k)
).
4.Setze x
(k+1)
:= x
(k)
+ t
k
d
(k)
, k
:= k + 1 und gehe zu 1 zurück.
Zu Beginn des Verfahrens wird ein Startpunkt x
(0)
R
n
gewählt, wobei k = 0 gilt.
Auÿerdem wird der Gradient der Zielfunktion f(x
(k)
) berechnet.
Nun gibt es zwei verschiedene Möglichkeiten um das Verfahren weiterzuführen:
1.Falls f(x
(k)
) = 0
n
gilt, wird das Verfahren abgebrochen.
2.Falls f(x
(k)
) = 0
n
gilt, so wird eine Suchrichtung d
(k)
= -f(x
(k)
), also die
Richtung des steilsten Abstieges, in f in x
(k)
bestimmt.
Um nun den nächten Punkt x
(k+1)
zu erhalten, an dem die Funktion untersucht werden
soll, muss noch eine möglichst eziente Schrittweite t
k
>
0 verwendent werden, so dass
die Iterationsvorschrift
x
(k+1)
= x
(k)
+ t
k
d
(k)
,
k > 0
bzw.
x
(k+1)
= x
(k)
- t
k
f(x
(k)
), k > 0
erfüllt ist.Der Faktor t
k
lässt sich auf viele verschiedene Weisen berechnen.Hier wird
jedoch die Strahlenminimierung, bzw.das CAUCHY-Prinzip verwendet.Dabei soll das
eindimensionale Minimierungsproblem
min
t0
h
(t) := f(x
(k)
+ td
(k)
)
gelöst werden.Damit ergibt sich die exakte Schrittweite aus dem folgenden Term
t
k
=
f(x
(k)
)
T
f(x
(k)
)
f(x
(k)
)
T
2
f
(x
(k)
)f(x
(k)
)
=
-f(x
(k)
)
T
d
(k)
(d
(k)
)
T
2
f
(x
(k)
)d
(k)
.
17

3. Das Gradientenverfahren
Dieses Verfahren gilt zwar als robust, erfüllt aber keine hohen Genauigkeitsansprüche
und konvergiert langsam.
Die exakte Schrittweite, die hier verwendet wurde, wird allerdings nur für theoreti-
sche Zwecke oder bei quadratischen Optimierungsproblemen benutzt. Praktisch benö-
tigt man ein numerisches Verfahren zur Schrittweitenberechenung.
Allerdings sind die theoretischen Konvergenzaussagen nicht erfüllt, wenn f eine nicht-
glatte Funktion und x
der Minimalpunkt von f ist und f in x
nicht dierenzierbar ist.
Folglich wird das Abbruchkriterum im zweiten Schritt niemals erreicht und ist somit
nicht anwendbar. Daher kann man nicht erwarten, dass das Gradientenverfahren in die-
sem Fall ein Minimum von f berechnet. Dazu werden später einige Beispiele betrachtet.
3.2. Schrittweitenbestimmung
Bevor das Gradientenverfahren an einem Beispiel genauer betrachtet wird, werden nun
noch andere, bekannte Schrittweitenverfahren vorgestellt. Die Informationen dazu stam-
men aus den Büchern: Numerische Verfahren zur Lösung unrestringierter Optimie-
rungsaufgaben von Carl Geiger und Christian Kanzow und Nichtlineare Optimierung:
Eine Einführung in Theorie, Verfahren und Anwendungen von Walter Alt.
Man geht für die folgenden Verfahren von folgender Situation aus: f : R
n
R sei
stetig dierenzierbar und die zu minimierende Zielfunktion, x R
n
sei die aktuelle Nä-
herung und d R
n
eine Abstiegsrichtung, die die hinreichende Bedingung f(x)
T
d <
0
erfüllt. Vom Prinzip her haben alle Verfahren das selbe Ziel: es wird immer versucht
eine Schrittweite t > 0 zu bestimmen, so dass die Hilfsfunktion
(t) := f(x + td), t 0
näherungsweise minimiert wird, bzw. im ausreichenden Maÿe verkleinert wird.
Wegen (t) = f(x + td)
T
d
gilt (0) < 0. Deswegen fällt für kleine t-Werte:
t
0
>
0 : t ]0, t
0
[: (t) < (0).
3.2.1. Armijo-Regel
Das wohl am weitesten verbreitete und am meisten angewandte Verfahren ist das
Schrittweitenverfahren von Armijo.
Die Zahlen (0, 1) und (0, 1) sind für das gesamte Verfahren fest vorgegeben.
Man wähle die Schrittweite t := max{
l
| l = 0, 1, 2, . . . }, so dass gilt
f
(x + td) f(x) + tf(x)
T
d.
(3.1)
Zur Berechnung von t hat man also die Ungleichung (3.1) nacheinander für t =
l
, l
=
0, 1, 2, . . . , zu überprüfen und nach ihrer erstmaligen Gültigkeit abzubrechen. Um dies
besser in Abbildung 3.1 zu veranschaulichen wird := f(x + td) deniert und die
Armijo-Bedingung lautet somit:
(t) (0) + t (0).
Aus dem Bereich, indem der Graph von unterhalb der sog. Armijo-Goldstein-Geraden
durch (0, (0)) mit der Steigung (0) verläuft, ist somit die Schrittweite t die gröÿte
der Zahlen
l
, l
= 0, 1, 2, . . . zu nehmen.
18

3. Das Gradientenverfahren
Abbildung 3.1.: Armijo-Schrittweite
3.2.2. Wolfe-Powell-Regel
Bei dem Wolfe-Powell-Schrittweiten-Verfahren seien die Zahlen (0,
1
2
) und [, 1)
fest vorgegeben. Man bestimme hier ebenso wie bei der Armijo-Regel, die Schrittweite
t >
0 mit
f
(x + td) f(x) + tf(x)
T
d
(3.2)
und
f(x + td)
T
d
f(x)
T
d.
(3.3)
Die Hilfsfunktion (t) := f(x + td) wird auch hier benutzt um das Ganze besser zu ver-
anschaulichen (siehe Abb. 3.2). Auÿerdem werden die Wolfe-Powell-Bedingungen (3.2)
und (3.3) zu
(t) (0) + t (0)
und
(t) (0).
Abbildung 3.2.: Wolfe-Powell-Schrittweiten
In diesem Fall ist die Schrittweite aus einem Bereich zu wählen, so dass der Graph von
einerseits unterhalb der Armijo-Goldstein-Geraden durch (0, (0)) mit Steigung
(0) verläuft und in dem andererseits, grob gesprochen, der Graph von nicht mehr
so steil wie in der Nähe von t = 0 abfällt oder bereits ansteigt.
19

3. Das Gradientenverfahren
3.2.3. Bisektion
Die Bisektion ist ein Verfahren welches auf Halbierung eines Intervalls beruht. Dieses
Verfahren wird in den später folgenden Beispielen, die auch programmiert sind, verwen-
det. Bei diesem Verfahren wird die Funktion f : R
n
R, ausgehend vom Startpunkt
x
0
in Richtung d R
n
minimiert. Hierbei ist wichtig, dass f stetig ist.
Zunächst nimmt man an, dass es ein Intervall I = [a, b] gibt mit f(a) · f(b) < 0.
Dieses Intervall wird später so oft verkleinert, bis man schlieÿlich die lokale Minimal-
stelle erhält. Aus Stetigkeitsgründen existiert eine Lösung s im Inneren von I, so dass
f
(s) = 0 erfüllt ist. Für den Mittelpunkt = (a + b)/2 wird der Funktionswert f()
berechnet. Wenn f() = 0 gilt, dann entscheidet das Vorzeichen, in welchem der beiden
Teilintervalle [a, ] und [, b] die gesuchte Lösung s ist.
Abbildung 3.3.: Verfahren der Bisektion [3]
Falls jedoch bereits der erste Teilschritt so groÿ ist, dass man über dem anfänglichen
Wert landet, muss man zunächst eine Schrittweite nden, deren Wert kleiner ist als der
Anfangswert. Dazu wird die Anfangs-Intervall-Länge solange halbiert, bis dieses Ziel
erreicht ist. Gleichzeitig wird die Anzahl der folgenden Bisektionsschritte reduziert.
Falls der erste Teilschritt in der Funktion abwärts führt, muss jetzt ein Punkt gefunden
werden, wo der Funktionswert stagniert oder wieder zunimmt.
Jetzt kann auf der Linie x
0
+ td das sogenannte Linien-Minimum gesucht werden.
Hier wird die einfache Bisektion dafür verwendet.
3.3. Beispiele
Um die Theorie nun zu verdeutlichen, werden im Folgenden einige Beispiele angeführt.
Diese Beispiele wurden in C/C++ und deren Graken in Scilab programmiert (siehe
Anhang). Auÿerdem wurde in allen Beispielen die Bisektions-Regel bzw. die Linien-
Minimierung als Schrittweitenverfahren gewählt.
20
Ende der Leseprobe aus 104 Seiten

Details

Titel
Nichtglatte Optimierung
Hochschule
Universität Augsburg  (Mathematik)
Note
1,7
Autor
Jahr
2010
Seiten
104
Katalognummer
V232845
ISBN (eBook)
9783656503071
ISBN (Buch)
9783656503842
Dateigröße
3293 KB
Sprache
Deutsch
Schlagworte
nichtglatte, optimierung
Arbeit zitieren
Bachelor of Science Irene Filipiak (Autor), 2010, Nichtglatte Optimierung, München, GRIN Verlag, https://www.grin.com/document/232845

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Nichtglatte 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