Datum: Di 26.02. und Mi 27.02.2019
Ort: Mathematisches Institut, Seminarraum 2
Im Seminar “Polynomielle Optimierung“ wird eine weitreichende Erweiterung der linearen Optimierung besprochen: Lineare Zielfunktion und lineare Ungleichungsnebenbedingungen werden durch polynomielle Zielfunktion und polynomielle Ungleichungsnebenbedingungen ersetzt. Dazu werden zunächst Grundlagen der konvexen algebraischen Geometrie (positive Polynome und das Momentenproblem) erarbeitet. Darauf aufbauend werden Anwendungen, wie zum Beispiel das algorithmische Lösen von polynomiellen Optimierungsproblemen oder das algorithmische Auffinden reeller Lösungen von polynomiellen Gleichungssystemen betrachtet.
Für das Seminar werden Vorkenntnisse im Gebiet der konvexen Optimierung benötigt, die z.B. im Rahmen der Vorlesung ”Konvexe Optimierung“ parallel zum Seminar erworben werden können.
Literatur
- M. Laurent, F. Vallentin – Semidefinite Optimization, Kapitel 13-15
- Grigoriy Blekherman – Semidefinite Optimization and Convex Algebraic Geometry, Chapter 4
- Ryan O’Donnell – SOS is not obviously automatizable, even approximately
(Erste) Vorbesprechung war Mi, 14.11.2018, 14:00 Uhr im Seminarraum 1 MI
Themen:
- Positivstellensätze [LV, Kap.13]
- Das Momentenproblem [LV, Kap.14]
- Quadratsummen und nichtnegative Polynome: kleine Unterschiede [B]
- Polynomialzeit und SDP Hierarchien [LV, Kap. 15 1.-3.], [D]
Anmeldung:
Wenn Sie an dem Seminar teilnehmen möchten, kommen Sie zur Vorbesprechung (siehe oben) und schreiben Sie bis zum 16.11. (23:59 Uhr) eine Mail an Frederik von Heymann, mit folgendem Inhalt:
- Ihr Name und Studiengang (Bachelor/Master)
- Falls Sie sich bereits als Zweiergruppe anmelden wollen, den Namen des anderen Gruppenmitglieds
- Eine vollständige Präferenzenliste der unten genannten 7 Themen. D.h.: Sie schreiben die Themen in nummerierter Reihenfolge in Ihre Mail, wobei das von Ihnen bevorzugte Thema die Nummer 1 erhält. Das Thema, das Sie als zweites wählen würden erhält die Nummer 2, u.s.w. Achten Sie darauf, dass Ihre Präferenzenliste alle 7 Themen enthält und in Ihrer Nummerierung die Zahlen von 1 bis 7 jeweils genau einmal vorkommen.
Spielregeln
- Die Vorträge werden in Zweiergruppen vorbereitet und gehalten
- 45 Minuten Präsentation pro Teilnehmer, also 90 Minuten pro Gruppe plus 30 Minuten für Diskussion
- Seminarausarbeitung: ca. 10-20 Seiten (LaTeX) pro Gruppe, erste Version spätestens eine Woche vor dem Vortrag, endgültige Version eine Woche nach dem Vortrag
- Besprechen der Präsentation in zwei Besprechungen: 1. Konzept muss in der vorletzten Vorlesungswoche vorgestellt werden 2. Vollständige Version muss zwei Wochen vor dem Vortrag vorgestellt werden.
- Zur Bewertung des Seminars werden folgende Kriterien herangezogen: Verständnis (40%), Eigenleistung (z.B. eigene Erklärungen, eigene Beispiele) (25%), Sorgfalt (25%), Präsentationstechnik (10%)
Für die Anfertigung der Präsentation können Sie natürlich die Software Ihrer Wahl nehmen. Häufig verwendet wird die „beamer“-Klasse für LaTeX (hier eine Beispiel-Datei von Eddie Kim), aber zu empfehlen sind auch Ipe (alle Plattformen) und Keynote (nur Mac; in Verbindung mit LaTeXiT).
Kontakt: Dr. A. Gundert, Dr. F. von Heymann und Prof. Dr. F. Vallentin