1. Dienstag, 15. Oktober 2013
Einführung: mathematische Programme, lineare vs. nichtlineare Programme, konvexe Programme
Kapitel I Konische Optimierung
I.1 Konvexe Kegel
Def. 1: a) konvexer Kegel, b) spitzer Kegel, c) ordentlicher Kegel
Spitze Kegel definieren Positivitätsbereiche und partielle Ordnungen
Prop. 2: Reflexivität, Antisymmetrie, Transitivität, Homogenität, Additivität
strikte Ungleichungen und Volldimensionalität
Abgeschlossenheit und Grenzwertbildung
I.2 Konstruktionen und Beispiele
Def. 1: a) konische Hülle, b) endlich erzeugte Kegel
Satz 2: a) konische Hülle b) Minkowski-Weyl
Def. 3: direktes Produkt
Def. 4: Dualer Kegel
Satz 5: a) K ist in (K^*)^* enthalten b) K = (K^*)^* falls K abgeschlossen
Satz 6: Trennende lineare Hyperebene
Bew: von Satz 5
2. Donnerstag, 17. Oktober 2013
Bew: von Satz 6 mit Hilfe der metrischen Projektion
Bsp. 7: Untervektorräume
Bsp. 8: Nichnegativer Orthant
Bsp. 9: Lorentzkegel
Bsp. 10: Kegel der positiv semidefiniten Matrizen
3. Dienstag, 22. Oktober 2013
Spektralzerlegung
Bsp. 11: Endlich erzeugte Kegel
Bem. 12: Koecher-Vinberg Klassifikation
I.3 Konische Programme
Def. 1: primales konisches Programm, duales konisches Programm
Geometrische Interpretation
Bsp. 2: Lineare Programme (LP)
Bsp. 3: Konische quadratische Programme (CQP)
4. Donnerstag, 24. Oktober 2013
Bsp. 4: Semidefinite Programme (SDP)
Lemma 5: Schurkomplement
Korollar 6: Lorentzkegel darstellbar mit Hilfe einer linearen Matrixungleichung
I.4 Alternativsätze
Lemma 1: Farkas Lemma für LP
Verallgemeinerungsversuch für konische Programme
Bsp. 2: Primales und duales System hat keine Lösung
Def. 3: schwach zulässiges System
Satz 4: Alternativsatz für schwach zulässige primale Systeme
Korollar 5: Alternativsatz für schwach zulässige duale Systeme
5. Dienstag, 29. Oktober 2013
Satz 6: Alternativsatz für strikt zulässige primale Systeme
Satz 7: Existenz von Trennhyperebenen
I.5 Dualitätstheorie
Def. 1: Dualitätslücke
Theorem 2: a) schwache Dualität, b) komplementärer Schlupf, c) Optimalitätsbedingung, d) starke Dualität
6. Donnerstag, 31. Oktober 2013
Ende von Beweis von Theorem 2
Kapitel II Semidefinite Optimierung
II.1 Grundlagen
Primales und duales SDP
Bem. 1: Lösungsverfahren von SDPs
Bsp.: sparse sdpa format
II.2 Eigenwertoptimierung
Rayleigh-Ritz-Prinzip
Satz 1: Berechnung des größten Eigenwerts mit SDP
7. Dienstag, 5. November 2013
Nachtrag II.1:
Bsp. 2: d^* nicht angenommen
Bsp. 3: positive Dualitätslücke
Satz 4: Charakterisierung von positiv semidefinite Matrizen
zurück zu II.2:
Def. 2: Extrempunkte konvexer Mengen
Satz 3: C konvex, kompakt, dann C = conv(ext(C)).
Satz 4: Fan, SDP-Formulierung der Summe der k-größten Eigenwerte
Lemma 5: Extrempunkte der zulässigen Lösungen der SDP Formulierung
8. Donnerstag, 7. November 2013
II.3 Relaxierung quadratischer Programme
Def. 1: quadratisches Programm
Bsp. 2: MAX CUT
Bsp. 3: Unabhängigkeitszahl
Satz 4: SDP Relaxierung von QP
Def. 5: MAX CUT Entscheidungsproblem
Def. 6: PARTITION
Satz 7: MAX CUT ist NP vollständig
9. Dienstag, 12. November 2013*
Satz 8: MAX CUT >= 0,878… * SDP-Relaxierung
Randomisiertes Runden
Lemma 9: Grothendieck Identität
Lemma 10: 0,878… <= Funktion, die im Beweis zu Satz 8 auftaucht
10. Donnerstag, 14. November 2013*
Lemma 11: Darstellung von mc(G,w) durch Laplace-Matrix
Verallgemeinerung von mc(G,w) zu quadratischen Programmen qp(A) mit {-1,+1}-Vektoren
Lemma 12: X psd impliziert arcsin(X)-X psd
Satz 13: sdp(A) >= qp(A)>= 2/pi sdp(A)
II.4 Grothendieck-Ungleichung
Definition von ||A||_{infty->1} und SDP Relaxierung
Satz 1: Grothendieck-Ungleichung
11. Dienstag, 19. November 2013
Satz 1: Grothendieck-Ungleichung
Lemma 2: Krivines Trick
Exkurs: Tensorprodukte
12. Donnerstag, 21. November 2013
Verwendung der Grothendieck-Ungleichung in der statistischen Physik
II.5 Approximation von MAX-2-SAT
Satz 1: sdp(a,b) >= qp(a,b) >= 0.878… sdp(a,b)
Def. 2: SAT
Def. 3: MAX-2-SAT
Satz 4: 0.878…-Approximation von MAX-2-SAT in polynomieller Zeit
13. Dienstag, 26. November 2013
Kapitel III Packungen und Färbungen in Graphen
III.1 Defintionen
komplementäre Graphen, unabhängige Mengen, Cliquen, Unabhängigkeitszahl, Cliquenzahl, k-Färbung, chromatische Zahl, Komplexität
III.2 Semidefinite Programmierungsschranke
Def. 1: Lovasz-Theta
Satz 2: Lovasz Sandwich Theorem
III.3 Perfekte Gaphen
Def. 1: induzierte Teilgraphen
Def. 2: perfekte Graphen
Bsp. 3:
a) bipartite Graphen sind perfekt
b) Kreisgraphen ungerader Länge sind nicht perfekt
c) Kantengraphen von bipartiten Graphen sind perfekt
14. Donnerstag, 28. November 2013
Theorem 4: perfect graph theorem
Korollar 5: G perfekt, dann alpha(G) = theta(G) = chi(Komplement G)
15. Dienstag, 3. Dezember 2013
Satz 6: Effiziente Bestimmung einer optimalen unabhängigen Menge in einem perfekten Graph
Def. 7: Duplikation eines Knoten
Satz 8: Durch Duplikation von Knoten wird Perfektheit behalten
Def. 9: Gewichtete Unabhängigkeitszahl
Satz 10: Effiziente Bestimmung einer optimalen Färbung in einem perfekten Graph
16. Donnerstag, 5. Dezember 2013
III.4 Shannon-Kapazität
Informationstheorie: Fehlerfreie Kommunikation
Def. 1: Starkes Graphenprodukt
Lemma 2: alpha(G x H) >= alpha(G) alpha(H)
Def. 3: Shannon-Kapazität eines Graphen
Def. 4: Kroneckerprodukt von Matrizen
Lemma 5: Rechenregeln für das Kroneckerprodukt
Satz 6: theta(G x H) = theta(G) theta(H)
Korollar 7: theta ist obere Schranke für Shannon-Kapazität
Satz 8: Shannon-Kapazität von C_5 = sqrt(5)
III.5 Berechnung von theta für symmetrische Graphen
Def. 1: a) Automorphismengruppe, b) homogene/knotentransitive Graphen
17. Dienstag, 10. Dezember 2013
Komplexität der Berechnung der Automorphismengruppe
Linksoperation von Permutationen auf Matrizen
Lemma 2: Optimale Lösungen von theta können Aut(G)-invariant gewählt werden
Satz 3: Eigenschaften invarianter optimaler Lösungen im Falle knotentransitiver Graphen
Satz 4: theta(G) theta(Komplement G) = |V|, falls G knotentransitiv
Korollar 5: theta(C_5) = sqrt(5)
III.6 Theta für Cayley-Graphen endlicher, abelscher Gruppen
Hauptsatz über endliche, abelsche Gruppen
Def. 1: Cayley-Graph
18. Donnerstag, 12. Dezember 2013
Def. 2. a) Torus b) Charakter
Bsp. Charakter von Z/nZ
Lemma 3: Orthogonalitätsrelation
Korollar 4: Es gibt es eine Orthgonalbasis von C^G bestehend aus Charakteren
Def. 5: duale Gruppe
Lemma 6: Eigenschaften G-invarianter Matrizen
Satz 7: Charakterisierung von G-invarianten Matrizen
Satz 8: Theta von Cayley-Graph ist ein lineares Programm
19. Dienstag, 17. Dezember 2013
Korollar 9: Theta von Kreisgraphen ungerader Länge
Kapitel IV Das Kusszahlproblem
IV.1 Das Kusszahlproblem in Dimension 8
20. Donnerstag, 19. Dezember 2013
Theorem: tau_8 = 240
21. Donnerstag, 9. Januar 2014
Kapitel V Determinantenmaximierung
V.1 Minkowskis Determinantenungleichung
Satz 1: F(X) = -(det X)^(1/n) ist konvex
Korollar 2: det(X + Y)^(1/n) >= det(X)^(1/n) + det(Y)^(1/n)
Lemma 3: gleichzeitiges Diagonalisieren
Lemma 4: AM-GM Ungleichung
V.2 Konvexe, spektrale Funktionen
Def. 1: a) Schur-Horn Orbitop SH(X), b) Permutaeder Pi(x_1, …, x_n)
Satz 2: Diag(SH(X)) = Pi(lambda_1, …, lamda_n)
22. Dienstag, 14. Januar 2014
Def. 3: spektrale Funktion
Satz 4: Davis 1957, Charakterisierung von konvexen, spektralen Funktionen
Korollar 5: F(X) = -(det X)^(1/n) ist konvex und spektral
Korollar 6: a) F(X) = Tr(X) b) F(X) = max EW von X sind konvex und spektral
23. Donnerstag, 16. Januar 2014
V.3 MAXDET Probleme
Satz 1: D^n ist ordentlicher, konvexer Kegel
Def. 2: primales MAXDET Problem
Satz 3: Bestimmung von (D^n)^*
Lemma 4: Tr(X) – n (det X)^(1/n) >= 0
Def. 5: duales MAXDET Problem
Satz 6: Optimalitätskriterium für MAXDET Probleme
24. Dienstag, 21. Januar 2014
V.4 Approximation von Polytopen durch Ellipsoide
Def. 1: Ellipsoid E(A,x)
Satz 2: innere Approximation
Satz 3: äußere Approximation
Def. 4: Loewner-John Ellipsoid
25. Donnerstag, 23. Januar 2014*
Satz 5: Johns Optimalitätskriterium
Korollar 6: Falls B_n optimal um P ist, liegt 1/n*B_n in P; entsprechend für inneres Ellipsoid.
26. Dienstag, 28. Januar 2014
Kapitel VI Polynomielle Optimierung
VI.1 Nichtnegative Polynome und SOS
Notation
Def. 1 a) SOS, b) SOS Kegel Sigma_{n,d}, c) Kegel der nichtnegativen Polynome P_{n,d}
Satz 2: Charakterisierung von Sigma_{n,d} mit SDP
Satz 3: Sigma_{1,2d} = P_{1,2d}
27. Donnerstag, 30. Januar 2014
Bsp. 4: Motzkinpolynom
Satz 5: Hilbert 1888
VI.2 Globale Optimierung mit Polynomen
Polynomielles Optimierungsproblem (POP)
Lasserre Hierarchie
Def. 1. a) quadratischer Modul, b) M(g_1,…,g_m), c) archimedisch
Theorem 2 Putinars Positivstellensatz
28. Dienstag, 4. Februar 2014
VI.3 Beweis von Putinars Positivstellensatz
29. Donnerstag, 6. Februar 2014
Diskussion der Übungsklausur