STOR Colloquium: Sercan Yildiz, SAMSI

Title: Polynomial Optimization with Sums-of-Squares Interpolants
Abstract: Sums-of-squares certificates define a hierarchy of relaxations for polynomial optimization problems which are parameterized 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 true optimal value under mild assumptions. However, solving the semidefinite programs that arise from sums-of-squares relaxations poses practical challenges at higher levels of the hierarchy. First, the sizes of these semidefinite programs depend quadratically on the number of monomials in the sums-of-squares representations. Second, numerical problems are often encountered. In this talk, we show that non-symmetric conic programming and polynomial interpolation techniques can be used to optimize efficiently over the sums-of-squares cone. Preliminary computational results indicate that our method compares favorably against standard approaches. The talk is based on joint work with David Papp.