Optimization over the Boolean Hypercube via Sums of Nonnegative Circuit Polynomials
Mareike Dressler Adam Kurpisz Timo de Wolff



Various key problems from theoretical computer science can be expressed as polynomial optimization problems over the boolean hypercube.
One particularly successful way to prove complexity bounds for these types of problems are based on sums of squares (SOS) as nonnegativity certificates. In this article, we initiate the analysis of optimization problems over the boolean hypercube via a recent, alternative certificate called sums of nonnegative circuit polynomials (SONC). We show that key results for SOS based certificates remain valid: First, for polynomials, which are nonnegative over the n-variate boolean hypercube with constraints of degree d there exists a SONC certificate of degree at most n+d. Second, if there exists a degree d SONC certificate for nonnegativity of a polynomial over the boolean hypercube, then there also exists a short degree d SONC certificate, that includes at most n^O(d) nonnegative circuit polynomials.

 
 
Space-Efficient Bimachine Construction Based on the Equalizer Accumulation Principle
    Stefan Gerdjikov1,2 Stoyan Mihov2 Klaus U. Schulz3
    
====================================================================================





§ INTRODUCTION


An optimization problem over a boolean hypercube is an n-variate (constrained) polynomial optimization problem where the feasibility set is restricted to the vertices of an n-dimensional hypercube

    min f(𝐱), 
        subject to    p_1(𝐱),…,p_m(𝐱) ≥ 0, 
          𝐱∈{a_i,b_i}^n, 
           f,p_1,…,p_m ∈[𝐱].


The formulation (<ref>) captures a class of optimization problems, that belong to the core of theoretical computer science. However, it is known that solving the above formulation is NP-hard in general, since one can easily cast, e.g., the Independent Set problem in this framework.

One of the most promising approaches in constructing efficient algorithms is the sum of squares (SOS) hierarchy <cit.>, also known as Lasserre relaxation <cit.>. The method is based on a Positivstellensatz result <cit.> saying that the polynomial f, which is nonnegative over the feasibility set given in (<ref>), can be expressed as a sum of squares times the constraints defining the set. Bounding a maximum degree of a polynomial used in a representation of f provides a family of algorithms parametrized by an integer d. Finding a degree d SOS certificate for nonnegativity of f can be performed by solving a semidefinite programming (SDP) formulation of size n^O(d). Finally, for every (feasible) n-variate unconstrained hypercube optimization problem there exists a degree 2n SOS certificate.

On the one hand, the SOS algorithm provide the best available approximation algorithms for
a wide variety of optimization problems.
For example, the degree 2 SOS for the Independent Set problem implies the Lovász θ-function <cit.> and gives the Goemans-Williamson relaxation <cit.> for the Max Cut problem. The ARV algorithm of the Sparsest Cut <cit.> problem can be captured by SOS of degree 6. Finally, the subexponential time algorithm for Unique Games <cit.> is implied by a SOS of sublinear degree <cit.>. More recently, it has been shown that O(1) degree SOS is equivalent in power to any polynomial size SDP extended formulation in approximating maximum constraint satisfaction problems <cit.>.

Other applications of the SOS method for combinatorial optimization can be found in <cit.>. For a more detailed overview on the use of SOS in approximation algorithms, see the surveys <cit.>.

On the other hand, it is known that the SOS algorithm admits certain weaknesses.  First, for some hypercube optimization problems the SOS algorithm performs much worse than other known methods. Grigoriev in <cit.> shows that a Ω(n) degree SOS certificate is needed to detect that the Knapsack instance {x∈ [0,1]^n : ∑_i=1^n x_i= ⌊ n/2 ⌋+1/2} contains no integer point. Simpler proofs can be found in <cit.>. Other SOS degree lower bounds for Knapsack problems appeared in <cit.>.
Another example is the problem of scheduling unit size jobs on a single machine to minimize the number of late jobs. The problem is solvable in polynomial time using the Moore-Hodgson algorithm; an Ω(√(n)) degree SOS algorithm, however, still attains an unbounded integrality gap <cit.>.

For other important SOS limitations see e.g. <cit.>.

Second, it remains open if finding a degree d SOS certificate can be performed in time n^O(d). Indeed, as noted in the recent paper by O'Donnell <cit.> and further discussed by Raghavendra and Weitz in <cit.> it is not obviously true that the search can be done so efficiently.

Namely, even if a small degree SOS certificate exists, the polynomials in the certificate do not have necessarily small coefficients.

O'Donnell in <cit.> gives an example of a polynomial optimization problem that admits a degree 2 SOS certificate, but every degree 2 SOS certificate for this problem has exponential bit complexity. Moreover, in <cit.> the example is modified and cast into a hypercube optimization problem again having a degree 2 SOS certificate, which, however, has super-polynomial bit complexity for certificates up to the degree O(√(n)).

For small d, this excludes the possibility that known optimization tools used for solving SDP problems like the ellipsoid method <cit.> are able to find a degree d certificates in time n^O(d) for optimization problems of the form (<ref>).



The above arguments motivate the search of new methods for solving hypercube optimization problems efficiently.


In this article, we initiate an analysis of hypercube optimization problems of the form (<ref>) via sums of nonnegative circuit polynomials (SONC). SONCs are a nonnegativity certificate introduced recently by Iliman and the third author <cit.>, which are independent of sums of squares; see Definition <ref> and Theorem <ref> for further details. Similarly as Lasserre relaxation for SOS, a Schmüdgen-like Positivstellensatz yields a converging hierarchy of lower bounds for polynomial optimization problems with compact constraint set; see <cit.> and Theorem <ref>. These bounds can be computed via a convex optimization program called relative entropy programming (REP) <cit.>.
Our main question in this article is:

 Can SONC certificates be an alternative for SOS methods for optimization problems over the hypercube?

We answer this question affirmatively in the sense that we prove SONC complexity bounds for (<ref>) analogous to the SOS bounds mentioned above. More specifically, we show:

 
  * For every polynomial which is nonnegative over an n-variate hypercube with constraints of degree at most d there exists a SONC certificate of nonnegativity of degree at most n+d; see Theorem <ref> and Corollary <ref>.
 
  * If a polynomial f admits a degree d SONC certificate of nonnegativity over an n-variate hypercube, then the polynomial f admits also a short degree d SONC certificate that includes at most n^O(d) nonnegative circuit polynomials; see Theorem <ref>.
  


For a discussion and remaining open problems, to turn these results into an efficient algorithms, see Section <ref> and the end of Section <ref>. 



Furthermore, we show some structural properties of SONCs:


	
  * We give a simple, constructive example showing that the SONC cone is not closed under multiplication. Subsequently we use this construction to show that the SONC cone is neither closed under taking affine transformations of variables, see Lemma <ref> and Corollary <ref>.
	
  * We address an open problem raised in <cit.> asking whether the Schmüdgen-like Positivstellensatz for SONCs (Theorem <ref>) can be improved to an equivalent of Putinar's Positivstellensatz <cit.>. We answer this question negatively by showing an explicit hypercube optimization example, which provably does not admit a Putinar representation for SONCs; see Theorem <ref> and the discussion afterwards.










Our article is organized as follows: In Section <ref> we introduce the necessary background about SONCs. In Section <ref> we show that the SONC cone is closed neither under multiplication nor under affine transformations. In Section <ref> we provide our two main results regarding the degree bounds for SONC certificates over the hypercube. In Section <ref> we prove the non-existence of an equivalent of Putinar's Positivstellensatz for SONCs and discuss this result.




 §.§ Acknowledgements

AK was supported by the Swiss National Science Foundation project PZ00P2_174117
“Theory and Applications of Linear and Semidefinite Relaxations for Combinatorial Optimization Problems”.
TdW was supported by the DFG  grant WO 2206/1-1. This article was finalized while TdW was hosted by the Institut Mittag-Leffler. We thank the institute for its hospitality.



§ PRELIMINARIES



In this section we collect basic notions and statements on sums of nonnegative circuit polynomials (SONC).


Throughout the paper, we use bold letters for vectors, e.g., 𝐱=(x_1,…,x_n) ∈^n. Let ^* = ∖{0} and _≥ 0 (_> 0) be the set of nonnegative (positive) real numbers. Furthermore let [𝐱] = [x_1,…,x_n] be the ring of real n-variate polynomials and the set of all n-variate polynomials of degree less than or equal to 2d is denoted by [𝐱]_n,2d. We denote by [n] the set {1,…,n} and the sum of binomial coefficients ∑_k=0^d nk is abbreviated by n≤ d. 

Let 𝐞_1,…,𝐞_𝐧 denote the canonical basis vectors in ^n. 













 §.§ Sums of Nonnegative Circuit Polynomials


Let A⊂^n be a finite set.

In what follows, we consider polynomials f ∈[𝐱] supported on A. Thus, f is of the form f(𝐱) = ∑_∈ A^ f_𝐱^ with f_∈ and 𝐱^ = x_1^_1⋯ x_n^_n. A lattice point is called even if it is in (2)^n and a term f_𝐱^ is called a monomial square if f_ > 0 and  even. We denote by (f) = {∈^n : f_≠ 0} the Newton polytope of f. 


Initially, we introduce the foundation of SONC polynomials, namely circuit polynomials; see also <cit.>:


	A polynomial f ∈[𝐱] 

	is called a circuit polynomial if it is of the form
	
    f(𝐱)    :=    ∑_j=0^r f_(j)𝐱^(j) + f_β𝐱^β,

	with r≤ n, exponents (j), β∈ A, and coefficients f_(j)∈_> 0, f_β∈, such that the following conditions hold:
	
	
		
  (C1) (f) is a simplex with even vertices (0), (1),…,(r).
		
  (C2) 
		The exponent β is in the strict interior of (f). Hence, there exist unique barycentric coordinates λ_j relative to the vertices (j) with j=0,…,r satisfying
		
    β =  ∑_j=0^r λ_j (j)   with  λ_j  >  0   and  ∑_j=0^r λ_j  =  1.


	
	We call the terms f_(0)𝐱^(0),…,f_(r)𝐱^(r) the outer terms and f_β𝐱^β the inner term of f. 
	
	For every circuit polynomial we define the corresponding circuit number as
	
    Θ_f :=  ∏_j = 0^r (f_(j)/λ_j)^λ_j.

	
	



The first fundamental statement about circuit polynomials is that its nonnegativity is determined by its circuit number Θ_f and f_β entirely:


	Let f  be a  circuit polynomial with inner term f_β𝐱^β and let Θ_f be the corresponding circuit number, as defined in (<ref>). Then the following statements are equivalent:
	
		
  * f is nonnegative.
		
  * |f_β| ≤Θ_f and β∉(2)^n   or   f_β≥ -Θ_f and β∈ (2)^n.
	
	




Therefore, expressing a polynomial as a sum of nonnegative circuit polynomials (SONC) is a certificate for the polynomials nonnegativity. 



	We define for every n,d ∈^* the set of sums of nonnegative circuit polynomials (SONC) in n variables of degree 2d as
	
    C_n,2d :=  {f ∈[𝐱]_n,2d :  f = ∑_i=1^k μ_i p_i, [ p_i  is a nonnegative circuit polynomial,;                            μ_i ≥ 0, k ∈^*;                                           ]}

	
	

We denote by SONC both the set of SONC polynomials and the property of a polynomial to be a sum of nonnegative circuit polynomials.

In what follows let P_n,2d be the cone of nonnegative  n-variate polynomials of degree at most 2d and _n,2d be the corresponding cone of sums of squares respectively. 
An important observation is, that SONC polynomials form a convex cone independent of the SOS cone:


	C_n,2d is a convex cone satisfying:
	
		
  * C_n,2d⊆ P_n,2d for all n,d ∈^*,
		
  * C_n,2d⊆Σ_n,2d if and only if (n,2d)∈{(1,2d),(n,2),(2,4)},
		
  * Σ_n,2d⊈C_n,2d for all (n,2d) with 2d ≥ 6.
	
	


For further details about the SONC cone see <cit.>.
 


 §.§ SONC Certificates over a Constrained Set

In <cit.>, Iliman, the first, and the third author showed that for an arbitrary real polynomial which is strictly positive on a compact, basic closed semialgebraic set K there exists a SONC certificate of nonnegativity. Hereinafter we recall this result.



We assume that K is given by polynomial inequalities g_i(𝐱)≥ 0 for i = 1,…,s and is compact. For technical reason we add 2n redundant box constraints l_j(𝐱) := N± x_j≥ 0 for some sufficiently large N ∈, which always exists due to our assumption of compactness of K; see <cit.> for further details. Hence, we have


    K := {𝐱∈^n: g_i(𝐱)≥ 0  for  i∈ [s]  and  l_j(𝐱)≥ 0  for  j∈ [2n]}.


In what follows we consider polynomials H^(q)(𝐱) defined as products of at most q ∈^* of the polynomials g_i,l_j and 1, i.e.,

    H^(q)(𝐱) :=  ∏_k=1^q h_k(𝐱),

where h_k∈{1,g_1,…,g_s,l_1,…,l_2n}. 
Now we can state:

Let f,g_1,…,g_s∈[𝐱] be real polynomials and K be a compact, basic closed semialgebraic set as in (<ref>). If f > 0 on K then there exist d,q ∈^* such that we have an explicit representation of f of the following form:

    f(𝐱)  =  ∑_ finite  s(𝐱)H^(q)(𝐱),

where the s(𝐱) are contained in C_n,2d and every H^(q)(𝐱) is a product as in (<ref>).



The central object of interest is the smallest value of d and q that allows f a decomposition as in Theorem <ref>. This motivates the following definition of a degree d SONC certificate.




	
	Let f ∈[𝐱] such that f is positive on the set K given in (<ref>). Then f has a degree d SONC certificate if it admits for some q ∈^* the following decomposition: 
	
    f(𝐱)  =  ∑_ finite  s(𝐱)H^(q)(𝐱),

	where the s(𝐱) are SONCs, the H^(q)(𝐱) are products as in (<ref>), and 
	
    (∑_ finite  s(𝐱)H^(q)(𝐱))  ≤ d.

	



 §.§ The Complexity of Finding a Degree d SONC Certificate


One can decide nonnegativity for a single given circuit polynomial by solving a system of linear equations. This is due to Theorem <ref> and the fact that the _j are unique (and thus trivially nonnegative), since the (j) are affinely independent by construction.

For finding a degree d SONC certificate, there are two main bottlenecks that might effect its complexity. The first one is to guarantee the existence of a sufficiently short degree d SONC certificate. If the first bottleneck is resolved, then a second one might occur: even if the existence of a short degree d SONC certificate is guaranteed, then it is not clear a priori, whether one can search through the space of n-variate circuit polynomials of degree at most d efficiently, in order to find such a short certificate.





Regarding the first bottleneck, given the fact that a polynomial f admits a degree d SONC certificate, it is open whether there also exists a degree d certificate which consists of a bounded (ideally n^O(d)) number of components. 

The answer to the equivalent question for the SOS degree d certificates follows from the fact that a polynomial is SOS if and only if the corresponding matrix of coefficients of size n^O(d), called the Gram matrix, is positive semidefinite. Since every real, symmetric matrix M that is positive semidefinite admits a decomposition M=VV^⊤, this yields an explicit SOS certificate including at most n^O(d) polynomials squared. For more details we refer the reader to the excellent lecture notes in <cit.>.  

In this paper we resolve the first bottleneck regarding the existence of short SONC certificates affirmatively. Namely, we show that one can always restrict oneself to SONC certificates including at most n^O(d) nonnegative circuit polynomials, see Section <ref> for further details.




§ PROPERTIES OF THE SONC CONE



In this section we show that the SONC cone is neither closed under multiplication nor under affine transformations. First, we give a constructive proof for the fact that the SONC cone is not closed under multiplication, which is simpler than the initial proof of this fact in <cit.>. Second, we use our construction to show that the SONC cone is not closed under affine transformation of variables.





	
For every d ≥ 2, n ∈ℕ^* the SONC cone C_n,d is not closed under multiplication in the following sense: if p_1,p_2 ∈ C_n,d, then p_1 · p_2 ∉C_n,2d in general.	



	For every d=2n, n ∈ℕ^* we construct two SONC polynomials p_1, p_2 ∈ C_n,d such that the product p_1 p_2 is an n variate, degree 2d polynomial that is not inside C_n,2d.
	
	Let n = 2. We construct the following two polynomials p_1, p_2 ∈ℝ[x_1,x_2]:
	
    p_1(x_1,x_2) := (1-x_1)^2,     p_2(x_1,x_2) := (1-x_2)^2.

	First, observe that p_1, p_2 are nonnegative circuit polynomials, since, in both cases, λ_1=λ_2=1/2, f_(1)=f_(2)=1, and f_β=-2, thus 2=Θ_f ≥ |f_β|.
	
	Now consider the polynomial r(x_1,x_2)= p_1 p_2 = ( (1-x_1) (1-x_2)  )^2. We show that this polynomial, even though it is nonnegative, is not a SONC polynomial. Note that r(x_1,x_2)=  1-2x_1-2x_2+4x_1x_2 +x_1^2  +x_2^2 -2x_1^2x_2 -2x_1x_2^2 +x_1^2x_2^2; the support of r is shown in Figure <ref>.
	
	Assume that r ∈ C_2,4, i.e., r has a SONC decomposition. This implies that the term -2x_1 has to be an inner term of some nonnegative circuit polynomial r_1 in this representation. Such a circuit polynomial necessarily has the terms 1 and x_1^2 as outer terms, that is, 
	
    r_1(x_1) =  p_1(x_1,x_2)   =  1+x_1^2-2x_1

	Since Θ_r_1=2 the polynomial r_1 is indeed nonnegative and, in addition, we cannot choose a smaller constant term to construct r_1.
	Next, also the term -2x_2 has to be an inner term of some nonnegative circuit polynomial r_2. Since this term again is on the boundary of (r) the only option for such an r_2 is: r_2(x_2)= p_2(x_1,x_2) = 1+x_2^2-2x_2. However, the term 1 has been already used in the above polynomial r_1, which leads to a contradiction, i.e., r∉ C_2,4. Since C_n,2d⊆ C_n+1,2d, the general statement follows.
































Hereinafter we show another operation, which behaves differently for SONC than it does for SOS: Similarly as in the case of multiplications, affine transformations also do not preserve the SONC structure. This observation is important for possible degree bounds on SONC certificates, when considering optimization problems over distinct descriptions of the hypercube.

	
	For every d ≥ 4, n ∈ℕ^* the SONC cone C_n,d is not closed under affine transformation of variables.	


	Consider the polynomial f(x_1,x_2) = x_1^2x_2^2. Clearly, the polynomial f is a nonnegative circuit polynomial since it is a monomial square, hence f ∈ C_n,d. Now consider the following affine transformation of the variables x_1 and x_2:
	
    x_1 → 1-x_1,     	x_2→ 1-x_2.

	After applying the transformation the polynomial f equals the polynomial p_1p_2 from the proof of Lemma <ref> and thus is not inside C_n,d.
	







§ AN UPPER BOUND ON THE DEGREE OF SONC CERTIFICATES OVER THE HYPERCUBE


 In the previous section we showed that the SONC cone is not closed under taking an affine transformation of variables, Corollary <ref>. Thus, if a polynomial f admits a degree d SONC certificate proving that it is nonnegative on a given compact semialgebraic set K, then it is a priori not clear whether a polynomial g, obtained from f via an affine transformation of variables, admits a degree d SONC certificate of nonnegativity on K, too. The degree needed to prove nonnegativity of g might be much larger than d according to the argumentation in the proof of Corollary <ref>.
 

 
 In this section we prove that every n-variate polynomial which is nonnegative over the boolean hypercube has a degree n SONC certificate. Moreover, if the hypercube is additionally constrained with some polynomials of degree at most d, then the nonnegative polynomial over such a set has degree n+d SONC certificate. We show this fact for all hypercubes {a_i,b_i}^n; see Theorem <ref> for further details.
 
 Formally, we consider the following setting: We investigate real multivariate polynomials in [𝐱]. For j ∈ [n], and a_j, b_j ∈ℝ, such that a_j < b_j let 
 
    g_j(𝐱) :=  (x_j-a_j)(x_j-b_j)

 be a quadratic polynomial with two distinct real roots. Let ⊂^n denote the n-dimensional hypercube given by ∏_j=1^n{a_j,  b_j}. 

 Moreover, let 
 
    𝒫 :=  {p_1,…,p_m:  p_i ∈[𝐱],   i ∈ [m]}
 
 be a set of polynomials, which we consider as constraints p_i(𝐱)≥ 0 with (p_i(𝐱)) ≤ d for all i ∈ [n] as follows. We define
 
    _𝒫 :=  {𝐱∈^n:   g_j(𝐱) =0,  j∈ [n],  p(𝐱) ≥ 0,  p ∈𝒫}

 as the n-dimensional hypercube  constrained by polynomial inequalities given by 𝒫.
 
 Throughout the paper we assume that ||=(n), i.e. the size of the constraint set  is polynomial in n. This is usually the case, since otherwise the problem gets less tractable from the optimization point of view.

 As a first step, we introduce a Kronecker function:
 
 	
For every 𝐯∈ the function

    δ_𝐯 (𝐱) :=  ∏_j ∈ [n]: v_j=a_j( -x_j +b_j /b_j-a_j) ·∏_j ∈ [n]: v_j=b_j( x_j - a_j /b_j-a_j)

is called the Kronecker delta (function) of the vector 𝐯.
 
 
Next we show that the term “Kronecker delta” is justified, i.e., we show that for every 𝐯∈ the function δ_𝐯(𝐱) takes the value zero for all 𝐱∈ except for 𝐱=𝐯 where it takes the value one.

	
	For every  𝐯∈ it holds that:
	
    δ_𝐯(𝐱)  = 
    	 0,         for every 𝐱∈∖{𝐯},
    
    	 1,         for 𝐱 =𝐯.



	On the one hand, if 𝐱∈∖{𝐯}, then there exists an index k such that 𝐱_k≠𝐯_k. This implies that there exists at least one multiplicative factor in δ_𝐯 which attains the value zero due to (<ref>). On the other hand if 𝐱 =𝐯 then we have 
	
    δ_𝐯 (𝐱)  =  ∏_j∈ [n]: v_j=a_j( -a_j +b_j /b_j-a_j)
    	∏_j∈ [n]: v_j=b_j( b_j - a_j /b_j-a_j)  =  1.


 
 The main result of this section is the following theorem.
 










 
	
	Let f(𝐱) ∈[𝐱]_n,n. Then f(𝐱) ≥ 0  for every 𝐱∈_𝒫 if and only if f has the following representation:

    f(𝐱)     =    ∑_𝐯∈_𝒫  c_𝐯δ_𝐯(𝐱)   +    ∑_𝐯∈∖_𝒫  c_𝐯δ_𝐯(𝐱) p_𝐯(𝐱)    +    ∑_j = 1^n s_j(𝐱) g_j(𝐱) + ∑_j = 1^n s_n + j(𝐱) (-g_j(𝐱)),

	where s_1,…, s_2n∈ C_n,n-2, c_𝐯∈ℝ_≥ 0 and p_𝐯∈𝒫. 

Since we are interested in optimization on the boolean hypercube , we assume without loss of generality that the polynomial f considered in Theorem <ref> has degree at most n. Indeed, it f has degree bigger than n, one can efficiently reduce the degree of f by applying iteratively the polynomial division with respect to polynomials g_j with j ∈ [n]. The remainder of the division process is a polynomial with degree at most n that agrees with f on all the vertices of .

We begin with proving the easy direction of the equivalence stated in Theorem <ref>.


 If f admits a decomposition of the form (<ref>), then f(𝐱) is nonnegative for all 𝐱∈_.
 



The coefficients c_𝐯 are nonnegative, all s_j(𝐱) are SONC and hence nonnegative on ^n. We have ± g_j(𝐱) ≥ 0 for all 𝐱∈, and for all choices of 𝐯∈ we have p_𝐯(𝐱) ≥ 0 for all 𝐱∈_, and δ_𝐯(𝐱) ∈{0,1} for all 𝐱∈. Thus, the right hand side of (<ref>) is a sum of positive terms for all 𝐱∈_.




We postpone the rest of the proof of Theorem <ref> to the end of the section. Now, we state an result about the presentation of the Kronecker delta function δ_𝐯. 


	
For every 𝐯∈ the Kronecker delta function can be written as

    δ_𝐯 =  ∑_j=1^2^ns_j H_j^(n),

for  s_1,…,s_2^n∈ℝ_≥ 0 and every H_j^(n) given as in (<ref>) with q=n and K given by the hypercube constraints g_1,…,g_n and l_1,…,l_2n.


First note that the function δ_𝐯 can be rewritten as	

    δ_𝐯 (𝐱) =  ∏_j=1^2n1 /b_j-a_j∏_j∈ [n]: v_j=a_j( -x_j +b_j     )
    ∏_j∈ [n]: v_j=b_j( x_j - a_j   ),
	
where ∏_j=1^n 1 /b_j-a_j∈ℝ_≥ 0. Now, the proof follows just by noting that for every j ∈ [n] both inequalities -x_j +b_j ≥ 0 and x_j - a_j ≥ 0 are in K.






The following statement is well-known in similar variations; see e.g. <cit.>. For clarity, we provide an own proof here.
 

Let f ∈[𝐱]_n,2d be a polynomial vanishing on . Then f = ∑_j = 1^n p_j g_j for some polynomials p_j ∈[𝐱]_n,2d-2.






	Let := ⟨ g_1,…,g_n ⟩ be the ideal generated by the g_j's. Let () denote the affine variety corresponding to , (()) denote its radical ideal, and let () denote the ideal of . It follows from ∏_j= 1^n g_j ∈ that () ⊆ and hence () ⊆(()) =. The last equality holds since  itself is a radical ideal. This results from Seidenberg's Lemma; see <cit.> by means of the following observations. The affine variety () consists exactly of the points defining , therefore we know that  is a zero-dimensional ideal. Furthermore, for every j∈ [n] the polynomials g_j satisfy g_j ∈∩[x_j] and (g_j,g_j')=1. Thus, every f ∈() is of the form f = ∑_j = 1^n p_j g_j.
	
	Moreover G := {g_1,…,g_n} is a Gröbner basis for  with respect to the graded lexicographic order ≺_ glex. This follows from Buchberger's Criterion, which says that G is a Gröbner basis for  if and only if for all pairs i≠ j the remainder on the division of the S-polynomials S(g_i,g_j) by G with respect to ≺_ glex is zero. Consider an arbitrary pair g_i,g_j with i > j. Then the corresponding S-polynomial is given by 
	
    S(g_i,g_j)  =  (a_j+b_j) x_i^2 x_j -(a_i+b_i) x_i x_j^2 - a_jb_j x_i^2  + a_ib_i x_j^2   .

	Applying polynomial division with respect to ≺_ glex yields the remainder 0 and hence G is a Gröbner basis for  with respect to ≺_ glex. Therefore, we conclude that if f ∈[𝐱]_n,2d, then (p_j)≤ 2d-2.


For an introduction to Gröbner bases see for example <cit.>.





	
Let d ∈ and f ∈[𝐱]_n,2d+2 such that f vanishes on . Then there exist s_1,…,s_2n ∈ C_n,2d such that f = ∑_j = 1^n s_j g_j + ∑_j = 1^n s_n + j (-g_j). 





By Proposition <ref> we know that f = ∑_j = 1^n p_j g_j for some polynomials p_j of degree ≤ 2d. Hence, it is sufficient to show that every single term p_j g_j is of the form ∑_j = 1^n s_j g_j - ∑_j = 1^n s_n + j g_j for some s_1,…,s_2n∈ C_n,2d. Let p_j = ∑_i = 1^ℓ a_ji m_ji where every a_ji∈ and every m_ji is a single monomial. We show that p_j g_j  has the desired form by investigating an arbitrary individual term a_ji m_ji g_j.

Case 1: Assume the exponent of m_ji is contained in (2)^n. If a_ji m_ji is a monomial square, then a_ji m_ji is a circuit polynomial. If a_ji < 0, then -a_ji m_ji is a monomial square. In both cases we obtain a representation s_ji (± g_ji), where s_ji∈ C_n,2d.

Case 2: Assume the the exponent β of m_ji contains odd numbers. Without loss of generality, assume that β = (β_1,…,β_k,β_k+1,…,β_n) such that the first k entries are odd and the remaining n-k entries are even.
We construct a SONC polynomial s_ji = a_(1)𝐱^(1) + a_(2)𝐱^(2) + a_ji𝐱^β such that 

    (1)     =    β + ∑_j = 1^⌈ k/2 ⌉𝐞_j - ∑_j = ⌈ k/2 ⌉ + 1^k𝐞_j,     (2)  =  β - ∑_j = 1^⌈ k/2 ⌉𝐞_j + ∑_j = ⌈ k/2 ⌉ + 1^k𝐞_j, 
    
     |a_ji|    ≤   √(2 a_(1) a_(2)).

By the construction (<ref>) (1),(2) ∈ (2)^n and β = 1/2 ((1) + (2)). Thus, s_ji is a circuit polynomial and by (<ref>) the coefficients a_(1), a_(2) are chosen large enough such that |a_ji| is bound by the circuit number √(2 a_(1) a_(2)) corresponding to s_ji. Thus, s_ji is nonnegative by <cit.>. Thus, we obtain 

    a_ji m_ji g_j  =  s_ji g_j + (a_(1)𝐱^(1) + a_(2)𝐱^(2)) (-g_j),

where s_ji, a_(1)𝐱^(1), and a_(2)𝐱^(2) are nonnegative circuit polynomials.

Degree: All involved nonnegative circuit polynomials are of degree at most 2d. In Case 1 this follows by construction. In Case 2 we have for the circuit polynomial s_ji that ((1)),((2)) = (β) if k is even, and ((1)) = (β) +1, ((2)) = (β) if k is odd. Since β is an exponent of the polynomial f, we know that (β) ≤ 2d. If k is odd, however, then 

    (β)  =  ∑_j = 1^k β_j_odd number + ∑_j = k+1^nβ_j_even number,

i.e., (β) is a sum of k many odd numbers, with k being odd, plus a sum of even numbers. Thus, (β) has to be an odd number and hence (β) < 2d. Therefore, all degrees of terms in s_ji are bounded by 2d and thus s_ji∈ C_n,2d.

Conclusion: We have that 

    f  =  ∑_j = 1^n p_j g_j  =  ∑_j = 1^n ∑_i = 1^ℓ_j a_ji m_ji g_j  =  ∑_j = 1^n ∑_i = 1^ℓ_j s_ji g_j.

By Cases 1 and 2 and the degree argument, we have s_ji∈ C_n,2d for every i,j and by defining s_j = ∑_i = 1^ℓ_j s_ji∈ C_n,2d we obtain the desired representation of f.



























 §.§ Proof of Theorem <ref>



In this section we combine the results of this section and finish the proof of Theorem <ref>.



Due to Lemma <ref>, it remains to show that f(𝐱) admits a decomposition of the form (<ref>) if f(𝐱) ≥ 0 for every 𝐱∈_.





































































Hence, when restricted to the hypercube , the polynomial f can be represented in the following way:

    f(𝐱)   =    f(𝐱) ∑_𝐯∈_𝒫δ_𝐯(𝐱)  + f(𝐱) ∑_𝐯∈∖_𝒫δ_𝐯(𝐱)          for all 𝐱∈ 
       =   ∑_𝐯∈_𝒫δ_𝐯(𝐱) f(𝐯)  +  ∑_𝐯∈∖_𝒫δ_𝐯(𝐱)f(𝐯)           for all 𝐱∈ ,

where the last equality follows by Lemma <ref> .


Note that there might exist a vector 𝐯∈∖_𝒫 such that f attains a negative value at 𝐯. If f(𝐯) <0, then let p_𝐯∈𝒫 be one of the polynomials among the constraints satisfying p_𝐯(𝐯) <0. Otherwise, let p_𝐯=1. Since by Lemma <ref> we have δ_𝐯(𝐱) p_𝐯(𝐱)  =   δ_𝐯(𝐱) p_𝐯(𝐯) for every 𝐯, 𝐱∈, we can now write:



    f(𝐱)   =   ∑_𝐯∈_𝒫δ_𝐯(𝐱) f(𝐯)  +  
    ∑_𝐯∈∖_𝒫δ_𝐯(𝐱)p_𝐯(𝐱) f(𝐯)/p_𝐯(𝐯)     for all 𝐱∈.


Thus, the polynomial f(𝐱)- ∑_𝐯∈_𝒫δ_𝐯(𝐱) f(𝐯) - 
∑_𝐯∈∖_𝒫δ_𝐯(𝐱)p_𝐯(𝐱) f(𝐯)/p_𝐯(𝐯) has degree at most n+d and vanishes on . By Theorem <ref> we finally get







    f(𝐱)  =  ∑_j = 1^n s_j(𝐱) g_j(𝐱) + ∑_j = 1^n s_n + j(𝐱) (-g_j(𝐱))   + ∑_𝐯∈_𝒫δ_𝐯(𝐱) f(𝐯)  +  
    ∑_𝐯∈∖_𝒫δ_𝐯(𝐱)p_𝐯(𝐱) f(𝐯)/p_𝐯(𝐯) ,

for some s_1,…, s_2n∈ C_n,n-2 and p_𝐯∈𝒫. This, together with Lemma <ref>, finishes proof together with.



	For every polynomial f which is nonnegative over the boolean hypercube constrained with polynomial inequalities of degree at most d there exists a degree n+d SONC certificate.



	The argument follows directly from Theorem <ref> by noting that the right hand side of (<ref>) is a SONC certificate of degree n+d (see the Definition <ref>).





 §.§ Degree d SONC Certificates


In this section we show that if a polynomial f admits a degree d SONC certificate, then f also admits a short degree d certificate that involves at most n^O(d) terms. We conclude the section with a discussion regarding the time complexity of finding a degree d SONC certificate.


	
	Let f be an n-variate polynomial, nonnegative on the constrained hypercube _ with ||=(n). Assume that there exists a degree d SONC certificate for f, then there exists a degree d SONC certificate for f involving at most O(n≤ d) many nonnegative circuit polynomials. 



	Since there exists a degree d SONC proof of the nonnegativity of f on _ we know that
	
    f(𝐱)  =  ∑_js_j H_j^(q),

	where the summation is finite, the s_j's are SONCs, and every H_j^(q) is a product as defined in (<ref>).
	
	Step 1: We analyze the terms s_j. Since every s_j is a SONC, we know that there exists a representation
	
    s_j  =  κ_j ·∑_i = 1^k_jμ_ij· q_ij

	such that κ_j, μ_1j,…, μ_k_jj∈_> 0, ∑_i = 1^k_jμ_ij = 1, and the q_ij are nonnegative circuit polynomials. Since s_j is of degree at most d, we know that Q_j := {q_1j,…,q_k_jj} is contained in _n,d[𝐱], which is a real vector space of dimension n+dd. Since s_j / κ_j is a convex combination of the q_ij, i.e. in the convex hull of Q_j, and (Q_j) ≤n+dd, applying Carathéodory's Theorem, see e.g.  <cit.>, yields that s_j/κ_j can be written as a convex combination of at most n+dd + 1 many of the c_ij.
	
	Step 2: We analyze the terms H_j^(q). By definition of the _ and the terms H_j^(q) we have
	
    H_j^(q) =  g_j_1⋯ g_j_s· l_r_1⋯ l_r_t· p_ℓ_1· p_ℓ_v

	with j_1,…,j_s ∈ [n], r_1,…,r_t ∈ [2n], and ℓ_1,…,ℓ_v ∈ [m]. Since the maximal degree of H_j^(q) is d, the number of different H_j^(q)'s is bounded from above by n+2n+md. 
	
	Conclusion: In summary, we obtain a representation:
	
    f(𝐱)  =  ∑_i=1^n+2n+md H_j^(q) s_j  =  ∑_i=1^n+2n+md H_j^(q)κ_j ∑_j = 1^n+dd +1μ_ij c_ij

	
	Since, as assumed m can bounded by (n), the total number of summands is (n)^O(d)=n^O(d), and we found a desired representation with at most n^O(d) nonnegative circuit polynomials of degree at most d.


The Theorem <ref> states that when searching for a degree d SONC certificate it is enough to restrict to certificates containing at most n^O(d) nonnegative circuit polynomials. Moreover, as proved in <cit.> for a given set A ⊆ℕ^n, searching through the space of degree d SONC certificates supported on set A can be computed via a relative entropy program (REP) of size n^O(d). 
However, the above arguments do not necessarily imply that that the search through the space of degree d SONC certificates can be performed in time n^O(d). The difficulty is that one needs to restrict the configuration space of n-variate degree d SONCs to a subset of order n^O(d) to be able to formulate the corresponding REP in time n^O(d). Since the current proof of Theorem <ref> just guarantees the existence of a short SONC certificate, it is currently not clear, how to search for a short certificate efficiently. We leave this as an open problem.































































§ THERE EXISTS NO EQUIVALENT TO PUTINAR'S POSITIVSTELLENSATZ FOR SONCS


In this section we address the open problem raised in <cit.> asking whether the Theorem <ref> can be strengthened by requiring q=1. Such a strengthening, for a positive polynomial over some basic closed semialgebraic set, would provide a SONC decomposition equivalent to Putinar's Positivstellensatz for SOS; for background see e.g., <cit.>. We answer this question in a negative way. More precisely, we provide a polynomial f which is strictly positive over the hypercube {± 1}^n such that there does not exist a SONC decomposition of f for q=1. Moreover, we prove it not only for the most natural choice of the box constraints, that is l_i =1 ± x_i, but for a generic type of box constraints of the form ℓ_i =1+c_i ± x_i with c_i ∈ℝ_≥ 0. We close the section with a short discussion.



Let ={± 1}^n and consider the following set of polynomials parametrized by a natural number a:

    f_a(𝐱) :=  (a-1)∏_i=1^n (  x_i +1/2) +1.

These polynomials satisfy f_a(𝐞) = a for the vector 𝐞=∑_i=1^n 𝐞_i and f_a(𝐱) = 1 for every other 𝐱∈∖{𝐞}. We define for every d ∈

    S_d :=  {∑_ finite s · h  :  s ∈  C_n,2d,  h ∈{1,±(x_i^2 -1), 1+c_i ± x_i  :  i ∈[n], c_i∈ℝ_≥ 0}}
 

as the set of polynomials admitting a SONC decomposition over  given by Theorem <ref> for q=1. The main result of this section is the following theorem.

	
	For every a > 2^n-1/2^n-2-1 we have f_a ∉ S_d for all d ∈.


Before we prove this theorem, we show the following structural results. Note that similar structural observations were already made for AGIforms by Reznick in <cit.> using a different notation.

	
	Every s(𝐱) ∈ C_n,2d attains at most two different values on ={± 1}^n. Moreover, if s(𝐱) attains two different values, then each value is attained for exactly the half of the hypercube vertices. 


	By Definition <ref> every nonnegative circuit polynomial is of the form:
	
    s(𝐱)  =  ∑_j=0^r f_(j)𝐱^(j) + f_β𝐱^β.

Note that for j=0,…,r, we have (j) ∈ (2)^n. Hence when evaluated over the hypercube 𝐱∈ ={± 1}^n, s(𝐱) can take only one of at most two different values ∑_j=0^rf_(j)± f_β. 

If s(𝐱) attains two different values over , then there has to exist a non empty subset of variables that have an odd entry in β. Let I⊆[n] be this subset. Then s(𝐱)=∑_j=0^rf_(j)(𝐱) - f_β(𝐱), for 𝐱∈ if and only if 𝐱 has an odd number of -1 entries in the set I. The number of such vectors is equal to

    2^n-|I|∑_i=0, 
     i  odd^|I| 2^i  =  2^n-|I| 2^|I|-1 =  2^n-1.





	
	Every polynomial s(𝐱)ℓ_i(𝐱), with s ∈ C_n,2d and ℓ_i = 1 + c_i ± x_i being a box constraint, attains at most four different values on ={± 1}^n. Moreover, each value is attained for at least one forth of the hypercube vertices. 


	By Lemma <ref>, s(𝐱) attains at most the two values (∑_j=0^rf_α(j)± f_β) on . Similarly, ℓ_i(𝐱) attains at most the two values 1+c_i ± x_i over . Thus, a polynomial s(𝐱) ℓ_i(𝐱) attains at most the four different values (∑_j=0^rf_α(j)± f_β) ( 1+c_i ± x_i  ) on .
	
	Let I be as in the proof of Lemma <ref>, i.e., the subset of variables that have an odd entry in β. If I=∅, then the first term ∑_j=0^rf_α(j) + f_β is constant over the hypercube , thus s(𝐱)ℓ_i(𝐱) takes two different values depending on the i-th entry of the vector. Each value is attained for exactly half of the vectors.
	
	If I≠∅ and i ∉ I the claim holds since the value of the first term depends only on the entries in I and the value of the second term depends on the i-th entry. Hence, the polynomial s(𝐱)ℓ_i(𝐱) attains four values each on exactly one fourth of  vectors.
	
	Finally, let I≠∅ and i ∈ I. Partition the hypercube vertices into two sets depending on the i-th entry. Each set has cardinality 2^n-1. Consider the set with x_i=1. For the vectors in this set the second term takes a constant value 2+c. Over this set the polynomial s takes one of the values ∑_j=0^rf_α(j)(𝐱) ± f_β(𝐱), depending on whether 𝐱 has an odd or even number of -1 entries in the set I∖{-1}. In both cases the number of such vectors is equal to
	
    2^n-|I|∑_i=0, 
     i  odd^|I|-1 2^i  =  2^n-|I| 2^|I|-2=2^n-2.

	The analysis for the case x_i=-1 is analogous.
	
	  


Now we can provide the proof of Theorem <ref>.

(Proof of Theorem <ref>)

Assume f_a ∈ S_d for some a ∈ℕ and d ∈. We prove that a has to be smaller or equal than 2^n-1/2^n-2-1.



Since f_a ∈ S_d we know that

    f_a(𝐱)    =     s_0(𝐱) + ∑_i = 1^n s_i(𝐱) ℓ_i(𝐱) + ∑_j = 1^n s̃_j(𝐱) (x_j^2 - 1) + s̃_j+n(𝐱) (1 - x_j^2)

with s_0,…,s_n,s̃_1,…,s̃_2n∈ C_n,2d. Since ± (x_j^2-1) for j∈[n] vanishes over the hypercube , we can conclude

    f_a(𝐱)  =  s_0(𝐱) + ∑_i = 1^n s_i(𝐱) ℓ_i(𝐱)      for all 𝐱∈

for some s_0,s_1,…,s_n ∈ C_n,2d.


Let s_0,k, and s_i,j be some nonnegative circuit polynomials such that s_0=∑_k s_0,k, and s_i= ∑_j s_i,j. Thus, we get

    ∑_𝐱∈(  s_0(𝐱) + ∑_i = 1^n s_i(𝐱) ℓ_i(𝐱) )     =   ∑_k ∑_𝐱∈   s_0,k(𝐱) +  ∑_i ∑_j ∑_𝐱∈  s_i,j(𝐱) ℓ_i,j(𝐱)
       ≥   ∑_k 2^n-1 s_0,k(𝐞) +  ∑_i = 1^n ∑_j 2^n-2 s_i,j(𝐞) ℓ_i,j(𝐞)
       ≥    2^n-2(  s_0(𝐞) + ∑_i = 1^n s_i(𝐞) ℓ_i(𝐞) )
       =    2^n-2 a

where the first inequality comes directly from Lemma <ref> and <ref> and the last equality from the fact that f_a(𝐞)=a.



On the other hand, by the properties of the function f_a and the equality (<ref>), we know that

    ∑_𝐱∈(  s_0(𝐱) + ∑_i s_i(𝐱) ℓ_i(𝐱) )  =  2^n-1+ a,

which makes the subsequent inequality a necessary requirement for f_a ∈ S_d: 

    a  ≤ 2^n-1/2^n-2-1.




Speaking from a broader perspective, we interpret Theorem <ref> as an indication that the real algebraic structures, which we use to handle sums of squares, do not apply in the same generality to SONCs. We find this not at all surprising from the point of view that in the 19th century Hilbert initially used SOS as a certificate for nonnegativity and many of the algebraic structures in question where developed afterwards with Hilbert's results in mind; see <cit.> for a historic overview. Our previous work shows that SONCs, in contrast, can, e.g., very well be analyzed with combinatorial methods. We thus see Theorem <ref> as further evidence about the very different behavior of SONCs and SOS and as an encouragement to take methods beside the traditional real algebraic ones into account for the successful application of SONCs in the future.


amsalpha

 
