Probeklausur zu

Technische Universität München
Zentrum Mathematik, M1
Prof. Dr. Boris Vexler
Dr. Dominik Meidner
Probeklausur zu „Nichtlineare Optimierung: Grundlagen“ (WS 2009/10)
Aufgabe 1 (10 Punkte: -1/0/1 Punkte für falsche/keine/richtige Antwort): In der
Gesamtwertung dieser Aufgabe können keine negativen Punkte erzielt werden, d. h. bei einer
negativen Gesamtpunktzahl wird diese Aufgabe mit null Punkten bewertet.
In dieser Aufgabe sei f : Rn → R eine zweimal stetig differenzierbare Funktion.
a) Für eine vom allgemeinen Abstiegsverfahren erzeugte Folge (xk ) gilt
f (xk+1 ) < f (xk ) ∀k ∈ N.
wahr falsch b) Die vom Gradientenverfahren erzeugte Folge (xk ) konvergiert gegen einen stationären Punkt.
wahr falsch wahr c) Die Armijoregel erzeugt zulässige Schrittweiten.
d) Eine Schrittweite, die der Armijobedingung mit γ <
Bedingungen (bei gleichem Parameter γ).
1
2
falsch genügt, erfüllt auch die Powell-Wolfewahr falsch e) Eine Schrittweite, die den Powell-Wolfe-Bedingungen genügt, erfüllt auch die Armijobedingung (bei gleichem Parameter γ).
wahr falsch f) Es sei x0 ∈ Rn der Startpunkt für das Gradientenverfahren mit Armijoregel, angewendet
auf f . Die Niveaumenge Nf (x0 ) sei beschränkt. Das Verfahren erzeuge die Folge (xk ). Mit
dem globalen Konvergenzsatz folgt unmittelbar, dass es eine Teilfolge von (xk ) gibt, die
gegen einen stationären Punkt konvergiert.
wahr falsch g) Sei x∗ ∈ Rn ein lokales Minimum von f , in dem die hinreichenden Optimalitätsbedingungen
zweiter Ordnung erfüllt sind (insbesondere ist also ∇f (x∗ ) = 0). Dann gilt: Es gibt eine
Umgebung von x∗ , in der sich keine weitere Gradientennullstelle befindet.
wahr falsch h) Sei x∗ ∈ Rn ein lokales Minimum von f . Wir wenden das lokale Newtonverfahren für
Optimierungsprobleme auf f an. Es erzeuge eine gegen x∗ konvergente Folge. Dann gilt: In
x∗ gelten die hinreichenden Optimalitätsbedingungen zweiter Ordnung.
wahr falsch i) Wir wenden das globalisierte Newtonverfahren mit Armijo-Regel auf f an. Es erzeuge die
Folge (xk ) ⊂ Rn . Dann gilt: Jeder Häufungspunkt von (xk ) ist stationär.
wahr falsch j) Wir wenden das globalisierte Newtonverfahren mit Armijo-Regel auf f an. Die erzeugte
Folge von Iterierten (xk ) konvergiere gegen ein Minimum x∗ von f , in dem die hinreichenden
Optimalitätsbedingungen 2. Ordnung erfüllt sind. Dann gilt: Die Folge (xk ) konvergiert
q-superlinear gegen x∗ .
wahr falsch Seite 1 von 2
Aufgabe 2 (ca. 15 Punkte):
Wir betrachten das Optimierungsproblem
1
α
min q(x) := kAx − bk22 + kxk22
2
2
x∈Rn
(P)
mit der Matrix A ∈ Rm×n , dem Vektor b ∈ Rm und der positiven Zahl α > 0.
a) Zeigen Sie, dass es sich bei (P) um ein quadratisches Optimierungsproblem handelt, indem
Sie q in die Standardform einer quadratischen Funktion, d. h.
1
q(x) = xT Cx + cT x + γ,
2
überführen, mit symmetrischer Matrix C ∈ Rn×n , c ∈ Rn und γ ∈ R.
(*)
b) Zeigen Sie, dass die von Ihnen ermittelte Matrix C positiv definit ist.
Hinweis: Sollten Sie Teil a) nicht bearbeitet haben, können Sie ab Teil c) die Form (*) für q
verwenden.
c) Begründen Sie, dass q genau ein lokales Minimum x∗ ∈ Rn besitzt und dass dieses sogar ein
globales Minimum ist. Berechnen Sie x∗ .
d) Wir betrachten einen Schritt des lokalen Newtonverfahrens zur Minimierung von q mit
gegebenem Startpunkt x0 ∈ Rn . Bestimmen Sie dazu zunächst s0 und anschließend x1 =
x0 + s 0 .
e) Wie viele Iterationen sind bei Verwendung des lokalen Newtonverfahrens zur Bestimmung
des Minimums von q maximal erforderlich?
Aufgabe 3 (ca. 15 Punkte):
Wir betrachten die quadratische Funktion
1
f (x) := xT Cx + cT x
2
mit einer symmetrischen, positiv definiten Matrix C ∈ Rn×n und c ∈ Rn . Weiter sei s ∈ Rn eine
Abstiegsrichtung von f im Punkt x ∈ Rn und
σ ∗ := arg min ϕ(σ)
mit
ϕ(σ) := f (x + σs)
σ≥0
bezeichne die durch die Minimierungsregel gelieferte Schrittweite.
a) Zeigen Sie, dass ϕ streng konvex ist und folgern Sie, dass σ ∗ wohldefiniert und sogar eindeutig
bestimmt ist.
b) Begründen Sie, dass σ ∗ > 0 gilt.
c) Zeigen Sie, indem Sie ϕ(σ) durch f (x), ∇f (x) und ∇2 f (x) ausdrücken, dass σ ∗ für alle
γ ∈ (0, 12 ] der Armijo-Bedingung
f (x + σ ∗ s) − f (x) ≤ σ ∗ γ∇f (x)T s
genügt, aber für kein γ > 21 .
d) Zeigen Sie, dass σ ∗ außerdem für jedes η ≥ 0 die zweite Bedingung der Powell-Wolfe-Schrittweitenregel
∇f (x + σ ∗ s)T s ≥ η∇f (x)T s
erfüllt.
Seite 2 von 2

Download Report