Moment methods in extremal geometry

Moment methods in extremal geometry

De Laat, D.

Vallentin, F. (promotor)
Aardal, K.I. (promotor)

Electrical Engineering, Mathematics and Computer Science

Delft Institute of Applied Mathematics

2016-01-29

In this thesis we develop techniques for solving problems in extremal geometry. We give an infinite dimensional generalization of moment techniques from polynomial optimization. We use this to construct semidefinite programming hierarchies for approximating optimal packing densities and ground state energies of particle systems. For this we define topological packing graphs as an abstraction for the graphs arising from geometric packing problems, and we prove results concerning convergence and strong duality. We use harmonic analysis to perform symmetry reduction and reduce to a finite dimensional variable space in the optimization problems. For this we explicitly work out the harmonic analysis for kernels on spaces consisting of subsets of another space. We show how sums of squares characterizations from real algebraic geometry can be used to reduce the infinitely many constraints to finitely many semidefinite constraints, where we focus in particular on numerical conditioning and symmetry reduction. We perform explicit computations for concrete problems: We give new bounds for binary spherical cap packings, binary sphere packings, and classical sphere packing problems. This can be used, for instance, to give a simple optimality proof of a binary spherical cap packing. We compute the second step of our hierarchy where the numerical results suggest the bound is sharp for the 5-particle case of the Thomson and related problems. This is the first time a 4-point bound has been computed for a continuous problem.

packing problems
energy minimization
semidefinite programming
Lasserre hierarchy
Riesz energy
bounds

https://doi.org/10.4233/uuid:fce81f72-8261-484d-b9f4-d3d0c26f0473

978-94-6186-582-3

Institutional Repository

doctoral thesis

(c) 2016 De Laat, D.