Universität Wien

510008 VU VGSCO: Semidefinite Programming (2022W)

4.00 ECTS (2.00 SWS), SPL 51 - Doktoratsstudium Mathematik
Continuous assessment of course work
ON-SITE
Moodle

Registration/Deregistration

Note: The time of your registration within the registration period has no effect on the allocation of places (no first come, first served).

Details

max. 25 participants
Language: English

Lecturers

Classes (iCal) - next class is marked with N

  • Monday 21.11. 09:45 - 11:15 Seminarraum 8 Oskar-Morgenstern-Platz 1 2.Stock
  • Monday 21.11. 13:15 - 14:45 Seminarraum 6 Oskar-Morgenstern-Platz 1 1.Stock
  • Tuesday 22.11. 09:45 - 11:15 Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Stock
  • Tuesday 22.11. 13:15 - 14:45 Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Stock
  • Wednesday 23.11. 09:45 - 11:15 Seminarraum 15 Oskar-Morgenstern-Platz 1 3.Stock
  • Thursday 24.11. 09:45 - 11:15 Seminarraum 9 Oskar-Morgenstern-Platz 1 2.Stock
  • Thursday 24.11. 13:15 - 14:45 Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Stock
  • Friday 25.11. 09:45 - 11:15 Seminarraum 15 Oskar-Morgenstern-Platz 1 3.Stock
  • Monday 28.11. 09:45 - 11:15 Seminarraum 8 Oskar-Morgenstern-Platz 1 2.Stock
  • Monday 28.11. 13:15 - 14:45 Seminarraum 6 Oskar-Morgenstern-Platz 1 1.Stock
  • Tuesday 29.11. 09:45 - 11:15 Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Stock
  • Tuesday 29.11. 13:15 - 14:45 Seminarraum 15 Oskar-Morgenstern-Platz 1 3.Stock
  • Wednesday 30.11. 09:45 - 11:15 Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Stock
  • Thursday 01.12. 09:45 - 11:15 Seminarraum 15 Oskar-Morgenstern-Platz 1 3.Stock
  • Thursday 01.12. 13:15 - 14:45 Seminarraum 5 Oskar-Morgenstern-Platz 1 1.Stock
  • Friday 02.12. 09:45 - 11:15 Seminarraum 15 Oskar-Morgenstern-Platz 1 3.Stock

Information

Aims, contents and method of the course

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?

Assessment and permitted materials

Course assessment: based on homeworks and class participation.

Minimum requirements and assessment criteria

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.

Examination topics

Reading list

Association in the course directory

MAMV

Last modified: Th 17.11.2022 10:50