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

(Page Last updated 1st July 2016)

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, 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**

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:

- Constrained or unconstrained optimization of polynomial functions.
- Mixed continuous-discrete optimization.
- Finding Lyapunov or Bendixson-Dulac functions for nonlinear dynamical systems (with polynomial vector fields).
- Deciding copositivity of a matrix.
- Inequalities in probability theory.
- Distinguishing separable from entangled states in quantum systems.
- Or, more generally, problems that deal with basic semialgebraic sets (sets defined by polynomial equalities and inequalities)..

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.

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:

- SOSTOOLS release v3.01 (1st July 2016): SOSTOOLS.301.zip

Older versions:

- SOSTOOLS release v3.00 (16 Oct 2013): SOSTOOLS.300.zip
- SOSTOOLS release v2.05 (17th Aug 2012): SOSTOOLS.205.zip
- SOSTOOLS release v2.04 (31st Aug 2010): SOSTOOLS.204.zip
- SOSTOOLS release v2.03 (31st May 2010): SOSTOOLS.203.zip
- SOSTOOLS release v2.02, compatible with MATLAB 7.1 (2nd May 2006): SOSTOOLS.202.zip
- SOSTOOLS release v2.01 (8th Oct 2004): SOSTOOLS.201.zip
- SOSTOOLS release v2.00 (28th June 2004): SOSTOOLS.200.zip
- SOSTOOLS release v1.01, compatible with MATLAB 6.5 (4th March 2003): SOSTOOLS.101.zip
- SOSTOOLS release v1.00 (11th April 2002): SOSTOOLS.100.zip

To install and run SOSTOOLS, you need:

- MATLAB version 6.0 or later.
- MATLAB Symbolic Math Toolbox version 2.1.2 (optional) for SOSTOOLS versions 2.05 and earlier, or the current version of the MATLAB Symbolic Math Toolbox for SOSTOOLS version 3.00 and later.
- An SDP solver, either SeDuMi, SDPT3, CSDP, SDPNAL, SDPNAL+ or SDPA. These solvers and their documentation can be downloaded for free. For information on how to install them, you are referred to their installation instructions.

SOSTOOLS can easily be run on Windows or MAC OSX machines. 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).

The software has been written and is maintained by:

- Antonis Papachristodoulou
- James Anderson
- Giorgio Valmorbida
- Stephen Prajna
- Peter Seiler
- Pablo A. Parrilo

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

Abstract, postscript, gzipped postscript, pdf.

P. A. Parrilo,

Abstract, postscript, gzipped postscript.

P. A. Parrilo, B. Sturmfels,

http://www.arxiv.org/abs/math.OC/0103170

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}}, }

- INTSOSTOOLS for formulating and solving optimization problems subject to one-dimensional integral inequalities.
- frlib for a pre-processing facial reduction step.