New applications of semidefinite programming


New applications of semidefinite programming: Discrete geometry and harmonic analysis 

Probably the two most important applications of semidefinite programming in combinatorial optimization are the Lovasz theta function and the Goemans-Williamson algorithm. Both deal with computational difficult problems. The Lovasz theta function gives an upper bound for the independence number of a finite graph. The Goemans-Williamson algorithm provides 0.878...-approximations for the largest cut in a graph.

I will explain how to extend semidefinite programming from finite-dimensional matrices to operators in order to generalize the Lovasz theta function from finite to infinite graphs. We will make use of abstract harmonic analysis for this. One motivation is the explicit computation of bounds for difficult packing and coloring problems in discrete geometry: 

1. Finding the measurable chromatic number of Euclidean space: What is the minimum number of colors needed to color all the points in space so that no two points at distance 1 get the same color and so that the color classes are measurable?

2. Finding the kissing number: What is the maximum number of unit balls that can simultaneously touch a central ball without overlapping? 

3. Finding the maximum density of a packing of rotated and translated copies of a given convex body in Euclidean space.

Then I will explain extensions of the Goemans-Williamson approximation algorithm which are based on Grothendieck inequalities which originated from functional analysis. In particular I will consider the following two problems: 

4. Approximating the cut norm of a matrix, a key tool to the new theory of graph limits introduced by Lovasz and Szegedy 

5. Approximating minimal energy states of the Ising model, XY-model, Heisenberg-model in statistical mechanics.


Relevant literature:


1. C. Bachoc, D.C. Gijswijt, A. Schrijver, F. Vallentin: Invariant semidefinite programs,

http://arxiv.org/abs/1007.2905 

2. F. Vallentin: Lecture notes: Semidefinite programming and harmonic analysis, 

http://arxiv.org/abs/0809.2017 

3. F.M. de Oliveira Filho: New Bounds for Geometric Packing and Coloring via Harmonic Analysis and Optimization,

http://homepages.cwi.nl/~fmario/thesis.pdf

4. J. Briet, F.M. de Oliveira Filho, F. Vallentin: Grothendieck inequalities for semidefinite programs with rank constraint,

http://arxiv.org/abs/1011.1754