9. ¨Ubung zu Optimierung I - Heinrich-Heine

Prof. F. Jarre
Institut für Mathematik
Heinrich Heine Universität Düsseldorf
15.1.2016
9. Übung zu Optimierung I
1. Man betrachte ein lineares Programm im Standardformat,
minimiere cT x | Ax = b, x ≥ 0,
wobei die Zeilen von A ∈ IRm×n mit (ai )T bezeichnet seien für 1 ≤ i ≤ m. Setze
fi (x) := −xi für 1 ≤ i ≤ n und fj (x) := (aj−n )T x − bj−n für n + 1 ≤ j ≤ n + m.
Man zeige:
(a) Die erweiterte Lagrangefunktion zu obigem Problem ist für jedes r > 0 konvex in
x und konkav in y.
(b) Sei x̄ eine eindeutige Optimallösung und ȳ ∈ IRn+m ein eindeutig bestimmter, strikt
komplementärer Multiplikator in x̄. Dann ist die erweiterte Lagrangefunktion in
der Nähe von x̄ streng konvex in x.
(Bem.: In der “Einführung in die Optimierung” wurde gezeigt, dass bei lösbaren
linearen Programmen immer eine strikt komplementäre Optimallösung existiert;
die strikte Komplementarität folgt somit aus der Eindeutigkeit.)
2. Gegeben sei das Problem
(P )
min{x21 + x2 | kxk∞ ≤ 1 }.
Zur Beschreibung der zulässigen Menge verwende man die Funktionen f1 (x) = x1 − 1,
f2 (x) = x2 −1, f3 (x) = −x1 −1 und f4 (x) = −x2 −1. Man gebe die erweiterte LagrangeFunktion Λ(x, y, r) und deren erste Ableitung ∇x,y Λ(x, y, r) an.
Sei ϕr (y) := Λ(x(y), y, r), wobei x(y) := arg minx∈IRn Λ(x, y, r). (Man nehme dabei an,
dass x(y) im betrachteten Bereich wohldefiniert und eindeutig ist.)
Für r := 1 und y 0 := (1, 1, 1, 2)T verwende man das folgende Verfahren, um die Optimallösung von (P ) zu ermitteln.
Für k = 0, 1, 2, . . .
1. Bestimme xk+1 := x(y k ) = arg minx∈IRn Λ(x, y k , r).
2. Falls (xk+1 , y k ) KKT-Punkt, STOPP.
3. Setze y k+1 := y k + r∇y ϕ(y k ).
3. Man betrachte erneut das Problem (P ) aus Aufgabe 1. Man verwende das folgende
Verfahren, um die Optimallösung anzunähern:
Ausgehend vom Startpunkt (1, 1)T linearisiere man in jedem Schritt zunächst die Zielfunktion und die Nebenbedingungen. Man gebe als nächstes die Optimallösung des
linearisierten Problems an und führe entlang dieser Richtung eine exakte line-search
aus, um die neue Iterierte zu bestimmen.
Bemerkung: Da hier der zulässige Bereich konvex ist und die Abstiegsrichtungen immer
strikt zulässig sind ist dieses Vorgehen überhaupt möglich.
Man diskutiere die Kovergenzrate dieses Ansatzes für wachsende Iterationszahl k.
Abgabe: Am 22. 1. 2016 zu Beginn der Vorlesung

Download Report