Skip to main content

Loading Events

« All Events

  • This event has passed.

Sercan Yildiz, SAMSI,Polynomial Optimization with Sums-of-Squares Interpolants

October 10, 2017 | 3:00 pm - 4:00 pm EDT

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 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.

Details

Date:
October 10, 2017
Time:
3:00 pm - 4:00 pm EDT
Event Category: