ON THE CONSTRUCTION OF CONVERGING HIERARCHIES
FOR POLYNOMIAL OPTIMIZATION
BASED ON CERTIFICATES OF GLOBAL POSITIVITY∗

arXiv:1709.09307v1 [math.OC] 27 Sep 2017

AMIR ALI AHMADI† AND GEORGINA HALL‡
Abstract. In recent years, techniques based on convex optimization and real algebra that
produce converging hierarchies of lower bounds for polynomial optimization problems (POPs) have
gained much popularity. At their heart, these hierarchies rely crucially on Positivstellensätze from
the late 20th century (e.g., due to Stengle, Putinar, or Schmüdgen) that certify positivity of a
polynomial on an arbitrary basic semialgebraic set. In this paper, we show that such hierarchies
could in fact be designed from much more limited Positivstellensätze dating back to the early 20th
century that only certify positivity of a polynomial globally. More precisely, we show that any inner
approximation to the cone of positive homogeneous polynomials that is arbitrarily tight can be turned
into a converging hierarchy for general polynomial optimization problems with compact feasible sets.
This in particular leads to a semidefinite programming-based hierarchy that relies solely on Artin’s
solution to Hilbert’s 17th problem. We also use a classical result of Polyá on global positivity of
even forms to construct an “optimization-free” converging hierarchy for general POPs with compact
feasible sets. This hierarchy only requires polynomial multiplication and checking nonnegativity of
coefficients of certain fixed polynomials. As a corollary, we obtain new linear programming and
second-order cone programming-based hierarchies for POPs that rely on the recently introduced
concepts of dsos (diagonally dominant sum of squares) and sdsos (scaled diagonally dominant sum
of squares) polynomials.
Key words. Positivstellensätze, polynomial optimization, convex optimization
AMS subject classifications. 14Q99, 90C05, 90C26, 90C22, 90-03

1. Introduction. A polynomial optimization problem (POP) is an optimization
problem of the form
inf

(1)

x∈Rn

s.t.

p(x)
gi (x) ≥ 0, i = 1, . . . , m,

where p, gi , i = 1, . . . , m, are polynomial functions in n variables x := (x1 , . . . , xn )
and with real coefficients. It is well-known that polynomial optimization is a hard
problem to solve in general. For example, simply testing whether the optimal value
of problem (1) is smaller than or equal to some rational number k is NP-hard already
when the objective is quadratic and the constraints are linear [14]. Nevertheless, these
problems remain topical due to their numerous applications throughout engineering,
operations research, and applied mathematics (see, e.g., [10, 6, 2]). In this paper, we
are interested in obtaining lower bounds on the optimal value of problem (1). We focus
on a class of methods which construct hierarchies of tractable convex optimization
problems whose optimal values are lowerbounds on the optimal value of (1), with
convergence to it as the sequence progresses. This implies that even though the
original POP is nonconvex, one can obtain increasingly accurate lower bounds on its
optimal value by solving convex optimization problems. One method for constructing
∗ This

work is partially funded by the DARPA Young Faculty Award, the Young Investigator
Award of the AFOSR, the CAREER Award of the NSF, the Google Faculty Award, and the Sloan
Fellowship.
† Department of Operations Research and Financial Engineering, Princeton, NJ 08540
(a_a_a@princeton.edu, http://aaa.princeton.edu).
‡ Department of Operations Research and Financial Engineering, Princeton, NJ 08540
(gh4@princeton.edu, http://scholar.princeton.edu/ghall).
1

2
these hierarchies of optimization problems that has gained attention in recent years
relies on the use of Positivstellensätze (see, e.g., [11] for a survey). Positivstellensätze
are algebraic identities that certify infeasibility of a set of polynomial inequalities, or
equivalently1 , positivity of a polynomial on a basic semialgebraic set. (Recall that
a basic semialgebraic set is a set defined by finitely many polynomial inequalities.)
These Positivstellensätze can be used to prove lowerbounds on POPs. Indeed, if we
denote the feasible set of (1) by S, the optimal value of problem (1) is equivalent to
sup

γ

γ

(2)

s.t.

p(x) − γ ≥ 0, ∀x ∈ S.

Hence if γ is a strict lower bound on (1), we have that p(x) − γ > 0 on S, a fact
that can be certified using Positivstellensätze. At a conceptual level, hierarchies that
provide lower bounds on (1) are constructed thus: we fix the “size of the certificate” at
each level of the hierarchy and search for the largest γ such that the Positivstellensätze
at hand can certify positivity of p(x) − γ over S with a certificate of this size. As the
sequence progresses, we increase the size of the certificates allowed, hence obtaining
increasingly accurate lower bounds on (1).
Below, we present three of the better-known Positivstellensätze, given respectively
by Stengle [25], Schmüdgen [21], and Putinar [19]. These all rely on sum of squares
certificates. We recall that a polynomial is a sum of squares (sos) if it can be written
as a sum of squares of other polynomials. We start with Stengle’s Positivstellensatz,
which certifies infeasibility of a set of polynomial inequalities. It is sometimes referred
to as “the Positivstellensatz” in related literature as it requires no assumptions, contrarily to Schmüdgen and Putinar’s theorems which can be viewed as refinements of
Stengle’s result under additional assumptions.
Theorem 1.1 (Stengle’s Positivstellensatz [25]). The basic semialgebraic set
S = {x ∈ Rn | g1 (x) ≥ 0, . . . , gm (x) ≥ 0}
is empty if and only if there exist sum of squares polynomials s0 (x),s1 (x),. . ., sm (x),
s12 (x), s13 (x),. . ., s123...m (x) such that
X
X
sij (x)gi (x)gj (x) + . . . + s123...m (x)g1 (x) . . . gm (x).
si (x)gi (x) +
−1 = s0 (x) +
i

{i,j}

The next two theorems, due to Schmüdgen and Putinar, certify positivity of a polynomial p over a basic semialgebraic set S. They impose additional compactness assumptions comparatively to Stengle’s Positivstellensatz.
Theorem 1.2 (Schmüdgen’s Positivstellensatz [21]). Assume that the set
S = {x ∈ Rn | g1 (x) ≥ 0, . . . , gm (x) ≥ 0}
is compact. If a polynomial p is positive on S, then
X
X
sij (x)gi (x)gj (x) + . . . + s123...m (x)g1 (x) . . . gm (x),
p(x) = s0 (x) +
si (x)gi (x) +
i

{i,j}

where s0 (x),s1 (x),. . ., sm (x), s12 (x), s13 (x),. . ., s123...m (x) are sums of squares.
that the set {x ∈ Rn | g1 (x) ≥ 0, . . . , gm (x) ≥ 0} is empty if and only if −g1 (x) > 0 on
the set {x ∈ Rn | g2 (x) ≥ 0, . . . , gm (x) ≥ 0}.
1 Note

CONVERGING HIERARCHIES FOR POLYNOMIAL OPTIMIZATION

3

Theorem 1.3 (Putinar’s Positivstellensatz [19]). Let
S = {x ∈ Rn | g1 (x) ≥ 0, . . . , gm (x) ≥ 0}
and assume that {g1 , . . . , gm } satisfy the Archimedean property, i.e., there exists
N ∈ N such that
X
x2i = σ0 (x) + σ1 (x)g1 (x) + . . . + σm (x)gm (x),
N−
i

where σ1 (x), . . . , σm (x) are sums of squares. If a polynomial p is positive on S, then
p(x) = s0 (x) + s1 (x)g1 (x) + . . . + sm (x)gm (x),
where s1 (x), . . . , sm (x) are sums of squares.
Note that these three Positivstellensätze involve in their expressions sum of squares
polynomials of unspecified degree. To construct hierarchies of tractable optimization problems for (2), we fix this degree: at level r, we search for the largest γ
such that positivity of p(x) − γ over S can be certified using the Positivstellensätze
where the degrees of all sos polynomials are taken to be less than or equal to 2r.
Solving each level of these hierarchies is then a semidefinite program (SDP). This is
a consequence of the fact that one can optimize over (or test membership to) the
set of sum of squares polynomials of fixed degree using semidefinite programming
[16, 15, 9]. Indeed, a polynomial p of degree 2d and in n variables is a sum of squares
if and only if there exists a symmetric matrix Q  0 such that p(x) = z(x)T Qz(x),
where z(x) = (1, x1 , . . . , xn , . . . , xdn )T is the standard vector of monomials in n variables and of degree less than or equal to d. We remark that the hierarchy obtained
from Stengle’s Positivstellensatz was proposed and analyzed by Parrilo in [16]; the
hierarchy obtained from Putinar’s Positivstellensatz was proposed and analyzed by
Lasserre in [9]. There have been more recent works that provide constructive proofs
of Schmüdgen and Putinar’s Positivstellensätze; see [5, 22, 24]. These proofs rely on
other Positivstellensätze, e.g., a result by Polyá (see Theorem 1.6 below) in [22, 24],
and the same result by Polyá, Farkas’ lemma, and Stengle’s Positivstellensatz in [5].
There has further been an effort to derive complexity bounds for Schmüdgen and
Putinar’s Positivstellensätze in recent years; see [13, 23].
On a historical note, Stengle, Schmüdgen, and Putinar’s Positivstellensätze were
derived in the latter half of the 20th century. As mentioned previously, they all
certify positivity of a polynomial over an arbitrary basic semialgebraic set (modulo
compactness assumptions). By contrast, there are Positivstellensätze from the early
20th century that certify positivity of a polynomial globally. Perhaps the most wellknown Positivstellensatz of this type is due to Artin in 1927, in response to Hilbert’s
17th problem. Artin shows that any nonnegative polynomial is a sum of squares of
rational functions. Here is an equivalent formulation of this statement:
Theorem 1.4 (Artin [4]). For any nonnegative polynomial p, there exists an sos
polynomial q such that p · q is a sum of squares.

To the best of our knowledge, in this area, all converging hierarchies of lower bounds
for POPs are based off of Positivstellensätze that certify nonnegativity of a polynomial
over an arbitrary basic semialgebraic set. In this paper, we show that in fact, under
compactness assumptions, it suffices to have only global certificates of nonnegativity
(such as the one given by Artin) to produce a converging hierarchy for general POPs.

4
As a matter of fact, even weaker statements that apply only to globally positive (as
opposed to globally nonnegative) forms are enough to derive converging hierarchies
for POPs. Examples of such statements are due to Habicht [8] and Reznick [20]. With
such an additional positivity assumption, more can usually be said about the structure
of the polynomial q in Artin’s result. Below, we present the result by Reznick.
Theorem 1.5
P (Reznick [20]). For any positive definite form p, there exists r ∈ N
such that p(x) · ( i x2i )r is a sum of squares.

We show in this paper that this Positivstellensatz also gives rise to a converging
hierarchy for POPs with a compact feasible set similarly to the one generated by
Artin’s Positivstellensatz.
Through their connections to sums of squares, the two hierarchies obtained using
the theorems of Reznick and Artin are semidefinite programming-based. In this paper,
we also derive an “optimization-free” converging hierarchy for POPs with compact
feasible sets where each level of the hierarchy only requires that we be able to test
nonnegativity of the coefficients of a given fixed polynomial. To the best of our
knowledge, this is the first converging hierarchy of lower bounds for POPs which
does not require that convex optimization problems be solved at each of its levels.
To construct this hierarchy, we use a result of Polyá [17], which just like Artin’s and
Reznick’s Positivstellensätze, certifies global positivity of forms. However this result is
restricted to even forms. Recall that a form p is even if each of the variables featuring
in its individual monomials has an even power. This is equivalent (see [7, Lemma 2])
to p being invariant under change of sign of each of its coordinates, i.e.,
p(x1 , . . . , xn ) = p(−x1 , . . . , xn ) = · · · = p(x1 , . . . , −xn ).
Theorem 1.6 (Polyá
P [17]). For any positive definite even form p, there exists
r ∈ N such that p(x) · ( i x2i )r has nonnegative coefficients.2

Our aforementioned hierarchy enables us to obtain faster-converging linear programming (LP) and second-order cone programming (SOCP)-based hierarchies for general
POPs with compact feasible sets that rely on the concepts of dsos and sdsos polynomials. These are recently introduced inner approximations to the set of sos polynomials
that have shown much better scalability properties in practice [3].
As a final remark, we wish to stress the point that the goal of this paper is
first and foremost theoretical, i.e., to provide methods for constructing converging
hierarchies of lower bounds for POPs using as sole building blocks certificates of
global positivity. We do not make any claims that these hierarchies can outperform
the popular existing hierarchies due, e.g., to Lasserre [9] and Parrilo [16]. We do
believe however that the optimization-free hierarchy presented in Section 4.1 could
potentially be of interest in large-scale applications where the convex optimization
problems appearing in traditional hierarchies are too cumbersome to solve.
1.1. Outline of the paper. The paper is structured as follows. In Section 2, we
show that if one can inner approximate the cone of positive definite forms arbitrarily
well (with certain basic properties), then one can produce a converging hierarchy
of lower bounds for POPs with compact feasible sets (Theorem 2.4). This relies
2 A perhaps better-known but equivalent formulation of this theorem is the following: for any
P
form h that is positive on the standard simplex, there exists r ∈ N such that h(x) · ( i xi )r has
nonnegative coefficients. The two formulations are equivalent by simply letting p(x) = h(x2 ).

CONVERGING HIERARCHIES FOR POLYNOMIAL OPTIMIZATION

5

on a reduction (Theorem 2.1) that reduces the problem of certifying a strict lower
bound on a POP to that of proving positivity of a certain form. In Section 3, we
see how this result can be used to derive semidefinite programming-based converging
hierarchies (Theorems 3.2 and 3.4) from the Positivstellensätze by Artin (Theorem
1.4) and Reznick (Theorem 1.5). In Section 4, we derive an optimization-free hierarchy
(Theorem 4.1) from the Positivstellensatz of Polyá (Theorem 1.6) as well as LP and
SOCP-based hierarchies which rely on dsos/sdsos polynomials (Corollary 4.8). We
conclude with a few open problems in Section 5.
1.2. Notation and basic definitions. We use the standard notation A  0
to denote that a symmetric matrix A is positive semidefinite. Recall that a form is
a homogeneous polynomial, i.e., a polynomial whose monomials all have the same
degree. We denote the degree of a form f by deg(f ). We say that a form f is
nonnegative (or positive semidefinite) if f (x) ≥ 0, for all x ∈ Rn (we write f ≥ 0). A
form f is positive definite (pd) if f (x) > 0, for all nonzero x in Rn (we write f > 0).
Throughout the paper, we denote the set of forms (resp. the set of nonnegative
forms) in n variables and of degree d by Hn,d (resp Pn,d ). We denote the ball of
radius R and centered at the origin by B(0, R) and the unit sphere in x-space, i.e.,
{x ∈ Rn | ||x||2 = 1}, by Sx . We use the shorthand f (y 2 − z 2 ) for y, z ∈ Rn to
denote f (y12 − z12 , . . . , yn2 − zn2 ). We say that a scalar γ is a strict lower bound on (1)
if p(x) > γ, ∀x ∈ S. Finally, we ask the reader to carefully read Remark 2.3 which
contains the details of a notational overwriting occurring before Theorem 2.4 and
valid from then on throughout the paper. This overwriting makes the paper much
simpler to parse.
2. Constructing converging hierarchies for POP using global certificates of positivity. Consider the polynomial optimization problem in (1) and denote its optimal value by p∗ . Let d be such that 2d is the smallest even integer larger
than or equal to the maximum degree of p, gi , i = 1, . . . , m. We denote the feasible
set of our optimization problem by
S = {x ∈ Rn | gi (x) ≥ 0, i = 1, . . . , m}
and assume that S is contained within a ball of radius R. From this, it is easy to
provide (possibly very loose) upper bounds on gi (x) over the set S: as S is contained
in a ball of radius R, we have |xi | ≤ R, for all i = 1, . . . , n. We then use this to
upper bound each monomial in gi and consequently gi itself. We use the notation ηi
to denote these upper bounds, i.e., gi (x) ≤ ηi , for all i = 1, . . . , m and for all x ∈ S.
Similarly, we can provide an upperbound on −p(x). We denote such a bound by β,
i.e., −p(x) ≤ β, ∀x ∈ S.
The goal of this section is to produce a method for constructing converging hierarchies of lower bounds for POPs if we have access to arbitrarily accurate inner
approximations of the set of positive definite forms. The first theorem (Theorem 2.1)
connects lower bounds on (1) to positive definiteness of a related form. The second
theorem (Theorem 2.4) shows how this can be used to derive a hierarchy for POPs.
Theorem 2.1. Consider the general polynomial optimization problem in (1) and
recall that d is such that 2d is the smallest even integer larger than or equal to the
maximum degree of p, gi , i = 1, . . . , m. Suppose S ⊆ B(0, R) for some positive scalar
R. Let ηi , i = 1, . . . , m (resp. β) be any finite upper bounds on gi (x), i = 1, . . . , m
(resp. −p(x)).
Then, a scalar γ is a strict lower bound on (1) if and only if the homogeneous

6
sum of squares polynomial
(3)

fγ (x, s, y) := γy 2d − y 2d p(x/y) − s20 y 2d−2
+

(R +

m
X
i=1

2

+

m
X
i=1

y 2d gi (x/y) − s2i y 2d−2

m
n
X
X
s2i )d − s2d
x2i +
ηi + β + γ)d y 2d − (
m+1
i=1

i=0

2

!2

of degree 4d and in n + m + 3 variables (x1 , . . . , xn , s0 , . . . , sm , sm+1 , y) is positive
definite.
Proof. It is easy to see that γ is a strict lower bound on (1) if and only if the set
X
x2i ≤ R}
T := {x ∈ Rn | γ − p(x) ≥ 0; gi (x) ≥ 0, i = 1, . . . , m;
i

is empty. Indeed, if T is nonempty, then there exists a point x̌ ∈ S such that p(x̌) ≤ γ.
This implies that γ cannot be a strict lower bound on (1). Conversely, if T is empty,
the intersection of S with {x | γ − p(x) ≥ 0} is empty, which implies that ∀x ∈ S,
p(x) > γ.
We now define the set:
(4)

Ts = {(x, s) ∈ Rn+m+2 | γ − p(x) = s20 ; gi (x) = s2i , i = 1, . . . , m;
m
n
m
X
X
X
s2i )d − s2d
x2i +
ηi + β + γ)d − (
(R +
m+1 = 0}.
i=1

i=1

i=0

Note that Ts is empty if and only if T is empty. Indeed, if Ts is nonempty, then there
exists x̂ ∈ Rn and ŝ ∈ Rm+2 such that the three sets of equations are satisfied. This
obviously implies
P that γ − p(x̂) ≥ 0 and that gi (x̂) ≥ 0, for all i = 1, . . . , m. It further
implies that i x̂2i ≤ R as by assumption, if x̂ ∈ S, then x̂ is in a ball of radius R.
Conversely, suppose now that TPis nonempty. There exists x̃ such that γ − p(x̃) ≥ 0,
gi (x̃) ≥ 0 for i = 1, . . . , m, and i x̃i 2 ≤ R. Hence, there exist s˜0 , . . . , s˜m such that
γ − p(x̃) = s˜0 2 and gi (x̃) = s˜i 2 , i = 1, . . . , m.
P
Combining the fact that i x̃i 2 ≤ R and the fact that ηi , i = 1, . . . , m (resp. γ + β)
are upperbounds on gi (resp. γ − p(x̃)), we obtain:
R+

m
X
i=1

ηi + β + γ ≥

n
X
i=1

x̃i 2 +

m
X

s˜i 2 .

i=0

By raising both sides of the inequality to the power d, we show the existence of s̃m+1 .
We now show that Ts is empty if and only if fγ (x, s, y) is positive definite. Suppose
that Ts is nonempty, i.e., there exists (x̆, s̆) ∈ Rn+m+2 such that the equalities given
in (4) hold. Note then that fγ (x̆, s̆, 1) = 0. As (x̆, s̆, 1) is nonzero, this implies that
fγ (x̆, s̆, y̆) is not positive definite.
For the converse, assume that fγ (x, s, y) is not positive definite. As fγ (x, s, y) is
a sum of squares and hence nonnegative, this means that there exists nonzero (x̄, s̄, ȳ)
such that f (x̄, s̄, ȳ) = 0. We proceed in two cases. If ȳ 6= 0, it is easy to see that
(x̄/ȳ, s̄/ȳ) ∈ Ts and Ts is nonempty. Consider now the case where ȳ = 0. The third
square in fγ being equal to zero gives us:
m
X
X
2
s̄2i )d = s̄2d
x̄i +
−(
m+1 .
i

i=0

CONVERGING HIERARCHIES FOR POLYNOMIAL OPTIMIZATION

7

This implies that s̄m+1 = 0 and that x̄1 = . . . = x̄m = s¯0 = . . . = s̄m = 0 which
contradicts the fact that (x̄, s̄, ȳ) is nonzero.
Remark 2.2. Note that Theorem 2.1 implies that testing feasibility of a set of
polynomial inequalities is no harder than checking whether a homogeneous polynomial
that is sos has a zero. Indeed, as mentioned before, the basic semialgebraic set
{x | g1 (x) ≥ 0, . . . , gm (x) ≥ 0}
is empty if and only if γ = 0 is a strict lower bound on the POP
inf

− g1 (x)

s.t.

g2 (x) ≥ 0, . . . , gm (x) ≥ 0.

x

In principle, this reduction can open up new possibilities for algorithms for testing
feasibility of a basic semialgebraic set. For example, the work in [1] shows that positive
definiteness of a form f is equivalent to global asymptotic stability of the polynomial
vector field ẋ = −∇f (x). One could as a consequence search for Lyapunov functions,
as is done in [1, Example 2.1.], to certify positivity of forms. Conversely, simulating
trajectories of the above vector field can be used to minimize f and potentially find its
nontrivial zeros, which, by our reduction, can be turned into a point that belongs to
the basic semialgebraic set at hand.
We further remark that one can always take the degree of the sos form fγ in
(3) whose positivity is under consideration to be equal to four. This can be done by
changing the general POP in (1) to only have quadratic constraints and a quadratic
objective via an iterative introduction of new variables and new constraints in the
following fashion: xij = xi xj .
Remark 2.3 (Notational remark). As a consequence of Theorem 2.1, we now
know that certifying lower bounds on (1) is equivalent to proving positivity of the form
fγ that appears in (3). To simplify notation, we take this form to have n variables
and be of degree 2d from now on (except for our Positivstellensätze in Corollaries 3.5
and 4.5 which stand on their own). To connect back to problem (1) and the original
notation, the reader should replace every occurrence of n and d in the future as follows:
n ← n + m + 3,

d ← 2d.

Recall that n was previously the dimension of the decision variable of problem (1), d
was such that 2d is the smallest even integer larger than or equal to the maximum
degree of gi and p in (1), and m was the number of constraints of problem (1).
Our next theorem shows that, modulo some technical assumptions, if one can
inner approximate the set of positive definite forms arbitrarily well (conditions (a)
and (b)), then one can construct a converging hierarchy for POPs.
r
Theorem 2.4. Let Kn,2d
be a sequence of sets (indexed by r) of homogeneous
polynomials in n variables and of degree 2d with the following properties:
r
0
(a) Kn,2d
⊆ Pn,2d , ∀r, and there exists a pd form sn,2d ∈ Kn,2d
.
r
(b) If p > 0, then ∃r ∈ N such that p ∈ Kn,2d .
r+1
r
(c) Kn,2d
⊆ Kn,2d
, ∀r.
r
r
(d) If p ∈ Kn,2d
, then ∀ǫ ∈ [0, 1], p + ǫsn,d ∈ Kn,2d
.
Recall the definition of fγ (z) given in (3). Consider the hierarchy of optimization

8
problems indexed by r:
lr := sup

γ

γ

(5)

s.t.

1
r
fγ (z) − sn,2d (z) ∈ Kn,2d
.
r

Then, lr ≤ p∗ for all r, {lr } is nondecreasing, and limr→∞ lr = p∗ .

Proof. We first show that the sequence {lr } is upperbounded by p∗ . Suppose that
a scalar γ satisfies
1
r
.
fγ (z) − sn,2d (z) ∈ Kn,2d
r
We then have fγ (z)− r1 sn,2d (z) ∈ Pn,2d using (a). This implies that fγ (z) ≥ 1r sn,2d (z),
and hence fγ is pd as sn,2d is pd. From Theorem 2.1, it follows that γ has to be a
strict lower bound on (1). As any such γ satisfies γ < p∗ , we have that lr ≤ p∗ for all r.
We now show monotonicity of the sequence {lr }. Let γ be such that
1
r
.
fγ (z) − sn,2d (z) ∈ Kn,2d
r
We have the following identity:
fγ (z) −

1
1
1
sn,2d (z) = fγ (z) − sn,2d (z) +
sn,2d (z).
r+1
r
r(r + 1)

Now, using the assumption and properties (c) and (d), we conclude that
fγ (z) −

1
r+1
sn,2d (z) ∈ Kn,2d
.
r+1

r+1
1
r
This implies that {γ | fγ (z) − 1r sn,2d (z) ∈ Kn,2d
} ⊆ {γ | fγ (z) − r+1
sn,2d (z) ∈ Kn,2d
}
and that lr ≤ lr+1 .

Note that as the sequence {lr } is upperbounded and nondecreasing, it converges.
Let us show that the limit of this sequence is p∗ . To do this, we show that for any strict
lower bound γ on (1), there exists a positive integer r such that fγ (z) − 1r sn,2d (z) ∈
r
Kn,2d
. By Theorem 2.1, as γ is a strict lower bound, fγ (z) is positive definite. Hence,
by continuity, there exists a positive integer r′ such that fγ (z) − r1′ sn,2d (z) is positive
definite. Using (b), this implies that there exists a positive integer r′′ such that
(6)

fγ (z) −

1
r ′′
sn,2d (z) ∈ Kn,2d
.
r′

We now proceed in two cases. If r′′ ≤ r′ , we take r = r′ and use property (c) to
conclude. If r′ ≤ r′′ , we have
fγ (z) −

1
r′′ − r′
1
s
(z)
=
f
(z)
−
s
(z)
+
sn,2d (z).
n,2d
γ
n,2d
r′′
r′
r′ · r′′

We take r = r′′ and use (6) and properties (c) and (d) to conclude.

Remark 2.5. Note that condition (d) is subsumed by the more natural condition
r
that Kn,d
be a convex cone for any n, d, and r. However, there are interesting and relevant cones which we cannot prove to be convex though they trivially satisfy condition
(d) (see Theorem 3.2 for an example).

CONVERGING HIERARCHIES FOR POLYNOMIAL OPTIMIZATION

9

3. Semidefinite programming-based hierarchies obtained from Artin’s
and Reznick’s Positivstellensätze. In this section, we construct two different
semidefinite programming-based hierarchies for POPs using Positivstellensätze derived by Artin (Theorem 1.4) and Reznick (Theorem 1.5). To do this, we introduce
two sets of cones that we call the Artin and Reznick cones.
Definition 3.1. We define the Reznick cone of level r to be
r
Rn,2d
:= {p ∈ Hn,2d | p(x) ·

n
X
i=1

x2i

!r

is sos}.

Similarly, we define the Artin cone of level r to be
Arn,2d := {p ∈ Hn,2d | p(x) · q(x) is sos for some sos form q of degree 2r}.
We show that both of these cones produce hierarchies of the type discussed in
Theorem 2.4. Recall that p∗ is the optimal value of problem (1) and that fγ is defined
as in (3) with the change of notation discussed in Remark 2.3.
Theorem 3.2. Consider the hierarchy of optimization problems indexed by r:
lr := sup

γ

γ

(7)

n
1 X 2 d
r
z ) ∈ Rn,2d
.
fγ (z) − (
r i=1 i

s.t.

Then, lr ≤ p∗ for all r, {lr } is nondecreasing, and limr→∞ lr = p∗ .

r
Proof. It suffices to show that the Reznick cones Rn,2d
satisfy properties (a)-(d)
result
will
then
follow
from
that
theorem.
For property (a),
in Theorem 2.4. The
P
P
it is clear that, as ( i x2i )r > 0 and p(x) · ( i x2i )r is a sum of squares and hence
r
nonnegative, p(x) must be nonnegative, so Rn,2d
⊆ Pn,2d . Furthermore, the form
P 2 d
0
sn,2d := ( i xi ) belongs to Rn,2d and is positive definite. Property (b) is verified
P 2 r
as a consequence
P 2 r+1 of Theorem 1.5. For (c), note that if p(x) · ( i xi ) is sos, then
is sos since the product of two sos polynomials is sos. Finally, for
p(x) · ( i xi )
r
property (d), note that Rn,2d
is a convex cone. Indeed, for any λ ∈ [0, 1],

X
X
X
x2i )r
x2i )r + (1 − λ)q(x)(
x2i )r = λp(x)(
(λp(x) + (1 − λ)q(x)) · (
i

i

i

r
r
is sos if p and q are in Rn,2d
. Combining the fact that Rn,2d
is a convex cone and the
P 2 d
r
fact that ( i xi ) ∈ Rn,d , we obtain (d).

Remark 3.3. To solve a fixed level r of the hierarchy given in Theorem 3.2, one
must proceed by bisection on γ. Bisection here would produce a sequence of upper
bounds {Uk } and lower bounds {Lk } on lr as follows. At iteration k, we test whether
k
k
γ = Uk +L
is feasible for (7). If it is, then we take Lk+1 = Uk +L
and Uk+1 = Uk .
2
2
Uk +Lk
If it is not, we take Uk+1 =
and Lk+1 = Lk . We stop when |Ukǫ − Lkǫ | < ǫ,
2
where ǫ is a prescribed accuracy, and the algorithm returns lr,ǫ = Lkǫ . Note that
lr − ǫ ≤ lr,ǫ ≤ lr and that to obtain lr,ǫ , one needs to take a logarithmic (in 1ǫ ) number
of steps using this method.

10
Hence, solving the rth level of this hierarchy using bisection can be done by
semidefinite programming. Indeed, for a fixed r and γ given by the bisection algorithm, one simply needs to test membership of
!
X
1 X 2 d
fγ (z) − (
zi2 )r
zi ) · (
r i
i
to the set of sum of squares polynomials. This amounts to solving a semidefinite
program. We remark that all semidefinite programming-based hierarchies available
only produce an approximate solution to the optimal value of the SDP solved at level
r in polynomial time. This is independent of whether they use bisection (e.g., such as
the hierarchy given in Theorem 3.2 or the one based on Stengle’s Positivstellensatz)
or not (e.g., the Lasserre hierarchy).
PnOur next theorem improves on our previous hierarchy by freeing the multiplier
( i=1 zi2 )r and taking advantage of our ability to search for an optimal multiplier
using semidefinite programming.
Theorem 3.4. Recall the definition of Artin cones from Definition 3.1. Consider
the hierarchy of optimization problems indexed by r:
lr := sup

γ

γ,q

(8)
s.t.

n
1 X 2 d
z ) ∈ Arn,2d .
fγ (z) − (
r i=1 i

Then, lr ≤ p∗ for all r, {lr } is nondecreasing, and limr→∞ lr = p∗ .

Proof. Just as the previous theorem, it suffices to show that the Artin cones Arn,2d
satisfy properties (a)-(d) of Theorem 2.4. The proof of property (a) follows the proof
given for Theorem 3.2. Property (b) is satisfied as a (weaker) consequence of Artin’s
sos for some sos
result (see Theorem 1.4). For (c), we have
P that if p(x) · q(x) isP
polynomial of degree 2r, then p(x) · q(x) · ( i x2i ) is sos, and q(x) · ( i x2i ) has degree
2(r + 1). Finally, for (d), suppose that p ∈ Arn,2d . Then there exists an sos form q
such that p(x) · q(x) is sos. We have
!
X
X
2 d
x2i )d · q(x),
xi ) · q(x) = p(x) · q(x) + ǫ(
p(x) + ǫ(
i

i

which is sos as the product (resp. sum) of two sos polynomials is sos.
Note that again, for any fixed r, the level r of the hierarchy can be solved using
bisection which leads to a sequence of semidefinite programs.
Our developments in the past two sections can be phrased in terms of a Positivstellensatz.
Corollary 3.5 (A new Positivstellensatz).

Consider the basic semialgebraic

set
S := {x ∈ Rn | gi (x) ≥ 0, i = 1, . . . , m}

and a polynomial p := p(x). Suppose that S is contained within a ball of radius R.
Let ηi and β be any finite upperbounds on gi (x) and, respectively, −p(x) over the set
S.3 Let d be such that 2d is the smallest integer larger than or equal to the maximum
3 As

discussed at the beginning of Section 2, such bounds are very easily computable.

11

CONVERGING HIERARCHIES FOR POLYNOMIAL OPTIMIZATION

degree of p, gi , i = 1, . . . , m. Then, p(x) > 0 for all x ∈ S if and only if there exists a
positive integer r such that

r
2d  

m+1
m+1
n
n
X
X
X
X
1


s2j + y 2 
s2j + y 2   · 
x2i +
x2 +
h(x, s, y) − 
r i=1 i
j=0
j=0
i=1
is a sum of squares, where the form h in variables (x1 , . . . , xn , s0 , . . . , sm+1 , y) is as
follows:
h(x, s, y) := y 2d p(x/y) + s20 y 2d−2
+

(R +

m
X
i=1

2

+

m
X
i=1

y 2d gi (x/y) − s2i y 2d−2

2

m
n
X
X
s2i )d − s2d
x2i +
ηi + β)d y 2d − (
m+1
i=1

i=0

!2

.

Proof. This is an immediate corollary of arguments given in the proof of Theorem
2.1 and in the proof of Theorem 3.2 for the case where γ = 0.
4. Polyá’s theorem and hierarchies for POPs that are optimizationfree, LP-based, and SOCP-based. In this section, we use a result by Polyá on
global positivity of even forms to obtain new hierarchies for polynomial optimization
problems. In Section 4.1, we present a hierarchy that is optimization-free, in the sense
that each level of the hierarchy only requires multiplication of two polynomials and
checking if the coefficients of the resulting polynomial are nonnegative. In Section 4.2,
we use the previous hierarchy to derive linear programming and second-order cone
programming-based hierarchies with faster convergence. These rely on the recently
developed concepts of dsos and sdsos polynomials (see Definition 4.7 and [3]), which
are alternatives to sos polynomials that have been used in diverse applications to
improve scalability; see [3, Section 4].
4.1. An optimization-free hierarchy of lower bounds for POPs. The
main theorem in this section presents an optimization-free hierarchy of lower bounds
for general POPs with compact feasible sets:
Theorem 4.1. Recall the definition of fγ (z) as given in (3), with z ∈ Rn and
deg(fγ ) = 2d. Let (v, w) ∈ R2n and define
(9)
!
n
X
X
2
1 X 4
4 d
r
2
2
vi2 +
P oln,2d := {p ∈ Hn,2d | p(v − w ) + ( (vi + wi )) · (
wi2 )r
2r i=1
i
i
has nonnegative coefficients }.

Consider the hierarchy of optimization problems indexed by r:
lr := sup

γ

γ

(10)
s.t.

n
1 X 2 d
r
z ) ∈ P oln,2d
.
fγ (z) − (
r i=1 i

Let mr = maxi=1,...,r li . Then mr ≤ p∗ for all r, {mr } is nondecreasing, and
limr→∞ mr = p∗ .

12
As before, we use bisection to obtain the optimal value lr of the rth level of the
hierarchy up to a fixed precision ǫ (see Remark 3.3). At each step of the bisection
algorithm, one simply needs to multiply two polynomials together and check nonnegativity of the coefficients of the resulting polynomial to proceed to the next step. As
a consequence, this hierarchy is optimization-free as we do not need to solve (convex)
optimization problems at each step of the bisection algorithm. To the best of our
knowledge, no other converging hierarchy of lower bounds for general POPs dispenses
altogether with the need to solve convex subprograms. We also provide a Positivstellensatz counterpart to the hierarchy given above (see Corollary 4.5). This corollary
implies in particular that one can always certify infeasibility of a basic semialgebraic
set by recursively multiplying polynomials together and simply checking nonnegativity
of the coefficients of the resulting polynomial.
We now make a few remarks regarding the techniques used in the proof of Theor
rem 4.1. Unlike Theorems 3.2 and 3.4, we do not show that P oln,d
satisfies properties
(a)-(d) as given in Theorem 2.4 due to some technical difficulties. It turns out however that we can avoid showing properties (c) and (d) by using a result by Reznick
and Powers [18] that we present below. Regarding properties (a) and (b), we show
that a slightly modified version of (a) holds and that (b), which is the key property
in Theorem 2.4, goes through as is. We note though that obtaining (b) from Polyá’s
result (Theorem 1.6) is not as immediate as obtaining (b) from Artin’s and Reznick’s
results. Indeed, unlike the theorems by Artin and Reznick (see Theorems 1.4 and
1.5) which certify global positivity of any form, Polyá’s result only certifies global
positivity of even forms. To make this latter result a statement about general forms,
we work in an appropriate lifted space. This is done by replacing any form p(z) in
variables z ∈ Rn by the even form p(v 2 − w2 ) in variables (v, w) ∈ R2n . This lifting
operation preserves nonnegativity, but unfortunately it does not preserve positivity:
even if p(z) is pd, p(v 2 − w2 ) always has zeros (e.g., when v = w). Hence, though we
now have access to an even form, we still cannot use Polyá’s property as p(v 2 − w2 )
is not positive. This
P is what leads us to consider the slightly more complicated form
1
( i vi4 + wi4 )d in (9).
p(v 2 − w2 ) + 2r
Theorem 4.2 (Powers and Reznick [18]). Let α = (α1 , . . . , αn ) ∈ Nn , xα =
n
. . . xα
n , and write |α| = α1 +. . .+αn . Denote the standard simplex by ∆n . Assume
that f is a form of degree 2d that is positive on ∆n and let

1
xα
1

λ = λ(f ) := min f (x).
x∈∆n

Define c(α) =

(2d)!
α1 !...αn ! .

We have:
f (x) =

X

|α|=2d

aα xα =

X

bα c(α)xα .

|α|=2d

Let ||f (x)|| := max|α|=2d |bα |.4
Then, the coefficients of
f (x1 , . . . , xn ) · (x1 + . . . + xn )N
are nonnegative for N > d(2d − 1) ||f (x)||
− 2d.
λ
4 As

defined, ||f || is a submultiplicative norm; see [23].

CONVERGING HIERARCHIES FOR POLYNOMIAL OPTIMIZATION

13

Note that here the bound is given in the case where one considers the alternative
(but equivalent) formulation of Polyá’s Positivstellensatz to the one given in Theorem
1.6, i.e., when one is concerned with positivity of a form over the simplex. The result
can easily be adapted to the formulation where one considers global positivity of an
even form as shown below.
Lemma 4.3. Let p := p(x) be an even form of degree 2d that is positive definite.
Let β > 0 be its minimum on Sx . Then,
X
x2i )N
p(x1 , . . . , xn ) · (
i

√

has nonnegative coefficients for N > d(2d − 1) ||p( β x)|| − 2d.
√
√
Proof. Let f (x1 , . . . , xn ) = p( x1 , . . . , xn ). Since p(x) ≥ β on Sx , then f (x) ≥
β on ∆n . Indeed, by contradiction, suppose
√ that there existsPx̂ ∈ ∆n such that
fP(x̂) = β − ǫ (where ǫ > 0) and let y = x̂. Note that as
i x̂i = 1, we have
2
y
=
1.
Furthermore,
p(y)
=
f
(x̂)
=
β
−
ǫ
which
contradicts
the assumption.
i i
√
||p( x)||
− 2d,
Hence, using Theorem 4.2, we have that when N > d(2d − 1) β
X
xi )N
f (x)(
i

has nonnegative coefficients. Hence,
X
X
yi2 )N
yi2 )N = p(y)(
f (y 2 )(
i

i

also has nonnegative coefficients.
Before we proceed with the proof of Theorem 4.1, we need the following lemma.
Lemma 4.4. Let
(11)

n
n
1 X
1 X
pγ,r (v, w) := fγ (v 2 − w2 ) − ( (vi2 − wi2 )2 )d + ( (vi4 + wi4 ))d ,
r i=1
2r i=1

where fγ is defined as in (3) and let
N (r) = d(2d − 1) ·

√ √
||pγ,r ( v, w)||
− 2d.
minSv,w pγ,r (v, w)

If fγ (z) is positive definite, there exists r̂ such that r2 ≥ N (r), for all r ≥ r̂.

Proof. P
As fγ (z) is positive definite, there exists a positive integer r0 such that
fγ (z) − r1 ( i zi2 )d is positive definite for all r ≥ r0 and hence

(12)

1 X
fγ (v 2 − w2 ) − ( (vi2 − wi2 )2 )d
r i

P
is nonnegative for all r ≥ r0 . Recall now that ||x||p = ( i xpi )1/p is a norm for p ≥ 1
and that
√
||x||2 ≤ n||x||4 .

14
This implies that
X
X
wi4 )d ≥
vi4 +
(
i

i

X
X
1
wi2 )2d
vi2 +
(
2d
(2n)
i
i

and hence in view of (12) and the definition of pγ,r , we have
pγ,r (v, w) ≥

X
X
1
2
wi2 )2d , ∀r ≥ r0 .
v
+
(
i
22d+1 n2d r i
i

This enables us to conclude that
(13)

min pγ,r (v, w) ≥
Sv,w

1
, for any r ≥ r0 .
22d+1 n2d r

Further, notice that using properties of the norm, we have the following chain of
inequalities for any positive integer r:
√ √
1 X
1 X
||pγ,r ( v, w)|| ≤ ||fγ (v − w)|| + ||( (vi − wi )2 )d || + ||( (vi2 + wi2 ))d ||
r
2r
i
i
X
X
2
2 d
vi + wi2 )d || =: cγ .
≤ ||fγ (v − w)|| + ||( (vi − wi ) ) || + ||(
i

i

As a consequence, combining this with the definition of N (r) and (13), we have
N (r) ≤ d(2d − 1)22d+1 rn2d cγ , ∀r ≥ r0 .
Now taking r̂ = max(r0 , ⌈d(2d − 1)22d+1 n2d cγ ⌉), we have r2 ≥ N (r), ∀r ≥ r̂.

We now proceed with the proof of Theorem 4.1.

Proof of Theorem 4.1. By definition, the sequence {mr } is nondecreasing. We
show that it is upperbounded by p∗ by showing that if γ is such that
1 X 2 d
r
fγ (z) − (
z ) ∈ P oln,2d
,
r i i
for some r, then fγ must be positive definite. Then Theorem 2.1 gives us that γ is
a strict lower bound on (1). As p∗ > γ for any such γ, we have that lr ≤ p∗ , ∀r and
hence mr ≤ p∗ , ∀r.
Assume that γ is such that
1 X 2 d
r
fγ (z) − (
z ) ∈ P oln,2d
r i i
P
P
2
r
for some r. By definition of P oln,2d
and as ( i vi2 + i wi2 )r is nonnegative, we get
that the form
1 X
1 X 4
fγ (v 2 − w2 ) − ( (vi2 − wi2 )2 )d + (
v + wi4 )d
r i
2r i i
is nonnegative. This implies that
(14)
X
X
1 X
1
fγ (v 2 − w2 ) − ( (vi2 − wi2 )2 )d ≥ −
wi4 = 1},
vi4 +
for (v, w) ∈ {(v, w) |
r i
2r
i
i

CONVERGING HIERARCHIES FOR POLYNOMIAL OPTIMIZATION

15

which gives
1 X 2 d
1
fγ (z) − (
z ) ≥ − , ∀z ∈ Sz .
r i i
2r

(15)

Indeed, suppose that there exists ẑ ∈ Sz such that (15) does not hold. Then, let
−
+
−
ẑ + = max(ẑ, 0) and
√ ẑ = max(−ẑ,
√ 0). Note that both ẑ and ẑ are nonnegative so
+
−
we
take
have that as ẑ ∈ Sz and ẑ = v̂ 2 − ŵ2 ,
P v̂ 4= ẑ and ŵ = ẑ . We2further
P can
2
4
i ŵi = 1. Substituting ẑ by v̂ − ŵ in (15) then violates (14). Using (15),
i v̂i +
we conclude that
1
fγ (z) ≥ , ∀z ∈ Sz
2r
and that fγ is positive definite.
We now show that the hierarchy converges, i.e., that limr→∞ mr = p∗ . To do
this, we show that if γ is a strict lower bound on (1), or equivalently from Theorem
2.1, if fγ (z) is positive definite, then there exists r′ such that
fγ (z) −

1 X 2 d
r′
z ) ∈ P oln,2d
.
(
r′ i i

Pn
Since fγ is pd, there exists a positive integer r0 such
that fγ (z) − r1 ( i=1 zi2 )d is pd
P
1
for any r ≥ r0 . This implies that fγ (v 2 − w2 ) − r ( i (vi2 − wi2 )2 )d is nonnegative and
1 X
1 X
fγ (v 2 − w2 ) − ( (vi2 − wi2 )2 )d + ( (vi4 + wi4 ))d
r i
2r i

is positive definite for r ≥ r0 . Using Lemma 4.3 and the definition of N (r) in Lemma
4.4, for any r ≥ r0 , we have that
!
X
X
1 X 4
1 X 2
2 2 d
4 d
2
2
wi2 )⌈N (r)⌉
vi2 +
fγ (v − w ) − ( (vi − wi ) ) + ( (vi + wi )) · (
r i
2r i
i
i
has nonnegative coefficients. From Lemma 4.4, there exists r̂ such that r ≥ r̂ implies
r2 ≥ N (r). Taking r′ = max{r0 , r̂} and considering pγ,r′ as defined in (11), we get
that
X
X
′2
wi2 )r
vi2 +
pγ,r′ (v, w)(
i

i

X
X
X
X
′2
′
′
wi2 )r −⌈N (r )⌉
vi2 +
wi2 )⌈N (r )⌉ · (
vi2 +
= pγ,r′ (v, w)(
i

i

i

i

has nonnegative coefficients, which is the desired result. This is because
X
X
′
wi2 )⌈N (r )⌉
vi2 +
pγ,r′ (v, w)(
i

i

has nonnegative coefficients as r′ ≥ r0 , and
X
X
′2
′
wi2 )r −⌈N (r )⌉
vi2 +
(
i

i

has nonnegative coefficients as r′ ≥ r̂, and that the product of two polynomials with
nonnegative coefficients has nonnegative coefficients.

16
Corollary 4.5 (An optimization-free Positivstellensatz).
semialgebraic set
S := {x ∈ Rn | gi (x) ≥ 0, i = 1, . . . , m}

Consider the basic

and a polynomial p := p(x). Suppose that S is contained within a ball of radius R. Let
ηi and β be any finite upperbounds on gi (x) and, respectively, −p(x) over the set S.5
Let d be such that 2d is the smallest even integer larger than or equal to the maximum
degree of p, gi , i = 1, . . . , m. Then, p(x) > 0 for all x ∈ S if and only if there exists a
positive integer r such that
!
n+m+3
n+m+3
1 X
1 X
2
2
2
2 2 d
4
4 d
h(v − w ) − (
(vi − wi ) ) + (
(vi + wi ))
r i=1
2r i=1
!r 2
n+m+3
n+m+3
X
X
2
2
wi
vi +
·
i=1

i=1

has nonnegative coefficients, where the form h := h(z) in variables
(z1 , . . . , zn+m+3 ) := (x1 , . . . , xn , s0 , . . . , sm+1 , y)
is as follows:
h(x, s, y) := y 2d p(x/y) + s20 y 2d−2
+

(R +

m
X
i=1

2

+

d 2d

ηi + β) y

m
X
i=1

y 2d gi (x/y) − s2i y 2d−2

2

m
n
X
X
s2i )d − s2d
x2i +
−(
m+1
i=1

i=0

!2

.

Proof. This is an immediate corollary of arguments given in the proof of Theorem 2.1 and in the proof of Theorem 4.1 for the case where γ = 0.
4.2. Linear programming and second-order cone programming-based
hierarchies for POPs. In this section, we present a linear programming and a
second-order cone programming-based hierarchy for general POPs which by construction converge faster than the hierarchy presented in Section 4.1. These hierarchies are
based on the recently-introduced concepts of dsos and sdsos polynomials [3] which we
briefly revisit below to keep the presentation self-contained.
Definition 4.6. A symmetric matrix M
P is said to be
• diagonally dominant (dd) if Mii ≥ j6=i |Mij | for all i.
• scaled diagonally dominant (sdd) if there exists a diagonal matrix D, with
positive diagonal entries, such that DAD is dd.
We have the following implications as a consequence of Gershgorin’s circle theorem:
(16)

M dd ⇒ M sdd ⇒ M  0.

Requiring M to be dd (resp. sdd) can be encoded via a linear program (resp. a
second-order cone program) (see [3] for more details). These notions give rise to the
concepts of dsos and sdsos polynomials.
5 Once

again, as discussed at the beginning of Section 2, such bounds are very easily computable.

CONVERGING HIERARCHIES FOR POLYNOMIAL OPTIMIZATION

17

Definition 4.7 ([3]). Let z(x) = (xd1 , xd−1
x2 , . . . , xdn )T be the vector of mono1
mials in (x1 , . . . , xn ) of degree d. A form p ∈ Hn,2d is said to be
• diagonally-dominant-sum-of-squares (dsos) if it admits a representation
p(x) = z T (x)Qz(x), where Q is a dd matrix.
• scaled-diagonally-dominant-sum-of-squares (sdsos) if it admits a representation
p(x) = z T (x)Qz(x), where Q is a sdd matrix.
The following implications are a consequence of (16):
(17)

p(x) dsos ⇒ p(x) sdsos ⇒ p(x) sos ⇒ p(x) nonnegative.

Given the fact that our Gram matrices and polynomials are related to each other via
linear equalities, it should be clear that optimizing over the set of dsos (resp. sdsos)
polynomials is an LP (resp. SOCP).
We now present our LP and SOCP-based hierarchies for POPs.
Corollary 4.8. Recall the definition of fγ (z) as given in (3), with z ∈ Rn and
deg(f ) = 2d, and let pγ,r be as in (11). Consider the hierarchy of optimization
problems indexed by r:
lr := sup

γ

γ,q

(18)

s.t.

pγ,r (v, w) · q(v, w) is s/dsos

q(v, w) is s/dsos and of degree 2r2 .
Let mr = maxi=1,...,r li . Then, mr ≤ p∗ for all r, {mr } is nondecreasing, and we have
limr→∞ mr = p∗ .
Proof. This is an immediate consequence of the fact that any even form p ∈ Hn,2d
with nonnegative coefficients can be written as p(x) = z(x)T Qz(x) where Q is diagonal
and has nonnegative (diagonal) entries. As such a Q is dd (and also sdd), we conclude
that p is dsos (and also sdsos). The corollary then follows from Theorem 4.1.
Note that similarly to our previous hierarchies, one must proceed by bisection on
γ to solve the level r of the hierarchy. At each step of the hierarchy, we solve a linear
program (resp. second-order cone program) that searches for the coefficients of q that
make q dsos (resp. sdsos) and pγ,r · q dsos (resp. sdsos).
There is a trade-off between the hierarchies developed in this subsection and the
one developed in the previous subsection: the hierarchy of Section 4.1 is optimizationfree whereas those of Section 4.2 use linear or second-order cone programming. Hence
the former hierarchy is faster to run at each step. However, the latter hierarchies could
potentially take fewer levels to converge. This is similar to the trade-off observed
between the hierarchies presented in Theorems 3.2 and 3.4.
5. Open problems. To conclude, we present two open problems spawned by
the writing of this paper. The first one concerns the assumptions needed to construct
our hierarchies.
Open problem 1. Theorems 2.1 and 2.4 require that the feasible set S of the POP
given in (1) be contained in a ball of radius R. Can these theorems be extended to
the case where there is no compactness assumption on S?
The second open problem is linked to the Artin and Reznick cones presented in
Definition 3.1.

18
r
Open problem 2. As mentioned before, Reznick cones Rn,2d
are convex for all r.
r
We are unable to prove however that Artin cones An,2d are convex (even though they
satisfy properties (a)-(d) of Theorem 2.4 like Reznick cones do). Are Artin cones
convex for all r? We know that they are convex for r = 0 and for r large enough as
they give respectively the sos and psd cones (see [12] for the latter claim). However,
we do not know the answer already for r = 1.

Acknowledgments. We are grateful to Pablo Parrilo for very insightful comments, particularly as regards Section 4 and the observation that any form can be
made even by only doubling the number of variables and the degree.
REFERENCES
[1] A. A. Ahmadi, On the difficulty of deciding asymptotic stability of cubic homogeneous vector
fields, in Proceedings of the American Control Conference, 2012.
[2] A. A. Ahmadi and A. Majumdar, Some applications of polynomial optimization in operations research and real-time decision making, Optimization Letters, 10 (2016), pp. 709–729.
[3] A. A. Ahmadi and A. Majumdar, DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization, (2017). Available on arXiv at
https://arxiv.org/abs/1706.02586.
[4] E. Artin, Über die Zerlegung definiter Funktionen in Quadrate, in Abhandlungen aus dem
mathematischen Seminar der Universität Hamburg, vol. 5, Springer, 1927, pp. 100–115.
[5] G. Averkov, Constructive proofs of some Positivstellensätze for compact semialgebraic subsets
of Rd , Journal of Optimization Theory and Applications, 158 (2013), pp. 410–418.
[6] G. Blekherman, P. A. Parrilo, and R. R. Thomas, Semidefinite Optimization and Convex
Algebraic Geometry, SIAM, 2012.
[7] E. de Klerk, M. Laurent, and P. Parrilo, On the equivalence of algebraic approaches
to the minimization of forms on the simplex, Positive Polynomials in Control, (2005),
pp. 580–580.
[8] W. Habicht, Über die Zerlegung strikte definiter Formen in Quadrate, Commentarii Mathematici Helvetici, 12 (1939), pp. 317–322.
[9] J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM
Journal on Optimization, 11 (2001), pp. 796–817.
[10] J. B. Lasserre, Moments, Positive Polynomials and their Applications, vol. 1, World Scientific, 2009.
[11] M. Laurent, Sums of squares, moment matrices and optimization over polynomials, in Emerging applications of algebraic geometry, Springer, 2009, pp. 157–270.
[12] H. Lombardi, D. Perrucci, and M.-F. Roy, An elementary recursive bound for effective
Positivstellensatz and Hilbert 17-th problem, arXiv preprint arXiv:1404.2338, (2014).
[13] J. Nie and M. Schweighofer, On the complexity of Putinar’s Positivstellensatz, Journal of
Complexity, 23 (2007), pp. 135–150.
[14] P. M. Pardalos and S. A. Vavasis, Quadratic programming with one negative eigenvalue is
NP-hard, Journal of Global Optimization, 1 (1991), pp. 15–22.
[15] P. A. Parrilo, Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization, PhD thesis, California Institute of Technology, May 2000.
[16] P. A. Parrilo, Semidefinite programming relaxations for semialgebraic problems, Mathematical Programming, 96 (2003), pp. 293–320.
[17] G. Pólya, Über positive Darstellung von Polynomen, Vierteljschr. Naturforsch. Ges. Zürich,
73 (1928), pp. 141–145.
[18] V. Powers and B. Reznick, A new bound for Pólya’s theorem with applications to polynomials positive on polyhedra, Journal of pure and applied algebra, 164 (2001), pp. 221–229.
[19] M. Putinar, Positive polynomials on compact semi-algebraic sets, Indiana University Mathematics Journal, 42 (1993), pp. 969–984.
[20] B. Reznick, Uniform denominators in Hilbert’s 17th problem, Math Z., 220 (1995), pp. 75–97.
[21] K. Schmüdgen, The k-moment problem for compact semi-algebraic sets, Mathematische Annalen, 289 (1991), pp. 203–206.
[22] M. Schweighofer, An algorithmic approach to Schmüdgen’s Positivstellensatz, Journal of
Pure and Applied Algebra, 166 (2002), pp. 307–319.
[23] M. Schweighofer, On the complexity of Schmüdgen’s Positivstellensatz, Journal of Complexity, 20 (2004), pp. 529–543.

CONVERGING HIERARCHIES FOR POLYNOMIAL OPTIMIZATION

19

[24] M. Schweighofer, Optimization of polynomials on compact semialgebraic sets, SIAM Journal
on Optimization, 15 (2005), pp. 805–825.
[25] G. Stengle, A Nullstellensatz and a Positivstellensatz in semialgebraic geometry, Mathematische Annalen, 207 (1974), pp. 87–97.

