Vorlesung
Semidefinite Programmierung
Mo, Di 14:00-15:30
im Raum 311-312, Pohlighaus

In der Vorlesung werden Grundlagen und Anwendungen der Semidefiniten Programmierung behandelt. Semidefinite Programme (SDP) können als Verallgemeinerung linearer Programme angesehen werden. Dabei wird zusätzlich zu den linearen Nebenbedingungen die positive Semidefinitheit einer Variablenmatrix gefordert.

Für zahlreiche Anwendungen liefern semidefinite Modelle gute Relaxierungen. Für das Problem maximaler Schnitte etwa besagt ein berühmtes Resultat von Goemans und Williamson, dass die Standard-SDP-Relaxierung bei nichtnegativen Gewichten ein Optimum hat, das höchstens 13% unter dem ganzzahligen Optimum liegt.

Weitere Anwendungen aus der kombinatorischen Optimierung sind das Stabile-Mengen-Problem sowie das Erfüllbarkeitsproblem. Neuere Ergebnisse zeigen außerdem, wie SDP-basierte Methoden bei polynomiellen Optimierungsproblemen eingesetzt werden können, die in der Vorlesung ausführlich diskutiert werden sollen.

Für die Vorlesung werden Grundkenntnisse der linearen Programmierung vorausgesetzt, die jedoch bei Bedarf in der Übung aufgefrischt werden können.

In den Übungen werden die Inhalte der Vorlesung unter Anleitung besprochen und vertieft. Außerdem dienen die Übungen der Vorbereitung einer mündlichen Prüfung am Ende des Semesters, hier können neun Leistungspunkte erworben werden.