510008 VU VGSCO: Semidefinite Programming (2022W)

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?