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

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

Leijenhorst, Nando (TU Delft Electrical Engineering, Mathematics and Computer Science)

de Laat, D. (mentor)
Gijswijt, D.C. (graduation committee)
van der Woude, J.W. (graduation committee)

Delft University of Technology

Applied Mathematics | Optimization

2021-06-02

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.    

Semidefinite programming
Polynomials
SDP
Sphere packing
Spherical cap packing

http://resolver.tudelft.nl/uuid:53e114a8-61cd-4f48-8151-76abb0159408

https://github.com/nanleij/Clustered-Low-Rank-SDP-solver Repository link Github repository with the Julia code of the solver

Student theses

master thesis

© 2021 Nando Leijenhorst