---

SparsePOP

(Sparse SDP Relaxation of Polynomial Optimization Problems)

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

August 16, 2019

---

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). http://dx.doi.org/10.1137/050623802

H. Waki, S. Kim, M. Kojima, M. Muramatsu and H. Sugimoto, "SparsePOP : a Sparse Semidefinite Programming Relaxation of Polynomial Optimization Problems", ACM Transactions on Mathematical Software Vol 35, (2) 15 (2008). http://dx.doi.org/10.1145/1377612.1377619

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.

• User Guide
• README of the latest version
• Gzipped tarred file of SparsePOP V2.20
• Gzipped tarred file of SparsePOP V2.60
• Gzipped tarred file of SparsePOP V2.80
• Gzipped tarred file of SparsePOP V2.85
• Gzipped tarred file of SparsePOP V2.90
• Gzipped tarred file of SparsePOP V2.95
• Gzipped tarred file of SparsePOP V2.96
• Gzipped tarred file of SparsePOP V2.97
• Gzipped tarred file of SparsePOP V2.98
• Gzipped tarred file of SparsePOP V2.99
• Gzipped tarred file of SparsePOP V3.00
• Gzipped tarred file of SparsePOP V3.01
• Gzipped tarred file of SparsePOP V3.02
• UPDATE! Gzipped tarred file of SparsePOP V3.03 (the latest version)
• Gzipped tarred file of C++ version of SparsePOP V2.59. This version does not exploit MATLAB. See README.txt contained in SparesePOPC++259.tar.gz for the installation.
• Zipped file of the Windows binary of SparsePOP V2.59. This version does not exploit MATLAB. See README.txt contained in SparesePOPC++259-windows.zip for the installation.

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