Sum-of-squares optimization

Given a vector $c\backslash in\; \backslash R^n$ and polynomials $a\_\{k,j\}$ for $k=1,\; \backslash dots\; N\_s$, $j\; =\; 0,\; 1,\; \backslash dots,\; n$, a sum-of-squares optimization problem is written as

\begin{aligned}

\underset{u\in\R^n}{\text{maximize}} \quad & c^T u \\

\text{subject to} \quad &

a_{k,0}(x) + a_{k,1}(x)u_1 + \cdots + a_{k,n}(x)u_n \in \text{SOS} \quad (k=1,\ldots, N_s).

\end{aligned}

Here "SOS" represents the class of sum-of-squares (SOS) polynomials.

The quantities $u\backslash in\; \backslash R^n$ are the decision variables. SOS programs can be converted to semidefinite programs (SDPs) using the duality of the SOS polynomial program and a relaxation for constrained polynomial optimization using positive-semidefinite matrices, see the following section.

Suppose we have an $n$-variate polynomial $p(x):\; \backslash mathbb\{R\}^n\; \backslash to\; \backslash mathbb\{R\}$ , and suppose that we would like to minimize this polynomial over a subset $A\; \backslash subseteq\; \backslash mathbb\{R\}^n$. Suppose furthermore that the constraints on the subset $A$ can be encoded using $m$ polynomial equalities of degree at most $2d$, each of the form $a\_i(x)\; =\; 0$ where $a\_i:\; \backslash mathbb\{R\}^n\; \backslash to\; \backslash mathbb\{R\}$ is a polynomial of degree at most $2d$. A natural, though generally non-convex program for this optimization problem is the following:

$$\backslash min\_\{x\; \backslash in\; \backslash mathbb\{R\}^\{n\}\}\; \backslash langle\; C,\; x^\{\backslash le\; d\}\; (x^\{\backslash le\; d\})^\backslash top\; \backslash rangle$$

subject to:

{{NumBlk||$$\backslash langle\; A\_i,\; x^\{\backslash le\; d\}(x^\{\backslash le\; d\})^\backslash top\; \backslash rangle\; =\; 0\; \backslash qquad\; \backslash forall\; \backslash \; i\; \backslash in\; [m],$$|{{EquationRef|1}}}}

$$x\_\{\backslash emptyset\}\; =\; 1,$$

where $x^\{\backslash le\; d\}$ is the $n^\{O(d)\}$-dimensional vector with one entry for every monomial in $x$ of degree at most $d$, so that for each multiset $S\; \backslash subset\; [n],\; |S|\; \backslash le\; d,$ $x\_S\; =\; \backslash prod\_\{i\; \backslash in\; S\}x\_i$, $C$ is a matrix of coefficients of the polynomial $p(x)$ that we want to minimize, and $A\_i$ is a matrix of coefficients of the polynomial $a\_i(x)$ encoding the $i$-th constraint on the subset $A\; \backslash subset\; \backslash R^n$. The additional, fixed constant index in our search space, $x\_\{\backslash emptyset\}\; =\; 1$, is added for the convenience of writing the polynomials $p(x)$ and $a\_i(x)$ in a matrix representation.

This program is generally non-convex, because the constraints ({{EquationNote|1}}) are not convex. One possible convex relaxation for this minimization problem uses semidefinite programming to replace the rank-one matrix of variables $x^\{\backslash le\; d\}\; (x^\{\backslash le\; d\})^\backslash top$ with a positive-semidefinite matrix $X$: we index each monomial of size at most $2d$ by a multiset $S$ of at most $2d$ indices, $S\; \backslash subset\; [n],\; |S|\; \backslash le\; 2d$. For each such monomial, we create a variable $X\_S$ in the program, and we arrange the variables $X\_S$ to form the matrix $X\; \backslash in\; \backslash mathbb\{R\}^\{[n]^\{\backslash le\; d\}\; \backslash times\; [n]^\{\backslash le\; d\}\}$, where $\backslash R^\{[n]^\{\backslash le\; d\}\backslash times\; [n]^\{\backslash le\; d\}\}$ is the set of real matrices whose rows and columns are identified with multisets of elements from $n$ of size at most $d$. We then write the following semidefinite program in the variables $X\_S$:

$$\backslash min\_\{X\; \backslash in\; \backslash R^\{[n]^\{\backslash le\; d\}\; \backslash times\; [n]^\{\backslash le\; d\}\; \}\}\backslash langle\; C,\; X\; \backslash rangle$$

subject to:

$$\backslash langle\; A\_i,\; X\; \backslash rangle\; =0\; \backslash qquad\; \backslash forall\; \backslash \; i\; \backslash in\; [m],\; Q$$

$$X\_\{\backslash emptyset\}\; =\; 1\; ,$$

$$X\_\{U\; \backslash cup\; V\}\; =\; X\_\{S\; \backslash cup\; T\}\; \backslash qquad\; \backslash forall\; \backslash \; U,V,S,T\; \backslash subseteq\; [n],\; |U|,|V|,|S|,|T|\; \backslash le\; d,\backslash text\{\; and\}\; \backslash \; U\; \backslash cup\; V\; =\; S\; \backslash cup\; T\; ,$$

$$X\; \backslash succeq\; 0,$$

where again $C$ is the matrix of coefficients of the polynomial $p(x)$ that we want to minimize, and $A\_i$ is the matrix of coefficients of the polynomial $a\_i(x)$ encoding the $i$-th constraint on the subset $A\; \backslash subset\; \backslash R^n$.

The third constraint ensures that the value of a monomial that appears several times within the matrix is equal throughout the matrix, and is added to make $X$ respect the symmetries present in the quadratic form $x^\{\backslash le\; d\}(x^\{\backslash le\; d\})^\backslash top$.

One can take the dual of the above semidefinite program and obtain the following program:

$$\backslash max\_\{y\; \backslash in\; \backslash mathbb\{R\}^\{m\text{'}\}\}\; y\_0\; ,$$

subject to:

$$C\; -\; y\_0\; e\_\{\backslash emptyset\}-\; \backslash sum\_\{i\; \backslash in\; [m]\}\; y\_i\; A\_i\; -\; \backslash sum\_\{S\backslash cup\; T\; =\; U\backslash cup\; V\}\; y\_\{S,T,U,V\}\; (e\_\{S,T\}\; -\; e\_\{U,V\})\backslash succeq\; 0.$$

We have a variable $y\_0$ corresponding to the constraint $\backslash langle\; e\_\{\backslash emptyset\},\; X\backslash rangle\; =\; 1$ (where $e\_\{\backslash emptyset\}$ is the matrix with all entries zero save for the entry indexed by $(\backslash varnothing,\backslash varnothing)$), a real variable $y\_i$ for each polynomial constraint $\backslash langle\; X,A\_i\; \backslash rangle\; =\; 0\; \backslash quad\; s.t.\; i\; \backslash in\; [m],$ and for each group of multisets $S,T,U,V\; \backslash subset\; [n],\; |S|,|T|,|U|,|V|\; \backslash le\; d,\; S\backslash cup\; T\; =\; U\; \backslash cup\; V$, we have a dual variable $y\_\{S,T,U,V\}$ for the symmetry constraint $\backslash langle\; X,\; e\_\{S,T\}\; -\; e\_\{U,V\}\; \backslash rangle\; =\; 0$. The positive-semidefiniteness constraint ensures that $p(x)\; -\; y\_0$ is a sum-of-squares of polynomials over $A\; \backslash subset\; \backslash R^n$: by a characterization of positive-semidefinite matrices, for any positive-semidefinite matrix $Q\backslash in\; \backslash mathbb\{R\}^\{m\; \backslash times\; m\}$, we can write $Q\; =\; \backslash sum\_\{i\; \backslash in\; [m]\}\; f\_i\; f\_i^\backslash top$

for vectors $f\_i\; \backslash in\; \backslash mathbb\{R\}^m$. Thus for any $x\; \backslash in\; A\; \backslash subset\; \backslash mathbb\{R\}^n$,

$$\backslash begin\{align\}$$

p(x) - y_0

&= p(x) - y_0 - \sum_{i \in [m']} y_i a_i(x) \qquad \text{since } x \in A\\

&=(x^{\le d})^\top \left( C - y_0 e_{\emptyset} - \sum_{i\in [m']} y_i A_i - \sum_{S\cup T = U \cup V} y_{S,T,U,V}(e_{S,T}-e_{U,V}) \right)x^{\le d}\qquad \text{by symmetry}\\

&= (x^{\le d})^\top \left( \sum_{i} f_i f_i^\top \right)x^{\le d} \\

&= \sum_{i} \langle x^{\le d}, f_i\rangle^2 \\

&= \sum_{i} f_i(x)^2,

\end{align}

where we have identified the vectors $f\_i$ with the coefficients of a polynomial of degree at most $d$. This gives a sum-of-squares proof that the value $p(x)\; \backslash ge\; y\_0$ over $$

A \subset \mathbb{R}^n .

The above can also be extended to regions $A\; \backslash subset\; \backslash mathbb\{R\}^n$ defined by polynomial inequalities.

The sum-of-squares hierarchy (SOS hierarchy), also known as the Lasserre hierarchy, is a hierarchy of convex relaxations of increasing power and increasing computational cost. For each natural number $d\; \backslash in\; \backslash mathbb\{N\}$ the corresponding convex relaxation is known as the $d$th level or $d$-th round of the SOS hierarchy. The $1$st round, when $d=1$, corresponds to a basic semidefinite program, or to sum-of-squares optimization over polynomials of degree at most $2$. To augment the basic convex program at the $1$st level of the hierarchy to $d$-th level, additional variables and constraints are added to the program to have the program consider polynomials of degree at most $2d$.

The SOS hierarchy derives its name from the fact that the value of the objective function at the $d$-th level is bounded with a sum-of-squares proof using polynomials of degree at most $2d$ via the dual (see "Duality" above). Consequently, any sum-of-squares proof that uses polynomials of degree at most $2d$ can be used to bound the objective value, allowing one to prove guarantees on the tightness of the relaxation.

In conjunction with a theorem of Berg, this further implies that given sufficiently many rounds, the relaxation becomes arbitrarily tight on any fixed interval. Berg's result{{Cite book |last = Berg|first = Christian| title=Moments in Mathematics | chapter=The multidimensional moment problem and semigroups | series=Proceedings of Symposia in Applied Mathematics |date = 1987 |volume = 37|pages = 110–124|doi = 10.1090/psapm/037/921086|isbn = 9780821801147|editor-last = Landau|editor-first = Henry J.|chapter-url=https://books.google.com/books?id=IEo2Iu_uogUC&dq=%22The+multidimensional+moment+problem+and+semigroups%22&pg=PA110}}{{Cite journal|title = A Sum of Squares Approximation of Nonnegative Polynomials|url = http://epubs.siam.org/doi/abs/10.1137/070693709|journal = SIAM Review|date = 2007-01-01|issn = 0036-1445|pages = 651–669|volume = 49|issue = 4|doi = 10.1137/070693709|first = J.|last = Lasserre|arxiv = math/0412398| bibcode=2007SIAMR..49..651L }} states that every non-negative real polynomial within a bounded interval can be approximated within accuracy $\backslash varepsilon$ on that interval with a sum-of-squares of real polynomials of sufficiently high degree, and thus if $OBJ(x)$ is the polynomial objective value as a function of the point $x$, if the inequality $c\; +\; \backslash varepsilon\; -\; OBJ(x)\; \backslash ge\; 0$ holds for all $x$ in the region of interest, then there must be a sum-of-squares proof of this fact. Choosing $c$ to be the minimum of the objective function over the feasible region, we have the result.

When optimizing over a function in $n$ variables, the $d$-th level of the hierarchy can be written as a semidefinite program over $n^\{O(d)\}$ variables, and can be solved in time $n^\{O(d)\}$ using the ellipsoid method.

{{Main|Polynomial SOS}}

A polynomial $p$ is a sum of squares (SOS) if there exist polynomials $\backslash \{f\_i\backslash \}\_\{i=1\}^m$ such that $p\; =\; \backslash sum\_\{i=1\}^m\; f\_i^2$. For example,

$$p=x^2\; -\; 4xy\; +\; 7y^2$$

is a sum of squares since

$$p\; =\; f\_1^2\; +\; f\_2^2$$

where

$$f\_1\; =\; (x-2y)\backslash text\{\; and\; \}f\_2\; =\; \backslash sqrt\{3\}y.$$

Note that if $p$ is a sum of squares then $p(x)\; \backslash ge\; 0$ for all $x\; \backslash in\; \backslash R^n$. Detailed descriptions of polynomial SOS are available.Parrilo, P., (2000) [https://thesis.library.caltech.edu/1647/1/Parrilo-Thesis.pdf Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization]. Ph.D. thesis, California Institute of Technology.

Parrilo, P. (2003) "[http://www.cds.caltech.edu/~doyle/hot/SDPrelaxations.pdf Semidefinite programming relaxations for semialgebraic problems]". Mathematical Programming Ser. B 96 (2), 293–320.Lasserre, J. (2001) "[http://khalilghorbal.info/assets/spa/papers/lasserre.pdf Global optimization with polynomials and the problem of moments]". SIAM Journal on Optimization, 11 (3), 796{817.

Quadratic forms can be expressed as $p(x)=x^T\; Q\; x$ where $Q$ is a symmetric matrix. Similarly, polynomials of degree ≤ 2d can be expressed as

$$p(x)=z(x)^\backslash mathsf\{T\}\; Q\; z(x)\; ,$$

where the vector $z$ contains all monomials of degree $\backslash le\; d$. This is known as the Gram matrix form. An important fact is that $p$ is SOS if and only if there exists a symmetric and positive-semidefinite matrix $Q$ such that $p(x)\; =\; z(x)^\backslash mathsf\{T\}\; Q\; z(x)$.

This provides a connection between SOS polynomials and positive-semidefinite matrices.

• [http://www.cds.caltech.edu/sostools/ SOSTOOLS], licensed under the GNU GPL. The reference guide is available at arXiv:1310.4716 [math.OC], and a presentation about its internals is available [https://www.youtube.com/watch?v=4_N16UPAgzQ here].
• [https://github.com/oxfordcontrol/CDCS/tree/master/packages/%2Bcdcs_sos CDCS-sos], a package from [https://github.com/oxfordcontrol/CDCS CDCS], an augmented Lagrangian method solver, to deal with large scale SOS programs.
• The [https://github.com/JuliaOpt/SumOfSquares.jl SumOfSquares] extension of [https://github.com/JuliaOpt/JuMP.jl JuMP] for Julia.
• [https://github.com/wangjie212/TSSOS TSSOS] for Julia, a polynomial optimization tool based on the sparsity adapted moment-SOS hierarchies.
• For the dual problem of constrained polynomial optimization, [http://homepages.laas.fr/henrion/software/gloptipoly/ GloptiPoly] for MATLAB/Octave, [https://github.com/peterwittek/ncpol2sdpa Ncpol2sdpa] for Python and [https://github.com/lanl-ansi/MomentOpt.jl MomentOpt] for Julia.

Category:Mathematical optimization

Category:Real algebraic geometry