Sparse sum-of-squares (SOS) optimization: A bridge between DSOS/SDSOS and SOS optimization for sparse polynomials

Optimization over non-negative polynomials is fundamental for nonlinear systems analysis and control. We investigate the relation between three tractable relaxations for optimizing over sparse non-negative polynomials: sparse sum-of-squares (SSOS) optimization, diagonally dominant sum-of-squares (DSOS) optimization, and scaled diagonally dominant sum-of-squares (SDSOS) optimization. We prove that the set of SSOS polynomials, an inner approximation of the cone of SOS polynomials, strictly contains the spaces of sparse DSOS/SDSOS polynomials. When applicable, therefore, SSOS optimization is less conservative than its DSOS/SDSOS counterparts. Numerical results for large-scale sparse polynomial optimization problems demonstrate this fact, and also that SSOS optimization can be faster than DSOS/SDSOS methods despite requiring the solution of semidefinite programs instead of less expensive linear/second-order cone programs.


I. INTRODUCTION
Optimization over non-negative polynomials plays a fundamental role in analysis and control of systems with polynomial dynamics. For instance, the construction of polynomial Lyapunov or Lyapunov-type functions subject to suitable polynomial inequalities can prove nonlinear stability of equilibrium solutions [1], approximate basins of attraction [2], and provide bounds on infinite-time averages [3]- [5].
Since deciding whether a given polynomial p(x) is nonnegative is NP-hard in general, a popular alternative is to look for a decomposition of p(x) as a sum-of-squares (SOS) of polynomials with lower degree. Checking this sufficient condition for non-negativity is attractive because it amounts to solving a semidefinite program (SDP) [6], [7], a well-known type of convex optimization problem for which polynomial-time algorithms exist. However, the dimension of this SDP typically grows in a combinatorial fashion as the number of variables and the polynomial degree increase [6], and very large SDPs are required to solve even when one employs well-known dimension reduction techniques, such as the Newton polytope [8], diagonal inconsistency [9], and symmetry [10] or facial reduction [11]. Consequently, SOSbased analysis is only practical for polynomial dynamical systems with few states and/or low degree.
In order to improve scalability, it has been proposed by many authors to replace positivity certificates based on SOS representations with other sufficient conditions for nonnegativity, which are stronger but have a lower computational complexity. For correlatively sparse polynomials, characterized by sparse couplings between different independent variables, Waki et al. [12] proposed to look for a decomposition as a sum of SOS polynomials, each involving only small subsets of the independent variables. While being more restrictive, the search for such a sparse sum-of-squares (SSOS) decomposition can be carried out at a fraction of the computational cost required for a standard SOS decomposition, because an SDP with one large matrix variable is replaced with an SDP with multiple much smaller matrix variables. The latter can be solved more efficiently, a fact that also underpins the more recent sparse-BSOS [13] and multi-ordered Lasserre relaxation hierarchies [14] for sparse polynomial optimization. Two other alternatives to SOS optimization, applicable also to polynomials without correlative sparsity, were put forward by Ahmadi and Majumdar [15], who observed that the cones of diagonally dominant sum-ofsquares (DSOS) polynomials and of scaled diagonally dominant sum-of-squares (SDSOS) polynomials are strict subsets of the cone of SOS polynomials. Optimization problems over DSOS and SDSOS polynomials can be recast as linear programs (LPs) and second-order cone programs (SOCP), respectively, and both of these can be solved with algorithms that scale more favourably than those for SDPs [15]. On the other hand, DSOS/SDSOS optimization might be very conservative (although the conservatism may be reduced using iterative methods based on basis pursuit [16] or column generation [17]).
The availability of such a variety of approaches poses a simple but important dilemma: when more than one method can be applied, which one should be used? To answer this question, theoretical results comparing the degree of conservatism and computational complexity for each of the aforementioned approaches would be desirable. In this paper, therefore, we study the relation between DSOS/SDSOS/SSOS positivity certificates for polynomials with correlative sparsity. Specifically, we prove that if a DSOS/SDSOS decomposition exists and the correlative sparsity is chordal (meaning that it can be represented by a chordal graph), then an SSOS decomposition is also available. In other words, the cones of DSOS/SDSOS polynomials with chordal correlative sparsity are strictly contained within the cone of polynomials that admit an SSOS decomposition in the sense of Waki et al. [12]. Thus, for polynomials with chordal correlative sparsity, DSOS/SDSOS optimization is provably more conservative than SSOS optimiza-tion (at least when the iterative improvement techniques for DSOS/SDSOS optimization mentioned above are not utilised). Also, SSOS optimization promises better scalability compared to standard SOS optimization. Therefore, we argue that SSOS optimization is a suitable candidate to bridge the gap between DSOS/SDSOS and SOS optimization.
The rest of this paper is organized as follows. Section II reviews some basic facts about SOS/DSOS/SDSOS polynomials, useful notions from graph theory, and correlatively sparse polynomials. We give a new interpretation of the positivity certificates of Waki et al [12] in Section III, which enables the connection to DSOS/SDSOS conditions for correlatively sparse polynomials in Section IV. In Section V, we extend our analysis to the cones of sparse DSOS/SDSOS/SSOS polynomial matrices. Section VI presents numerical results. Finally, Section VII concludes the paper.

A. SOS, DSOS, and SDSOS polynomials
Given a vector of variables x ∈ R n and a multi-index α ∈ N n , the quantity An n-variate polynomial of degree 2d can be written as p(x) = α∈N n 2d c α x α . We denote the set of polynomials in n variables with real coefficients of degree no more than 2d by R[x] n,2d , and the subset of nonnegative polynomials in R[x] n,2d by PSD n,2d .
Checking if p(x) ∈ PSD n,2d is NP-hard already for polynomials of degree 4, but it is computationally tractable to test membership to the following subsets of PSD n,2d .
(1) SOS polynomials: We denote the set of n-variate SOS polynomials of degree no larger than 2d by SOS n,2d . It is known [6] that p(x) ∈ SOS n,2d if and only if there exists a PSD matrix Q (denoted Q 0), such that where T is the vector of monomials of x of degree d or less. Following [6], we refer to (1) as the Gram matrix representation of the polynomial p(x). Note that the size of the Gram matrix Q is n+d d × n+d d in general.
(2) DSOS polynomials: Recall that a symmetric matrix A ∈ S r is diagonally dominant (DD) if A ii ≥ r j=1 |A ij | for all i = 1, . . . , r, and that DD matrices are positive semidefinite (this directly follows, for example, from Gershgorin's circle theorem). Following [15], we say that polynomial p(x) ∈ R[x] n,2d is a diagonally dominant sum-of-squares (DSOS) if it admits a Gram matrix representation (1) with a DD Gram matrix Q. We denote the set of DSOS polynomials in n variables and degree no larger than 2d by DSOS n,2d . (3) SDSOS polynomials: Recall that a symmetric matrix A ∈ S r is scaled diagonally dominant (SDD) if there exists a positive definite r ×r diagonal matrix D such that DAD is diagonally dominant. Following [15], we say that polynomial p(x) ∈ R[x] n,2d is a scaled diagonally dominant sum-ofsquares (SDSOS) if it admits a Gram matrix representation (1) with an SDD Gram matrix Q. We denote the set of SDSOS polynomials in n variables and degree no larger than 2d by SDSOS n,2d .
Let p 0 , . . . , p t ∈ R[x] n,2d be given polynomials. An SOS optimization problem takes the standard form where u ∈ R t is the decision variable. It is not difficult to see that (1) enables one to recast (2) as an SDP [6]. It has also been proved that if SOS n,2d is replaced with DSOS n,2d in (2) (resp. SDSOS n,2d ), then one obtains an LP (resp. SOCP) [15]. Thus, DSOS/SDSOS optimization are more scalable alternatives to SOS optimization, but are typically more conservative since the strict inclusion DSOS n,2d ⊂ SDSOS n,2d ⊂ SOS n,2d holds.

B. Chordal graphs and sparse matrices
The sparsity of a polynomial p(x) ∈ R[x] n,2d , or of any of its possible Gram matrices, can be conveniently represented by an undirected graph G(V, E), that is, a set of nodes V = {1, 2, . . . , n} and a set of edges E ⊆ V × V such that (i, j) ∈ E implies that (j, i) ∈ E also. For this reason, it is useful to review some essential notions about graphs and their relation to sparse matrices.
A cycle of length k of an undirected graph between nonconsecutive nodes of the cycle, and an undirected graph is called chordal if all its cycles with length ≥ 4 have a chord. Simple examples of chordal graphs are given in Fig. 1. Note that any nonchordal graph G(V, E) can always be extended to a chordal graph G(V,Ê) by adding edges to E [18]. Finally, a clique C ⊆ V is a subset of nodes where (i, j) ∈ E, ∀i, j ∈ C, i = j. If a clique C is not included in any other clique, then it is referred to as a maximal clique. For example, the graph in Fig. 1(c) has maximal cliques {1, 2, 3} and {2, 3, 4}, while that in Fig. 1(b) has maximal cliques {1, i+1}, i = 1, . . . , 4.
Given an undirected graph G(V, E), we consider the extended set of edges E * = E ∪ {(i, i), ∀i ∈ V} and define the space of n × n symmetric matrices with sparsity pattern characterized by G as Similarly the cone of sparse positive semidefinite (PSD) matrices with sparsity pattern described by G is For simplicity, we will slight abuse the terminology and say that S n (E, 0) has sparsity pattern E. Finally, for each maximal clique C k of G we define an index matrix E C k ∈ R |C k |×r as where |C k | denotes the number of nodes in C k , and C k (i) denotes the i-th node in C k , sorted in the natural ordering.
The following key result states that when the graph G is chordal, then X ∈ S r + (E, 0) if and only if it can be written as a sum of "inflated" PSD matrices.

C. Correlatively sparse polynomials
The notion of correlative sparsity was introduced by Waki et al. [12] to describe couplings between the variables x 1 , . . . , x n of a polynomial p(x) = |α|≤2d c α x α . Key to this description is the so-called correlative sparsity matrix For example, we have n,2d is said to have a correlative sparsity pattern characterized by an undirected graph G(V, E) if csp(p) ∈ S n (E, 0). It is then natural to define the vector space of polynomials with the same correlative sparsity as and its subset of sparse SOS polynomials as Throughout this paper, we assume that the correlative sparsity pattern E is chordal, or that a suitable chordal extension has been found.

III. REVISITING SPARSE SOS DECOMPOSITIONS
Suppose we wish to determine whether a correlatively sparse polynomial p(x) ∈ R[x] n,2d (E) is non-negative using an SOS certificate, meaning that we seek a Gram matrix representation of the form Using multi-indices β ∈ N n d and γ ∈ N n d to index the entries of Q, the equality constraints in (6) can be rewritten as It is clear that, even though p(x) is correlatively sparse, its Gram matrix Q need not be sparse: the only requirement is that β+γ=α Q β,γ = 0 if p(x) does not contain the monomial x α . Nonetheless, in order to exploit correlative sparsity and reduce the cost of searching for a suitable PSD Gram matrix, we insist that Q should be sparse by imposing that Q β,γ = 0 if the monomial x β+γ does not appears in any polynomial of R[x] n,2d (E). More precisely, we define Another method to exploit sparsity, proposed by Waki et al. [12], is to search for a sparse SOS (SSOS) decomposition: let C 1 , . . . , C t be the maximal cliques of G(V, E), let E C k be as in (5) for all k = 1, . . . , t, and try to find PSD matrices Q 1 , . . . , Q t such that In other words, one can try to write p as a sum of SOS polynomials , each of which depends only on the corresponding subset of variables E C k x. Our first main result is to show that these two strategies-imposing that Q is sparse according to (7) and looking for the SSOS decomposition (8)-are equivalent.
Proof: To prove the ⇒ part, we show that the Gram matrix Q has a chordal pattern when (7) holds, so the chordal decomposition (Theorem 1) can be applied to recover (8).
The ⇐ part will also follows from this. a) ⇒: If β and γ are such that an entry Q β,γ is not required to vanish due to (7), then (i, j) ∈ E for all i, j such that β i +γ i = 0 or β j +γ j = 0. Consequently, the set C β,γ = {i ∈ V | β i + γ i = 0} is a clique of the graph G(V, E) and is therefore contained in one of its maximal cliques C 1 , . . . , C t .

Fig. 2:
Graph patterns for polynomial (13): (a) the correlative sparsity pattern G(V, E) of (13) is a line graph; (b) the corresponding super-graph In other words, C β,γ ⊆ C k for some k ∈ {1, . . . , t}. Clearly, this also implies that Thus, if β and γ do not satisfy the condition in (7), then there exists a value k ∈ {1, . . . , t} such that At this stage, define a hyper-graph as edges. Since C 1 , . . . , C t are the maximal cliques of the chordal graph G(V, E), it can be shown [21] is also chordal, and that C d 1 , . . . , C d t are its maximal cliques. Moreover, given that condition (10) holds for some k ∈ {1, . . . , t} for each pair (β, γ) such that Q β,γ is not required to vanish by (7), the hyper-graph G d (V d , E d ) characterizes the sparsity pattern of the PSD matrix Q in (6) Thus, according to Theorem 1, Q in (6) can be decomposed as where (10), we then obtain from (6) that which is exactly (8) as claimed. b) ⇐: This follows after rearranging the last set of equalities in a suitable way.
Note that, in fact, we have shown that p(x) ∈ SSOS n,2d if and only if it admits a sparse Gram matrix Q ∈ S N + (E d , 0), so searching for an SSOS decomposition (8) amounts to imposing a sparsity constraint on the Gram matrix.
where csp(p) is a line graph with maximal cliques C 1 = {1, 2} and C 2 = {2, 3}, as shown in Fig. 2. The Gram matrix Q, which is unique in this case, is PSD and has a chordal sparsity pattern corresponding to the graph in Fig. 2(b), and according to Theorem 1 it can be written as Therefore, the 3-variate p(x) can be written as the sum of the two bi-variate SOS polynomials:

IV. RELATING SSOS TO SPARSE DSOS/SDSOS
We have seen that finding an SSOS decomposition of a correlatively sparse polynomial p ∈ R[x] n,2d (E) amounts to constraining the sparsity of its Gram matrix. This fact makes it possible to draw a connection between the space SSOS n,2d (E) of sparse SOS polynomials and those of sparse DSOS/SDSOS polynomials, defined as Specifically, we have the following result.
Proposition 1: For any sparsity pattern E and the first two inclusions are strict. The third inclusion is strict unless E is full or d = 1, in which cases SSOS n,2d (E) ≡ SOS n,2d (E). Proof: We only need to prove that SDSOS n,2d (E) ⊂ SSOS n,2d (E); the rest is true by definition, and the identity SSOS n,2 (E) ≡ SOS n,2 (E) holds because the Gram matrix representation of correlatively sparse quadratic polynomials is unique and must be sparse. Recall that any p ∈ SDSOS n,2d (E) can be represented by an SDD Gram matrix Q, not necessarily sparse. We then construct a sparse Gram matrixQ according tô It is not difficult to see that p(x) = v d (x)Qv d (x), and that Q is also SDD. Indeed, replacing any off-diagonal entries with zeros does not affect the scaled diagonal dominance of a matrix, while if a diagonal entry Q β,β is replaced by zero, then there exists (i, j) / ∈ E such that β i = 0 and β j = 0, and so the entire row Q β,• and column Q •,β are also replaced with zeros. Thus,Q satisfies the condition (7) and p(x) ∈ SSOS n,2d (E). Finally, the inclusion SDSOS n,2d (E) ⊂ SSOS n,2d (E) is strict because there exist SSOS polynomials whose Gram matrix is not SDD.
The implication of Proposition 1 is simple but important: SSOS n,2d (E) is a strictly better inner approximation of SOS n,2d (E), compared to the DSOS/SDSOS counterparts. Consequently, given correlatively sparse polynomials p 0 , . . . , p t ∈ R[x] n,2d (E) and an optimization variable u ∈ R t , the SOS optimization problem Specifically, if we denote the optimization problems arising in each of these cases by P ssos , P sdsos , and P dsos , and let f * ssos , f * sdsos , and f * dsos be their respective optimal values 1 , Proposition 1 implies that Additionally, it should be clear from Theorem 2 that the SSOS optimization problem P ssos can be recast as an SDP with multiple PSD matrix variables whose size is bounded by m+d d , where m is the size of the largest clique of the underlying correlative sparsity graph G(V, E). Therefore, even though problems P dsos and P sdsos can be solved as LPs and SOCPs [15], the added representation power offered by SSOS constraints need not add much computational cost when m ≪ n. Table I summarizes the problem types for SOS, SSOS, SDSOS, and SOS optimization. In fact, as will be demonstrated by the numerical examples in Section VI, SSOS optimization can be much faster than DSOS/SDSOS optimization provided by the package SPOTless [22]. Seen in this light, SSOS optimization bridges the gap between DSOS/SDSOS and SOS optimization for problems with correlatively sparse polynomials.

POLYNOMIALS
The results of the previous sections can be extended to sparse matrix-valued polynomials, which arise naturally in some applications [23], [24]. Let R[x] r×s n,2d be the space of r × s matrices whose entries are polynomials in R[x] n,2d , and S[x] r n,2d be the space of r × r symmetric polynomial matrices. A symmetric polynomial matrix P (x) ∈ S[x] r n,2d is PSD if P (x) 0, ∀ x ∈ R n , and it belongs to the space 1 For an infeasible problem, we denote the optimal cost value as infinity.  [10], [23], [25].
Clearly, SOS matrices are PSD, and it is well-known (see, e.g., [10], [23], [25]) that P (x) ∈ SOS r n,2d if and only if there exists a Gram matrix Q 0 such that where I r is the r × r identity matrix and ⊗ is the usual Kronecker product. Similarly to DSOS/SDSOS polynomials, we can define DSOS/SDSOS matrices as follows. Definition 1: A polynomial matrix P ∈ S[x] r n,2d is • DSOS, denoted P ∈ DSOS r n,2d , if it admits a Gram matrix representation (16) with a DD matrix Q. • SDSOS, denoted P ∈ SDSOS r n,2d , if it admits a Gram matrix representation (16) with an SDD matrix Q. An alternative characterization of SOS/DSOS/SDSOS matrices can be given as follows [10].
Proposition 2: A polynomial matrix P ∈ S[x] r n,2d is SOS (resp., DSOS or SDSOS) if and only if, given y ∈ R r , the polynomial y T P (x)y is SOS (resp. DSOS or SDSOS) in [x; y] ∈ R m+n .
Proof: Using (16), where z(x, y) = y ⊗ v d (x) is a subset of the vector of monomials in x and y. Therefore, P (x) ∈ SSOS r n,2d (resp. P (x) ∈ DSOS r n,2d and P (x) ∈ SDSOS r n,2d ) if and only if Q is PSD (resp., DD and SDD).

A. Sparse SOS, SDSOS, and DSOS matrices
Similar to the spaces of sparse matrices mentioned in Section II, we can define the space of sparse symmetric polynomial matrices whose sparsity pattern is characterized by an undirected graph G(V, E) as We can also introduce the subspaces of sparse SOS/SDSOS/DSOS matrices, The Gram matrix representation (16) of a sparse SOS matrix P ∈ SOS r n,2d (E) can be rewritten as where the (i, j)-th block Q ij ∈ S N of the Gram matrix is to be chosen such that Q 0 and Note that Q ij need not be a zero matrix to satisfy (18), so the Gram matrix Q for a sparse SOS matrix is dense in general and checking that P ∈ SOS r n,2d (E) can be computationally expensive. For this reason, in [26] the authors proposed to impose sparsity in the Gram matrix Q and test if P belongs to the space of polynomial matrices that admit a sparse SOS decomposition, defined as The following proposition shows that this space is larger than both DSOS r n,2d (E) and SDSOS r n,2d (E), and is the matrix-valued analogue of Proposition 1.
Proposition 3: For any pattern E, we have (20) and the first two inclusions are strict. The third inclusion is strict unless E is full in which SSOS r n,2d (E) ≡ SOS r n,2d (E). Proof: We only need to prove that SDSOS r n,2d (E, 0) ⊂ SSOS r n,2d (E, 0), since the other inclusions follow directly from the definition of each space. To this end, note that any P ∈ SDSOS r n,2d (E) admits a Gram matrix representation (16) with an SDD matrix Q. Then, consider the matrix obtained by setting to zero blocks of Q corresponding to zero entries of P . The matrixQ is still SDD, and hence PSD, and satisfies Hence, P (x) ∈ SSOS r n,2d (E) and (21) is true; the inclusion is strict because there clearly exist polynomial matrices in SSOS n,2d (E) whose Gram matrix is not SDD. Finally, the identity SSOS r n,2d (E) ≡ SOS r n,2d (E) holds obviously when E contains all edges.
As in the scalar case, sparse matrix SOS certificates are expected to be less conservative than their DSOS/SDSOS counterparts. Additionally, if the sparsity pattern of a sparse polynomial matrix is chordal, then working with SSOS n,2d (E) can be computationally efficient because-similar to the SSOS decomposition for scalar polynomials-it requires solving SDPs with small PSD cones. This follows from the next theorem, originally proven in [26], which extends Theorem 1 to sparse polynomial matrices.
Theorem 3 ( [26]): Let G(V, E) be a chordal graph with maximal cliques {C 1 , C 2 , . . . , C t }. Then, with P k ∈ SOS |C k | n,2d for each k = 1, . . . , t. Proof: A detailed proof can be found in [26]. Briefly, the "if" part is obvious, while the "only if" part relies on the fact that, when G(V, E) is chordal, the sparse Gram matrix Q of P has a chordal sparsity pattern also, and can be decomposed using Theorem 1 to obtain (22).
Consequently, one can use the cones DSOS r n,2d (E), SDSOS r n,2d (E), and SSOS r n,2d (E) to formulate increasingly better and computationally tractable approximations of largescale matrix-valued SOS optimization problems of the form where P 0 , . . . , P t ∈ S r n,2d (E, 0) are given sparse symmetric polynomial matrices and u ∈ R t is the decision variable. All comments given at the end of Section IV on the relation between scalar SSOS/SDSOS/DSOS optimization are also valid for matrix-valued problems.

B. Reduction to the scalar analysis
Proposition 2 states that a matrix-valued polynomial P (x) is SOS (resp., DSOS or SDSOS) if the associated scalar polynomial p(x, y) = y T P (x)y is so, and it is natural to ask if the same is true for the SSOS condition. Here show that applying Theorem 3 to P ∈ SSOS r n,2d (E) is indeed equivalent to applying Theorem 2 to p(x, y), but only if any correlative sparsity with respect to the variable x is ignored.
Indeed, p(x, y) has correlative sparsity pattern E with respect to y since the monomial y i y j appears if and only if P ij (x) = 0, meaning that (i, j) ∈ E. It is then not difficult to verify that, if any correlative sparsity with respect to the variable x is ignored, Theorem 2 guarantees that p(x, y) can be decomposed as for some SOS polynomials p k , k = 1, . . . , t. In particular, each p k is quadratic in y and has degree d in x, so it admits the Gram matrix representation with Q k 0. But then, upon defining and using the properties of the Kronecker product to rewrite Since p(x, y) = y T P (x)y we conclude that which is exactly the statement of Theorem 3. The argument can easily be reversed to show that Theorem 3 implies the existence of an SSOS decomposition of p(x, y). Remark 1: It is important to note that the equivalence outlined above holds only when any correlative sparsity of the entries of the polynomial matrix P with respect to x is disregarded, because we do not take it into account in our analysis of polynomial matrices. However, it may be possible to exploit correlative sparsity in x when applying Theorem 2 to y T P (x)y. In this case, working at the scalar level will not be equivalent to applying Theorem 3 to P directly, and will instead result in a stronger (but possibly computationally cheaper) constraint. Therefore, our results for matrix-valued polynomials remain of independent interest.

VI. NUMERICAL EXAMPLES
To demonstrate that DSOS/SDSOS constraints are indeed more conservative than sparse SOS conditions in practice, we report the results of numerical experiments on sparse versions of the examples considered in [15]. We implemented sparse SOS conditions in YALMIP [27], adapting the undocumented option sos.csp to exploit correlative sparsity using the chordal extension methods described in [12]. For the DSOS/SDSOS constraints, instead, we used SPOTless [22]. The solver MOSEK [28] was used to solve the LPs, SOCPs, and SDPs arising, respectively, from DSOS, SDSOS and SSOS constraints. All computations were carried out on a PC with a 2.8 GHz Intel Core i7 CPU and 8GB of RAM.

A. Lower bounds on scalar polynomials
Given the Broyden tridiagonal polynomial  consider the best lower bound problem Upon replacing the non-negativity constraint with an SOS/SSOS/SDSOS/DSOS conditions, this problem can be reformulated as an SDP/SDP/SOCP/LP, respectively. The optimal γ obtained in each case for different values of n is reported in Table II, and MOSEK's runtime is reported in Table III. For all values of n the cone of DSOS polynomials is too restrictive and the DSOS constraint is infeasible. Moreover, as expected from Proposition 1, the SDSOS condition is more conservative that the SSOS one 2 . For this example, SSOS conditions appear not to introduce any conservativeness: they yield the same optimal value as the classical SOS relaxation, and at a fraction of the computational cost. Interestingly, solving the SSOS conditions was also faster than solving SDSOS conditions. This is likely due to the fact that the SSOS condition translates to an SDP with n − 1 PSD matrix variables of size 6 × 6 for this particular problem (27), while, the number of second-order cones required for an SDSOS constraint is O(n 2 ). Whether sparsity can be exploited in SPOTless to formulate a smaller SOCP for sparse SDSOS constraints remains an interesting open question for future work.

B. Eigenvalue bounds on matrix polynomials
Let G(V, E) be the 5-node star graph of Fig. 1(b), and let P ∈ S r×r 2,2 (E, 0) be a sparse polynomial matrix whose entries are randomly generated quadratic polynomials in 2 variables. The best lower bound on the smallest eigenvalue of P (x) valid for all x ∈ R 5 is given by the solution of the optimization problem min γ γ subject to P (x) + γI 0 ∀x ∈ R 5 .  We solved this problem for P (x) of increasing size r after replacing the PSD constraint with SOS, SSOS, DSOS and SDSOS conditions. The optimal γ for each case is reported in Table IV, while the CPU time is shown in Table V. As in the previous example, SSOS conditions exhibit the best trade-off between conservativeness and computational cost.

C. Co-positive programming
Our next experiment is an optimization problem over the cone CP n of co-positive n × n matrices, which has recently attracted attention since it can model several combinatorial optimization problems exactly [29]. A symmetric matrix Z ∈ S n is co-positive if y T Zy ≥ 0 for all y ≥ 0, or [6] Z ∈ CP n ⇔ n i,j=1 Replacing the non-negativity constraint with SOS, SSOS, SDSOS and DSOS conditions yields tractable inner approximations of CP n . Here, we solve such approximations for l blocks e e h h Fig. 3: Block-arrow sparsity pattern (dots indicate repeating diagonal blocks). The parameters are: the number of blocks, l; block size, e; the width of the arrow head, h.  optimization problems of the form where Z is a randomly generated symmetric matrix with a block-arrow sparsity pattern with l blocks of size e × e, and arrow head h; see Fig. 3 for an illustration. Such a sparsity pattern is chordal, with l maximal cliques of size e + h.
We fixed the block size e = 3, arrow head size h = 2, and varied the number of blocks l. Table VI shows that the upper bound on the optimal solution of (29) obtained with SSOS constraints is always strictly better than that obtained with SDSOS and DSOS optimization, and gives the same result as the classical SOS relaxation in all cases for which this could be implemented. Again, SSOS constraints are also extremely competitive in terms of CPU time, cf. Table VII.

D. Lyapunov stability analysis
As our final example, we considered randomly generated n-dimensional, degree-3 polynomial dynamical systems of the form           ẋ with a linearly stable equilibrium at the origin. We then searched for quadratic Lyapunov functions of the form that certify the nonlinear local stability of the origin for a subset of initial conditions in the box D = [−0.1, 0.1] n . Specifically, we looked for V (x) that satisfies (where we used ǫ = 10 −6 in the simulation) after replacing the non-negativity conditions with SOS, SSOS, SDSOS, and DSOS constraints in turn.  VII. CONCLUSION In this paper we have demonstrated that, for correlatively sparse polynomials, sparse SOS positivity certificates are more general and typically less conservative than those based on DSOS and SDSOS methods. Key to this result is a new interpretation of the sparse SOS conditions proposed by Waki et al. [12] in terms of a sparsity constraint of the Gram matrix Q used to represent sparse SOS polynomials, to which a well known chordal decomposition theorem can be applied. Numerical examples have confirmed our theoretical findings, and also demonstrated that SSOS conditions can be dramatically more efficient than the DSOS/SDSOS conditions formulated by the dedicated package SPOTless. Thus, although DSOS/SDSOS methods remain one of the few methods to implement non-negativity constraints for dense polynomials with many variables and/or high degree, one should try to utilize SSOS constraints when possible.
In the particular context of systems analysis, our findings motivate the development of robust methods that exploit sparsity in the system's governing equations and result in sparse polynomial non-negativity conditions. In Section VI-D, we have done this by choosing a Lyapunov function with a structure such that the correlative sparsity of the governing equations is inherited by the eventual non-negativity constraints, but this construction was made possible by the simplicity of our example. Identifying a general procedure to formulate sparse SOS conditions will therefore be essential to enable the analysis of complex, large-scale sparse systems.