It is NP-hard to decide whether a polynomial is nonnegative, however, semidefinite programming can be used to decide whether a polynomial is a sum of squares of polynomials (SOS) in a practically efficient manner. In the context of polynomial optimization, it has become usual to substitute testing for nonnegativity with testing for SOS. Since there are much fewer sums of squares than nonnegative polynomials, we get only a relaxation and one that does not scale very well with the number of variables and degree of the polynomial. Recently, Ahmadi and Majumdar introduced a more scalable alternative to SOS optimization that they refer to as scaled diagonally dominant sums of squares (SDSOS). The idea is searching for sums of squares of binomials, instead of general polynomials, which leads to a more scalable SOCP problem. In this presentation, we investigate the quantitative relationship between sums of squares of polynomials and scaled diagonally dominant polynomials. More specifically, we use techniques established by Blekherman to bound the ratio between the volume of the cones of these two classes of polynomials, showing that there are significantly less SDSOS polynomials than SOS polynomials. This drawback can be circumvented by using a recently introduced basis pursuit procedure of Ahmadi and Hall that iteratively changes the polynomial basis to a more suitable relaxation. We illustrate this by presenting a new application of this technique to an optimization problem.
The seminar takes place in PORTO.
(*) Mina Saee Bostanabad is a PhD student of the Joint PhD Program UC-UP, working at the University of Coimbra, in Optimization, under the supervision of Professor João Eduardo da Silveira Gouveia.