(Sparse SDP Relaxation of Polynomial Optimization Problems)
Hayato Waki, Sunyoung Kim, Masakazu Kojima, Masakazu Muramatsu,
Hiroshi Sugimoto and Makoto Yamashita
July 26, 2011
SparesPOP is a MATLAB implementation of a sparse semidefinite programming (SDP)
relaxation method proposed for polynomial optimization problems (POPs) in the
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).
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).
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.
Download SparsePOP software for free at SourceForge.net
If you have any questions, please send a message to kojima-spop "insert at mark" is.titech.ac.jp.