Universität Wien

510008 VU VGSCO: Semidefinite Programming (2022W)

4.00 ECTS (2.00 SWS), SPL 51 - Doktoratsstudium Mathematik
Prüfungsimmanente Lehrveranstaltung
VOR-ORT
Moodle

An/Abmeldung

Hinweis: Ihr Anmeldezeitpunkt innerhalb der Frist hat keine Auswirkungen auf die Platzvergabe (kein "first come, first served").

Details

max. 25 Teilnehmer*innen
Sprache: Englisch

Lehrende

Termine (iCal) - nächster Termin ist mit N markiert

  • Montag 21.11. 09:45 - 11:15 Seminarraum 8 Oskar-Morgenstern-Platz 1 2.Stock
  • Montag 21.11. 13:15 - 14:45 Seminarraum 6 Oskar-Morgenstern-Platz 1 1.Stock
  • Dienstag 22.11. 09:45 - 11:15 Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Stock
  • Dienstag 22.11. 13:15 - 14:45 Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Stock
  • Mittwoch 23.11. 09:45 - 11:15 Seminarraum 15 Oskar-Morgenstern-Platz 1 3.Stock
  • Donnerstag 24.11. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
  • Donnerstag 24.11. 13:15 - 14:45 Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Stock
  • Freitag 25.11. 09:45 - 11:15 Seminarraum 15 Oskar-Morgenstern-Platz 1 3.Stock
  • Montag 28.11. 09:45 - 11:15 Seminarraum 8 Oskar-Morgenstern-Platz 1 2.Stock
  • Montag 28.11. 13:15 - 14:45 Seminarraum 6 Oskar-Morgenstern-Platz 1 1.Stock
  • Dienstag 29.11. 09:45 - 11:15 Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Stock
  • Dienstag 29.11. 13:15 - 14:45 Seminarraum 15 Oskar-Morgenstern-Platz 1 3.Stock
  • Mittwoch 30.11. 09:45 - 11:15 Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Stock
  • Donnerstag 01.12. 09:45 - 11:15 Seminarraum 15 Oskar-Morgenstern-Platz 1 3.Stock
  • Donnerstag 01.12. 13:15 - 14:45 Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Stock
  • Freitag 02.12. 09:45 - 11:15 Seminarraum 15 Oskar-Morgenstern-Platz 1 3.Stock

Information

Ziele, Inhalte und Methode der Lehrveranstaltung

Semidefinite programming (SDP) – optimization with positive semidefinite matrices, linear constraints and linear objective – is one of the most active and exciting areas of optimization in the last 30 years. Semidefinite programs (SDPs) have a surprising number of applications and they can be solved efficiently by modern optimization algorithms. Further, SDPs have a fascinating geometry, similar to the geometry of linear programming, but richer and more complex.

This course takes participants on a tour of SDP, in particular, we cover:

1) Applications:
a) relaxations of quadratic optimization problems;
b) applications in combinatorial optimization: maximum cut and maximum clique;
c) geometric problems: graph realization and kissing numbers;
d) applications in coding theory: computing the Shannon capacity of a graph;
e) polynomial optimization: sum-of-squares certificates; minimizing multivariate polynomials; Nullstellensatz and Positivstellensatz;
f) fastest mixing Markov chain on a graph.

2) Duality theory:
a) asymptotic duality and strong duality
b) certificates of (un)desirable properties of SDPs: of strict feasibility, boundedness of feasible and optimal sets, and infeasibility

3) Combinatorial aspects of duality: how to use elementary row operations – inherited from Gaussian elimination! -- to certify infeasibility; of the bad behavior of feasible SDPs; and of the closedness/nonclosedness of the linear image of the semidefinite cone

4) Geometry of spectrahedral: faces, extreme points, tangent cones, tangent spaces.

5) Time permitting: how do exponential size solutions arise in SDP? Can we solve SDPs in polynomial time?

Art der Leistungskontrolle und erlaubte Hilfsmittel

Course assessment: based on homeworks and class participation.

Mindestanforderungen und Beurteilungsmaßstab

Prerequisites: having seen some optimization, such as linear programming is useful. But linear algebra, and some basic real analysis – open and closed sets, convergence of sequences – are sufficient prerequsites.

Prüfungsstoff

Literatur

Zuordnung im Vorlesungsverzeichnis

MAMV

Letzte Änderung: Do 17.11.2022 10:50