Sums of Squares and Semidefinite Programming Relaxations for Polynomial Optimization Problems with Structured Sparsity

Hayato Waki (waki9is.titech.ac.jp)
Sunyoung Kim (skimmath.ewha.ac.kr)
Masakazu Kojima (kojimais.titech.ac.jp)
Masakazu Muramatsu (muramatucs.uec.ac.jp)

Abstract: Unconstrained and inequality constrained sparse polynomial optimization problems (POPs) are considered. A correlative sparsity pattern graph is defined to find a certain sparse structure in the objective and constraint polynomials of a POP. Based on this graph, sets of supports for sums of squares (SOS) polynomials that lead to efficient SOS and semidefinite programming (SDP) relaxations are obtained. Numerical results from various test problems are included to show the improved performance of the SOS and SDP relaxations.

Keywords: Polynomial optimization problem, sparsity, global optimization, Lagrangian relaxation, Lagrangian dual, sums of squares optimization, semidefinite programming relaxation

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Global Optimization

Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Research Report B-411, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo 152-8552, Japan

Download: [PDF]

Entry Submitted: 10/30/2004
Entry Accepted: 10/30/2004
Entry Last Modified: 02/03/2005

Modify/Update this entry