Oberwolfach Seminar

Semidefinite Optimization: Theory, Algorithms and Applications

May 23-29, 2010

Semidefinite programming (SDP) has turned out to be a very powerful tool in optimization in the past decades. It can be seen as a natural extension of linear programming where vector variables are replaced by matrices constrained to be positive semidefinite. As such matrices are basic ubiquitous objects, SDP applies to a great variety of research areas, including graph theory, geometry, combinatorial optimization, real algebraic geometry, quantum computing, approximation algorithms, and complexity theory.

The aim of this seminar is to introduce the participants to the basic theory of semidefinite programming, to algorithmic and complexity aspects, and to a number of applications to several other fields of pure and applied mathematics.

The lectures will be based on available documents: surveys and recent papers, with a special effort on being accessible to non specialists.

Deadline for applications: April 1st, 2010.

The seminar is open for PhD students and postdocs.
See the MFO webpage for details on how to apply - click on 'SCIENTIFIC PROGRAMME - Oberwolfach Seminars' on the left side.

Please note the following other related event which you might want to combine with your trip to Oberwolfach:
EIDMA minicourse on Algebraic Optimization and Semidefinite Programming by Pablo Parrilo, at CWI, Amsterdam, on May 31 - June 4, 2010.

Sanjeev Arora (Princeton University)

SDP based approximation algorithms for hard combinatorial problems

We will discuss several topics dealing with the use of semidefinite programming in theoretical computer science, in particular, for designing approximation algorithms for hard combinatorial optimization problems and the link to the Unique Games Conjecture. The following topics will be covered: Slides and references:
- Multiplicative weights method: A meta algorithm with applications to linear and semi-definite programming. Slides.
- S. Arora, S. Rao, U. Vazirani, Expander Flows, Geometric Embeddings, and Graph Partitioning, Link.
- S. Arora, S. Rao, U. Vazirani, Geometry, Flows, and Graph-partititiong algorithms, Link.
- S. Arora and S. Kale, Combinatorial, Primal-Dual Approach to SDPs. Link.
- M. Charikar, Y. Makarychev, Y. Makarychev, Near-Optimal Algorithms for Unique Games, Link.
- Dimacs lecture notes, Chapter 9, Link.

Monique Laurent (CWI, Amsterdam and Tilburg University)

Basic theory of SDP and applications to combinatorial optimization

We will introduce the basic properties of semidefinite programs and explain how they can be used to build hierarchies of convex relaxations for linear programming problems in the presence of additional 0/1 integrality constraints and thus for combinatorial optimization problems. We will treat in particular the following topics:
Some relevant survey papers:
- M. Groetschel, L. Lovasz, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer, 1988.
- D. Knuth, The sandwich theorem, Electronic J. of Combinatorics, 1:1--48, 1994. File here.
- L. Lovasz, On the Shannon capacity of a graph, IEEE Trans. Information Theory, IT-25:1-7, 1979.
- L. Lovasz, Semidefinite Programs and Combinatorial Optimization. File here.
Chapter of Recent Advances in Algorithms and Combinatorics (B.R. Reed and C.L.Sales, eds.), pages 137--194, Springer, 2003.
- M. Laurent and F. Rendl, Semidefinite Programming and Integer Programming. File here.
Chapter of the Handbook on Discrete Optimization (K. Aardal, G. Nemhauser, R. Weismantel, eds.), pages 393-514, Elsevier, 2005.

Pablo Parrilo (MIT, Cambridge)

Sums of squares of polynomials, algebraic/geometric aspects of convexity, and SDP representability

We will discuss techniques based on sums of squares of polynomials, emphasizing the algebraic and geometric aspects of convexity, and applications in different domains.

Franz Rendl (University Klagenfurt)

Algorithms for solving semidefinite programs

We will cover several approaches for solving semidefinite programs. Slides and references:
- Semidefinite optimization - Algorithms - Basics. Slides.
- Interior points, bundle methods and partail Lagragian. Slides.
- Projection methods to solve SDP. Slides.
- Survey paper: Semidefinite relaxations for integer programming. In the volume '50 Years of Integer Programming 1958-2008' (M. Junger et al. eds.), Springer, 2010. File.

Frank Vallentin (Technical University Delft and CWI, Amsterdam)

Semidefinite programming, harmonic analysis, and applications in geometry

In these lectures we explain how to extend semidefinite programming from finite-dimensional matrices to infinite-dimensional operators. For this we first provide the necessary background in harmonic analysis. We study several applications coming from geometry.