Semidefinite Optimization - M1 - 8EC

1) Prerequisites

Good knowledge of linear algebra is required (in particular, basic notions about matrices, eigenvalues and eigenvectors, positive semidefinite matrices; e.g. Gilbert Strang's linear algebra lecture http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/video-lectures/). Some good knowledge about linear programming and convex optimization would be helpful (in particular, basic notions about convex sets, convex functions, polytopes and polyhedra, optimality conditions and duality theory in linear programming).

2) Aim of the course

The course aims at students with an interest in optimization, combinatorics, geometry, and algebra. The purpose of the course is to give an introduction to the theoretical background, to computational techniques, and to applications of semidefinite optimization. In particular, after successful participation in the course students will be able to: explain the theory and algorithmic approach to solve semidefinite optimization problems, give examples of problems in optimization, combinatorics, geometry and algebra to which semidefinite optimization is applicable, solve semidefinite optimization problems with the help of solvers, recognize problems which can be tackled using semidefinite optimization.


Semidefinite optimization is a recent tool in mathematical optimization and can be seen as a vast generalization of linear programming. One can define it as minimizing a linear function of a symmetric, positive semidefinite matrix subject to linear constraints. Only a few decades ago it became clear that one can solve semidefinite optimization problems efficiently in theory and practice. Since then, semidefinite optimization has become a frequently used tool of high mathematical elegance with big expressive and computational power.


Course contents:

  • Part 1 (Theory of semidefinite optimization): conic programming, duality theory, algorithms (only selected topics)

  • Part 2 (Applications in combinatorics): Lovász theta function, 0/1 programming, max-cut, Grothendieck’s constant

  • Part 3 (Applications in geometry): geometry of spectrahedra, hidden convexity results, kissing number, sphere packings

  • Part 4 (Applications in algebra): polynomial optimization, positive polynomials and sums of squares, Lasserre hierarchy, noncommutative setting and applications to quantum information.

3) Rules about Homework/Exam

The examination of the course will be based on homework assignments and on the final/retake exams.  Both the final and retake exams will be written exams. The total grade will be the average of homework assignments (30%) and the final exam (70%). The weights remain the same if the student does the retake exam (30% homework assignments and 70% retake exam). Students can only pass if they score at least a 5.0 in the final (or retake) exam. 

 

4) Lecture notes/Literature

Lecture notes will be provided during the course.  Some supplementary, optional material: