Using relaxations of sum of squares formulations for the kissing number problem
J. Rang (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Fernando Mário de Oliveira Filho – Mentor (TU Delft - Discrete Mathematics and Optimization)
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
In recent years the importance of sum of squares and semidefinte pro-gramming has been seen in the field of combinatorial optimisation. Alllinear programs can be rewritten into a semidefinte one and by usinghierarchies of semidefinite programs these can be solved for polynomialoptimisation problems. Recently, in 2019, A.A. Ahmadi and A. Majumdarreleased a paper called “DSOS and SDSOS Optimization: More TractableAlternatives to Sum of Squares and Semidefinite Optimization”[1] wherethey introduced the concept of sum of square polynomials obtained fromdiagonally dominant matrices. Since this concept is relatively new I amgoing to look at the viability of these sum of square polynomials in olderknown optimisation problems such as the kissing number problem. I willdo this by writing a semidefinite program in which the sum of square poly-nomials are created by diagonally dominant matrices. I will then comparethe newly found upper bounds with the upper bounds found by samplingand the volume bound.