  


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 (Semidefinite Programming ) Category 2: Global Optimization (Theory ) Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization ) Citation: Research Report B397, Dept. of Mathematical and Computing Sciences, Tokyo Inst. of Technology, Meguroku, Tokyo 1528552 Japan, November 2003 Download: [Postscript][Compressed Postscript][PDF] Entry Submitted: 11/11/2003 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  