Optimization Online


Sums of Squares Relaxations of Polynomial Semidefinite Programs

Masakazu Kojima (kojima***at***is.titech.ac.jp)

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

Keywords: Polynomial Optimization Problem, Sums of Squares Optimization, Semidefinite Program Relaxation, Lagrangian Relaxation, Lagrangian Dual, Penalty Function, Bilinear Matrix Inequality, Global Optimization.

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Global Optimization (Theory )

Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization )

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

Download: [Postscript][Compressed Postscript][PDF]

Entry Submitted: 11/11/2003
Entry Accepted: 11/11/2003
Entry Last Modified: 11/19/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society