SparsePOP
(A Sparse SemiDefinite Programming Relaxation of 
Polynomial Optimization Problems)

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

----------------------------------------
Index

1. Overview
2. System Requirements
3. Installation Guide
4. Usage of SparsePOP
5. Acknowledgements
6. License
7. E-mail address
8. History

----------------------------------------


1. Overview

SparesPOP is a MATLAB package for a sparse semidefinite 
programming (SDP) relaxation method for approximating a 
global optimal value and solution of a polynomial optimization 
problem (POP) proposed by Waki et al. The sparse SDP relaxation 
exploits a sparse structure of polynomials in POPs when applying 
ga hierarchy of LMI relaxations of increasing dimensionsh by 
Lasserre. The efficiency of SparsePOP to approximate optimal 
solutions of POPs is thus increased, and larger scale POPs can 
be handled. 

Two versions of SparsePOP are available in this package:
   (A) MATLAB only version
   (B) MATLAB with C++ version
(A) will always be installed, while (B) is optional.

The functions and capabilities of the two versions are identical. 
Some of time-consuming parts of (B) is coded in C++, thus, it is
faster in generating SDP problems than (A). We recommend to use (B)
whenever possible, although in many cases (A) is sufficient.


2. System Requirements

The following software packages are required for SparsePOP.

  i. MATLAB R2006b or later.
	-- available from Mathworks inc.

  ii. SeDuMi 1.1R3 or later
	-- available from http://sedumi.ie.lehigh.edu/ 
	to call SeDuMi from SparsePOP for solving an SDP relaxation problem
  and/or 
  iii. sdpa.7.3.1 or later  
	-- available from http://sdpa.indsys.chuo-u.ac.jp/sdpa/
	to call sedumiwrap.m from SparsePOP for solving an SDP relaxation problem


If you want to use (B), then you need appropriate C++ compilers,
compatible with MATLAB, to compile the programs.

NOTE: If Symbolic Math Toolbox is available on your computer, 
SparsePOP can handle a gms file which contains parentheses, 
e.g. Bex2_1_2.gms.

NOTE2: If Optimization Toolbox 4.0 or later is available on your 
computer, you can refine approximated solutions of SparsePOP by 
using some functions in Optimization Toolbox. See  Section 3.4 in 
User Manual for more detail. 


3. Installation Guide

See install.txt in the top directory of SparsePOP. After installing 
SparsePOP, add the path of SparsePOP in your MATLAB search path. 
	

4. Usage of SparsePOP

We assume that SDPA and/or SeDuMi have been already installed on 
your computer and that the paths of their folders and subfolders 
have been already added in your Matlab search path.

The usage of SparsePOP is explained in the user manual available at
http://www.is.titech.ac.jp/~kojima/SparsePOP


5. Acknowledgments

The authors are grateful to Mr. Mevissen Martine and 
Mr. Dan Gugenheim for bug reports.


6. License

This software is distributed under GNU General Public License 2.0


7. E-mail address

kojima-spop@is.titech.ac.jp

Please send a message if you have any questions, ideas, or 
bug reports.


8. History

Version 2.20 (August 20, 2009)
(1) Users can use SDPA instead of SeDuMi for solving an SDP 
relaxation problem.  See `readmeRevision.txt' for more detail.


Version 2.15 (June 22, 2009)
(1) The function for writing an SDP as the sdpa sparse 
format is modified and included into the function 
solveBySeDuMi.m

(2) SparsePOP outputs a file which contains information 
on scaling for a given POP. See `readmeRevision.txt' for 
more detail.


Version 2.10 (April 3, 2009)
(1) SparsePOP can accept a new input format for a 
constrained nonlinear least square problem.  
(2) To refine approximated solution obtained by SparsePOP, 
users can call some functions in Optimization Toolbox. See 
`readmeRevision.txt' for more detail.


Version 2.00 (June, 2007)
(1) For speedup, C++ subroutines are developed. 
(2) The second version (B) of SparsePOP are added in 
SparsePOP.
(3) Improve user interface.
(4) Some bugs are fixed.

Version 1.20 (September, 2005)