Good knowledge of linear algebra is required (e.g. Gilbert Strang's linear algebra lecture http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/video-lectures/). Some knowledge about linear programming and convex optimization would be helpful (in particular basic notions about convex sets, convex functions, optimality conditions and duality theory in linear programming).
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 the 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 Matlab-based 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 twenty years ago it became clear that one van 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): Lovasz theta function, 0/1 programming, maxcut, Grothendieck’s constant Part 3 (Applications in geometry): geometry of spectrahedra, distance geometry, Euclidean embeddings Part 4 (Applications in algebra): polynomial optimization, positive polynomials and sums of squares, real roots.
Rules about Homework / Exam
The final grade will be based for 30% on homework assignments and for 70% on the final written exam. In addition weakly exercises will be posted at the course website, which will be discussed in class.
Lecture Notes / Literature
Lecture notes will be provided during the course. Some supplementary, optional material:
S. Boyd, L. Vandenberghe, Convex Optimization http://www.stanford.edu/~boyd/cvxbook/
A. Nemirovski, Lectures on Modern Convex Optimization http://www.2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.pdf
L. Lovasz, Semidefinite programs and combinatorial optimization http://www.cs.elte.hu/~lovasz/semidef.ps
Monique Laurent (CWI) Fernando Oliveira (TU Delft)