Solving clustered low-rank semidefinite programs arising from polynomial optimization

Abstract

We study a primal-dual interior point method specialized to clustered low-rank semidefinite programs requiring high precision numerics, which arise from certain multivariate polynomial (matrix) programs through sums-of-squares characterizations and sampling. We consider the interplay of sampling and symmetry reduction as well as a greedy 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. This allows for the computation of improved kissing number bounds in dimensions $11$ through $23$. The approach performs well for problems with bad numerical conditioning, which we show through new computations for the binary sphere packing problem.

28 pages, revision based on suggestions by referee

References in corpus (13)

• Symmetry groups, semidefinite programs, and sums of squares
• New upper bounds on sphere packings I
• The sphere packing problem in dimension 24
• The sphere packing problem in dimension 8
• New upper bounds for kissing numbers from semidefinite programming
• Nemo/Hecke: Computer Algebra and Number Theory Packages for the Julia Programming Language
• High accuracy semidefinite programming bounds for kissing numbers
• Upper bounds for packings of spheres of several radii
• Pure states, positive matrix polynomials and sums of hermitian squares
• Three-point bounds for energy minimization
• New upper bounds for the density of translative packings of three-dimensional convex bodies with tetrahedral symmetry
• On "A Homogeneous Interior-Point Algorithm for Non-Symmetric Convex Conic Optimization"
• Moment methods in energy minimization: New bounds for Riesz minimal energy problems

Cited by in corpus (2)

• On two maximally entangled couples
• Getting to the Root of the Problem: Sums of Squares for Limits of Trees