Semidefinite Programming

Michel Goemans (MIT)

Semidefinite programming refers to the optimization of a linear function over an affine subspace of the cone of positive semidefinite matrices. It generalizes linear programming, is a special case of convex optimization, and is closely related to eigenvalue problems. It has a powerful duality theory. Recently, semidefinite programming has been the focus of much attention, partly because of its applications to control theory and combinatorial optimization.

After presenting the scenery surrounding semidefinite programming, we will explore several areas where semidefinite programming has been particularly useful. We will start by visiting Lyapunov theory, John's minimum volume ellipsoids, and other areas, and then head towards more combinatorial applications, including the approximability of maximum cuts and Lovasz's seminal work on perfect graphs. During our journey, we will encounter several interesting combinatorial or geometric open questions.

Partially based on joint work with David Williamson, Uri Feige, and Jon Kleinberg.