Algebraische Methoden der Diskreten Optimierung (SoSe 2016)

Inhalt

Zentrales Thema der Vorlesung wird das Problem sein, Polynomfunktionen über durch Polynomgleichungen und -ungleichungen definierten (also semi-algebraischen) Mengen zu minimieren. Schon der sehr eingeschränkte Spezialfall linearer Zielfunktionen und Ungleichungen sowie Polynomgleichungen x_i(x_i-1)=0 (d.h. x_i 0/1-Variable) ist sehr relevant und bekanntlich NP-schwer, da man diverse schwierige kombinatorische Optimierungsprobleme auf diese Art modellieren kann. Aber auch die allgemeinere Polynomoptimierung ist in den vergangene Jahren in das Zentrum des Interesses gerückt, da ihre enorme Modellierungsstärke einerseits aus Anwendungssicht sehr attraktiv ist, und die Entwicklung ihrer Theorie andererseits immer engere Verbindungen der diskreten Optimierung zu anderen Bereichen der Mathematik, insbesondere der reellen algebraischen Geometrie, geknüpft hat. In der Vorlesung werden wir Grundzüge dieser Theorie vorstellen.

Termine

Vorlesung / Übung (Prof. V. Kaibel); Eintrag im LSF

(Campus-Plan)

Übungsblätter

Literatur

Die Vorlesung wird sich in weiten Teilen an (einer überarbeiteten Version) der folgenden Arbeit orientieren:

Diese überarbeitete Version wird von der Autorin hier zum Download bereit gestellt.

Zur weiterführenden Lektüre empfehlen wir:

Einige Inhalte der Vorlesung findet man (neben zahlreichen anderen Themen) auch in dem sehr schönen Buch

Für algebraische Hintergrundinformationen eignet sich sehr gut: