Polynomial programming with DIGS: a second order cone implementation

DIGS is an algorithm developed by Anjos, Ghaddar and Vera (2016) proved to be a valid alternative to Lasserre Hierarchies for solving Polynomial Programs. In this thesis we implemented, tested and then improved its SOCP formulation. At first we investigated the relationship between SOCP and SDSOS polynomials, and how to relax a polynomial program as an SOCP. We focused our attention on comparing SDSOS and SOS implementation, in terms of complexity, speed and accuracy. Specifically, we implemented DIGS algorithm in these settings and tested it on some quadratic programs. Then we exploited sparsity for the SDSOS formulation, using the approach of Sheen and Yamashita (2019), and noticed improved performances on Quadratic Knapsack instances. Finally we enriched the formulation with valid inequalities for binary programs, showing how this can further improve the algorithm.