Sercan Yildiz, SAMSI,Polynomial Optimization with Sums-of-Squares Interpolants
Sums-of-squares certificates define a hierarchy of relaxations for polynomial optimization problems which are parametrized with the degree of the polynomials in the sums-of-squares representation. Each level of the hierarchy generates a lower bound on the true optimal value, which can be computed in polynomial time via semidefinite programming, and these lower bounds converge to the…