A specialized SDP solver for sums-of-squares problems in discrete geometry

Nando Leijenhorst (TU Delft)

Jan 18. 2022, 14:00 — 14:40

In this talk, we give a primal-dual interior point method specialized to clustered low-rank semidefinite programs, which arise from multivariate polynomial (matrix) programs. This extends the work of Simmons-Duffin [J. High Energ. Phys. 1506, no. 174 (2015)] from univariate to multivariate polynomial matrix programs, and to more general clustered low-rank semidefinite programs.

We study the interplay of sampling (Löfberg and Parrilo [43rd IEEE CDC (2004)]) and symmetry reduction as well as a method to obtain numerically good bases and sample points. We apply this to the computation of three-point bounds for the kissing number problem, for which we show a significant speedup (easily by a factor 20 for previously computed bounds). We also use the extra stability due to the chosen bases and samples to perform computations for the binary sphere packing problem.

Further Information
ESI Boltzmann Lecture Hall
Associated Event:
Optimal Point Configurations on Manifolds (Workshop)
Christine Bachoc (U Bordeaux)
Henry Cohn (Microsoft, Redmond)
Peter Grabner (TU Graz)
Douglas Hardin (Vanderbilt U, Nashville)
Edward Saff (Vanderbilt U, Nashville)
Achill Schürmann (U of Rostock)
Robert Womersley (UNSW, Sydney)