Newton Methoden - Fachbereich Mathematik und Informatik

Newton Methoden
Seminararbeit
für das Seminar
optimale Steuerung
Westfälische Wilhelms-Universität Münster
Fachbereich Mathematik und Informatik
Institut für Numerische und Angewandte Mathematik
Betreuung:
Prof. Dr. Benedikt Wirth
Eingereicht von:
Ines Ahrens
Münster, Mai 2015
i
Inhaltsverzeichnis
1 Einleitung
1
2 Generalisierte Newton Methoden
2.1 Newton Methoden mit einfachen Nebenbedingungen . . . . . . . . . . .
2.1.1 Konvergenz der generalisierten Newton Methode . . . . . . . . .
2.1.2 Die klassische Newton Methode . . . . . . . . . . . . . . . . . .
2.2 verallgemeinerte Ableitung . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 semidiffbare Newton Methoden . . . . . . . . . . . . . . . . . . . . . .
2.3.1 semidiffbare Newtonmethoden für endlich dimensionale KKT Systeme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2
3
6
6
10
3 semidiffbare Newton Methoden in Funktionsräumen
3.1 Punktweise Randbedingungen in L2 . . . . . . . . . . . . . . . . . . . .
3.2 semidiffbarheit von superpositions Operatoren . . . . . . . . . . . . . .
3.3 Punktweise Randbedingungen in L2 überarbeitet . . . . . . . . . . . .
3.4 Anwendung für optimale Steuerung . . . . . . . . . . . . . . . . . . . .
3.5 Allgemeine Optimierungsprobleme mit Ungleichungsbedingungen in L2
3.6 Anwendung für elliptische optimale Steuerung . . . . . . . . . . . . . .
3.6.1 Verteilte Kontrolle . . . . . . . . . . . . . . . . . . . . . . . . .
3.6.2 Neumann Rand Bedingungen . . . . . . . . . . . . . . . . . . .
3.7 Optimale Steuerung der nicht komprimierbaren Navier-Stokes Gleichung
14
14
15
17
18
21
22
22
25
25
11
1
1 Einleitung
Mein Vortrag befasst sich mit dem Thema Newton Methoden. Insbesondere möchte ich
Verfahren finden, die optimale Steuerungsprobleme lösen. Zu unterscheiden sind dabei
endlich und unendlich dimensionale Probleme.
Unser Ziel ist es, Probleme der Form
min f (w) s.t. e(w) = 0,
w∈W
c(w) ≤ 0 a.e. auf Ω
mittels Newtonverfahren numerisch zu lösen. Hierbei sind W und Z Banachräume.
f : W → R ist die zu optimierende Funktion. e : W → Z und c : W → L2 (Ω) sind
zweimal stetig F-diffbar und die Nebenbedingungen. Dabei ist e oftmals eine partielle
Differenzialgleichung und c ist zum Beispiel eine Einschränkung auf ein Gebiet. Ω ⊂ Rn
ist messbar und beschränkt und das Gebiet auf dem c gelten soll.
Um das Problem zu lösen, werden wir zunächst ein sehr viel einfacheres Problem betrachten. Dieses analysieren wir solange, bis wir eine gute Darstellung gefunden haben.
Zu dieser Darstellung entwickeln wir dann ein Newtonverfahren. Das Vorgehen werden
wir einige Male wiederholen, bis wir bei unserem ursprünglichen Problem angelangt
sind. Die erste Vereinfachung ist es, das Problem nur im endlichdimensionalen zu betrachten und die Nebenbedingungen wegzulassen. Nach und nach werden wir diese
mit hinzunehmen und so ein Newtonverfahren für das endlichdimensionale Problem
finden. Im unendlichdimensionalen wenden wir das gleiche Vorgehen an, werden aber
nach einigen theoretischen Vorüberlegungen auf ein Problem stoßen, dessen Lösung
den Rahmen dieses Vortrages sprengen würde. Auf ein Beispiel lässt sich jedoch die
vorherige Theorie anwenden und werden auch ein konkretes Newtonverfahren dazu
aufstellen.
2
2 Generalisierte Newton Methoden
2.1 Newton Methoden mit einfachen
Nebenbedingungen
Wir betrachten das Problem
min f (w)
w∈Rn
(2.1)
wobei f : Rn → R.
Die Optimalbedingung zu diesem Problem lautet:
∇f (w) = 0
Nun wollen wir ein numerisches Verfahren für dieses Problem entwickeln. Dazu setzen
wir G := ∇f . Da wir ein diskretes Verfahren wollen, setzten wir w0 , w1 , · · · in G ein.
Wir erhalten:
G(wk+1 ) = 0
Um ein iteratives Verfahren zu erhalten taylorn wir G ist wk . Das ergibt:
Theorem 2.1.1 (einfaches Newtonverfahren). Sei das Problem (2.1) gegeben und G :=
∇f . Dann wird das Problem mit folgendem Verfahren gelöst:
G(wk ) + G0 (wk )sk = 0
wk+1 = wk + sk
Das Verfahren konvergiert superlinear falls G ∈ C 1 und G0 invertierbar ist.
2
Generalisierte Newton Methoden
3
Das Verfahren dazu lautet:
Data: w0 (möglichst Nah an der Lösung w)
for k = 0, 1, · · · do
Löse Mk sk = −G(wk );
wk+1 = wk + sk ;
end
Algorithm 1: einfache Newton Methode
Hier ist M k = G0 (wk )
Nun wollen wir auch Nebenbedingungen zulassen. Wir haben schon gesehen, dass das
Minimierungsproblem
min f (w) s.t. w ∈ S
w∈Rn
äquivalent ist zu
w − PS (w − θ∇f (w)) = 0
mit θ > 0 fest. Die Projektion betrachten wir, da das Newtonverfahren sonst auch
Werte zulassen würde, die nicht in S liegen. Eine genauere Erklärung war in einem
vorherigem Vortrag.
Wir betrachten also die Funktion
φ(w) = w − PS (w − θ∇f (w))
Nun wollen wir also das Newtonverfahren auf φ anwenden. Dabei ist φ leider nicht differenzierbar. Also müssen wir unser M k anders wählen. Wie diese Wahl aussieht, lernen
wir später. Um über Newtonverfahren sprechen zu können, brauchen wir zunächst einen
Begriff für Konvergenz. Diesen werden wir im folgendem Kapitel betrachten
2.1.1 Konvergenz der generalisierten Newton Methode
Zunächst eine kleine Wiederholung des Konvergenzbegriffes:
Definition 2.1.2 (Konvergenzgeschwindigkeit). Sei xk eine Folge, die x approximiert.
• lineare Konvergenz: kxk+1 − xk ≤ ckxk − xk
∀k > k0
2
Generalisierte Newton Methoden
4
• superlineare Konvergenz: Sei ck eine Nullfolge. kxk+1 −xk ≤ ck kxk −xk
• Konvergenz der Ordnung p: kxk+1 − xk ≤ ckxk − xkp
∀k > k0
∀k > k0
Betrachte nun
G(x) = 0
(2.2)
mit G : X → Y , wobei X, Y Banachräume sind. Sei x die Lösung der Gleichung.
Um eine numerische Lösung von (2.2) zu erhalten, benutzen wir einen ähnlichen Algorithmus, wie den für das einfache Newtonverfahren, nur allgemeiner:
Data: x0 ∈ X (möglichst Nah an der Lösung x)
for k = 0, 1, · · · do
Wähle invertierbaren Operator Mk ∈ L(X, Y );
Erhalte sk beim lösen von Mk sk = −G(xk );
xk+1 = xk + sk ;
end
Algorithm 2: Generalisierte Newton Methode
Wie dieser Operator Mk sinnvoll zu wählen ist, wird später genauer bestimmt.
Nun untersuchen wir die durch diesen Algorithmus gewonnene Folge xk in einer Umgebung von x. Sei dk+1 = xk+1 − x der Abstand zwischen der Iteration und der Lösung.
Dann gilt:
Mk dk+1 = Mk (xk+1 − x) = Mk (xk + sk − x) = Mk dk − G(xk )
= G(x) + Mk dk − G(xk )
Wir erhalten:
Theorem 2.1.3. Betrachte (2.2) mit der Lösung x. Sei xk die Folge, die durch den
Generalisierten Newton Algorithmus 2 erzeugt wurde. Sei x0 nah genug an x gewählt
1. Falls ∃γ ∈ (0, 1) mit
kdk+1 kX = kMk−1 G(x + dk ) − G(x) − Mk dk kX ≤ γkdk kX
∀k mit kdk kX klein genug
gilt, dann konvergiert xk → x linear mit Konstante γ
2
Generalisierte Newton Methoden
5
2. Falls ∀η ∈ (0, 1) ∃δη > 0, sodass
kdk+1 kX = kMk−1 G(x + dk ) − G(x) − Mk dk kX ≤ ηkdk+1 kX
für kdk kX < δη
gilt, dann konvergiert xk → x super linear
3. Falls ∃γ ∈ (0, 1) mit
kdk+1 kX = kMk−1 G(x + dk ) − G(x) − Mk dk kX ≤ Ckdk k1+α
X
für kdk kX → 0
gilt, dann konvergiert xk → x super linear der Ordnung α + 1
Beweis. einfaches nachrechnen, siehe Buch.
Oft teilt man diese Kleinheitsannahmen in zwei Teile auf:
Definition 2.1.4 (Regularitätsannahme). Sei Mk ∈ L(X, Y ), wobei X,Y Banachräume
sind. Dann ist die Regularitätsannahme gegeben durch:
kMk−1 kY →X ≤ C
∀k ≥ 0
Bemerkung (Operatornorm). Die Notation für die Operatornorm von einem linearen
Operator f : X → Y , wobei X, Y normierte Vektorräume sind lautet:
kf kX→Y := sup kf (x)kY
kxkX =1
Definition 2.1.5 (Approximationsannahme). Sei Mk ∈ L(X, Y ), wobei X,Y Banachräume sind, x die Lösung von G(x) = 0 und dk := xk − x Sei α + 1 > 1 Dann ist
die Approximationsannahme gegeben durch:
kG(x + dk ) − G(x) − Mk dk kY = o(kdk kX ) für kdk kX → 0
oder
kG(x + dk ) − G(x) − Mk dk kY = o(kdk k1+α
X ) für kdk kX → 0
Nun probieren wir eine geeignete Wahl für Mk zu finden.
2
Generalisierte Newton Methoden
6
2.1.2 Die klassische Newton Methode
Theorem 2.1.6 (Konvergenz der klassischen Newton Methode). Sei das Problem (2.2)
gegeben mit der Lösung x und sei G : X → Y mit X, Y Banachräume F-diffbar.
Sei außerdem G0 (x) stetig invertierbar. Dann konvergiert die Generalisierte Newton
Methode 2 mit Mk = G0 (xk ) lokal super linear.
Falls G0 zusätzlich α-Hölderstetig ist, dann konvergiert die klassische Newton Methode
von der Ordnung 1 + α
Beweis. der Beweis ist im Script und nicht schwer nachzurechnen.
2.2 verallgemeinerte Ableitung
Nun wollen wir auch das Newtonverfahren anwenden können, falls G nicht diffbar ist.
Dazu wird der Begriff der verallgemeinerten Ableitung eingeführt. Leider gibt es nicht
viel Literatur zu diesem Begriff, sodass ich ihn recht informal einführen muss. Beginnen
wir mit einem Beispiel.
Wir betrachten die Betragsfunktion f : R → R x 7→ |x|. Diese ist überall diffbar
außer in 0. Nun wollen wir auch hier eine Ableitung finden. Die Ableitung gibt die
Steigung der Funktion in einem Punkt an. Unser neuer Begriff der Ableitung soll dieser
Eigenschaft genügen. Da aber die Steigung im Punkt 0 nicht eindeutig definiert ist,
nimmt man als Ableitung alle möglichen Steigungen in 0. Das ist hier das Intervall
[−1, 1], da die Steigung wenigstens −1 aber höchstens 1 ist. Alle Werte dazwischen
können aber auch angenommen werden. Also gilt:


 {−1} x ∈ (−∞, 0)
cl
∂ f (x) =
[−1, 1] x = 0


{1}
x ∈ (0, ∞)
Diese Ableitung nennt sich Clarke Differential.
Definition 2.2.1 (Clarke Differential). Sei G : Rn → Rm lipschitz stetig. Dann wird
das Clarke Differential definiert als
∂ cl G(x) := conv M ∈ Rn×m |xk → x,
G0 (xk ) → M,
G ist diffbar in xk
2
Generalisierte Newton Methoden
7
wobei conv{M } die konvexe Hülle von M meint. Dabei zu beachten ist, dass dieses
Differenzial keine Funktion, sondern eine Menge ist.
Die Lipschitzstetigkeit wird gebracht, da nach dem Satz von Rademacher eine lipschitzstetige Funktion fast überall differenzierbar ist.
Diese Definition stimmt mit unserer Ableitung der Betragsfunktion überein:
Sei x ∈ (−∞, 0) und xk eine Folge, die gegen x konvergiert. Dann gilt
lim f 0 (xk ) = −1
k→∞
Sei nun x ∈ (0, ∞) und xk eine Folge, die gegen x konvergiert. Dann gilt
lim f 0 (xk ) = 1
k→∞
Nun gilt für x ∈ (−∞, 0)
∂ cl f = conv M |xk → x,
f 0 (xk ) → M,
f ist diffbar in xk
= conv {−1} = {−1}
Für x ∈ (0, ∞) das Gleiche nur mit 1 statt −1. Sei x = 0. Dann gilt:
∂ cl f = conv M |xk → x,
f 0 (xk ) → M,
f ist diffbar in xk
= conv {−1, 1} = [−1, 1]
Theorem 2.2.2. Sei G : Rn → Rm eine Funktion, deren Richtungsableitung existiert
und stetig ist. Dann gilt, dass {G0 } = ∂ cl G
Beweis. Sei {xk } ⊂ Rn eine Folge, die gegen x ∈ Rn konvergiert. G0 bezeichnet die
Richtungsableitung. Dann gilt:
lim G0 (xk ) = G0 ( lim xk ) = G0 (x)
k→∞
k→∞
Den Limes darf ich reinziehen, da G0 stetig ist. Damit ist ∂ cl G = {G0 }.
Falls die Richtungsableitung existiert und diese nicht stetig ist, stimmen die Differen-
2
Generalisierte Newton Methoden
8
ziale nicht überein!
Dieses Konzept lässt sich noch weiter verallgemeinern auf Banachräume.
Definition 2.2.3 (verallgemeinerte Differentiale). Seien X, Y Banachräume und G :
X → Y ein stetiger Operator. Dann ist die Menge der verallgemeinerten Differentiale
definiert als
∂G : X ⇒ L(X, Y )
Dabei meint ⇒ L(X, Y ), dass ein Punkt x ∈ X auf eine Menge von linearen Operatoren
abgebildet wird (und nicht nur auf einen Operator). Ein Beispiel für ein verallgemeinertes Differenzial ist das Clarke Differenzial. Dies ist jedoch nur für Vektorwertige
Funktionen definiert.
Nun können wir, um unser Newtonverfahren umzugestalten Mk ∈ ∂G(xk ) wählen.
Damit unser Verfahren aber super linear konvergiert, muss gelten
kG(x + dk ) − G(x) − Mk dkY = o (kdkX ) für kdkX → 0
sup
M ∈∂G(x+d)
Dieses nennt sich semidiffbar.
Definition 2.2.4 (semidiffbar). Sei G : X → Y ein stetiger Operator zwischen Banachräumen. Sei ∂G : X ⇒ L(X, Y ) mit nicht leeren Bildern gegeben wie oben.
1. G heißt ∂G semidiffbar in x ∈ X, falls
sup
kG(x + dk ) − G(x) − Mk dkY = o (kdkX ) für kdkX → 0
M ∈∂G(x+d)
2. G heißt ∂G semidiffbar von der Ordnung α + 1 > 1 in x ∈ X, falls
sup
M ∈∂G(x+d)
kG(x + dk ) − G(x) − Mk dkY = O kdkα+1
X
für kdkX → 0
Lemma 2.2.5. Sei G : X → Y ein Operator zwischen Banachräumen und stetig
F-diffbar in einer Umgebung von x. Dann ist G {G0 }-semidiffbar in x. Falls G0 αHölderstetig in einer Umgebung von x ist, dann ist G {G0 }-semidiffbar in x von der
Ordnung α.
{G0 } beschreibt den Operator {G0 } : X ⇒ L(X, Y ) mit {G0 }(x) = {G0 (x)}
2
Generalisierte Newton Methoden
9
Beweis.
kG(x + dk ) − G(x) − G0 (x + d)dkY
≤ kG(x + dk ) − G(x) − G0 (x)dkY + kG0 (x)d − G0 (x + d)dkY
≤ o (kdkX ) + kG0 (x) − G0 (x + d)kX→Y kdkX = o (kdkX )
zweiter Teil analog, siehe Buch.
Beispiel 2.2.6 (Projektion). Betrachte ψ : R → R, ψ(x) = P[a,b] (x) mit a < b. Dann
ist das Clarke Differential gegeben durch:


 {0} x < a oder x > b
cl
∂ ψ(x) =
{1} a < x < b


[0, 1] x = a oder x = b
Beweis. Für alle x ∈
/ {a, b} gilt, dass ψ stetig diffbar in einer Umgebung von x ist. Mit
Lemma 2.2.5 gilt, dass ψ ∂ cl ψ- semidiffbar in x ist.
Sei nun x = a Für kleine d > 0 ergibt sich, dass ∂ cl ψ(x) = {ψ 0 (a + d)} = {1} und
damit
sup
|ψ(x + d) − ψ(x) − M d| = a + d − a − 1d = 0
M ∈∂ cl ψ(x+d)
Für kleine d < 0 ergibt sich, dass ∂ cl ψ(x) = {ψ 0 (a + d)} = {0} und damit
sup
|ψ(x + d) − ψ(x) − M d| = a − a − 0d = 0
M ∈∂ cl ψ(x+d)
Somit ist die ∂ cl ψ- semidiffbarheit in x = a gezeigt.
Für x = b dasselbe.
Theorem 2.2.7 (Rechenregeln semidiffbare Funktionen). Seien X, Y, Z, Xi , Yi Banachräume.
1. Falls die Operatoren Gi : Xi → Yi ∂Gi -semidiffbar in x sind, dann ist (G1 , G2 )
(∂G1 , ∂G2 )-semidiffbar in x.
2. Falls die Operatoren Gi : X → Y ∂Gi -semidiffbar in x sind, dann ist G1 + G2
(∂G1 + ∂G2 )-semidiffbar in x.
2
Generalisierte Newton Methoden
10
3. Seien G1 : Y → Z und G2 : X → Y ∂Gi -semidiffbar in G2 (x) und in x. Sei außerdem ∂G1 beschränkt in einer Umgebung von x = G2 (x) und G2 ist Lipschitzstetig
in einer Umgebung von x. Dann ist G = G1 ◦ G2 ∂G-semidiffbar mit
∂G(x) = {M1 M2 |M1 ∈ ∂G1 (∂G2 (x)) ,
M2 ∈ ∂G2 (x)}
Beweis. siehe Buch
2.3 semidiffbare Newton Methoden
Um Konvergenz zu erhalten muss die Approximationsannahme und die Regularitätsannahme
erfüllt sein. Die Approximationsannahme ist durch die Semidiffbarkeit gegeben. Jetzt
fehlt noch die Regularitätsannahme.
Definition 2.3.1 (Regularitätsannahme für semidiffbare Newton Verfahren). Betrachte (2.2) mit der Lösung x. Dann lautet die Regularitätsannahme
∃C > 0,
∃δ > 0 : kM −1 kX→Y ≤ C
∀M ∈ ∂G(x) ∀x ∈ X,
kx − xkX < δ
(2.3)
Data: x0 ∈ X (möglichst Nah an der Lösung x)
for k = 0, 1, · · · do
Wähle Mk ∈ ∂G(xk );
Erhalte sk beim lösen von Mk sk = −G(xk );
xk+1 = xk + sk ;
end
Algorithm 3: semidiffbare Newton Methode
Theorem 2.3.2 (Konvergenz des semidiffbaren Newton-Verfahrens). Sei das Problem
(2.2) gegeben mit der Lösung x. Seien X, Y Banachräume, G : X → Y stetig und
∂G semidiffbar und die Regularitätsannahme (2.3) sei gegeben. Dann existiert δ > 0,
sodass für alle x0 ∈ X mit kx0 −xkX < δ die semidiffbare Newton Methode super linear
gegen x konvergiert.
Falls G ∂G-semidiffbar der Odnung α > 0 in x ist, dann ist die Konvergenzordnung
1+α
Beweis. 2.1.3 besagt, dass wenn ich ein Newtonverfahren der Form 2 habe, also Mk ∈
2
Generalisierte Newton Methoden
11
L(X, Y ), Mk invertierbar ist und
kMk−1 G(x + dk ) − G(x) − Mk dk kX = o(kdk kX )
gilt, dann konvergiert das Newtonverfahren super linear. Da Mk ∈ ∂G, ist Mk ∈
L(X, Y ). Mk ist invertierbar, da die Regularitätsannahme gilt. Außerdem gilt mit der
Regularitätsannahme und der Semidiffbarkeit:
kMk−1 G(x + dk ) − G(x) − Mk dk kX
≤ kMk−1 kX k G(x + dk ) − G(x) − Mk dk kX
≤ Co(kdk kX ) = o(kdk kX )
Also ist 2.1.3 anwendbar.
2.3.1 semidiffbare Newtonmethoden für endlich dimensionale
KKT Systeme
Nun wollen wir die Theorie auf das endlich dimensionale KKT System anwenden.
Sei f : Rn → Rm die zu optimierende Funktion. e : Rn → Rp und c : Rn → Rm sind
die Nebenbedingungen des Optimierungsproblems. Wir betrachten das Problem
min f (w) s.t. e(w) = 0 c(w) ≤ 0
w∈Rn
(2.4)
wobei f ∈ C 2 (Rn ), e ∈ C 2 (Rn , Rp ), c ∈ C 2 (Rn , Rm )
Sei w die Lösung von (2.4). Dann existieren Lagrange Multiplikatoren p ∈ Rp , λ ∈ Rm
, sodass (w, p, λ) das folgende KKT System löst:
∇w L(w, λ, µ) = ∇f (w) + c0 (w)T λ + e0 (w)T µ = 0
λ≥0
∇λ L(w, λ, µ)(z − λ) = c(w)T (z − λ) ≤ 0 ∀z ≥ 0
∇µ L(w, λ, µ) = e(w) = 0
wobei L(w, λ, µ) := f (w) + λT c(w) + µT e(w) die Lagrangefunktion ist.
Jetzt schreiben wir das KKT zu einer Funktion G um:
2
Generalisierte Newton Methoden
12


∇w L(w, λ, µ)


G(w, λ, µ) := λ − PRp+ (λ + c(w)) = 0
(2.5)
e(w)
Damit das Newton Verfahren konvergiert, muss G semidiffbar sein. Das zeigt folgendes
Theorem:
Theorem 2.3.3 (semidiffbarheit des KKT Systems). Wir betrachten das Problem 2.4.
Sei G wie in 2.5 definiert.
Dann ist G semidiffbar mit



0
T
0
T


∇
L(w,
λ,
µ)
c
(w)
e
(w)
ww




cl
0
∂G =  −Dg c (w)
I − Dg
0  gi ∈ ∂ ψ(λi + ci (w))




0
e (w)
0
0
wobei ψ(t) := PR+ (t) und Dg = diag(gi )
Beweis. Sei x = (w, λ, µ). Zunächst ist ∇w L {∇wx L}-semidiffbar und e ist {e0 }semidiffbar, da L, e zweimal stetig diffbar sind.
Außerdem ist ψ ∂ cl ψ -semidiffbar, da wir dies für die Projektion schon gezeigt haben,
siehe 2.2.6. Nach Summen und Kettenregel ist
φi (w, λi ) := λi − PR+ (λi + ci (w))
semidiffbar mit
∂φi (w, λi ) := (−gi c0i (w), 1 − gi ) |gi ∈ ∂ cl ψ(λi c0i (w))
wobei die erste Komponente die Ableitung nach w und die zweite Komponente die
Ableitung nach λi darstellt. Deshalb ist der Operator
φ(w, λ) := λ − PRp+ (λ + c(w))
semidiffbar mit
∂φ(w, λ) := (−Dg c0i (w), I − Dg ) |Dg = diag(gi ), gi ∈ ∂ cl ψ(λi c0i (w))
2
Generalisierte Newton Methoden
13
Wenn man nun alles ableitet und dabei die Definition von L beachtet, kommt man auf
∂G(x)
Falls nun auch noch die Regularitätsannahme 2.3.1 erfüllt ist, ist 2.3.2 anwendbar und
das semidiffbare Newtonverfahren konvergiert superlinear für das KKT.
Hier haben wir angenommen, dass unsere PDGL Nebenbedingung stetig Differenzierbar ist. Das ist jedoch in der Praxis meist nicht der Fall. Deshalb werden wir uns im
Nächsten Kapitel mit L2 Funktionen befassen und zeigen, dass wir auch hier Semidifferenzierbarkeit haben.
14
3 semidiffbare Newton Methoden in
Funktionsräumen
Bislang nahm unsere Funktion nur Elemente aus dem Rn entgegen. Da dies für viele
Probleme unzureichend ist, befassen wir uns nun auch damit, dass unsere zu optimierende Funktion Funktionen entgegennimmt. Außerdem waren unsere Nebenbedingungen stetig differenzierbar, was auch nicht immer der Fall ist. Wie wir das verändern
betrachten wir später. Wir kümmern uns nun um die Funktionen als Eingaben.
3.1 Punktweise Randbedingungen in L2
Um das Problem einfach zu behalten, betrachten wir nur L2 und nicht Lp . Die Konzepte
können übertragen werden, würden jedoch den Rahmen hier sprengen.
Sei Ω ⊂ Rn messbar mit 0 ≤ |Ω| ≤ ∞. Wir betrachten das Problem
min f (u) a ≤ u ≤ b a.e. auf Ω
u∈L2 (Ω)
wobei f : L2 (Ω) → R zweimal stetig F-diffbar ist und a, b ∈ L∞ (Ω) mit b − a ≥ ν > 0,
wobei ν ∈ L∞ . Dieses Problem kann vereinfacht werden, indem wir die Schranken zu
konstanten Schranken transformieren. Da a ≤ u, gilt 0 ≤ u − a. Dann formen sich
unsere Schranken um zu 0 ≤ u − a ≤ b − a. Dies ist äquivalent zu 0 ≤ u−a
≤ 1. Damit
b−a
habe ich konstante Grenzen
Nun lautet das Problem
min f (u) βl ≤ u ≤ βr
u∈L2 (Ω)
mit βl < βr konstant.
a.e. auf Ω
(3.1)
3
semidiffbare Newton Methoden in Funktionsräumen
15
Jetzt können wir, wie vorher schon oft geschehen, unser Minmierungsproblem als nichtglattes Funktional darstellen. Betrachten wir dazu S := {u ∈ L2 (Ω)|βl ≤ u ≤ βr }. Da
wir in L2 sind, können wir die Dualpaarung mit dem Skalarprodukt identifizieren
h·, ·iU ∗ ,U = (·, ·)L2 (Ω) . Die Optimalitätsbedingung ist also
u ∈ S,
(∇f (u), v − u)L2 (Ω) ≥ 0 ∀v ∈ S
Jetzt können wir die Projektion für dieses Problem definieren
PS (v)(x) = P[βl ,βr ] (v(x))
und erhalten damit insgesamt
φ(u)(x) := u − P[βl ,βr ] (u(x) − θ∇f (u)(x))
(3.2)
mit θ > 0 beliebig aber fest.
Unser Ziel ist es, das verallgemeinerte Differenzial ∂φ von φ zu finden, sodass φ semidiffbar ist. Mit Kettenregel können wir das Problem vereinfachen, indem wir nur das
verallgemeinerte Differenzial von P[βl ,βr ] (v(·)) bestimmen.
3.2 Semidiffbarkeit von Superpositionsoperatoren
Definition 3.2.1. Sei ψ : Rm → R lipschitz stetig und (∂ cl ψ-) semidiffbar. Für 1 ≤
q ≤ p ≤ ∞ betrachte
Ψ : Lp (Ω)m → Lq (Ω),
Ψ(w)(x) := ψ(w1 (x), · · · , wm (x))
Wir definieren das Differenzial
∂Ψ : Lp (Ω)m ⇒ L(Lp (Ω)m , Lq (Ω)),
∂Ψ(w) = M |M v = g T v, g ∈ L∞ (Ω)m , g(x) ∈ ∂ cl ψ(w(x)) f.f.a x ∈ Ω
Eigentlich hätten wir gerne, dass L2 (Ω) 3 v 7→ P[βl ,βr ] (v(·)) ∈ L2 (Ω) semidiffbar ist.
Dies stimmt aber leider nicht.
Lemma 3.2.2. Sei Ω ⊂ Rn nichtleer, offen und beschränkt. Sei ψ : Rm → R eine
3
semidiffbare Newton Methoden in Funktionsräumen
16
lipschitz stetige, nicht affin lineare Abbildung. Dann ist für alle q ∈ [1, ∞) der Operator
Ψ : Lq (Ω) 3 u 7→ ψ(u(·)) ∈ Lq (Ω)
nicht ∂Ψ-semidiffbar
Beweis. Der Beweis ist zu lang und nicht intuitiv. Allerdings sieht man, dass das Problem die nicht Linearität von ψ ist.
Definition 3.2.3. Sei ψ : Rm → R lipschitz stetig und ∂Ψ semidiffbar. Sei 1 ≤ q ≤
p ≤ ∞. Betrachte
ΨG : Y → Lq (Ω),
ΨG (y)(x) = ψ(G(y)(x))
wobei G : Y → Lp (Ω)m stetig F-diffbar und Y Banachraum ist. Wir definieren das
Differenzial
∂ΨG : Y ⇒ L(Y, Lq (Ω))
( )
M v = g T (G0 (y)v), g ∈ L∞ (Ω)m ,
∂ΨG (y) = M g(x) ∈ ∂ cl ψ(G(y)(x)) f.f.a x ∈ Ω
Falls wir G als Identität wählen, ist diese Definition die Gleiche die oben. Die Ableitung
von G kommt nach Kettenregel mit rein.
Theorem 3.2.4. Sei Ω ⊂ Rn messbar mit 0 < |Ω| < ∞. Sei ψ : Rm → R lipschitz
stetig und semidiffbar. Sei Y eine Banachraum, 1 ≤ q < p ≤ ∞ und sei der Operator
G : Y → Lq (Ω)m stetig F diffbar und lokal lipschitz stetig. Dann ist der Operator
ΨG : Y → Lq (Ω),
ΨG (y)(x) = ψ(G(y)(x))
∂ΨG semidiffbar.
3.3 Punktweise Randbedingungen in L2 überarbeitet
Unser Ziel war es, Semidiffbarkeit von φ aus (3.2) zu zeigen. Dies können wir nur mit
ein paar zusätzlichen Annahmen machen.
Theorem 3.3.1. Betrachte das Problem (3.1) mit βl < βr . Es gelte für ∇f , dass
3
semidiffbare Newton Methoden in Funktionsräumen
17
∃α > 0, p > 2 sodass ∇f (u) = αu + H(u) mit
H : L2 (Ω) → L2 (Ω),
H : L2 (Ω) → Lp (Ω),
stetig F-diffbar
lokal lipschitzstetig
Dann ist der Operator φ mit θ = 1/α aus (3.2) ∂φ semidiffbar mit
∂φ : L2 (Ω) ⇒ L(L2 (Ω), L2 (Ω)),
)
( M = I + g · H 0 (u), g ∈ L∞ (Ω),
α
∂φ(x) = M g(x) ∈ ∂ cl P[βl ,βr ] − α1 H(u)(x) f.f.a x ∈ Ω
Hier gilt, dass


 {0}, t < βl oder t > βr
∂ cl P[βl ,βr ] (t) =
{1}, βl < t < βr


[0, 1], t = βl oder t = βr
Beweis. Es gilt:
1
1
φ(u) = u − P[βl ,βr ] u − (αu + H(u)) = u − P[βl ,βr ] − H(u)
α
α
Setze nun q = 2, ψ = P[βl ,βr ] und G = −(1/α)H. Nun können wir 3.2.4 anwenden und
erhalten, dass der Operator ΨG : L2 (Ω) → L2 (Ω) ΨG -semidiffbar ist. Mit Summenregel
folgt, dass φ = I − ΨG (I − ∂ΨG ) semidiffbar ist. Da ∂Φ = I − ∂ΨG ist der Beweis
fertig.
Wir bräuchten auch noch Regularitätsbedingungen, die werde ich aber hier weglassen,
da sie auch nicht im Buch stehen.
3.4 Anwendung für optimale Steuerung
Diese Theorie können wir jetzt anwenden. Dazu betrachten wir das Problem:
min
y∈H01 (Ω),u∈L2 (Ω)
1
α
J(y, u) := ky − yd kL2 (Ω) + kuk2L2 (Ω)
2
2
s.t. Ay = r + Bu,
βl ≤ u ≤ βr
3
semidiffbare Newton Methoden in Funktionsräumen
18
Dabei ist y der Zustand und u die Kontrolle. Der Zustand soll möglichst nah an unserer
Vorgabe yd sein. Also soll dieser Abstand minimiert werden, wodurch aber Kosten
entstehen. Diese werden durch den hinteren Term der Gleichung bestraft. Wie stark
diese Bestrafung ist, hängt von dem (häufig kleinen) Parameter α ab.
Als Nebenbedingung haben wir einen gleichförmigen linear elliptischen partiellen Differenzialoperator A : H01 (Ω) → H −1 (Ω) gegeben, der beschreibt wie sich der Zustand
verhält. Z.b. kann A eine Darstellung für −∆ sein. B beschreibt, wie sich unsere Kontrolle verhält. Außerdem können wir die Kontrolle nur in einem gewissen Rahmen
regulieren, weshalb βl ≤ u ≤ βr gelten soll. Zusammengefasst haben wir:
A : H01 (Ω) → H −1 (Ω)
r ∈ H −1 (Ω)
0
B : Lp (Ω) → H −1 (Ω)
p0 ∈ [1, 2)
elliptischer Differentialoperator
gegeben
stetig und linear
sodass H01 (Ω) im Dualraum Lp (Ω), p = p0 /(p0 − 1),
0
von Lp (Ω) stetig eingebettet ist
βl < βr
Da der Zustand von der Kontrolle abhängt, können wir dies auch ausdrücken mit
y = y(u) = A−1 (r + Bu). Die Invertierbarkeit von A folgt aus Thm 1.23 aus dem Buch.
Nun erhalten wir das reduzierte Problem
α
1
ˆ
J(u)
:= J(y(u), u) = ky(u) − yd kL2 (Ω) + kuk2L2 (Ω)
min
2
u∈L (Ω)
2
2
s.t. βl ≤ u ≤ βr
Um die Variationsungleichung aufzustellen brauchen wir
S := u ∈ L2 (Ω)|βl ≤ u ≤ βr
Diese lautet dann:
ˆ S) :
V I(∇J,
u∈S
ˆ
(∇J(u),
v − u)L2 (Ω) ≥ 0 ∀v ∈ S
Die Variationsungleichung ist eine Optimalitätsbedingung, die schon in einem vorherigen Vortrag eingeführt wurde. Mit der Projektion PS (u) = P[βl ,βr ] (u) kann das Problem
3
semidiffbare Newton Methoden in Funktionsräumen
19
neu geschrieben werden als
ˆ
φ(u) := u − P[βl ,βr ] (u − θ∇J(u))
=0
wobei θ > 0 fest ist. Die Variationsungleichung und φ(u) = 0 sind äquivalente Formulierungen. Wir benötigen die Darstellung mit der Projektion.
Nun berechnen wir den Gradienten:
ˆ
∇J(u),
d
L2 (Ω)
= (y(u) − yd , y 0 (u)d)L2 (Ω) + α(u, d)L2 (Ω)
= (y 0 (u)∗ (y(u) − yd ) + αu, d)L2 (Ω)
Frage 1. Wie hängt das genau mit dem p0 zusammen? warum soll p0 < 2 gelten?
Dadurch ist gewährleistet, dass p ∈ (1, ∞]. Das müsste irgendwas mit einem Einbettungssatz sein.
Daraus folgt, dass
ˆ
∇J(u)
= y 0 (u)∗ (y(u) − yd ) + αu
∗ −1
= B ∗ A−1
A (r + Bu) − yd + αu
=: H(u) + αu
0
Da B ∈ L(Lp (Ω), H −1 (Ω)), ist B ∗ ∈ L(H01 (Ω), Lp (Ω)) mit p = p0 /(p0 − 1) > 2
Daraus folgt, dass der affin lineare Operator
H(u) = B ∗ A−1
∗
A−1 (r + Bu) − yd
eine stetige, affin lineare Abbildung L2 (Ω) → Lp (Ω) ist.
Damit und mit 3.3.1 ist der Operator
1
φ(u) := u − P[βl ,βr ] (− H(u)) = 0
α
semidiffbar.
Nun können wir die semidiffbare Newton Methode für unser optimales Steuerungspro-
3
semidiffbare Newton Methoden in Funktionsräumen
20
blem anwenden:
Data: u0 ∈ L2 (Ω) (möglichst Nah an der Lösung u)
for k = 0, 1, · · · do
Wähle g k ∈ L∞ (Ω) ;
Erhalte sk beim lösen von I + α1 g k · H 0 (uk ) sk = −φ(uk ) ;
uk+1 = uk + sk ;
end
Algorithm 4: semidiffbare Newton Methode für optimale Steuerung
∗
wobei g · H 0 (u) für v 7→ g · (H 0 (u)v) steht. Hier ist H 0 (uk ) = B ∗ (A−1 ) A−1 B und


−(1/α)H(uk )(x) ∈
/ [βl , βr ]
 = 0,
k
k
g (x) = 1,
−(1/α)H(u )(x) ∈ (βl , βr )


∈ [0, 1] −(1/α)H(uk )(x) ∈ {βl , βr }
Die Form des Verfahrens entsteht aus dem semidiffbaren Newtonverfahren und 3.3.1.
Die Gleichung im Newtonverfahren wirklich zu lösen ist nicht ganz einfach. Die kann
man aber vereinfachen, indem man bemerkt, dass sk das Newtonverfahren dann und
nur dann löst, falls sk = dku und (dky , dku , dkµ ) löst


  k 
I
0
A∗
0
dy


  
 0 I − α1 g k · B ∗  dku  = −φ(uk )
dkµ
0
A −B
0
Die Äquivalenz kann durch einfaches nachrechnen gezeigt werden.
3.5 Allgemeine Optimierungsprobleme mit
Ungleichungsbedingungen in L2
Nun wollen wir Probleme der Form
min f (w) s.t. e(w) = 0,
w∈W
cj (w) ≤ 0 a.e. auf Ωj ,
j = 1, · · · , m
(3.3)
lösen, wobei W und Z Banachräume sind, f : W → R, e : W → Z und cj : W → L2 (Ωj )
zweimal stetig F-diffbar sind. Ωj ⊂ Rnj sind messbar und beschränkt.
3
semidiffbare Newton Methoden in Funktionsräumen
21
Dieses impliziert schon optimale Steuerungsprobleme der Form
min f (w) s.t. e(w) = 0,
w∈W
ai ≤ u ≤ bi
i = 1, · · · , l
wobei y ∈ Y der Zustand und u ∈ L2 (Ω1 ) × · · · × L2 (Ωl ) die Kontrollen sind, ai , bi ∈
L∞ (Ωi ). Dies geschieht, indem man die Grenzen ai , bi durch das cj (w) ≤ 0 repräsentiert
mit ci = ai − ui bzw cj = uj − bj
Um das Problem einfach zu halten, betrachten wir nur den Fall mit m=1. Streng
genommen repräsentiert das das optimale Steuerungsproblem nicht, da m ungerade ist
(bzw nur den Fall mit einer Schranke), aber das lassen wir außer acht.
Durch vorherige Theorie wissen wir, dass wir das Problem mittels der Lagrangefunktion
darstellen können. Diese lautet hier:
L : W × L2 (Ω) × Z ∗ → R
L(w, λ, µ) = f (w) + (λ, c(w))L2 (Ω) + hµ, e(w)iZ ∗ ,Z
Wir nehmen an, dass die Nebenbedingungen an der Lösung w ∈ W gelten. Dann kann
das KKT System aufgestellt werden: Es existieren λ ∈ L2 (Ω) und µ ∈ Z ∗ , sodass
(w, λ, µ) folgenden System genügen.
Lw (w, λ, µ) = 0
e(w) = 0
c(w) ≤ 0,
(3.4)
λ ≥ 0,
(λ, c(w))L2 (Ω) = 0
Die letzte Gleichung kann als Variationsungleichung geschrieben werden, also
(−c(w), v − w)L2 (Ω) ≥ 0 ∀v ∈ K
mit K := {u ∈ L2 (Ω)|u ≥ 0}
Dies kann nun wieder mittels Projektion umgeschrieben werden:
λ − PK λ + θc(w) = 0
mit θ > 0 fest. Da PK (u) = P[0,∞) (u(·)) gilt, müssen wir wieder mit Superpositionsoperatoren arbeiten. Um das KKT zu einer semidiffbaren Gleichung zu machen,
3
semidiffbare Newton Methoden in Funktionsräumen
22
brauchen wir einen Glättungsoperator innerhalb der Projektion . Dazu brauchen wir
mehr Theorie. Aber zuerst ein Motivationsbeispiel.
3.6 Anwendung für elliptische optimale Steuerung
3.6.1 Verteilte Kontrolle
Wir betrachten
min
y∈H01 (Ω),u∈L2 (Ω)
1
α
J(y, u) := ky − yd k2L2 (Ω) + kuk2L2 (Ω)
2
2
s.t. Ay = r + Bu,
u≤b
Es gilt:
b ∈ L∞ (Ω)
A : H01 (Ω) → H −1 (Ω)
r ∈ H −1 (Ω)
0
B : Lp (Ω) → H −1 (Ω)
p0 ∈ [1, 2)
elliptischer Differentialoperator 2. Ordnung
gegeben
stetig und linear
sodass H01 (Ω) im Dualraum Lp (Ω), p = p0 /(p0 − 1),
0
von Lp (Ω) stetig eingebettet ist
βl < βr
Jetzt bringen wir das Problem in die Form (3.3) mit m = 1 mit
w = (y, u) W = Y × U
Y = H01 (Ω) U = L2 (Ω)
Z = H −1 (Ω) e(y, u) = Ay − Bu − r
c(y, u) = u − b
Dabei sind e und c stetige affin lineare Operatoren. Die Lagrangefunktion dazu lautet:
L : Y × U × L2 (Ω) × H01 (Ω)L(y, u, λ, µ) = J(y, u) + (λ, c(y, u))L2 (Ω) + hµ, e(y, u)iH01 (Ω),H −1 (Ω)
3
semidiffbare Newton Methoden in Funktionsräumen
23
Dadurch können wir die Optimalitätsbedingungen ausrechnen:
Ly (y, u, λ, µ) = Jy (y, u) + cy (y, u)∗ λ + ey (y, u)∗ µ = y − yd + a∗ µ = 0
Lu (y, u, λ, µ) = Ju (y, u) + cu (y, u)∗ λ + eu (y, u)∗ µ = αu + λ − B ∗ µ = 0
λ ≥ 0,
c(y, u) = u − b ≤ 0,
(λ, c(y, u))L2 (Ω) = (λ, u − b)L2 (Ω) = 0
e(y, u) = Ay − Bu − r = 0
Diese Bedingungen entsprechen denjenigen von (3.4).
Daraus ergibt sich, dass λ = B ∗ µ − αu. Wenn wir dies einsetzen erhalten wir
A∗ µ = −(y − yd )
B ∗ µ − αu ≥ 0,
u ≤ b,
(B ∗ µ − αu, u − b)L2 (Ω)
Ay = r + Bu
Für die Projektion bedeutet dies, dass
b − u − P[0,∞) (b − u − θ(B ∗ µ − αu)) = 0
Für θ = 1/α führt das zu
Φ(u, µ) = b − u − P[0,∞) (b −
1 ∗
B µ) = 0
α
Da B ∗ ∈ L(H01 (Ω), Lp (Ω)) mit p = p0 /(p0 − 1)) > 2 sehen wir, dass
(u, µ) ∈ L2 (Ω) × H01 (Ω) 7→ b −
1 ∗
B µ ∈ Lp (Ω)
α
stetig und affin linear ist.
Frage 2. warum können wir jetzt Thm 3.2.4 anwenden? also ist ja nicht Rm (gleiches
Problem bei Beweis zu 2.3.2
Deshalb ist Φ ∂Φ-semidiffbar mit
∂Φ : L2 (Ω) × H01 (Ω) ⇒ L L2 (Ω) × H01 (Ω), L2 (Ω)
( )
M = (I, − g · B ∗ ), g ∈ L∞ (Ω),
α
∂Φ(u, µ) = M g(x) ∈ ∂ cl P[0,∞) (b(x) − α1 (B ∗ µ)(x)) f.f.a.x ∈ Ω
3
semidiffbare Newton Methoden in Funktionsräumen
24
Hierbei ist die Projektion gegeben durch:


 {0}, t < 0
cl
∂ P[0,∞) (t) =
{1}, t > 0


[0, 1], t = 0
Das semidiffbare Newtonsystem sieht dann wie folgt aus:
 


sy
y k − y d + A ∗ µk
I
0
A∗
k
 



 0 I − gα · B ∗  su  = − uk − b + P[0,∞) (b − α1 B ∗ µk )
A −B
0
sµ
Ay k − Buk − r

Frage 3. (hier nochmal genau verstehen. Die zweite Zeile ist nur Mk sk = Φ. Die
anderen Zeilen kann ich nicht genau sagen. Wie sieht dann der Alorithmus dazu aus?
)
Bei diesem System ist die linke Seite genau die Gleiche, wie bei dem System davor.

Download Report