SparsePOP : a Sparse Semidefinite Programming Relaxation of Polynomial Optimization Problems

Hayato Waki (Hayato.Wakiis.titech.ac.jp)
Sunyoung Kim (skimewha.ac.kr)
Masakazu Kojima (kojimais.titech.ac.jp)
Masakazu Muramatsu (muramatucs.uec.ac.jp)

Abstract: SparesPOP is a MATLAB implementation of a sparse semidefinite programming (SDP) relaxation method proposed for polynomial optimization problems (POPs) in the recent paper by Waki et al. The sparse SDP relaxation is based on a hierarchy of LMI relaxations of increasing dimensions by Lasserre, and exploits a sparsity structure of polynomials in POPs. The efficiency of SparsePOP to compute bounds for optimal values of POPs is increased and larger scale POPs can be handled. The software package SparesPOP and this manual with some numerical examples are available at http://www.is.titech.ac.jp/~kojima/SparsePOP

Keywords: Polynomial optimization problem, sparsity, global optimization, sums of squares optimization, semidefinite programming relaxation, MATLAB software package

Category 1: Global Optimization

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

Category 3: Optimization Software and Modeling Systems

Citation: Research Report B-414, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Tehnology, Oh-Okayama, Meguro 152-8552, Tokyo, Japan

Download: [PDF]

Entry Submitted: 03/09/2005
Entry Accepted: 03/10/2005
Entry Last Modified: 03/09/2005

Modify/Update this entry