1

VorlesungEinfuhrung

in dieMathematische Optimierung

(Wintersemester 2016/17)Kapitel 7: Polynomiale Algorithmen fur Konvexe

Optimierungsprobleme

Volker Kaibel

Otto-von-Guericke Universitat Magdeburg

(Version vom 16. Januar 2017)

2

Gliederung

Die Ellipsoid-MethodeEllipsoideDie MethodeKomplexitatsresultate

Innere-Punkte VerfahrenGrundidee und zentrale FragenSelbst-konkordante Barrier-FunktionenDer zentrale PfadDie Short-Step Barrier MethodeErweiterungen

3

Wiederholung: Ellipsoide

Definition

Ist Q ∈ Rn×n symmetrisch und positiv definit, und ist z ∈ Rn, soheißt Ell(z ,Q) := x ∈ Rn : (x − z)TQ−1(x − z) ≤ 1 einEllipsoid (mit Zentrum z). Fur % ∈ R, % > 0, heißtB(z , %) := Ell(z , %2In) der Ball um z mit Radius %.

Affine Transformationen von Einheitsballen

Ist C eine Matrix, deren Spalten bis auf Skalierung mit denQuadratwurzeln der jeweiligen Eigenwerte eine aus Eigenvektorenvon Q bestehende Orthonormalbasis von Rn bilden, so ist

Ell(z ,Q) = C · B(On, 1) + z .

4

Das Lowner-John Ellipsoid eines konvexen Korpers

Definition 7.1

Ein konvexer Korper in Rn ist eine kompakte konvexe Teilmengevon Rn, die einen Ball (mit Radius % > 0) enthalt.

Satz 7.2

fur jeden konvexen Korper K ⊆ Rn gibt es ein eindeutigbestimmtes Ellipsoid (das Lowner-John-Ellipsoid Loew(K ) ⊆ Rn

von K ) minimalen Volumens unter allen Ellipsoiden, die Kenthalten. Es gilt:

z + 1n (Loew(K )− z) ⊆ K ⊆ Loew(K ) ,

wobei z der Mittelpunkt von Loew(K ) sei.

Beweis z.B. in: Danzer, Grunbaum, Klee, Helly’s theorem andrelatives, in: V. Klee, Convexity. AMS 1963, S. 101–180.

5

Lowner-John Ellipsoide abgeschnittener Ellipsoide

Satz 7.3

Seien Q ∈ Rn×n symmetrisch und positiv definit, z ∈ Rn unda ∈ Rn \On. Dann ist

Loew(Ell(z ,Q) ∩ H≤(a, 〈a, z〉)

)= Ell(z ′,Q ′)

mit

z ′ = z − 1n+1b und Q ′ = n2

n2−1

(Q − 2

n+1bbT),

wobei b = 1√aTQa

Qa ist.

Beweis: Abschnitt nach Theorem 3.1.9 in [Grotschel, Lovasz,Schrijver]

6

Volumenreduktion

Satz 7.4

Sind Q ∈ Rn×n symmetrisch und positiv definit, z ∈ Rn unda ∈ Rn \ On, so ist

Vol(Loew

(Ell(z ,Q) ∩ H≤(a, 〈a, z〉)

))Vol(Ell(z ,Q)

) < 1e1/(2n) < 1.

Beweis: Lemma 3.1.34 in [Grotschel, Lovasz, Schrijver]

7

Die “ideale” Ellipsoid-Methode

I Seien K ⊆ Rn ein konvexer Korper und z(0) ∈ Rn, R > 0 mitK ⊆ E (0) := B(z ,R) sowie ε > 0.

I Definiere rekursiv eine (endliche) Folge E (1), . . . ,E (k) ⊆ Rn

von Ellipsoiden mit Zentren z(1), . . . , z(k) wie folgt:

1. Falls z (i) ∈ K oder volE (i) < ε: Setze k := i (Stop)2. Sonst: Wahle ein beliebiges a ∈ Rn mit K ⊆ H≤(a, 〈a, z (i)〉)

(existiert nach Satz 2.15) und definiere

E (i+1) := Loew(E (i) ∩ H≤(a, 〈a, z (i)〉)

).

I Wegen Satz 7.4 ist volE (i) ≤ e−i

2n volE (0) ≤ e−i

2n (2R)n

I Also ist die Folge in der Tat endlich mit

k ≤ 2 ln(2R) n2 + (2 ln 1ε )n + 1 .

8

Binarsuche

I Ein Zulassigkeitsproblem ist die Aufgabe, zu entscheiden, obeine gegebene Menge X ∈ Rn leer ist, und falls X 6= ∅ einbeliebiges x ∈ X zu bestimmen.

I Sind X ⊆ Rn, f : X → R und L,U ∈ R mit

L ≤ minf (x) : x ∈ X ≤ U

gegeben, so kann man mit Hilfe einer Folge vonZulassigkeitsproblemen das Optimierungsproblemapproximativ losen.

I Solange U − L noch nicht klein genug ist:

x ∈ Rn : x ∈ X , f (x) ≤ L+U2

= ∅ : L← (L + U)/2

6= ∅ : U ← (L + U)/2

I “Ideale” Ellipsoid-Methode: Approximative Losung konvexerZulassigkeitsprobleme

9

Algorithmische Reprasentation konvexer Korper

Definition 7.5

Ein (starkes) Separationsorakel fur eine konvexe Menge X ⊆ Rn

ist ein Algorithmus, der fur jedes y ∈ Qn entscheidet, ob y ∈ X ist,und falls y 6∈ X ein a ∈ Qn und β ∈ Q bestimmt mit:

X ⊆ H≤(a, β) aber 〈a, y〉 > β

I P = x ∈ Rn : Ax ≤ b Polyeder mit explizit gegebenerMatrix A ∈ Qm×n und Vektor b ∈ Qm: Implementation einesSeparationsorakels mittels Ausrechnen von Ay und Vergleichmit b.

10

Algorithmische Reprasentation konvexer Korper

Definition 7.6

Fur eine konvexe Menge X ⊆ Rn und ε > 0 definiere

X [ε] := y ∈ Rn : ||y − x || ≤ ε fur ein x ∈ X

undX [−ε] := x ∈ X : x + B(On, ε) ⊆ X .

Definition 7.7

Ein schwaches Separationsorakel fur eine konvexeMenge X ⊆ Rn ist ein Algorithmus, der fur y ∈ Qn und ε ∈ Q(ε > 0) feststellt, dass y ∈ X [ε] ist oder ein a ∈ Qn mit ‖a‖∞ = 1bestimmt, fur das X [−ε] ⊆ H≤(a, 〈a, y〉+ ε) ist.

11

Das schwache Optimierungsproblem

Definition 7.8

Das schwache (konvexe) Optimierungproblem ist die Aufgabe,fur einen konvexen Korper K ⊆ Rn, c ∈ Qn und ε ∈ Q (ε > 0)einen Punkt x? ∈ Qn zu bestimmen mit x? ∈ K [ε] und

〈c , x〉 ≤ 〈c , x?〉+ ε fur alle x ∈ K [−ε] ,

oder K [−ε] = ∅ festzustellen.

I x? ist also fast in K und maximiert 〈c , x〉 fast uber K [−ε].

I Minimieren von 〈c , x〉 via Maximieren von 〈−c , x〉I Konvexe Zielfunktion f :

K := (x , ζ) ∈ Rn+1 : x ∈ K , f (x) ≤ ζ ist konvex mit

minf (x) : x ∈ K = minζ : (x , ζ) ∈ K .

12

Kodierungslangen

Definition 7.9

Wir definieren folgende Kodierungslangen 〈·〉 fur rationaleZahlen, Vektoren und Matrizen:

I Fur n ∈ Z: 〈n〉 := 1 + dlog2(|n|+ 1)eI Fur r ∈ Q: 〈r〉 := 〈p〉+ 〈q〉, wobei r = p

q mit p, q ∈ Zteilerfremd, q > 0

I Fur a ∈ Qn: 〈a〉 :=∑n

i=1〈ai 〉I Fur A = (aij) ∈ Qm×n: 〈A〉 :=

∑mi=1

∑nj=1〈aij〉

13

Komplexitatsresultate fur konvexe Minimierung

Satz 7.10

Es gibt einen Algorithmus und eine Polynomfunktion p, der dasschwache Optimierungsproblem fur durch schwacheSeparationsorakel gegebene konvexe Korper mit hochstensp(〈c〉+ 〈ε〉+ 〈R〉) Orakelaufrufen und Rechenschritten lost. Dabeiist K ⊆ Rn und R ∈ Q eine positive Zahl mit K ⊂ B(On,R), diedem Algorithmus ubergeben werden muss; c ∈ Qn und ε > 0 sindwie in Def. 7.8.

I Corollary 4.2.7 in [Grotschel, Lovasz, Schrijver]

I “Vernunftig gestellte” konvexe Minimierungsprobleme(konvexe Zielfunktion uber konvexer Menge) konnen also inpolynomialer Zeit approximativ gelost werden.

I Insbesondere: Semidefinite Optimierungsprobleme(Trennhyperebene fur nicht positiv-semidefinite symmetrischeMatrizen aus Eigenvektor zu negativem Eigenwert)

14

Komplexitatsresultate fur lineare Optimierung

Satz 7.11

Es gibt einen Algorithmus und eine Polynomfunktion q, der lineareOptimierungsprobleme

max〈c, x〉 : Ax ≤ b (LP)

fur gegebene A ∈ Qm×n, b ∈ Qm und c ∈ Qn in durchq(〈A〉+ 〈b〉+ 〈c〉) beschrankter Laufzeit exakt lost, d.h., eineOptimallosung x? ∈ Qn von (LP) bestimmt oder feststellt, dass(und ob) (LP) unzulassig oder unbeschrankt ist.

I Theorem 6.4.9 in [Grotschel, Lovasz, Schrijver]I Der Beweis (Exakte Losung!) braucht Strukturresultate uber

Polyeder aus Kap. 5.I Insbesondere: Lineare Optimierungsprobleme haben rationale

Optimallosungen (wenn sie nicht unbeschrankt oderunzulassig sind).

15

Bemerkungen zur Ellipsoid-Methode

Bemerkung 7.12

Sind die Ungleichungssysteme Ax ≤ b nicht explizit gegeben,sondern hat man fur eine Klasse von linearenOptimierungsproblemen nur (starke) Separationsorakel fur diePolyeder der zulassigen Losungen, so kann man die LPs trotzdemin polynomialer Laufzeit losen, sofern die Separationsorakelpolynomiale Laufzeit haben (bezuglich der Kodierungslangen derrelevanten Problemdaten).

I Die Ellipsoid-Methode liefert fur die komplexitatstheoretischeKlassifikation von Optimierungsproblemen eminent wichtigeErgebnisse. . .

I . . . jedoch keine praktisch brauchbaren Algorithmen fur dielineare oder konvexe Optimierung

I Technische Bedingung an die Orakel fur Satz 7.10 undBem. 7.12: Die Kodierungslange der Ausgabe muss polynomialbeschrankt sein in der Kodierungslange der Eingabe.

16

Das Setup

I min〈c , x〉 : x ∈ XI X ∈ Rn: konvexe Menge, c ∈ Rn

I (Konvexe Zielfunktion f : Rn → R: mint : f (x) ≤ t, x ∈ X)

0.2

0.4

0.6

0.8

0.2

0.4

0.6

0.8

0

2

4

6

0.2

0.4

0.6

0.80 0.2 0.4 0.6 0.8 1

0

0.2

0.4

0.6

0.8

1

Beispiel: min〈c , x〉 : x ∈ X, X = [0, 1]2, c = (5, 2)

17

Beispiel

I Fur η > 0 definiere fη : int(X )→ R mittels:

fη(x) = η · 〈c , x〉+(− ln x1 − ln x2 − ln(1− x1)− ln(1− x2)

)

0.2

0.4

0.6

0.8

0.2

0.4

0.6

0.8

20

40

60

80

100

0.2

0.4

0.6

0.8 0 0.2 0.4 0.6 0.8 1

0

0.2

0.4

0.6

0.8

1

I fη streng konvex, Minimum eindeutig in z(η) ∈ int(X )

I Fur großes η: z(η) in der Nahe einer Optimallosung vonmin〈c , x〉 : x ∈ X.

I Newton-Verfahren fur fη zur Approximation von z(η)

18

Verschiedene η

η = 0.1 η = 1 η = 10

I Wichtig fur Newton-Verfahren: Start nah bei z(η)I Ansatz: Folge η1 < η2 < . . .

I Bestimme η0 und Punkt x (0) ∈ int(X ) in der Nahe von z(η0).I Fur k > 0: Bestimme ηk > ηk−1 und mache einen

Newton-Schritt fur fηk von x (k−1) zu x (k) ∈ int(X ).

19

Fragen

1. Welche Funktionen konnen i.A. die Rolle von

− ln x1 − ln x2 − ln(1− x1)− ln(1− x2)

spielen? ( (selbstkonkordante) Barrier-Funktionen)

2. Konvergiert z(η) fur η →∞ gegen eine Optimallosung?

3. Wie findet man η0 und x (0)?

4. Wie erreicht man, dass x (k) in int(X ) ist? Wie groß darfηk − ηk−1 sein, damit x (k) ebenfalls nah an z(ηk) ist(vorausgesetzt, dass x (k−1) nah an z(ηk−1) ist)?

5. Was heißt “nah”?

6. Wie groß muss k sein, damit (fur vorgegebenes ε > 0)

〈c, x (k)〉 −min〈c , x〉 : x ∈ X < ε

ist?

7. Welche arithmetischen Operationen mussen durchgefuhrtwerden?

20

Intrinsische SkalarprodukteGeneralvoraussetzungen von jetzt an:

I D ⊆ Rn offen und konvex

I f : D → R zweimal stetig differenzierbar

I hessx f positiv definit fur alle x ∈ D (f streng konvex)

Definition 7.13

Fur jedes x ∈ D sei 〈·, ·〉x : Rn × Rn → R das durch

〈v ,w〉x = 〈v , (hessx f )w〉 = 〈(hessx f )v ,w〉 = vT(hessx f )w

definierte Skalarprodukt auf Rn. Die von diesem Skalarproduktinduzierte Norm bezeichnen wir mit ‖·‖x : Rn → R:

‖v‖x =√〈v , v〉x

Der offene Ball vom Radius % > 0 bzgl. ‖·‖x um v istBx(v , %) = w ∈ Rn : ‖w − v‖x < % .

21

Beispiele

22

Selbstkonkordante FunktionenI D → Sn, x 7→ hessx f ist stetigI Fur alle v ∈ Rn \ On und fur jedes x ∈ D und ε > 0 gibt es

eine Umgebung U ⊆ D von x mit:

1− ε ≤ ‖v‖x‖v‖y

≤ 1 + ε fur alle y ∈ U

Definition 7.14

Die Funktion f heißt selbstkonkordant, wenn fur alle x ∈ D gilt:

I Bx(x , 1) ⊆ D und

I Fur alle y ∈ Bx(x , 1) ist

1−‖y − x‖x ≤‖v‖x‖v‖y

≤ 1

1− ‖y − x‖xfur alle v ∈ Rn\On

(Literatur: strongly non-degenerate self-concordant function)

23

In der Nahe des Randes

Satz 7.15

Sind f selbstkonkordant und (x (k))k∈N eine Folge in D mit

limk→∞

x (k) ∈ bd(D) ,

(mit bd(D) = cl(D) \ D) so gelten

limk→∞

f (x (k)) =∞

undlimk→∞

||gradx(k) f || =∞ .

Beweis: [Renegar, Thm. 2.2.9]

James Renegar, A Mathemtical View of Interior-PointMethods in Convex Optimization. MPS-SIAM Series onOptimization , SIAM 2001.

24

Newton-Schritte

Definition 7.16

Wir bezeichnen mit

newx(f ) := −(hessx f )−1 gradx f ∈ Rn

den Newton-Schritt fur f in x ∈ D.

I Wir haben: newx(f ) = On ⇔ gradx f = On

I Also wegen der Konvexitat von f :

Beobachtung 7.17

Ein Punkt x ∈ D ist genau dann der Minimierer von f (uber D),wenn newx(f ) = On gilt.

25

Abschatzungen fur selbstkonkordante Funktionen

Satz 7.18

Sind f selbstkonkordant und x ∈ D mit γ := ‖newx(f )‖x < 1, soist x ′ = x + newx(f ) ∈ D und es gilt:

‖newx ′(f )‖x ′ ≤( γ

1−γ)2.

Beweis: [Renegar, Thm. 2.2.4]

Satz 7.19

Sind f selbstkonkordant und x ∈ D mit γ := ‖newx(f )‖x ≤ 14 , so

hat f einen eindeutigen Minimierer z ∈ D, und es gilt

‖x − z‖x ≤ γ + 3γ2

(1−γ)3 .

Beweis: [Renegar, Thm. 2.2.5]

26

Barrier-Funktionen

Definition 7.20

Die Funktion f : D → R ist eine Barrier-Funktion, wenn sieselbstkonkordant ist und ihr Komplexitatswert

ϑf := sup‖newx(f )‖x : x ∈ D < ∞

endlich ist.

Satz 7.21

Ist f eine Barrier-Funktion mit Komplexitatsparameter ϑf , so gilt

〈gradx f , y − x〉 < ϑf

fur alle x , y ∈ D.

Beweis: [Renegar, Thm. 2.2.3]

27

Addition von Barrier-Funktionen

Satz 7.22

Sind f1 : Df1 → R und f2 : Df2 → R Barrier-Funktionen mitD := Df1 ∩ Df2 6= ∅ und Komplexitatsparametern ϑ1 bzw. ϑ2, soist f1 + f2 : D → R eine Barrier-Funktion mit ϑf ≤ ϑ1 + ϑ2.

Beweis: [Renegar, Thm. 2.2.6 und 2.3.1]

Bemerkung 7.23

Durch f (x) := − ln x wird eine Barrierfunktion aufR++ := x ∈ R : x > 0 definiert mit ϑf = 1.

Korollar 7.24

Durch f (x) := −∑n

i=1 ln xi ist eine Barrier-Funktion auf Rn++ mit

ϑf ≤ n definiert.

28

Barrier-Funktionen fur Polyeder

Satz 7.25

Ist f : R++ ⊆ R eine Barrierfunktion und sind a ∈ Rn \ On,β ∈ R, so ist auch

fa,β : x ∈ Rn : 〈a, x〉 < β → R mit fa,β(x) = f (β − 〈a, x〉)

eine Barrier-Funktion mit ϑfa,β ≤ ϑf .

Beweis: [Renegar, Theoreme 2.2.7 und 2.3.2]

Korollar 7.26

Sind A ∈ Rm×n und b ∈ Rm so, dassx ∈ Rn : Ax < b = int(P≤(A, b)) 6= ∅

ist, so ist f : int(P≤(A, b))→ R mit

f (x) = −m∑i=1

ln(bi − Ai ,?x)

eine Barrier-Funktion mit ϑf ≤ m.

29

Affine UnterraumeI Sei A ⊆ Rn affiner Unterraum.I Affiner Isomorphismus A ↔ Rp liefert

Differenzierbarkeitsbegriff fur Funktionen auf AI Begriff der Selbstkonkordanz von auf (relativ offenen)

Teilmengen von A definierten FunktionenI Unabhangig von Wahl des Ismorphismus A ↔ Rp

Bemerkung 7.27

Sind f eine Barrier-Funktion und A ⊆ Rn ein affiner Unterraummit D ∩ A 6= ∅, so ist die Einschrankung f |A von f auf A eineBarrier-Funktion auf D ∩ A mit ϑf |A ≤ ϑf .

(Siehe [Renegar, Abschn. 2.2.1 und 2.3.1])

Korollar 7.28

Sind A ∈ Rm×n und b ∈ Rm so, dass es ein x ∈ Rn++ gibt mit

Ax = b, so ist durch f (x) := −∑n

i=1 ln xi eine Barrier-Funktionauf relintx ∈ Rn

+ : Ax = b mit ϑf ≤ n definiert

30

Eine Barrier-Funktion fur Sk+

Satz 7.29

Die Funktion f : relint(Sk+)→ R mit f (X ) = − ln(detX ) ist eine

Barrier-Funktion mit ϑf = k .

Beweis: [Renegar, Abschn. 2.2.1]

Korollar 7.30

Sind A(1), . . . ,A(m) ∈ Sk , b ∈ Rm so, dass es eine positiv definiteMatrix X ∈ Sk gibt mit 〈A(i), X 〉 = bi fur alle i ∈ [m] , so definiertf (X ) = − ln(det(X )) eine Barrier-Funktion auf

relintX ∈ Sk+ : 〈A(i),X 〉 = bi fur alle i ∈ [m]

mit ϑf ≤ k .

31

Der zentrale PfadGeneralvoraussetzungen von jetzt an:I D ⊆ Rn offen und konvexI f : D → R Barrier-FunktionI A ⊆ Rn affiner Unterraum (A = Rn moglich)I D ′ = D ∩ A 6= ∅ beschrankt, X = cl(D ′)I c ∈ Rn, ω := min〈c , x〉 : x ∈ X

Definition 7.31

Fur η ∈ R+ definiere streng konvexe Funktionen fη : D ′ → Rdurch fη(x) := η〈c , x〉+ f (x)

fur alle x ∈ D ′. Der Minimierer von fη sei z(η) ∈ D ′. Der zentralePfad von (fη)η∈R+ ist z(η) : η ∈ R+.

Beobachtung 7.32

Die intrinsischen Skaparprodukte bzgl. der Funktionen fη sind dieintrinsischen Skalarprodukte bzgl. f ; insbesondere sind alle fηselbstkonkordant.

32

Auf dem zentralen PfadI Es gilt: gradz(η) fη = On fur alle η ∈ R+

I Andererseits: gradz(η) fη = ηc + gradz(η) fI Also: gradz(η) f = −ηcI Wegen Satz 7.21 fur alle y ∈ D ′: 〈gradz(η) f , y − z(η)〉 < ϑf

I Also fur alle y ∈ D ′: 〈c , z(η)〉 − 〈c , y〉 < ϑfη

Bemerkung 7.33

Fur alle η ∈ R+ gilt 〈c , z(η)〉 ≤ ω+ 1ηϑf . Insbesondere (Frage 2):

limη→∞〈c, z(η)〉 = ω

Außerdem gilt fur alle y ∈ Rn:

〈c , y〉 ≤ ω + 1ηϑf (1 + ‖y − z(η)‖z(η))

(Beweis: [Renegar, Abschnitt 2.4.1])

33

Der Short-Step Barrier Algorithmus

1. Bestimme eine Iterationszahl K .

2. Bestimme η0 > 0 und x (0) ∈ D ′ mit ‖newx(0)(fη0)‖x(0) ≤ 19 .

3. Fur k = 1, . . . ,K :

3.1 Setze ηk := (1 + 18√ϑf

)ηk−1.

3.2 Berechne newx (k−1) (fηk )3.3 Setze x (k) := x (k−1) + newx (k−1) (fηk )

Lemma 7.34

Fur alle k gilt:

1. ‖newx(k−1)(fηk )‖x(k−1) < 1 (also x (k) ∈ D ′ fur alle k)

2. ‖newx(k)(fηk )‖x(k) ≤ 19

Beweis: [Renegar, Abschnitt 2.4.2] (Fragen 4,5)

34

AnalyseI Nach Satz 7.19 also:

‖x (k) − z(ηk)‖x(k) ≤19 ( 8

9 )3 + 3( 19 )2

( 89 )3

≤ 1

6.

I Definition der Selbstkonkordanz (mit x = x (k), y = z(η),v = x − y):

‖x (k) − z(ηk)‖x(k)

‖x (k) − z(ηk)‖z(ηk )

≥ 5

6

I Also fur alle k : ‖x (k) − z(ηk)‖z(ηk ) ≤ 15

I Nach Bem 7.33 also: 〈c , x (k)〉 ≤ ω + 1ηk

6ϑf5

Lemma 7.35

Fur ε > 0 und K ≥ 10√ϑf ln 6ϑf

5η0εist x (K) ∈ D ′ mit

〈c, x (K)〉 ≤ ω + ε.

(Frage 6)

35

Die Bestimmung von η0 und x (0)

I (Frage 3)

I newx(fη) = −η(hessx f )−1c + newx(f )

I Ziel: Finde ein x ∈ D ′ mit ‖newx(f )‖x ≤ 16 (Z)

I (newx(f ) = On ⇔ x minimiert f uber D ′)

I Dann setze:

η0 :=1

12‖(hessx f )−1c‖x

I Dann ist ‖newx(fη0)‖x ≤ 112 + 1

6 = 14

I Furx (0) := x + newx(fη)

gilt dann wegen Satz 7.18 (mit γ = 14 ):

‖newx(0)(fη0)‖x(0) ≤(1/4

3/4

)2=

1

9

36

Erreichen des Ziels (Z)

I Gegeben: Ein beliebiger Punkt x (0) ∈ D ′

I Sei g := − gradx(0) fI Fur 0 < ν ≤ 1:

I Definiere fν : D ′ → R via fν(x) := ν〈g , x〉+ f (x)I Der Minimierer von fν sei z(ν)

I gradx(0) f1 = g + gradx(0) f = On

I Also: z(1) = x (0) und newx(0)(f1) = On

I Algorithmus:1. ` := 0, ν0 := 12. Solange ‖newx (`) (f )‖x (`) > 1

6 ist:2.1 Inkrementiere `2.2 Setze ν` := (1− 1

8√ϑf

)ν`−1

2.3 Berechne newx(`−1)(fν`)2.4 Setze x (`) := x (`−1) + newx(`−1)(fν`)

I Analog zu Lemma 7.34 zeigt man fur alle `:I ‖newx (`−1) (fν`)‖x (`−1) < 1 (also x (`) ∈ D ′ fur alle `)I ‖newx (`) (fν`)‖x (`) ≤ 1

9

37

Wie klein muss ν` werden?

I Gilt: newx(`)(fν`) = −ν`(hessx(`) f )−1g + newx(`)(f )

I Also (wegen ‖newx(`)(fν`)‖x(`) ≤ 19 ):

‖newx(`)(f )‖x(`) ≤ 19 + ν`‖(hessx(`) f )−1 gradx(0) f ‖x(`)

= 19 + ν`

√gradx(0) f T(hessx(`) f )−1 gradx(0) f

Satz 7.36

Ist f : D ′ → R eine Barrier-Funktion, so gilt fur alle x , y ∈ D ′:√gradx f

T(hessy f )−1 gradx f ≤(

1 +1

sym(x ,D)

)ϑf

Beweis: [Renegar, Proposition 2.3.7]

38

Die Symmetrie von D

Definition 7.37

Fur x ∈ D ′ sei L(x ,D ′) die Menge aller affinen Geraden L ⊆ A mitx ∈ L. Fur L ∈ L(x ,D ′) ist L ∩ D ′ eine (offene) Strecke, die von xin zwei Teile der Langen λ1, λ2 > 0 geteilt wird; seir(L) := minλ1

λ2, λ2λ1. Die Symmetrie von D bzgl. x ist

sym(x ,D) := infr(L) : L ∈ L(x ,D) .

39

Zuruck zu ν`I Also mit Satz 7.36:

‖newx(`)(f )‖x(`) ≤ 19 + ν`

(1 +

1

sym(x (0),D)

)ϑf

I Daher gilt ‖newx(`)(f )‖x(`) ≤ 16 , sobald

ν` ≥(

18ϑf (1 +1

sym(x (0),D)))−1

ist.

I Mit Ω := sup〈c , x〉 : x ∈ D ′ kann man zeigen:‖(hessx f )−1c‖x ≤ Ω− ω fur alle x ∈ D ′

[Renegar, Abschnitt 2.4.1]

I Also

η0 =1

12‖(hessx f )−1c‖x≥ 1

12(Ω− ω)

40

Das Ergebnis

Satz 7.38

Fur einen gegebenen Startpunkt x (0) ∈ D ′ und 0 < ε < 1berechnet der Short-Step Barrier Algorithmus in

O(√ϑf ln ϑf

ε sym(x(0),D′))

Newton-Iterationen einen Punkt x (K) ∈ D ′ mit

〈c,x(K)〉−ωΩ−ω ≤ ε .

41

Arithmetischer Aufwand

I (Frage 7)

I Ein Newton-Schritt erfordert dabei die Berechnung vonnewx(fη) bzw. newx(fν).

I Da hessx fη = hessx fν = hessx f ist, muss in jedem Schritt furein g ∈ Rn die Losung v ∈ Rn eines linearenGleichungssystems (hessx f )v = g gefunden werden.

I Beispiel f (x) = −∑m

i=1 ln(bi − 〈Ai ,?, x〉), D = int(P≤(A, b)):I Sei ∆(x) ∈ Rm×m die Diagonalmatrix mit

∆i,i = (bi − 〈Ai,?, x〉)−1

I Dann ist hessx f = ∆(x)ATA∆(x).I ATA positiv semidefinit, also gibt es Cholesky-Zerlegung

ATA = CCT mit oberer Dreiecksmatrix C .I Hat man die Cholesky-Zerlegung einmal berechnet, kann man

danach in jeder Iteration das Gleichungssystem(∆(x)C )(∆(x)C )T = g in O(n2) arithmetischen Operationenlosen.

42

Primal-duale Methoden fur konische Probleme

I Fur f : D → R definiert f ?(u) = − inf〈u, x〉+ f (x) : x ∈ Ddie zu f konjugierte Funktion auf Rn.

I Sind K ⊆ Rn ein konvexer Kegel, D = int(K ) und f eineBarrier-Funktion, so ist f ? eine Barrier Funktion fur int(K ).

I Primal-duale Methoden verfolgen die zentralen Pfade furprimales und duales Problem simultan.

I Geschickte Schrittwahl (nicht Newton) durch Ausnutzen derdualen Informationen (z.B. Nesterov-Todd Richtungen)

I Sehr erfolgreich in der Praxis.

I Insbesondere: Stets aktuelle Gutegarantie uber dual zulassigeLosung.

43

Komplexitatsresultate

I Lineare Optimierungsprobleme konnen mit Barrier-Methodenin polynomialer Zeit exakt gelost werden.

I Fur min〈c , x〉 : Ax ≤ b hangt die Laufzeit polynomial von〈A〉+ 〈b〉+ 〈c〉 ab.

I Schwierigkeiten:I Wie findet man uberhaupt einen zulassigen Punkt?I Wie findet man eine exakte Losung?

I Semidefinite Optimierungsprobleme (unterRegularitatsannahmen) konnen in polynomialer Zeit(approximativ) gelost werden.

I Geeignete Varianten von Innere-Punkte Methoden sind (imGegensatz zur Ellipsoid-Methode) praktisch effizient.