[Caltech site] [MIT site] [Oxford site]

(Page Last updated 16th October 2013)

SOSTOOLS

 

Latest Release: SOSTOOLS release v3.00 (16 Oct 2013): SOSTOOLS.300.zip

Introduction

SOSTOOLS is a free MATLAB toolbox for formulating and solving sums of squares (SOS) optimization programs. SOSTOOLS can be used to specify and solve sum of squares polynomial problems using a very simple, flexible, and intuitive high-level notation. The SOS programs can be solved using SeDuMi, SDPT3 and more recently with CSDP, SDPNAL and SDPA. All these are well-known semidefinite programming solvers, with SOSTOOLS handling internally all the necessary reformulations and data conversion.

What is a "sum of squares optimization program"? Why would I want such a thing?

A sum of squares (SOS) program, in the simplest case, has the form:

minimize: c_1 * u_1 + ... + c_n * u_n

subject to constraints:

P_i(x) := A_i0(x) + A_i1(x) * u_1 + ... + A_in(x) * u_n

are sums of squares of polynomials (for i=1..n).

Here, the A_ij(x) are multivariate polynomials, and the decision variables u_i are scalars. This is a convex optimization problem, since the objective function is linear and the set of feasible u_i is convex.

While this looks quite nice, perhaps you are actually interested in more concrete problems such as:

Although most of these problems are NP-hard, it turns out that useful bounds (or even exact solutions) for all these problems can be found by formulating them in a sum of squares optimization framework.

Hopefully, by now you'll be intrigued, and a bit more inclined to think that this sum of squares stuff may actually be useful to you. If interested, you'll find a much more detailed explanation of the toolbox, some of the applications, and the concepts behind it in the SOSTOOLS user's guide, and the references below.


Distribution and release information

SOSTOOLS is freely available under the GNU license from either site:

CDS at Caltech: http://www.cds.caltech.edu/sostools or

LIDS at MIT: http://www.mit.edu/~parrilo/sostools.

Control Group at Oxford: http://www.eng.ox.ac.uk/control/sostools.

The available release for download:


Older versions:

 

System requirements

To install and run SOSTOOLS, you need:

SOSTOOLS can be easily run on a UNIX workstation or on a Windows PC desktop, or even a laptop. It utilizes MATLAB sparse matrix representation for good performance and to reduce the amount of memory needed.

Detailed installation instructions are available in the SOSTOOLS user's guide (also included with the standard distribution).

 


Authors

The software has been written and is maintained by:

References

For a detailed explanation of the theory and applications of sums of squares programming, as well as references to related work, please see:

  • Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization
    California Institute of Technology, Pasadena, CA, May 2000.
    Abstract, postscript, gzipped postscript, pdf.
  • Semidefinite programming relaxations for semialgebraic problems.
    P. A. Parrilo,
    Abstract, postscript, gzipped postscript.
  • Minimizing polynomial functions
    P. A. Parrilo, B. Sturmfels,
    http://www.arxiv.org/abs/math.OC/0103170
  • For more references please see http://hot.caltech.edu/math.html but also the authors' websites.

     


    Feedback

    For comments, bug reports, encouragement, suggestions, complaints, etc., please send email to: sostools@cds.caltech.edu.

    If you use SOSTOOLS for research purposes, we'd be happy to hear about it and mention it in the reference guide. Please drop us a line, to sostools@cds.caltech.edu

    Here's the bibtex entry, for citation:

    @manual{sostools,
    author = {A. Papachristodoulou, J. Anderson, G. Valmorbida, S. Prajna, P. Seiler and P. A. Parrilo},
    title = {{SOSTOOLS}: Sum of squares optimization toolbox for {MATLAB}},
    note = {Available from \texttt{http://www.eng.ox.ac.uk/control/sostools}, \texttt{http://www.cds.caltech.edu/sostools} and \texttt{http://www.mit.edu/\~{}parrilo/sostools}},
    year = {2013},
    address = {\texttt{http://arxiv.org/abs/1310.4716}},
    }