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:
- ARV-type sparsest cut algorithms.
- Primal-dual methods for fast solutions to SDPs.
- Algorithms for unique games.
- Connections between the Unique Games Conjecture and integrality gaps
for SDPs.
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:
- Lecture 1: Introduction to semidefinite programming I.
Slides.
(SDP duality, application to stable sets and max-cut, Goemans-Williamson approximation algorithm, extension to binary quadratic programming, Grothendieck constant, link to psd matrix completion, max k-cut).
- Lecture 2: Introduction to semidefinite programming II.
Slides.
(Lovasz theta number, polynomial algorithms in perfect graphs, link to Delsarte bound for codes, block-diagonalization, stronger bounds).
- Lecture 3: SDP hierarchies for combinatorial optimization.
(Lift and project techniques, Lovasz-Schrijver
matrix cut method, Sherali-Adams LP relaxations,
the moment relaxations of Lasserre, application to stable sets).
Slides.
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.
-
Sums of squares (SOS) decomposition of multivariate polynomials.
-
SOS-based semidefinite relaxations for semialgebraic problems.
- Techniques for exploiting algebraic (e.g., sparsity, symmetry) and
numerical structure.
- SDP representability of convex sets.
Franz Rendl (University Klagenfurt)
Algorithms for solving semidefinite programs
We will cover several approaches for solving semidefinite programs.
-
The most elegant way to solve SDP is based on
Newton's method applied to a slightly modified
version of the problem. This leads to the class
interior-point primal-dual path-following methods.
We will briefly recall their convergence
behaviour, their practical performance, and
their limitations.
-
More recently, projection and regularization
methods in combination with the classical
augmented Lagrangian technique have successfully
been applied to large-scale SDP. We explain
the basic ideas underlying these approaches.
-
Finally, combinatorial optimization problems often
have semidefinite relaxations, which can be refined
by polyhedral combinatorics, leading to an SDP with
a large number of (linear) inequality constraints.
We show how these can be handled using a combination
of interior-point methods and standard techniques
from nonsmooth optimization.
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.
- Lecture 1: The kissing number in three dimensions.
(Kissing number, some history, elementary SDP proof
essentially using spherical coordinates only, some words about higher dimensions).
Relevant references:
C. Bachoc, F. Vallentin, New upper bounds for kissing numbers from semidefinite
programming, J. Amer. Math. Soc. 21 (2008), 909-924.
Link.
C. Bachoc, F. Vallentin, Semidefinite programming, multivariate orthogonal
polynomials, and codes in spherical caps,
European J. Combin. 30 (2009), 625-637.
Link.
F. Pfender, G.M. Ziegler, Kissing Numbers, Sphere Packings and Some Unexpected
Proofs, Notices Amer. Math. Soc. 51 (2004), 873-883.
H. Cohn, Order and disorder in energy minimization
Link.
-
Lecture 2: Tools from harmonic analysis.
(Bochner's theorem for compact groups, for locally compact
groups, Schoenberg's theorem for the unit sphere, stationary phase estimates).
Relevant references:
F. Vallentin, Lecture notes: Semidefinite programing and harmonic analysis.
Link.
F. Vallentin, Symmetry in semidefinite programs, Linear Algebra and Appl. 430
(2009), 360-369.
Link.
C. Bachoc, Semidefinite programming, harmonic analysis and coding theory.
Link.
T. Wolff, Lectures on Harmonic Analysis.
Link.
-
Lecture 3: Geometric packing and coloring problems.
(Measurable chromatic number of Euclidean space,
Delsarte-style linear programming bound for densities of distance avoiding sets,
Euclidean Ramsey theory and Furstenberg-Katznelson-Weiss theorem).
Slides.
Relevant references:
C. Bachoc, G. Nebe, F.M. de Oliveira Filho, F. Vallentin,
Lower bounds for
measurable chromatic numbers, Geom. Funct. Anal. 19 (2009), 645-661.
Link.
F.M. de Oliveira Filho, F. Vallentin, Fourier analysis, linear programming, and
densities of distance avoiding sets in R^n, to appear in J. Eur. Math. Soc. (JEMS),
Link.