Sums of Squares Relaxations of Polynomial Semidefinite Programs
Masakazu Kojima (kojimais.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
Entry Submitted: 11/11/2003
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|