---

SparsePOP

(Sparse SDP Relaxation of Polynomial Optimization Problems)

Hayato Waki, Sunyoung Kim, Masakazu Kojima, Masakazu Muramatsu, and Hiroshi Sugimoto

December 27, 2007

---

SparesPOP is a MATLAB implementation of a sparse semidefinite programming (SDP) relaxation method proposed for polynomial optimization problems (POPs) in the paper

H. Waki, S. Kim, M. Kojima and M. Muramatsu, ''Sums of squares and semidefinite programming relaxation for polynomial optimization problems with structured sparsity'', SIAM J. Optim. Vol 17, (1) 218-242 (2006).

The sparse SDP relaxation exploits a sparse structure of polynomials in POPs when applying ``a hierarchy of LMI relaxations of increasing dimensions'' by Lasserre. The efficiency of SparsePOP to approximate optimal values of POPs is thus increased, and larger scale POPs can be handled.

• Install Guide
• User Guide
• On the latest revision
• Gzipped tarred file of SparsePOP V200

If you have any questions, please send a message to kojima-spop at is.titech.ac.jp.