SumOfSquares –- Sum of Squares Programming for Julia

SumOfSquares implements Sum of Squares reformulation for PolyJuMP, enabling the creation of sum of squares variables and constraints in JuMP.

The polynomial can be represented by any library implementing the MultivariatePolynomial.jl interface. That is, you can currently choose between DynamicPolynomials and TypedPolynomials. As a rule of thumb, if you know at compile time (or at the time you are writing your code), the number of variable and that this number is small, use TypedPolynomials, otherwise, use DynamicPolynomials.

Some presentations on, or using, SumOfSquares (see here for the source code of the presentations):

• Tillmann Weisser, Benoît Legat, Chris Coey, Lea Kapelevich and Juan Pablo Vielma at JuliaCon 2019 [Slides] [Video]
• Benoît Legat at CNLS 2019 [Slides]
• Benoît Legat at EURO 2019 [Slides]
• Benoît Legat at juliaday Nantes 2019 [Slides]
• Benoît Legat at Summer School on Numerical Computing in Algebraic Geometry 2018 [Poster]
• Benoît Legat at The First Annual JuMP-dev Workshop 2017 [Slides] [Video]
• Joey Huchette at SIAM Opt 2017

Contents

• Sum-of-Squares Programming
• • Quadratic forms and Semidefinite programming
  • Polynomial nonnegativity and Semidefinite programming
  • When is nonnegativity equivalent to sum of squares ?
• Polynomial and Sum-of-Squares variables
• • Polynomial variables
  • Nonnegative polynomial variables
  • Choosing a polynomial basis
  • Reference
• Constraints
• • Equality constraints between polynomials
  • Inequality constraints between polynomials
  • Changing the polynomial basis
  • Polynomial nonnegativity on a subset of the space
  • Dual of polynomial constraints
  • Reference