Sums of Squares Relaxations of Polynomial Semidefinite Programs

A polynomial SDP (semidefinite program) minimizes a polynomial objective function over a feasible region described by a positive semidefinite constraint of a symmetric matrix whose components are multivariate polynomials. Sums of squares relaxations developed for polynomial optimization problems are extended to propose sums of squares relaxations for polynomial SDPs with an additional constraint for the variables to be in the unit ball. It is proved that optimal values of a sequence of sums of squares relaxations of the polynomial SDP, which correspond to duals of Lasserre's SDP relaxations applied to the polynomial SDP, converge to the optimal value of the polynomial SDP. The proof of the convergence is obtained by fully utilizing a penalty function and a generalized Lagrangian duals that were recently proposed by Kim et al for sparse polynomial optimization problems.

Citation

Research Report B-397, Dept. of Mathematical and Computing Sciences, Tokyo Inst. of Technology, Meguro-ku, Tokyo 152-8552 Japan, November 2003

Article

Download

View Sums of Squares Relaxations of Polynomial Semidefinite Programs