Die Optimierung ist ein sehr wichtiger Bestandteil unserer heutigen Gesellschaft geworden.
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 erfolgreichen
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 reifen
die mathematischen Theorien, sowie die Software zunehmend aus. Es wird versucht
anwendungsrelevante Probleme durch mathematische Formulierungen und die Implementierung
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
differenzierbar ist.
Ziel dieser Arbeit besteht darin, verschiedene Methoden zu untersuchen und zu implementieren,
die solche Optimierungsprobleme lösen. Diese Arbeit orientiert sich hauptsä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.

Excerpt

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

2. Grundlagen

2.1. Konvexe Mengen und Funktionen . . . . . . . . . . . . . . . . . . . . . .

2.1.1. Konvexe Mengen . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.2. Konvexe Funktionen . . . . . . . . . . . . . . . . . . . . . . . . .

2.2. Lokale Lipschitz-Stetigkeit . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3. Subdierential und Richtungsableitung . . . . . . . . . . . . . . . . . . .

2.4. Konvexe Optimierungsprobleme . . . . . . . . . . . . . . . . . . . . . . . 13

2.5. Abstiegsrichtungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.6. Lagrange-Multiplikatoren . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3. Das Gradientenverfahren

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

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

6. Bundle-Verfahren

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

A. Anhang

Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

Notationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

Quellcode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

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.

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

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

, r

0 und eine beliebige Norm · auf dem R

sind

die oene Kugel um x mit Radius r,

(x, r) = {y R

| x - y < r},

und die abgeschlossene Kugel um x mit Radius r,

(x, r) = {y R

| x - y r},

konvexe Mengen.

Denition 2.1.1.3.[6] Eine Konvexkombination von k Vektoren x

, . . . , x

ist ein

Vektor der Form

i=1

mit

i=1

= 1 und

0, i = 1, . . . , k.

2. Grundlagen

Satz 2.1.1.4.[6] Eine Menge X R

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

k+1

i+1

= (1 -

k+1

)

i=1

1 -

k+1

i+1

so ist dies eine Konvexkombination der beiden Punkte

i=1

k+1

, x

k+1

X mit

k+1

[0, 1]

Denition 2.1.1.5.[6] Eine nichtleere Teilmenge K R

heiÿt Kegel, wenn mit x K

auch {x | > 0} K ist.

Satz 2.1.1.6.[6] Sind X

, X

nichtleere, konvexe Mengen mit intX

= und

intX

= , dann gibt es eine Hyperebene, die X

und X

trennt, d.h., es gibt ein

, s

= 0

und r R mit

sup

r inf

Weiter gilt s

y > r

für alle y intX

, d.h., X

ist nicht in der Hyperebene enthalten.

2.1.2. Konvexe Funktionen

Denition 2.1.2.1.[6] Ist X R

eine nichtleere, konvexe Menge, dann heiÿt die

Funktion f : X R konvex, wenn

((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]

2. Grundlagen

Beispiel 2.1.2.2.[6] Die durch f(x) = x, f(x) = x

und f(x) = |x| denierten Funk-

tionen f : R R sind konvex. Die Funktion

: R

R, f(x) =

i=1

= x, x = x

ist konvex. Ist · eine beliebige Norm auf R

, dann ist die Funktion f : R

R mit

(x) = x konvex.

Lemma 2.1.2.3.[6] Sind f

, . . . , f

ConvR

, t

, . . . , t

positive, reelle Zahlen und

gibt es ein x R

mit f

(x) < +, j = 1, . . . , m, dann ist auch die Funktion f :=

j=1

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

nichtleer und f : R

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

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

und gilt für z int(domf) und , m, M R

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

- 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

:= y +

- x

2. Grundlagen

Wegen v - z v - y + y - z < 2 ist v B(z, 2) und

- x

+ y - 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

(y) - f(x)

- x

+ y - x

[f(v) - f(x)]

- x (M - m).

Vertauscht man x und y, so hat man entsprechend

(x) - f(y)

- x

+ y - x

[f(v) - f(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

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

ist deniert durch

(x, d) := lim

(x + td) - f(x)

= inf

t>0

(x + td) - f(x)

(2.4)

sofern der rechts stehende Grenzwert existiert.

Lemma 2.3.2.[2] Seien X R

eine oene und konvexe Menge, f : X R eine

konvexe Funktion, x X und d R

. Dann gilt:

a) Der Dierenzenquotient

(t) :=

(x + td) - f(x)

ist monoton fallend für t 0, d.h., es ist q(t

) q(t

) für alle 0 < t

< t

mit

+ t

b) Die Richtungsableitung von f im Punkt x in Richtung d existiert und es ist

(x, d) := inf

t>0

(x + td) - f(x)

2. Grundlagen

Beweis zu Lemma 2.3.2.[2]

a) Seien 0 < t

< t

mit x + t

X (und damit auch x + t

X). Wegen der

Konvexität von f gilt

(x + t

) = f

(x + t

) + (1 -

(x + t

) + (1 -

)f(x).

Diese Ungleichung impliziert

) =

(x + t

) - f(x)

(x + t

) - f(x)

= q(t

Dies ist die Behauptung.

b) Seien t, > 0 mit x - d X und x + td X gegeben. Da f konvex ist,gilt

(x) = f

(x - d) +

(x + td)

(x - d) +

(x + td).

also

(t) =

(x + td) - f(x)

(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

(x, d) = lim

(x + td) - f(x)

= inf

t>0

(x + td) - f(x)

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

eine oene und konvexe Menge, f : X R eine

konvexe Funktion und x X. Ein Vektor s R

heiÿt Subgradient von f in x,wenn

gilt

(y) f(x) + s

(y - x) y X.

(2.5)

Die Menge der Subgradienten von f in x heiÿt das (konvexe) Subdierential von f in

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.

(x) =

{1},

falls x > 0,

[-1, 1], falls x = 0,

{-1},

falls x < 0.

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

für alle d R

und alle t > 0 mit x + td X nach

Division durch t und Grenzübergang t 0

f(x)

d R

Speziell für d = s - f(x) ergibt dies

= 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

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

(x) = {s R

f (x, d) für alle d R

}

c) Für die Richtungsableitung von f in x gilt

(x, d) = max

sf (x)

für alle d R

Beweis von Satz 2.3.5.[2], [6]

)

Sei s f(x), dann gilt für beliebiges d R

(x + td) f(x) + t(s

) t 0,

also

(x + td) - f(x)

t > 0.

2. Grundlagen

Für t 0 folgt daraus s

f (x, d).

Ist s R

mit s

f (x, d) für alle d R

, dann gilt für eine beliebige Richtung

wegen der rechten Seite von (2.4)

f (x, d)

(x + td) - f(x)

t > 0.

Ist x + d domf, dann ist [x, x + d] domf und für t = 1 folgt

(x + d) f(x) + s

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

gilt für alle d R

. Für beliebiges y R

folgt

jetzt mit d := y - x

(y) = f(x + d) f(x) + s

(y - x),

d.h. s f(x).

)

Nach (b) folgt, dass f(x) der Durchschnitt der abgeschlossenen Halbräume {s

| s

f (x, d)}, d R

und damit selbst abgeschlossen und konvex ist. Aus

(b) kann ebenso gefolgert werden, dass f(x) beschränkt ist. Dazu verwendet man den

-ten Einheitsvektor e

= (0, . . . , 0, 1, 0, . . . , 0)

dann gilt für jeden Vektor s f(x)

max

i=1,...,n

(x, ±e

die Menge f(x) ist kompakt.

Nun bleibt noch zu zeigen, dass die Menge f(x) nichtleer ist. Dies wird zusammen mit

)

Man betrachte die beiden konvexen, nichtleeren Mengen

:= {(y, z) X × R | z > f(y)},

:= {(y, z) X × R | y = x + td, z = f(x) + tf (x, d), t > 0},

X ist dabei der vorgegebene Punkt und d R

ist ein beliebiger Vektor. K

ist

eine Säule oberhalb des Graphen f und K

ist der vom Punkt (x, f(x)) ausgehende

Stahl in Richtung (d, f (x, d)). Um die Konvexität von K

nachzuweisen, folgert man

aus (y, z), (~y, ~z) K

mit (0, 1)

+ (1 - )~z > f(y) + (1 - )f(~y) f(y + (1 - )~y),

also (y, z) + (1 - )(~y, ~z) K

Weiter gilt

= .

Denn (y, z) K

bedeutet, dass es ein t > 0 gibt, so dass

(y) < z = f(x) + tf (x, d) mit y = x + td

gilt. Daraus erhält man

(x + td) - f(x)

< f

(x, d).

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

= (s, ) R

× R mit

+ z s

(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

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

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

- f(y) s

- f(x) y X,

d.h., es ist s f(x)

f(x) = .

Wenn man aber y := x in (2.6) einsetzt, so folgt

- z s

(x + td) - f(x) + tf (x, d)

z > f(x) und t > 0.

Der Grenzübergang z f(x) und t := 1 liefert

(x, d) s

Allerdings gilt nach (b) s

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

, f

: R

R konvexe, überall endliche Funktionen und t

, t

positive, reelle Zahlen, dann gilt

+ t

)(x) = t

(x) + t

(x) x R

Beweis von Satz 2.3.6.[6] Die Funktion f := t

+ t

ist nach Lemma 2.1.2.3 konvex.

Weiter gilt für x R

(1)

(x, ·) = t

(x, ·) + t

(x, ·).

2. Grundlagen

Nach Satz 2.3.5. b) ist daher

(2)

(x) = {s R

| s

(x, d) + t

(x, d) für alle d R

Wendet man Satz 2.3.5. b) auf f

und f

an, so folgt für beliebiges s

(x) und

(x)

, d

+ t

, d

(x, d) + t

(x, d) d R

also wegen (2) t

+ t

f(x). Damit folgt

:= t

(x) + t

(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

= d R

mit

d >

max

Mit s

(x), s

(x) ist s = t

+ t

F . Dies gilt speziell für s

(x), i = 1, 2, mit

)

= max

(x)

Daher ist

d >

max

= t

max

(x)

+ t

max

(x)

Nach Satz 2.3.5. c) folgt daraus wegen s f(x)

(x, d) s

d > t

(x, d) + t

(x, d)

im Widerspruch zu (1).

Beispiel 2.3.7.[6] Sind f

, f

: R

R konvexe, überall endliche Funktionen, dann gilt

nach Satz 2.3.6 (setze t

= t

= 1)

+ f

)(x) = f

(x) + f

(x) x R

Sind allgemeiner f

: R

R, i = 1, . . . , m, konvexe Funktionen und ist f : R

durch f(x) =

i=1

(x) deniert, dann ist f nach Lemma 2.1.2.3 konvex und durch

wiederholte Anwendung von Satz 2.3.6 erhält man

(x) = f

(x) +

i=2

(x)

f(x) =

i=1

(x)

für alle x R

. Die Funktion

(x) =

i=1

(x)

ist mit positiven reellen Zahlen t

, i

= 1, . . . , m, nach Lemma 2.1.2.3 konvex und durch

wiederholte Anwendung von Satz 2.3.6 erhält man schlieÿlich

(x) = t

(x) +

i=2

(x)

2. Grundlagen

f(x) =

i=1

(x)

für alle x R

. Um einen speziellen Subgradienten s f(x) zu erhalten, kann man

also beliebige Subgradienten s

(x) wählen und dann s =

i=1

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

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

(x)

Die Menge X kann Restriktionen denieren, die in der Regel durch Gleichungen und

Ungleichungen dargestellt werden.

(P L)

min

(x)

unter g

(x) 0 i = 1, . . . , m

(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

(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

, dann spricht man von einem Optimierungsproblem ohne Re-

striktionen oder von einem unrestringiertem Optimierungsproblem. Hierbei ist die Ziel-

funktion f : R

R konvex und endlich.

(P U)

min

(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

R sind die folgenden Aussagen

äquivalent:

a) x

ist Lösung von (P U),

b) 0

f(x

c) f (x

, d

) 0 für alle d R

2. Grundlagen

Beweis zu Satz 2.4.2. [6]

(a) (b)

Es gilt f(x) f(x

) für alle x R

genau dann, wenn

(x) f(x

) + 0

, x

- x

x R

gilt. Dies ist äquivalent zu 0

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

beliebig gilt

(f(x

+ td) - f(x

)) 0 t > 0.

Für t 0 erhält man f (x

, d

) 0.

Nach Denition der Richtungsableitung ist für ein beliebiges x R

0 f (x

, x

- x

)

+ 1(x - x

)) - f(x

)

= 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

. 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

(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)

und eine Schrittweite

0 berechnet, so dass die Bedingung (2.7) mit x

(k+1)

:= x

(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

R und x R

heiÿt ein Vektor d R

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

R und x, d R

sind folgende

Aussagen äquivalent:

a) d ist Abstiegsrichtung von f in x,

b) f (x, d) < 0,

c) max

sf (x)

s, d <

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) <

(x), dann folgt aus der Denition der Richtungsableitung

(x, d)

(x + td) - f(x)

also gilt (b).

(b) (a) Ist f (x, d) < 0, d.h., es gilt

0 > f (x, d) = lim

(x + td) - f(x)

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

auf f(x

(k)

) bestimmen. Ist s

(k)

= 0

dann ist 0

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

die eindeutig bestimmte Projektion von 0

auf f(x

(k)

dann ist d

(k)

:= -s

(k)

/ s

(k)

eine Abstiegsrichtung von f in x

(k)

und es gilt

(k)

, d

(k)

) = - s

(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

und

Punkte z R

^x X ist ^x = P

(z) genau dann, wenn

- ^x, x - ^x 0 x X

gilt.

Beweis von Satz 2.5.3.[6] Da s

(k)

die Projektion von 0

auf f(x

(k)

) ist, folgt aus obigem

Satz

- 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)

, d

(k)

= - s

(k)

s f(x

(k)

Daraus ergibt sich wegen s

(k)

f(x

(k)

)

(k)

, d

(k)

) = max

sf (x

(k)

)

s, d

(k)

= - s

(k)

d.h., d

(k)

ist Abstiegsrichtung von f in x

(k)

·) ist positiv homogen f (x

(k)

-s

(k)

) = - s

(k) 2

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

kann man (mindestens) einen Subgradienten s(x)

(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

und R

heiÿen Lagrange-Multiplikatoren,

wenn

(x, , ) L(x, , ) := f(x) +

i=1

(x) +

j=1

(x)

gilt, wobei g

(x) und h

(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

und R

zu x

gibt.

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)

und setze k := 0.

1.Berechne f(x

(k)

2.Abbruchkriterium: Falls f(x

(k)

) = 0

, dann stoppe das Verfahren.

3.Berechne zu d

(k)

= -f(x

(k)

) eine Schrittweite t

0 durch Lösung des eindi-

mensionalen Minimierungsproblems min

(t) := f(x

(k)

+ td

(k)

4.Setze x

(k+1)

:= x

(k)

+ t

(k)

, k

:= k + 1 und gehe zu 1 zurück.

Zu Beginn des Verfahrens wird ein Startpunkt x

(0)

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

gilt, wird das Verfahren abgebrochen.

2.Falls f(x

(k)

) = 0

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

0 verwendent werden, so dass

die Iterationsvorschrift

(k+1)

= x

(k)

+ t

(k)

k > 0

bzw.

(k+1)

= x

(k)

- t

f(x

(k)

), k > 0

erfüllt ist.Der Faktor t

lässt sich auf viele verschiedene Weisen berechnen.Hier wird

jedoch die Strahlenminimierung, bzw.das CAUCHY-Prinzip verwendet.Dabei soll das

eindimensionale Minimierungsproblem

min

(t) := f(x

(k)

+ td

(k)

)

gelöst werden.Damit ergibt sich die exakte Schrittweite aus dem folgenden Term

f(x

(k)

)

f(x

(k)

)

f(x

(k)

)

(k)

)f(x

(k)

)

-f(x

(k)

)

(k)

)

(k)

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

R sei

stetig dierenzierbar und die zu minimierende Zielfunktion, x R

sei die aktuelle Nä-

herung und d R

eine Abstiegsrichtung, die die hinreichende Bedingung f(x)

d <

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)

gilt (0) < 0. Deswegen fällt für kleine t-Werte:

0 : t ]0, t

[: (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 = 0, 1, 2, . . . }, so dass gilt

(x + td) f(x) + tf(x)

(3.1)

Zur Berechnung von t hat man also die Ungleichung (3.1) nacheinander für t =

, 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

= 0, 1, 2, . . . zu nehmen.

3. Das Gradientenverfahren

Abbildung 3.1.: Armijo-Schrittweite

3.2.2. Wolfe-Powell-Regel

Bei dem Wolfe-Powell-Schrittweiten-Verfahren seien die Zahlen (0,

) und [, 1)

fest vorgegeben. Man bestimme hier ebenso wie bei der Armijo-Regel, die Schrittweite

t >

0 mit

(x + td) f(x) + tf(x)

(3.2)

und

f(x + td)

f(x)

(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.

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

R, ausgehend vom Startpunkt

in Richtung d R

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

(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

+ 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.

Excerpt out of 104 pages - scroll top

Details

Title: Nichtglatte Optimierung
College: University of Augsburg (Mathematik)
Grade: 1,7
Author: Bachelor of Science Irene Filipiak (Author)
Publication Year: 2010
Pages: 104
Catalog Number: V232845
ISBN (eBook): 9783656503071
ISBN (Book): 9783656503842
Language: German
Tags: nichtglatte optimierung
Product Safety: GRIN Publishing GmbH

Quote paper: Bachelor of Science Irene Filipiak (Author), 2010, Nichtglatte Optimierung, Munich, GRIN Verlag, https://www.grin.com/document/232845