A cutting plane approach to upper bounds on the kissing number
N. Riemens (TU Delft - Electrical Engineering, Mathematics and Computer Science)
F.M. de Oliveira Filho – Mentor (TU Delft - Discrete Mathematics and Optimization)
WGM Groenevelt – Graduation committee member (TU Delft - Analysis)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Upper bounds for the kissing number can be written as a semidefinite program (SDP) through the Delsarte-Goethals-Seidel method for spherical codes. This thesis solves the resulting SDP with a cutting plane approach, in which a sequence of linear programs (LPs) is solved with the addition of linear constraints every round. We study the computational efficiency of dense and sparser cuts. Sparse cuts are obtained through a relation to the $k$-Sparse Principal Component Analysis problem. For the modest polynomial degrees considered, the dense and sparse methods show similar performance. Upper bounds are obtained through calculations in standard and where necessary quadruple precision. Lastly, it is shown that under a linear cutting plane approach the SDP is solved quicker if not every subsequent LP is solved till optimality.