Lehre‎ > ‎

Vorlesung Konvexe Optimierung

Diese Spezialvorlesung von Prof. Sven Rahmann findet im WS 2009/10 statt.
Sie gehört in die SpGs 4,6,7 nach DPO'01 und ist wahlweise als 2V+2Ü = 6 LP (Master) oder 3V+1Ü (Diplom) anrechenbar.
Termin und Raum: Mo 10-12 in OH14/R104 und Fr 12-14 in OH14/R304.

Inhalt (Vorlesungskommentar)

Konvexe Optimierungsprobleme ergeben sich aus vielen Anwendungen; sie sind wesentlich allgemeiner als lineare Optimierungsprobleme, aber ähnlich einfach zu lösen. Charakteristisch für konvexe Probleme ist, dass jedes lokale Optimum auch ein globales Optimum ist. Wir beginnen mit einer Untersuchung konvexer Mengen und konvexer Funtionen, beschreiben verschiedene Klassen konvexer Optimierungsprobleme. Es ist häufig eine Kunst, ein Anwendungsproblem geschickt als konvexes Optimierungsproblem zu formulieren. Hier werden wir Beispiele aus der Bioinformatik kennenlernen. Dualitätssätze werden ausführlich besprochen. Es folgt eine eingehende Diskussion zu innere-Punkte-Verfahren zur Lösung konvexer Optimierungsprobleme.

Literatur und Material

Der Inhalt der Vorlesung entspricht großen Teilen des Buchs Convex Optimization von Stephen Boyd und Lieven Vandenberghe (Cambridge University Press, 2004). Es ist online hier frei verfügbar erhältlich (ein eigenes Exemplar ist allerdings gut investiertes Geld). Die Reihenfolge und Auswahl des Materials wird teilweise von dieser Vorlage abweichen.
Von Stephen Boyd gibt es Vorlesungsvideos zu seinem Buch hier: http://www.academicearth.org/courses/convex-optimization-i.
ACHTUNG: Mein Fokus und meine Präsentation weichen davon ab. Mit anderen Worten: Die Video-Aufzeichnungen aus Stanford ersetzen nicht meine Vorlesung.

Skript

Das Skript wird parallel zur Vorlesung erstellt. Hier liegt der aktuelle Entwurf.

Termine und Themen

Es ist dringend empfehlenswert, sich an den Übungen aktiv zu beteiligen!

 Mo 12.10.Einführende Beispiele. Konvexe Optimierungsprobleme. Wiederholung Lineare Algebra, bra-ket-Notation
 Fr 16.10.
Konvexe Mengen und ihre Eigenschaften, Unterräume, affine Räume, (konvexe) Kegel.
Ausgabe und Besprechung von Übungsaufgaben.
 Mo 19.10.  
Konvexitätserhaltende Operationen.
Spezielle konvexe Mengen (insbesondere Polyeder und Polytope).
 Fr 23.10.
Konvexe Funktionen: Konvexität, strikte Konvexität, starke Konvexität. Beispiele.
Jensen'sche Ungleichung.
Ausgabe und Besprechung von Übungsaufgaben.
 Mo 26.10.
-- fällt aus --
 Fr 30.10.
Richtungsableitung. Gateaux-Variation.
 Mo 02.11.  
Differenzierbare konvexe Funktionen.
Konvexitätskriterien erster Ordnung. Monotonie des Gradienten.
 Fr 06.11.
Konvexitätskriterien zweiter Ordnung.
Mehrdimensionale Beispiele konvexer Funktionen.
Ausgabe und Besprechung von Übungsaufgaben.
 Mo 09.11.
Konvexitätserhaltende Operationen für Funktionen
 Fr 13.11.
Optimierungsprobleme (allgemein, konvex, quadratisch, linear).
Ausgabe und Besprechung von Übungsaufgaben.
 Mo 16.11.
Beispiele für konvexe Optimierungsprobleme.
 Fr 20.11.
-- fällt wegen Krankheit aus --
 Mo 23.11.
Optimalitätsbedingungen für konvexe Optimierungsprobleme.
Unrestringierte konvexe Optimierungsprobleme.
Übersicht über Minimierungsalgorithmen.
 Fr 27.11.
-- Gedenkkolloquium für Ingo Wegener in E23 --
 Mo 30.11.
Abstiegsrichtungen. Gradientenverfahren.
Ausgabe und Besprechung von Übungsaufgaben.
 Fr 04.12.
Newton- und BFGS-Verfahren.
 Mo 07.12.
Analyse des Gradienten-Verfahrens, lineare Konvergenz.
 Fr 11.12.    
Klassische Analyse des Newton-Verfahrens, lokal quadratische Konvergenz.
Ausgabe und Besprechung von Übungsaufgaben.
 Mo 14.12.
Konvexe selbst-konkordante Funktionen.
 Fr 18.12.    
Analyse des Newton-Verfahrens für selbst-konkordante Funktionen.
 Mo 04.01.
Dualität: Lagrange-Funktion, duale Funktion, duales Problem.
 Fr 08.01.
Beispiele für primale und duale Probleme.
 Mo 11.01.
Weitere Beispiele. Konjugierte Funktion, duale Norm.
 Fr 15.01.
Starke Dualität: Geometrische Charakterisierung.
 Mo 18.01.
Starke Dualität: Slater's Bedingungen, Satz von Slater.
 Fr 22.01.
Sensitivitätsanalyse von Optimierungsproblemem.
 Mo 25.01.
Ausführliches Beispiel: Support-Vector-Machines
 Fr 29.01.
Anwendungen: Kommunikationskanal-Kapazität, Basis-Pursuit.
 Mo 01.02.
Optimierungsverfahren für konvexe Probleme mit Gleichungsbedingungen
 Fr 05.02.
Innere-Punkte-Verfahren. Implementierung.