Springe zum Hauptinhalt
Professur Algorithmische und Diskrete Mathematik
Algorithmische und Diskrete Mathematik

Semidefinite Optimierung
(B02; FM1, FD1-3, FO1-3)

Sommersemester 2020

Vorlesung: Christoph Helmberg

Montag, 9:15 - 10:45, Raum C22.202 - 2/B202
ACHTUNG: Start am 6.4. als OPAL-Kurs

LOGO

Kurzbeschreibung

Inhalt:

Lineare Optimierung über dem Kegel der symmetrischen positiv semidefiniten Matrizen, Dualitätstheorie, semidefinit darstellbare Mengen, Lösungsverfahren, Anwendungen: diskrete Optimierung, Sum-of-squares und Momenten-Matrizen, Optimierung über Polynomen, robuste Optimierung, ...

The course will be given in English if any student prefers so:

Linear optimization over cones (in particular second order cone SOC and positive semdefinite cone PSC), duality theory, SOC- and PSC-representable sets, solution methods and applications: discrete optimization, sum-of-squares (SOS) and moment matrices, polynomial optimization, robust optimization

Corona-Mode: please visit the OPAL-course

Zielgruppe:

wob: D_MaIn6, D_Ma__6, D_WM__6, M_MaDI2, M_MaOW2, D_InEM8
fak: D_InEM6, D_MaIn8, D_Ma__8, D_WM__8, M_MaDI4, M_MaOW4

Vorwissen:

Grundlagen der Optimierung, Grundbegriffe der Graphentheorie

Prüfung:

mündliche Prüfung (Teil einer Modul-/Fachprüfung oder Schein mit Note)


Literatur

Semidefinite Programming gibt einen Überblick über die Literatur. Die wichtigsten Quellen der Vorlesung sind:
  • A. Ben-Tal, A. Nemirovski.
    Lectures on Modern Convex Optimization,
    MPS-SIAM Series on Optimization, SIAM, Philadelphia, 2001.
    ISBN 0-89871-491-5
  • S. Boyd, L. Vandenberghe.
    Convex Optimization,
    Cambridge University Press, Cambridge, 2004, reprinted 2007 (with corrections).
    ISBN 0 521 83378 7
  • H. Wolkowicz, R. Saigal, L. Vandenberghe.
    Handbook of Semidefinite Programming,
    Kluwer Academic Publishers, Boston, 2000.
    ISBN 0-7923-7771-0
  • M. Laurent.
    "Sums of squares, moment matrices and optimization over polynomials",
    Emerging Applications of Algebraic Geometry, Vol. 149 of IMA Volumes in Mathematics and its Applications, M. Putinar and S. Sullivant (eds.), Springer, pages 157-270, 2009.
    Available on the homepage of Monique Laurent and in its updated version.
  • C. Helmberg.
    "Semidefinite Programming for Combinatorial Optimization",
    Habilitationsschrift, TU Berlin, January 2000.
    ZIB-Report ZR-00-34, Konrad-Zuse-Zentrum Berlin, October 2000.
    pdf-file (ftp), abstract

Zusatzmaterial