Disjunctive Sum of Squares
Amir Ali Ahmadi, Sanjeeb Dash, Yixuan Hua, Bartolomeo Stellato · 2026
Read Disjunctive Sum of Squares by Amir Ali Ahmadi, Sanjeeb Dash, Yixuan Hua, Bartolomeo Stellato (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-28674.txt.
Introduction
Amir Ali Ahmadi, Sanjeeb Dash, Yixuan Hua, and Bartolomeo Stellato present disjunctive sum of squares, a way to certify that polynomials never go negative. Unlike the standard sum-of-squares approach, which uses one algebraic identity, the disjunctive approach uses several identities that can be found in parallel. Their main result, a disjunctive Positivstellensatz, keeps each identity's degree as low as the polynomial's degree. From it they build a hierarchy of lower bounds for shrinking a polynomial over a compact basic semialgebraic set, with the largest semidefinite constraint fixed throughout.
Catalog record
| CREATOR | Amir Ali Ahmadi, Sanjeeb Dash, Yixuan Hua, Bartolomeo Stellato |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 108762 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.28674
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Disjunctive Sum of Squares Amir Ali Ahmadi, Sanjeeb Dash, Yixuan Hua, Bartolomeo Stellato Abstract We introduce the concept of disjunctive sum of squares for certifying nonnegativity of polynomials. Unlike the popular sum of squares approach where nonnegativity is certified by a single algebraic identity, the disjunctive sum of squares approach certifies nonnegativity with multiple algebraic identities which can be found in parallel. Our main result is a disjunctive Positivstellensatz proving that we can keep the degree of each algebraic identity as low as the degree of the polynomial whose nonnegativity is in question. Based on this result, we construct a semidefinite programming based converging hierarchy of lower bounds for the problem of minimizing a polynomial over a compact basic semialgebraic set, where the size of the largest semidefinite constraint is fixed throughout the hierarchy. We further prove a second disjunctive Positivstellensatz which leads to an optimization-free hierarchy for polynomial optimization. We specialize this result to the problem of proving copositivity of matrices. Finally, we describe how the disjunctive sum of squares approach can be combined with a branch-and-bound algorithm and we present numerical experiments on polynomial, copositive, and combinatorial optimization problems. 1 Introduction A polynomial p:\mathbb{R}^{n}\rightarrow\mathbb{R} is said to be nonnegative if p(x)\geq 0 for all x\in\mathbb{R}^{n} . The problem of optimizing over the intersection of the cone of nonnegative polynomials of a given degree with an affine subspace is fundamental to optimization and algebraic geometry, with broad applications in polynomial optimization [ 28 ] , control systems and robotics [ 23 , 51 ] , probability theory [ 6 ] , and statistics [ 15 ] , to name a few; see the textbooks [ 29 , 8 , 30 ] , or survey papers [ 31 , 22 ] for many other applications and further context. A polynomial p:\mathbb{R}^{n}\rightarrow\mathbb{R} is said to be a sum of squares (sos) if it can be expressed as p(x)=\sum_{i}q_{i}^{2}(x) for some polynomials q_{i}:\mathbb{R}^{n}\rightarrow\mathbb{R} . A sum of squares decomposition of a polynomial provides a single algebraic identity that certifies its nonnegativity. Moreover, as is well known by now, such a decomposition (assuming it exists) can be obtained by solving a semidefinite program (SDP) [ 40 , 28 , 41 ] . Throughout the paper, we denote the set of nonnegative polynomials and sos polynomials in n variables and degree at most d by P_{n,d} and \mathbf{\Sigma}_{n,d} , respectively. It has been known since the seminal work of Hilbert [ 25 ] that not every nonnegative polynomial is a sum of squares. In fact, Hilbert established that P_{n,d} and \mathbf{\Sigma}_{n,d} coincide only in three specific cases: when n=1 , d=2 , or (n,d)=(2,4) . The first example of a nonnegative polynomial which is not sos was constructed by Motzkin many years later [ 37 ] : M(x_{1},x_{2})=x_{1}^{4}x_{2}^{2}+x_{1}^{2}x_{2}^{4}-3x_{1}^{2}x_{2}^{2}+1. (1) Despite the existence of such examples, it turns out that a proof of nonnegativity based on a single algebraic identity is always possible though at the expense of increasing the degree of the sos polynomials that appear in the identity. More specifically, it follows from Artin’s solution to Hilbert’s 17th problem [ 4 ] that for every nonnegative polynomial p , there exists a nonzero sos polynomial q , such that the product pq is sos (and hence nonnegativity of p is algebraically certified by a representation as a ratio of two sos polynomials). For example, for the Motzkin polynomial, we have the following degree-8 identity: (x_{1}^{2}+x_{2}^{2})M(x_{1},x_{2})=x_{1}^{2}(1-x_{2}^{2})^{2}+x_{2}^{2}(1-x_{1}^{2})^{2}+x_{1}^{2}x_{2}^{2}(x_{1}^{2}+x_{2}^{2}-2)^{2}. (2) By utilizing Artin’s theorem, one can design a complete SDP-based hierarchy for proving nonnegativity of a polynomial p . In level j of this hierarchy, one searches for a nonzero sos polynomial q of degree 2j that makes the product pq also sos. 1 1 1 Unlike the approach we later propose in this paper, one cannot use this SDP hierarchy to impose a nonnegativity constraint on a polynomial p . This is because of the bilinear matrix inequality that arises from the sos constraint on the product of the two unknown polynomials p and q . However, the degree of the polynomial pq can be much higher than the degree of p (see, e.g., [ 7 ] ) and is upper bounded currently only by a tower of five exponentials in the number of variables and degree of p [ 34 ] . Since the size of the SDP underlying an sos constraint grows rapidly with the degree of the sos polynomial, the SDP hierarchy based on Artin’s theorem can quickly become impractical in certain applications. This challenge also arises in the context of other sum of squares based SDP hierarchies (e.g., in [ 40 , 28 , 41 ] ) which rely on related seminal theorems of algebraic geometry such as the Positivstellensätze of Stengle [ 49 ] , Schmüdgen [ 47 ] , or Putinar [ 42 ] . With this context in mind, the central question that motivates our research is the following: “Can one lower the complexity of a sum of squares based proof of polynomial nonnegativity by constructing several algebraic identities instead of a single one?” Our primary notion of complexity here is the degree of the sos polynomials that appear in the proof of nonnegativity. However, our results also simplify the structure of these sos polynomials making the search for them amenable to cheaper classes of conic programs, such as linear programs. As an example, consider the following proof of nonnegativity of the Motzkin polynomial using two degree-6 algebraic identities: \displaystyle M(x_{1},x_{2}) \displaystyle=(1-x_{1}x_{2})^{2}+(x_{1}^{2}x_{2}-x_{1}x_{2}^{2})^{2}+2x_{1}x_{2}(1-x_{1}x_{2})^{2} (3) \displaystyle=(1+x_{1}x_{2})^{2}+(x_{1}^{2}x_{2}+x_{1}x_{2}^{2})^{2}-2x_{1}x_{2}(1+x_{1}x_{2})^{2}. Indeed, for every point (x_{1},x_{2})\in\mathbb{R}^{2} , either x_{1}x_{2}\geq 0 or x_{1}x_{2}<0 . When x_{1}x_{2}\geq 0 , nonnegativity of M(x_{1},x_{2}) follows from the first identity. Similarly, when x_{1}x_{2}<0 or equivalently -x_{1}x_{2}>0 , nonnegativity of M(x_{1},x_{2}) follows from the second identity. We call a proof of this type a disjunctive sum of squares proof of nonnegativity. Comparing the two algebraic proofs in ( 2 ) and ( 3 ), we see that the former involves an sos polynomial of degree 8 while the latter involves two sos polynomials of degree 6, which is the same as the degree of the Motzkin polynomial. From a computational standpoint, this means that the size of the semidefinite constraint underlying the second proof is smaller. 2 2 2 We recall that, imposing an sos constraint on a polynomial in n variables and degree 2d results in a positive semidefinite constraint on a matrix of size {{n+d}\choose{d}}\times{{n+d}\choose{d}} (see, e.g., [ 40 , 41 ] ). Moreover, the sos polynomials appearing in ( 3 ) have a special structure (known as “diagonal dominance”; see [ 3 ] ), that enables the search for this particular disjunctive sum of squares proof to be carried out by solving a linear program. This is, in general, much cheaper than solving a semidefinite program. Our main contribution in this paper is to formalize the concept of disjunctive sum of squares proofs of nonnegativity and show that low-degree proofs of this type always exist under standard assumptions. We outline our contributions in some more detail next. 1.1 Organization and Main Contributions The remainder of this paper is organized as follows. In Section 2 , we define the notion of a disjunctive sum of squares proof of nonnegativity of