Packing, coding, and ground states
David de Laat
Semidefinite programming hierarchies for packing and energy minimization
In the lectures we will consider semidefinite programming hierarchies with applications in discrete geometry. We will first consider Parrilo’s sum-of-squares approach and Lasserre’s dual moment approach in polynomial optimization. Then we discuss how these techniques can be adapted to bound packing densities, and we prove convergence to the optimal density. Finally we adapt this to energy minimization and discuss how concrete computations can be performed.
Optimization for lattices, packings, and coverings
In my lectures I will consider optimization problems whose set of feasible solutions is the cone of positive semidefinite matrices. In the first lecture, I will start with a general introduction to conic optimization, a very useful version of convex optimization with a powerful duality theory, having many good theoretical and practical algorithms. In the second and third lecture, the cone of positive semidefinite matrices will be interpreted as the parameter space of lattices. Many lattice parameters have a natural formulation as optimization problems over this cone. Here we will treat maximizing the packing density, minimizing the covering density, and minimizing potential energy. We emphasize local aspects and the relation to spherical designs.
Exact semidefinite programming bounds for packing problems
(Joint work with Maria Dostert and David de Laat.)
In the first part of the talk, we present how semidefinite programming methods can provide upper bounds for various geometric packing problems, such as kissing numbers, spherical codes, or packings of spheres into a larger sphere. When these bounds are sharp, they give additional information on optimal configurations, that may lead to prove the uniqueness of such packings. For example, we show that the lattice E8 is the unique solution for the kissing number problem on the hemisphere in dimension 8.
However, semidefinite programming solvers provide approximate solutions, and some additional work is required to turn them into an exact solution, giving a certificate that the bound is sharp. In the second part of the talk, we explain how, via our rounding procedure, we can obtain an exact rational solution of semidefinite program from an approximate solution in floating point given by the solver.
Fernando M. de Oliveira Filho
Completely positive and copositive type functions for packing and distance-avoiding sets
The cones of completely positive and copositive matrices allow us to provide exact conic programming formulations for the independent set problem. In this talk I will discuss recent work on how to extend these results to obtain exact formulations for densities of distance-avoiding sets and densities of packings of convex bodies in Euclidean space. Many improvements of the linear programming bound of Delsarte, Goethals, and Seidel for the kissing number, or of the linear programming bound of Cohn and Elkies for the sphere packing density, can be seen as coming from these exact formulations. (Joint work with Evan DeCorte, David de Laat, and Frank Vallentin.)