SPOPT

SPOPT is a Sparse Polynomial OPTimizing package written in C++.

---

SPOPT numerically gains a lower bound for the polynomial optimization programs

minimize        f(x)
subject to      x in K

where K is a semi-algebraic set, by using Lasserre Hierarchy [1].

---

Requirements and Dependencies

SPOPT uses CMake to build the entire package. Please download and install CMake.

Also, following C++ libraries are used in the source code. Please install them, and place the header file (or, its symbolic link) to ext/include/ and the static library files to ext/lib/ (or any other place where your C++ compilier can recognize).

• Eigen
• yaml-cpp (ver 0.6.3)
• Boost (ver 1.74.0)
  • SPOPT only uses boost::program_options.
• AA
• MOSEK fusion API (Optional)
  • Change the parameter MOSEK_EXTENSION in CMakeLists.txt to true to use MOSEK to solve SDPs. You need to obtain an appropriate license to use MOSEK.
• SCS (Optional)
  • Change the parameter SCS_EXTENSION in CMakeLists.txt to true to use SCS to solve SDPs. Add the directory include as scs under the directory ext/include, and also add the directory linsys under the directory ext/include. Also, add the files made by make command to ext/lib/scs, i.e., add an symbolic link from (scs_install_dir_on_your_file_system)/out to ext/lib/scs.
• BLAS
• LAPACK

---

Compilation

By typing following commands, cmake will automatically generate Makefile and make command makes it able to compile the code and create SPOPT executable program in the build folder.

cd build
cmake ..
make

---

Basic Usage

See the file problem_data.yml and solver.yml in example directory. If you have correctly compiled SPOPT, then by running the following command,

(SPOPT_install_dir)/build/SPOPT -p (SPOPT_install_dir)/example/problem_data.yml -s (SPOPT_install_dir)/example/solver.yml

SPOPT will solve the following POP problem :

minimize        x_1 + x_2 + x_3 + x_4
subject to      x_1^2 + x_2^2 + x_3^2 + x_4^2 = 1.

It should show the optimal value -0.5 and its corresponding solution vector.

Type

(SPOPT_install_dir)/build/SPOPT --help

to obtain further information.

---

References

• [1] J. B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization, 11 (2001), pp. 796-817.