A solver for clustered low-rank SDPs arising from multivariate polynomial (matrix) programs

Abstract

In this thesis, we give a primal-dual interior point method
specialized to clustered low-rank semidefinite programs. We introduce
multivariate polynomial matrix programs, and we reduce these to clustered
low-rank semidefinite 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.  Clustered low-rank
semidefinite programs are programs with low-rank constraint matrices where the
positive semidefinite variables are only used within clusters of constraints. The
free variables can be used in any constraint, and can be used to connect
clusters. The solver uses this structure to speed up the computations in two
ways. First, the low rank structure is used to reduce matrix products to
products of the form uT M v, where M is a matrix and u and v are vectors, as
already suggested by Löfberg and Parrilo in [43rd IEEE CDC (2004)]. Second, an
additional block-diagonal structure is introduced due to the clusters. This
gives the possibility to do operations such as the Cholesky decomposition
block-wise.   We apply this to sphere
packing and spherical cap packing. For sphere packing, the speed of the solver
is compared to the often used arbitrary precision solver SDPA-GMP, showing the
theoretical speedup in time complexity. We give a new three-point bound for the
maximum density when packing spherical caps of $N$ sizes on the unit sphere.