COMPUTATION WITH POLYNOMIAL EQUATIONS AND

INEQUALITIES ARISING IN COMBINATORIAL

OPTIMIZATION
JESUS A. DE LOERA∗ , PETER N. MALKIN† , AND PABLO A. PARRILO‡

Abstract. The purpose of this note is to survey a methodology to solve systems

of polynomial equations and inequalities. The techniques we discuss use the algebra of
multivariate polynomials with coefficients over a field to create large-scale linear algebra
or semidefinite programming relaxations of many kinds of feasibility or optimization
questions. We are particularly interested in problems arising in combinatorial optimiza-
tion.

Key words. Polynomial equations and inequalities, combinatorial optimization,

Nullstellensatz, Positivstellensatz, graph colorability, max-cut, semidefinite program-
ming, large-scale linear algebra.

AMS(MOS) subject classifications. 90C27, 90C22, 68W05

1. Introduction. A wide variety of problems in optimization can be

easily modeled using systems of polynomial equations and inequalities. Fea-
sibility and optimization problems translate, either directly or via branch-
ing, into the problem of finding a solution of a system of equations and
inequalities. In this survey paper, we explain how to manipulate such sys-
tems for finding solutions or proving that they do not exist. Although these
techniques work in general, we are particularly motivated by problems of
combinatorial origin. For example, in the case of graphs, here is how one
can think about stable sets, k-colorability and max-cut problems in terms
of polynomial (non-linear) constraints:
Proposition 1.1. Let G = (V, E) be a graph.
• For a given positive integer k, consider the following polynomial
system:
X
x2i − xi = 0 ∀i ∈ V, xi xj = 0 ∀(i, j) ∈ E and xi = k.
i∈V

This system is feasible if and only if G has a stable set of size k.

• For a positive integer k, consider the following polynomial system

∗ Department of Mathematics, University of California at Davis, Davis, CA 95616

(deloera@math.ucdavis.edu); partially supported by NSF and an IBM OCR award

† Department of Mathematics, University of California at Davis, Davis, CA 95616

(malkin@math.ucdavis.edu); partially supported by an IBM OCR award.

‡ Laboratory for Information and Decision Systems, Department of Electrical Engi-

neering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA

02139 (parrilo@mit.edu); partially supported by AFOSR MURI 2003-07688-1 and NSF
FRG DMS-0757207.
1
2 J.A. DE LOERA, P.N. MALKIN AND P.A. PARRILO

of |V | + |E| polynomials equations:

k−1
X
xki − 1 = 0 ∀i ∈ V and xik−1−s xsj = 0 ∀(i, j) ∈ E.
s=0

The graph G is k-colorable if and only if this system has a complex

solution. Furthermore, when k is odd, G is k-colorable if and only
if this system has a common root over F2 , the algebraic closure of
the finite field with two elements.
• We can represent the set of cuts of G (i.e., bipartitions on V ) as
the 0-1 incidence vectors

SG := {χF : F ⊆ E is contained in a cut of G} ⊆ {0, 1}E .

Thus, the max cut problem with non-negative weights we on the

edges e ∈ E is
X
max{ we xe : x ∈ SG}.
e∈E

The vectors χF are the solutions of the polynomial system

Y
x2e − xe = 0 ∀ e ∈ E, and xi = 0 ∀ T an odd cycle in G.
i∈T

There are many other combinatorial problems that can be modeled

concisely by polynomial systems (see [9] and the many references therein).
In fact, a given problem can often be modeled non-linearly in many differ-
ent ways, and in practice choosing a “good” formulation is critical for an
efficient solution.
Given a polynomial system encoding a combinatorial question, we ex-
plain how to use two famous algebraic identities to derive solution methods.
In what follows, let K denote a field and let K denote the algebraic clo-
sure of K. Let R = K[x1 , . . . , xn ] = K[x] denote the ring of polynomials
in n variables with coefficients over K. The situation is slightly different
depending on whether only equations are being considered, or if there also
inequalities (more precisely, on whether the underlying field K[x] is alge-
braically closed or formally real):
1. First, suppose that the system contains only the polynomial equa-
tions f1 (x) = 0, f2 (x) = 0, . . . , fs (x) = 0 where f1 , ..., fs ∈ K[x].
We explain how to generate a finite sequence of linear algebra sys-
tems which terminate with either a solution over K of the problem
or provide a certificate of infeasibility. The calculations reduce to
matrix manipulations, mostly rank computations. The techniques
we use are a specialization of prior techniques from computational
algebra (see [36, 20, 21, 37]). As it turns out this technique is par-
ticularly effective when the number of solutions is finite, when K
 POLYNOMIALS IN COMBINATORIAL OPTIMIZATION 3

is a finite field, or when the system has nice combinatorial infor-

mation (see [9]).
2. Second, several authors (see e.g. [23, 40, 28] and references therein)
considered the solvability (over the reals) of systems of polynomial
equations and inequalities. It was shown that in this situation
there is a way to set up the feasibility problem

∃x ∈ Rn s.t. f1 (x) = 0, . . . , fs (x) = 0, g1 (x) ≥ 0, . . . , gk (x) ≥ 0,

where f1 , . . . , fs , g1 , . . . , gk ∈ R[x], as a sequence of semidefinite

programs terminating with a feasible solution (see [28]). Once
more, the combinatorial structure can help in the understanding
of the structure of these relaxations, as is well-known from the case
of stable sets [31] and max-cut [27]. In recent work, Gouveia et al.
[15, 14] considered a sequence of semidefinite relaxations of the con-
vex hull of real solutions to an arbitrary combinatorial polynomial
system. They called these approximations theta bodies because for
stable sets of graphs the first theta body in this hierarchy is exactly
Lovász’s theta body of a graph [31].
The common central idea to both of the relaxations procedures de-
scribed above is to use the right infeasibility certificates or theorems of
alternative. Just as Farkas’ lemma is a centerpiece for the development of
Linear Programming, here the key point is that the infeasibility of poly-
nomial systems can always be certified by particular algebraic identities
(on non-linear polynomials). To find these infeasibility certificates we rely
either on linear algebra or semidefinite programming (for a quick overview
of semidefinite programming see [49]).
We now state the necessary notation and algebraic concepts that jus-
tify our approach. For a detailed introduction we recommend the books
[5, 6, 2, 35]. We denote the monomials in the polynomial ring R =
K[x1 , . . . , xn ] = K[x] as xα P := xα 1 α2 αn n
1 x2 · · · xn for α ∈ N . The degree
α α n
of x is deg(x ) := |α| := i=1 αi . The degree of a polynomial f =
α
the maximum degree of xα where fα 6= 0
P
α∈N n f α x , written deg(f ), is
n
for α ∈ N . Given a set of polynomials F ⊂ R, we write deg(F ) for the
maximum degree of the polynomials in F . The variety of F over K, writ-
ten VK (F ), is the set of common zeros of polynomials in F in Kn , that is,
VK (F ) := {v ∈ Kn : f (v) = 0 ∀f ∈ I}. Also, VK (F ), the variety of F
n
over K, is the set of common zeros of F in K . Note that in combinatorial
problems, the variety of a polynomial system typically has finitely many
solutions (e.g., colorings, cuts, stable sets, etc.).
Given a set of polynomials F := {f1 , . . . , fm } ⊆ R = K[x], we define
the ideal of F as
(m )
X
hF iR := hf1 , . . . , fm iR := βi fi | β1 , . . . , βm ∈ K[x] .
i=1
4 J.A. DE LOERA, P.N. MALKIN AND P.A. PARRILO

For an ideal I ⊆ R, when VK (I) is finite, the ideal is called zero-dimensional

(this is the case for all of the applications considered here). An ideal I ⊆ R
k
√ radical if f ∈ I for some positive integer k implies
is
k
f ∈ I. We denote by
I the ideal of all polynomials
√ f ∈ R such that f ∈ I for some positive
integer k. The ideal I is necessarily radical and √ it is called the radical
ideal of I. Note that I is radical if and only if I = I.
To study of varieties over a non-algebraically closed field like R requires
extra structure. Given a set of real polynomials G := {g1 , . . . , gm } ⊆ R[x],
we define the cone of G as
X X X
cone(G) := {g | g = s0 + si g i + sij gi gj + sijk gi gj gk + · · · },
{i} {i,j} {i,j,k}

where each term in the sum is a square-free product of the polynomials gi ,

with a coefficient sα ∈ R[x] that is a sums of squares. The sum is finite,
with a total of 2m − 1 terms, corresponding to the nonempty subsets of
{g1 , . . . , gm }.
The notions of ideal and cone are standard in real algebraic geom-
etry, but they also have inherent convex geometry: Ideals are affine sets
and cones are closed under convex combinations and non-negative scal-
ings, i.e., they are actually cones in the convex geometry sense. Ideals
and cones are used for deriving new valid constraints, which are logical
consequences of the given constraints. For example, notice that by con-
struction, every polynomial in hf1 , . . . , fm iR vanishes in the solution set
of the system f1 (x) = 0, . . . , fm (x) = 0 over the algebraic closure of K.
Similarly, every element of cone(gi ) is clearly non-negative on the feasible
set of g1 (x) ≥ 0, . . . , gm (x) ≥ 0.
It is well-known that optimization algorithms are intimately tied to the
development of feasibility certificates. For example, the simplex method is
closely related to Farkas’ lemma. Our starting point is a generalization of
this famous principle. We start with a description of two powerful infea-
sibility certificates for polynomial systems which generalizes the classical
ones for linear optimization. First, recall from elementary linear algebra
the “Fredholm alternative theorem” (e.g., [44]):
Theorem 1.1 (Fredholm’s alternative). Given a matrix A ∈ Km×n
and a vector b ∈ Km ,

∄ x ∈ Kn s.t. Ax + b = 0 ⇔ ∃ µ ∈ Km s.t. µT A = 0, µT b = 1.

It turns out that there are much stronger versions for general polynomials,
which unfortunately does not seem to be widely known among optimizers
(for more details see e.g., [5]).
Theorem 1.2 (Hilbert’s Nullstellensatz). Let F := {f1 , . . . , fm } ⊆
K[x]. Then,
n
∄ x ∈ K s.t. f1 (x) = 0, ..., fs (x) = 0 ⇔ 1 ∈ hF iR .
 POLYNOMIALS IN COMBINATORIAL OPTIMIZATION 5

Note that 1 ∈ PhF iR means that there exist polynomials β1 , . . . , βm ∈

m
K[x] such that 1 = i=1 βi fi . Note that Fredholm’s alternative theorem is
simply a special case of Hilbert’s Nullstellensatz where all the polynomials
are linear and the βi ’s are constant.
Now, the two theorems above deal only with the case of equations.
The inclusion of inequalities in the problem formulation poses additional
algebraic challenges because we need to take into account special properties
of the reals. Consider first the case of linear inequalities where linear
programming duality provides the following characterization:
Theorem 1.3 (Farkas’ lemma). Let A ∈ Rm×n , b ∈ Rm , C ∈ Rk×n ,
and d ∈ Rk .

∄ x ∈ Rn s.t. Ax + b = 0, Cx + d ≥ 0
m
∃λ ∈ Rm
+, ∃µ ∈ R k
s.t. µ A + λT C = 0, µT b + λT d = −1.
T

Again, although not widely known in optimization, it turns out that sim-
ilar certificates do exist for arbitrary systems of polynomial equations and
inequalities over the reals. The result essentially appears in this form in
[2], and is due to Stengle [47].
Theorem 1.4 (Positivstellensatz). Let F := {f1 , . . . , fm } ⊂ R[x] and
G := {g1 , . . . , gk } ⊂ R[x].

∄x ∈ Rn s.t. f1 (x) = 0, . . . , fm (x) = 0, g1 (x) ≥ 0, . . . , gk (x) ≥ 0

m
∃ f ∈ hF iR , ∃ g ∈ cone(G) s.t. f (x) + g(x) = −1

The theorem states that for every infeasible system of polynomial equa-
tions and inequalities, there exists a simple algebraic identity that directly
certifies the non-existence of real solutions.
Of course, we are very concerned with the effective practical compu-
tation of the infeasibility certificates. For the sake of computation and
complexity, we must worry about the growth of degrees of the infeasibility
certificates. On the negative side, the degrees of the certificates are ex-
pected to be high (in the worst case) simply because the NP-hardness of
the original combinatorial questions; see e.g. [9]. At the same time, tight
exponential upper bounds have been derived (see e.g. [22], [16] and refer-
ences therein). Nevertheless, for many problems of practical interest, it is
often the case that it is possible to prove infeasibility using low-degree cer-
tificates (see [8, 7]). Even more important is the fact that for fixed degree
of the certificates the calculations can be reduced to either linear algebra
or semidefinite programming. We summarize the strong analogies between
the case of linear equations and inequalities with high-degree polynomial
systems in the following table:
6 J.A. DE LOERA, P.N. MALKIN AND P.A. PARRILO

Degree\Field Arbitrary Real

Linear Fredholm Alternative Farkas’ Lemma
Linear Algebra Linear Programming
Polynomial Nullstellensatz Positivstellensatz
Bounded degree Linear Algebra Bounded degree SDP
Table 1
Infeasibility certificates and their associated computational techniques.

It is important to remark that just as in the classical case of linear

programming, the problem of computation of certificates has very natural
primal-dual formulations, with the corresponding primal and dual vari-
ables playing distinct, but well-define roles. For example, in the case of
Fredholm’s alternative, the primal variables are the variables x1 , . . . , xn
while there is a dual variable for each equation. For Nullstellensatz and
Positivstellensatz there is a similar duality, based on linear duality and
semidefinite programming duality, respectively. In what follows, we use
the most intuitive or convenient set-up and we leave the reader the exer-
cise of transferring the results to the corresponding dual version.
The remainder of the paper is divided in two main sections: Section
2 is a study of the Hilbert Nullstellensatz, for general fields, used in the
solution of systems of equations. In Section 3, we survey the use of the
Positivstellensatz in the context of solving systems of equations and in-
equalities over the reals. Both sections contain combinatorial applications
that show why these techniques can be of interest in this setting. The fo-
cus of the combinatorial results is understanding those situations when a
constant degree certificate is enough to show infeasibility. These are situa-
tions when hard combinatorial problems have polynomial time algorithms
and as such provide structural insight. Finally, in Section 4, we describe a
methodology, common to both approaches, to recover feasible solutions of
the original combinatorial problem from the outcome of these relaxations.
To conclude the introduction we include some more notation. Given a
vector space W over a field K, we write dim(W ) for the dimension of W .
Given vector spaces U ⊆ W , we write W/U as the vector space quotient.
Recall that dim(W/U ) = dim(W ) − dim(U ). As a slight abuse of notation,
if U 6⊆ W , then we write W/U when we strictly mean W/(U ∩ W ), in
which case, dim(W/U ) = dim(W ) − dim(U ∩ W ). Given a set F ⊂ R, hF iK
denotes the vector space generated by F over the field K. Please note the
distinction between the vector space hF iK and the ideal hF iR .

2. Solving combinatorial systems of equations. In this section,

we wish to solve a given zero-dimensional system of polynomial equations
f1 (x) = 0, f2 (x) = 0, . . . , fm (x) = 0 where f1 , . . . , fs ∈ R. We abbreviate
this system as F (x) = 0 where F := {f1 , . . . , fm } ⊂ R. Here, by solving
a system, we mean first determining if F (x) = 0 is feasible over K, the
 POLYNOMIALS IN COMBINATORIAL OPTIMIZATION 7

algebraic closure of K, and furthermore finding a solution (or all solutions)

of F (x) = 0 if feasible. We say that a system is combinatorial when it
is defined in terms of combinatorial information such as graph properties
and it has finitely many solutions (if any). The literature on polynomial
solving is very extensive and it continues to be an area of active research
(see [48, 6, 10] for an overview and background).
Here we choose to focus on techniques that fit well with optimization
methods. The main idea is that solving a polynomial system of equations
can be reduced to solving a sequence of linear algebra problems. The foun-
dations of this technique can be traced back to ([36, 20, 21, 37]). Variants
of this technique have been applied to stable sets [9, 34], vertex coloring
[8, 34], satisfiability (see e.g., [3]) and cryptography (see for example [4]).
This technique is also strongly related to Gröbner bases techniques (see
e.g., [20, 37, 48]).
The linear algebra systems of equations have primal and dual represen-
tations in the sense of Fredholm’s lemma. Specifically, in this survey, the
primal approach Psolves a linear system to find constant multipliers µ ∈ Km
m
such that 1 = i=1 µi fi providing a certificate of (non-linear) infeasibil-
ity. Then, the dual approach aims P to find a vector λ with entries in K
indexed by monomials such that α λxα fi,α = 0 for all i = 1, . . . , m and
λ1 = 1 where fi = α fi,α xα for all i. As we see in Section 2.2, the dual
P
approach amounts to constructing linear relaxations of the set of feasible
solutions. In Sections 2.1 and 2.2, we present examples of the primal and
dual approaches respectively.
2.1. Linear algebra certificates. Consider the following corollary
of
Pm Hilbert’s Nullstellensatz: If there exists constants µ ∈ Km such that
i=1 µi fi = 1, then the polynomial system F (x) = 0 must be infeasi-
ble. In other words, if the system F (x) = 0 is infeasible, then 1 ∈ hF iK .
The crucialPpoint here is that determining whether there exists a µ ∈ Km
m
such Pthat i=1 µi fi = 1 is a linear algebra problem over K. The equa-
m
tion i=1 µi fi = 1 is called a certificate of infeasibility of the polynomial
system.
Example 1. Consider the following infeasible system in R[x1 , x2 , x3 ]:

x21 − 1 = 0, 2x1 x2 + x3 = 0, x1 + x2 = 0, x1 + x3 = 0.

Let F = {f1 , f2 , f3 , f4 } where f1 = x21 − 1 = 0, f2 = 2x1 x2 + x3 = 0,

f3 = x1 + x2 = 0, and f4 = x1 + x3 = 0. So, we abbreviate the above system
as F (x) = 0. We can prove that the system F (x) = 0 is infeasible if we
can find µ ∈ R4 satisfying the following:

µ1 f1 + µ2 f2 + µ3 f3 + µ4 f4 = 1
⇔ µ1 (x21 − 1) + µ2 (2x1 x2 + x3 ) + µ3 (x1 + x2 ) + µ4 (x1 + x3 ) =1
⇔ µ1 x21 + 2µ2 x1 x2 + (µ2 + µ4 )x3 + µ3 x2 + (µ3 + µ4 )x1 − µ1 = 1.
8 J.A. DE LOERA, P.N. MALKIN AND P.A. PARRILO

Then, equating coefficients on the left and right hand sides of the equation
above gives the following linear system of equations:

−µ1 = 1 (1), µ3 + µ4 = 0 (x1 ), µ3 = 0 (x2 ),

µ3 + µ4 = 0 (x3 ), 2µ2 = 0 (x1 x2 ), µ1 = 0 (x21 ).

We abbreviate this system as µT F = 1. Even though F (x) = 0 is infeasible,

the linear system µT F = 1 is infeasible, and so, we have not found a
certificate of infeasibility.
α
P
More formally, let fi = α∈Nn fi,α x P for i = 1, ..., m. Note that
m
only
Pm finitely many f i,α are non-zero. Then, i=1 µi fi = 1 if and only if
m
N n
P
µ
i=1 i i,0 f = 1 and µ f
i=1 i i,α = 0 for all α ∈ where α 6= 0. Note that
there is one linear equation per monomial appearing in F . We abbreviate
this linear system as µT F = 1 where we consider F as a matrix whose rows
are the coefficient vectors of its polynomials and we consider the constant
polynomial 1 as the vector of its coefficients (i.e., a unit vector). The
columns of F are indexed by monomials with non-zero coefficients.
We remark that in the special case where F (x) = 0 is a linear system
of equations, then Fredholm’s alternative says that F (x) = 0 is infeasible
if and only if µT F = 1 is feasible.
In general, even if F (x) = 0 is infeasible, µT F = 1 may not be feasible
as in the above example. In order to prove infeasibility, we must add
polynomials from hF iR to F and try again to find a µ such that µT F = 1.
Hilbert’s Nullstellensatz guarantees that, if F (x) = 0 is infeasible, there
exists a finite set of polynomials from hF iR that we can add to F so that
the linear system µT F = 1 is feasible.
More precisely, it is enough to add polynomials of the form xα f for
xα a monomial and some polynomial f ∈ F . Why Pmis this? If F (x) = 0
is infeasible, then Hilbert’s Nullstellensatz says i=1 βi fi = 1 for some
β1 , . . . , βm ∈ R. Let d = maxi {deg(βi )}. Then, if we add to F all polyno-
mials of the form xα f where f ∈ F and deg(xα ) ≤ d. Then, the K-linear
span of F , that is hF iK , contains βi fi for all i, and thus, 1 ∈ hF iK or
equivalently µT F ′ = 1 is feasible (as a linear algebra problem) where F ′
denotes the larger polynomial system.
Example 2. Consider again the polynomial system F (x) = 0 from Ex-
ample 1. Here, µT F = 1 is feasible, so we must thus add redundant polyno-
mial equations to the system F (x) = 0. In particular, we add the following
redundant polynomial equations: x2 f1 (x) = 0, x1 f2 (x) = 0, x1 f3 (x) = 0,
and x1 f4 (x) = 0. Let F ′ := {f1 , f2 , f3 , f4 , x2 f1 , x1 f2 , x1 f3 , x1 f4 }.
Then, the system µT F ′ = 1 is now as follows:

−µ1 = 1 (1), µ3 + µ4 = 0 (x1 ), µ3 − µ5 = 0 (x2 ),

µ2 + µ4 = 0 (x3 ), 2µ2 + µ7 = 0 (x1 x2 ), µ1 + µ7 + µ8 = 0 (x21 ),
µ6 + µ8 = 0 (x1 x3 ), µ5 + 2µ6 = 0 (x21 x2 ).
 POLYNOMIALS IN COMBINATORIAL OPTIMIZATION 9

This system is feasible proving that F (x) = 0 is infeasible. The solution is

µ = (−1, − 32 , − 32 , 32 , − 32 , − 13 , 34 , − 31 ), which gives the following certificate of
infeasibility:
2 2 2 2 1 4 1
−f1 − f2 − f3 + f4 − x2 f1 + x1 f2 + x1 f3 − x1 f4 = 1.
3 3 3 3 3 3 3
Next, we present the dual approach to the one in this section.
2.2. Linear algebra relaxations. In optimization, it is quite com-
mon to “linearize” non-linear polynomial systems of equations by replacing
all monomials in the system with new variables giving a system of linear
constraints. Specifically, we can construct a linear algebra relaxation of
the solutions of F (x) = 0 by replacing every monomial xα in a polynomial
equation in F (x) = 0 with a new variable λxα thereby giving a system
of linear equations in the new λ variables, one variable for each mono-
mial appearing in F . Readers familiar with relaxation procedures such as
Sherali-Adams and Lovász-Schrijver (see [26] and references therein) will
see a lot of similarities, but here we deal only with equality constraints.
Example 3. Consider the following feasible system in R[x1 , x2 , x3 ]:
f1 (x) = x21 − 1 = 0, f2 (x) = 2x1 x2 + x3 = 0, f3 (x) = x1 + x2 = 0.

This system has two solutions (x1 , x2 , x3 ) = (1, −1, 2) and (x1 , x2 , x3 ) =
(−1, 1, 2). Let F = {f1 , f2 , f3 }. So, we abbreviate the above system as
F (x) = 0. We can replace the monomials 1, x1 , x2 , x3 , x21 , x1 x2 with the
variables λ1 , λx1 , λx2 , λx3 , λx21 , λx1 x2 respectively. The system F (x) = 0
thus gives rise to the following set of linear equations:

λx21 − λ1 = 0, 2λx1 x2 + λx3 = 0, λx1 + λx2 = 0. (2.1)

We abbreviate the above system as F ∗ λ = 0.
Solutions of F (x) = 0 give solutions of F ∗ λ = 0: If x is a solution of
F (x) = 0 above, then setting λ1 = 1, λx1 = x1 , λx2 = x2 , λx3 = x3 , λx21 =
x21 , λx1 x2 = x1 x2 gives a solution of F ∗ λ = 0. So, taking x = (1, −1, 1), we
set λ1 = 1, λx1 = 1, λx2 = −1, λx3 = 2, λx21 = 1, and λx1 x2 = −1. Then,
we have F ∗ λ = 0. Thus, the solutions of F ∗ λ = 0 gives a vector space
effectively containing all of the solutions of F (x) = 0. Hence, F ∗ λ = 0
gives a linear relaxation of F (x) = 0.
There are solutions of F ∗ λ = 0 that do not correspond to solutions
of F (x) = 0 because the linear system F ∗ λ = 0 does not take into account
the non-linear constraints that λ1 = 1, λx21 = λ2x1 and λx1 x2 = λx1 λx2 ; For
example, λ1 = 1, λx1 = 2, λx2 = −2, λx3 = −2, λx21 = 1 and λx1 x2 = 1 is a
solution of F ∗λ = 0, but x1 = λx1 = 2, x2 = λx2 = −2, and x3 = λx3 = −2
is not a solution of F (x) = 0.
We now formalize the above example construction of a linear system.
We can consider the polynomial ring R = K[x1 , . . . , xn ] as an infinite di-
mensional vector space over K where the set of all monomials xα forms a
10 J.A. DE LOERA, P.N. MALKIN AND P.A. PARRILO

vector space basis of R. In other words, a polynomial f = α∈Nn fα xα

P
can be represented as an infinite sequence (fα )α∈Nn where only finitely
many fα are non-zero. We define R̄∗ = K[[x1 , . . . , xn ]] = K[[x]] as the
ring of formal power series in the
P variablesα x1 , . . . , xn with coefficients in
K. So, the power series λ = α∈Nn λα x can be represented as an in-
finite sequence (λα )α∈Nn . Note that we do not require that only finitely
∗
many λα are non-zero. We define the bilinearP form ∗ : αR × R̄ → K as
α ∗
P
follows: P given f = α∈Nn fα x ∈ R and λ = α∈Nn λα x ∈ R̄ , we define
f ∗ λ = α∈Nn fα λα , which is always finite since only finitely many fα are
n
non-zero. Thus, we define a linear relaxation of x ∈ K , F (x) = 0, written
∗
as λ ∈ R̄ , F ∗ λ = 0, as the set of linear equations f ∗ λ = 0 for all f ∈ F .
Note that, for any polynomial f ∈ R and any point v ∈ Kn , we have
n
f (v) = f ∗ λv where λv = (v α )α∈Nn . Thus, for any v ∈ K , F (v) = 0 if and
only if F ∗ λv = 0. So, the system F ∗ λ = 0 can be considered as a linear
relaxation of the system F (x) = 0. As mentioned in the above example,
there are solutions of F ∗ λ = 0 that do not correspond to solutions of
F (x) = 0 because the linear system F ∗ λ = 0 does not take into account
the relationships between the λ variables. Specifically, if λ corresponded to
a solution of F (x) = 0, then we must have λxα = λxβ λxγ for all monomials
xα , xβ , xγ where xα = xβ xγ . If we added these non-linear constraints to
the linear constraints F ∗ λ = 0, then we would essentially have the original
polynomial system F (x) = 0.
The system F ∗ λ = 0 is always feasible, but the constraint λ1 = 1 also
holds for any λ that corresponds to a solution x of F (x) = 0. Thus, if the
inhomogeneous linear system F ∗ λ = 0, λ1 = 1 is infeasible, then so is the
system of polynomials F (x) = 0.
Remark 2.1. Crucially, this linear system F ∗ λ = 0, λ1 = 1 is
dual to the linear system µT F = 1 from the previous section by Fredholm’s
alternative meaning that F ∗ λ = 0, λ1 = 1 is infeasible if and only if
µT F = 1 is feasible.
There is a fundamental observation we wish to make here: adding
redundant polynomial equations can lead to a tighter relaxation.
Example 4. (Cont.) Add x1 f3 (x) = x21 + x1 x2 = 0 to the system
F (x) = 0 giving the system F ′ (x) = 0 where F ′ := {f1 , f2 , f3 , x1 f3 }. The
system F ′ (x) = 0 has the same solutions as F (x) = 0. The polynomial
equation x1 f3 (x) = 0 gives rise to a new linear equation λx21 + λx1 x2 = 0
giving the following linear system F ′ ∗ λ = 0:

λx21 − λ1 = 0, 2λx1 x2 + λx3 = 0, λx1 + λx2 = 0, λx21 + λx1 x2 = 0. (2.2)

The dimension of the solution space of the original system F ∗λ = 0 is three

if we ignore all λ variables that do not appear in the linear system, or in
other words, if we project the solution space onto the λ variables appearing
in the system. However, the dimension of the projected solution space of
F ′ ∗ λ = 0 is two; so, F ′ ∗ λ = 0 is a tighter relaxation of F (x) = 0.
 POLYNOMIALS IN COMBINATORIAL OPTIMIZATION 11

We denote the set of solutions of the linear system F ∗ λ = 0 as

F ◦ := {λ ∈ R̄∗ : F ∗ λ = 0}, called the annihilator of F , which is a vector
subspace of R̄∗ . The fact that adding redundant equations leads to a tighter
linear relaxation is summarized by the following fact: For sets F ⊆ F̃ ⊆ R,
we have F ◦ ⊆ F̃ ◦ .
Extending this idea, consider the ideal I = hF iR , which is the set of
all redundant polynomials given as a polynomial combination of polynomi-
als in F , then I ◦ becomes a finite dimensional vector space where dim(I ◦ )
is precisely the number of solutions of F (x) = 0 over K, including mul-
tiplicities, assuming that there are finitely many solutions. Note that by
linear algebra, I ◦ is isomorphic to the vector space quotient R/I (see e.g.,
[48]). Furthermore, if I is radical, then dim(I ◦ ) = dim(R/I) is precisely
the number of solutions of F (x) = 0. So, there is a direct relationship be-
tween the number of solutions of a polynomial system and the dimension
of the solution space of its linear relaxation (see e.g., [6]).
Theorem 2.1. Let I ⊆ R be a zero-dimensional ideal. Then, dim(I ◦ )
is finite and dim(I ◦ ) is the number of solutions of polynomial system I(x) =
0 over K including multiplicities, so |VK (I)| ≤ dim(I ◦ ) with equality when
I is radical.
So, if we can compute dim(I ◦ ), then we can determine the feasibility
of I(x) = 0 over K. Unfortunately, we cannot compute dim(I ◦ ) directly.
Instead, under some conditions (see Theorem 2.2), we can compute dim(I ◦ )
by computing the dimension of F ◦ when projected onto the λxα variables
where deg(xα ) ≤ deg(F ).

2.3. Nullstellensatz Linear Algebra Algorithm (NulLA). We

now present an algorithm for determining whether a polynomial system of
equations is infeasible using linear relaxations. Let F ⊆ K[x] and again let
F (x) = 0 be the polynomial system f (x) = 0 for all f ∈ F . We wish to
determine whether F (x) = 0 has a solution over K.
The idea behind NulLA [8] is straightforward: we check whether the
linear system F ∗ λ = 0, λ1 = 1 is infeasible or equivalently whether
µT F = 1 is feasible (i.e., 1 ∈ hF iK ) using linear algebra over K and if
not then we add polynomials from hF iR to F and try again. We add
polynomials in the following systematic way: for each polynomial f ∈ F
and for each variable xi , we add xi f to F . So, the NulLA algorithm is as
follows: if F ∗ λ = 0, λ1 = 1 is infeasible, then F (x) = 0 is infeasible and
stop, otherwise for every variable xi and every f ∈ F add xi f to F and
repeat.
In the following, we assume without loss of generality that F is closed
under K-linear combinations, that is F = hF iK , and thus, F is a vector
space over K. Note that taking the closure of F under K-linear combina-
tions does not change the set of solutions of F (x) = 0 and does not change
the set of solutions of F ∗ λ = 0. In practice, we must choose a vector
space basis of F for computation, but the point we wish to make is that
12 J.A. DE LOERA, P.N. MALKIN AND P.A. PARRILO

the choice of basis is irrelevant. Moreover, we find that it is more natural

to work with vector spaces and that it leads to a more concise exposition.
Recall from above that F ∗λ = 0, λ1 = 1 is infeasible if and only if 1 ∈ hF iK ,
which when F is a vector space, simplifies to 1 ∈ F since P hF iK = F .
n
For a vector space F ⊂ R, we define F + := F + i=1 xi F where
+
xi F := {xi f : f ∈ F }. Note that F is also a vector subspace of R. Then,
F + is precisely the linear span of F and xi F for all i = 1, . . . , n. So, the
NulLA algorithm for vector spaces is as follows (see Algorithm 1): if 1 ∈ F ,
then F (x) = 0 is infeasible and stop, otherwise set F := F + and repeat.
There is an upper bound on the number of times we need to repeat the
above step given by the Nullstellensatz bound of the system F (x) = 0.
This follows since after d iterations of NulLA, the set F contains all linear
combinations of polynomials of the form xα f where the total degree |α| ≤ d
and where f was one of the initial polynomials in F .

Algorithm 1 NulLA Algorithm [8]

Input: A finite dimensional vector space F ⊆ R and a Nullstellensatz
bound D.
Output: Feasible, if F (x) = 0 is feasible over K, else Infeasible.
for d = 0, 1, 2, . . . , D do
If 1 ∈ F , then return Infeasible.
F := F + .
end for
Return Feasible.

While theoretically the Nullstellensatz bound limits the number of

iterations, this bound is in general too large to be practically useful (see
[8]). Hence, in practice, NulLA is most useful for proving infeasibility (see
Section 2.4).
Next, we discuss improving NulLA by adding redundant polynomials
to F in such a way so that deg(F ) does not grow unnecessarily. The im-
proved algorithm is called the Fixed-Point Nullstellensatz Linear Algebra
(FPNulLA) algorithm (see [7]). The basic idea behind the FPNulLA algo-
rithm is that, if 1 6∈ F , then instead of replacing F with F + and thereby
increasing deg(F ), we check to see whether there are any new polynomials
in F + with degree at most deg(F ) that were not in F and add them to
F , and then check again whether 1 6∈ F . More formally, if 1 6∈ F , then we
replace F with F + ∩ Rd where Rd is the set of all polynomials with degree
at most d = deg(F ). We keep replacing F with F + ∩ Rd until either 1 ∈ F
or we reach a fixed point, F = F + ∩ Rd . This process must terminate.
Note that if we find that 1 ∈ F at some stage of FPNulLA
Ps this implies
that there exists an infeasibility certificate of the form 1 = i=1 βi fi where
β1 , ..., βs ∈ K[x] and the polynomials f1 , ..., fs ∈ K[x] are a vector space
basis of the original set F .
Moreover, we can also improve NulLA by proving that the system
 POLYNOMIALS IN COMBINATORIAL OPTIMIZATION 13

F (x) = 0 is feasible well before reaching the Nullstellensatz bound as fol-

lows. When 1 6∈ F and F = F + ∩ Rd , then we could set F := F + and
d := d + 1 and repeat the above process. However, when we reach the fixed
point F = F + ∩ Rd , we can use the following theorem to determine if the
system is feasible and if so how many solutions it has. First, we introduce
some notation. Let πd : R̄∗ → R̄d be the projection of a power series onto a
polynomial of degree at most d with coefficients in K. Below, we abbreviate
dim(πd (F ◦ )) as dimd (F ◦ ) and similarly dim(πd−1 (F ◦ )) as dimd−1 (F ◦ ).
Theorem 2.2. Let F ⊂ R be a finite dimensional vector space and
let d = deg(F ). If F = F + ∩ Rd and dimd (F ◦ ) = dimd−1 (F ◦ ), then
dim(I ◦ ) = dimd (F ◦ ) where I = hF iR .
See [36, 7] for a proof of Theorem 2.2. Recall from Theorem 2.1, that
there are dim(I ◦ ) solutions of F (x) = 0 over K including multiplicities
where I = hF iR and exactly dim(I ◦ ) solutions when I is radical.
There are many equivalent forms of the above theorem that appear
in the literature. (see e.g., [36, 43, 24]). Note that the condition that
F = F + ∩Rd is equivalent to the condition that dimd (F ◦ ) = dimd ((F + )◦ )).
Also, since Rd is a vector space and F ⊆ Rd is vector subspace, we can
form the vector space quotient Rd /F , which is isomorphic to πd (F ◦ ) (see
◦
for example [48]), and thus,
n+d

dimd (F ) = dim(Rd /F ) = dim(Rd ) − dim(F ◦
)
where dim(Rd ) = d . Similarly, dim(R d−1 /F ) = dim d−1 (F ) and
dim(Rd /F + ) = dimd ((F + )◦ ). Thus, in practice, checking the conditions of
Theorem 2.2 means computing dim(F ), dim(F ∩ Rd−1 ) and dim(F + ∩ Rd ).
We can now present the FPNulLA algorithm [36, 7]. See [36] for a
proof of termination.

Algorithm 2 FPNulLA Algorithm

Input: A vector space F ⊂ R.
Output: The number of solutions of F (x) = 0 over K up to multiplicities.
Let d = deg(F ).
loop
if 1 ∈ F then Return 0.
while F 6= F + ∩ Rd do
Set F := F + ∩ Rd .
if 1 ∈ F then return 0.
end while
if dimd (F ◦ ) = dimd−1 (F ◦ ) then return dimd (F ◦ ).
F := F + .
d := d + 1.
end loop

Example 5. Consider the following feasible system with polynomials

in K[x] with K = F2 .

1 + x + x2 = 0, 1 + y + y 2 = 0, x2 + xy + y 2 = 0.
14 J.A. DE LOERA, P.N. MALKIN AND P.A. PARRILO

This system has two solutions over K = F2 . Let F := h1 + x + x2 , 1 + y +

y 2 , x2 + xy + y 2 iK . Then, 1 6∈ F and deg(F ) = 2. Now,

F + = F + xF + yF
= F + hx + x2 + x3 , x + xy + xy 2 , x3 + x2 y + xy 2 iK
+ hy + xy + x2 y, y + y 2 + y 3 , x2 y + xy 2 + y 3 iK

Then, F + ∩ R2 = h1 + x + x2 , 1 + y + y 2 , x2 + xy + y 2 , 1 + x + yiK . So,

F 6= F + ∩ R2 . Next, let F := F + ∩ R2 . Then, F = F + ∩ R2 . Moreover,
dim2 (F ◦ ) = 2 and dim1 (F ◦ ) = 2. Therefore, the system is feasible.
2.4. Experimental results. In this section, we summarize experi-
mental results for graph 3-coloring from [7], which illustrate the practical
performance of the NulLA and FPNulLA algorithms. For further and more
detailed results, see [8, 34, 7]. Experimentally, for graph 3-coloring, NulLA
and FPNulLA are well-suited to proving infeasibility, that is, that no 3-
coloring exists. The polynomials encoding of 3-coloring that is used here
is over F2 (see Proposition 1.1) and thus any linear algebra operations are
very fast. However, even though in theory NulLA and FPNulLA can deter-
mine feasibility, for the experiments described below NulLA and FPNulLA
were not able to prove feasibility in practice.
We refer to the number of iterations that NulLA takes to solve a given
system of equations as the NulLA degree of the system. Similarly to the
NulLA degree, we refer to the number of outer iterations that FPNulLA
takes to the system as the FPNulLA degree of the system. We can consider
the NulLA degree and the FPNulLA degree as measures of the hardness of
proving infeasibility of the system. In this section, we present experimen-
tal evidence that the NulLA degree of an infeasible combinatorial system
is a good measure of the hardness of proving infeasibility of the system.
Similarly, we present experimental evidence (see also [3] for theoretical ev-
idence) suggesting that the FPNulLA degree is also a good measure of the
hardness of a problem and an even better measure than the NulLA degree.
Here, we are interested in the percentage of randomly generated graphs
whose polynomial system encoding has a NulLA degree of one or a FP-
NulLA degree of one. The G(n, p) model [13] is used for generating random
graphs where n is the number of vertices and p is the probability that an
edge is included between any two vertices. Also, without loss of generality,
for a slightly smaller polynomial encoding, the color of one of the vertices
of each randomly generated graph was fixed.
The experimental results are presented in Figure 1 (taken from [7]),
which plots the percentage of 1000 random graphs in G(100, p) that were
proven infeasible with a NulLA degree of one, with a FPNulLA degree of
one, or with an exact method versus the p value. The exact method used
was to model graph 3-coloring as a Boolean satisfiability problem [12] and
then use the program zchaff [50] to solve the satisfiability problem.
 POLYNOMIALS IN COMBINATORIAL OPTIMIZATION 15

100
Exact
NulLA
FPNulLA

80

60
% infeasible

40

20

0
0 0.02 0.04 0.06 0.08 0.1
p - edge probability

Fig. 1. Non-3-colorable graphs with NulLA or FPNulLA degree of 1

It is well-known that there is a distinct phase transition from feasibil-

ity to infeasibility for graph 3-coloring, and it is at this phase transition
that graphs exists for which it is difficult on average to prove infeasibility or
feasibility (see [19]). Observe that the infeasibility curve for NulLA resem-
bles that of the exact infeasibility curve and that the infeasibility curve for
FPNulLA also resembles the infeasibility curve and clearly dominates the
infeasibility curve for NulLA. These results support that statement that
the NulLA degree or FPNulLA degree is a reasonable measure of the hard-
ness of proving infeasibility since those graphs that require a higher degree
than one are located near the phase transition.
2.5. Application: the structure of non-3-colorable graphs. For
a given class of combinatorial system of equations, it is of interest to under-
stand the growth of the NulLA degree or FPNulLA degree. For some fixed
degree, it is also interesting to characterize which graphs can be proved
at that degree to lack a certain property. In this section, we state a com-
binatorial characterization of those graphs whose combinatorial system of
equations encoding 3-colorability has a NulLA degree of one and recall
bounds for the NulLA degree (see [34]):
Theorem 2.3. The NulLA degree for a polynomial encoding over
F2 of the 3-colorability of a graph with n vertices with no 3-coloring is at
least one and at most 2n. Moreover, in the case of a non-3-colorable graph
containing an odd-wheel or a 4-clique as a subgraph, the NulLA degree is
exactly one.
Now we look at those non-3-colorable graphs that have a degree one
16 J.A. DE LOERA, P.N. MALKIN AND P.A. PARRILO

NulLA degree. Let A denote the set of all possible directed edges or arcs in
the graph G. We are interested in two types of substructures of the graph
G: oriented partial-3-cycles and oriented chordless 4-cycles (see Figure 2.5).
An oriented partial-3-cycle is a set of two arcs of a 3-cycle, that is, a
set {(i, j), (j, k)} also denoted (i, j, k) where (i, j), (j, k), (k, i) ∈ A. An
oriented chordless 4-cycle is a set of four arcs {(i, j), (j, l), (l, k), (k, i)}
also denoted (i, j, k, l) where (i, j), (j, l), (l, k), (k, i) ∈ A and (j, k), (i, l) 6∈
A.

Fig. 2. (i) oriented partial 3-cycle and (ii) an oriented chordless 4-cycle

Now, we can state a sufficient condition for non-3-colorability [7]. This

sufficient condition is satisfied if and only if the combinatorial system en-
coding 3-coloring has a NulLA degree of one, which is proved in [7].
Theorem 2.4. The graph G is not 3-colorable if there exists a set C
of oriented partial 3-cycles and oriented chordless 4-cycles such that
1. |C
P(i,j) | + |C(j,i) | ≡ 0 (mod 2) for all (i, j) ∈ E and
2. (i,j)∈A,i<j |C(i,j) | ≡ 1 (mod 2)
where |C(i,j) | denotes the number of cycles in C (either 3-cycles or 4-cycles)
in which the arc (i, j) ∈ A appears.
Condition 1 in Lemma 2.4 means that every undirected edge of G is
covered by an even number of directed edges from cycles in C (ignoring
orientation). Condition 2 in Lemma 2.4 means that, given any orientation
of G, the total number of times the arcs in that orientation appear in the
cycles of C is odd. The particular orientation we use in Lemma 2.4 is the
orientation given by the set of arcs {(i, j) ∈ A : i < j}, but the particular
orientation we use for Condition 2 is irrelevant (see [7]).
Example 6. Consider the Grötzsch graph (Mycielski 4) in Figure 3,
which has no 3-coloring. It contains no 3-cycles. Now, consider the follow-
ing set of oriented chordless 4-cycles, which we show gives a certificate of
non-3-colorability by Lemma 2.4.

C := {(1, 2, 3, 7), (2, 3, 4, 8), (3, 4, 5, 9), (4, 5, 1, 10), (1, 10, 11, 7),
(2, 6, 11, 8), (3, 7, 11, 9), (4, 8, 11, 10), (5, 9, 11, 6)}.

Figure 3 illustrates the edge directions for the 4-cycles of C. Each undi-
rected edge of the graph is contained in exactly two 4-cycles, so C satisfies
Condition 1 of Lemma 2.4. Now,

|C(6,11) | = |C(7,11) | = |C(8,11) | = |C(9,11) | = |C(10,11) | = 1,

 POLYNOMIALS IN COMBINATORIAL OPTIMIZATION 17

and |C(i,j) ≡ 0 (mod 2) for all other arcs (i, j) ∈ A where i < j. Thus,
X
|C(i,j) | ≡ 1 (mod 2),
(i,j)∈A,i<j

so Condition 2 is satisfied, and therefore, the graph has no 3-coloring.

Fig. 3. Grötzsch graph

3. Adding polynomial inequalities. Up until this point we have

worked over arbitrary fields (with special attention to finite fields due to
their fast and exact computation), where the only allowable constraints
were equations. Now we turn our attention to the real case (i.e. K = R),
where we have the additional possibility of specifying inequalities (more
generally, one can work over ordered or formally real fields). In this case,
following the terminology of real algebraic geometry, we call the solution set
of a system of polynomial equations and inequalities a basic semialgebraic
set. Note that convex polyhedra correspond to the particular case where
all the constraint polynomials have degree one. As we have seen earlier
in the Positivstellensatz (Theorem 1.4 above), the emptiness of a basic
semialgebraic set can be certified through an algebraic identity involving
sum of squares of polynomials.
The connection between sum of squares decompositions of polynomi-
als and convex optimization can be traced back to the work of N. Z. Shor
[46]. His work went relatively unnoticed for several years, until several au-
thors, including Lasserre, Nesterov, and Parrilo, observed around the year
2000 that the existence of sum of squares decompositions and the search
for infeasibility certificates for a semialgebraic set can be addressed via a
sequence of semidefinite programs relaxations [23, 39, 40, 38]. The first
part of this section will be a short description of the connections between
sums of squares and semidefinite programming, and how the Positivstel-
lensatz allows, in a analogous way to what was presented in Section 2 for
18 J.A. DE LOERA, P.N. MALKIN AND P.A. PARRILO

the Nullstellensatz, for a systematic way to formulate these semidefinite

relaxations.
A very central preoccupation of combinatorial optimizers has been
the understanding of the facets that describe the integer hull (normally
binary) of a combinatorial problem. As we will see in the last part of
this survey, one can recover quite a bit of information about the integer
hull of combinatorial problems from a sequence combinatorially controlled
SDPs. This kind of approach was pioneered in the lift-and-project method
of Balas, Ceria and Cornuéjols [1], the matrix-cut method of Lovász and
Schrijver [33] and the linearization technique of Sherali-Adams [45]. Here
we try to present more recent developments (see [29] and references therein
for a very extensive survey).

3.1. Sums of squares, SDP, and feasibility of semialgebraic

sets. A multivariate polynomial p(x) is a sum of squares (SOS for short)
if it can be written as a sum of squares of other polynomials, i.e.,
X
p(x) = qi2 (x), qi (x) ∈ R[x].
i

If p(x) is SOS, then clearly p(x) ≥ 0 for all x ∈ Rn .

Example 7. The polynomial p(x1 , x2 ) = x21 − x1 x22 + x42 + 1 is SOS.
Among infinitely many others, it has the following decompositions:

3 1
p(x1 , x2 ) =(x1 − x22 )2 + (x1 + x22 )2 + 1
4 4
1 2 2 2 2 1 23
= (3 − x2 ) + x2 + (9x1 − 16x22 )2 + x21 .
9 3 288 32

The sum of squares condition is a quite natural sufficient test for polyno-
mial non-negativity. Thus instead of asking whether even degree polyno-
mials are non-negative we ask the easier question whether they are sums
of squares. More importantly, as we shall see, the existence of a sum of
squares decomposition can be decided via semidefinite programming.
Theorem 3.1. A polynomial p(x) is SOS if and only if p(x) = z T Qz,
where z is a vector of monomials in the xi variables, and Q is a symmetric
positive semidefinite matrix.
By the theorem above, every SOS polynomial can be written as a
quadratic form in a set of monomials, with the corresponding matrix being
positive semidefinite. The vector of monomials z in general depends on
the degree and sparsity pattern of p(x). If p(x) has n variables and total
degree 2d, then z can always be chosen as a subset of the set
of monomials
of degree less than or equal to d, which has cardinality n+d
d .
Example 8. Consider again the polynomial from Example 7. It has
 POLYNOMIALS IN COMBINATORIAL OPTIMIZATION 19

the representation
 T   
1 6 0 −2 0 1
1 x2  
  0 4 0 0   x2 
p(x1 , x2 ) =  2  
 2 ,
6  x2 −2 0 6 −3   x2 
x1 0 0 −3 6 x1

and the matrix in the expression above is positive semidefinite.

In the representation f (x) = z T Qz, for the right- and left-hand sides
to be identical, all the coefficients of the corresponding polynomials should
be equal. Since Q is simultaneously constrained by linear equations and a
positive semidefiniteness condition, the problem can be easily seen to be
directly equivalent to an semidefinite programming feasibility problem in
the standard primal form.
Now we describe an algorithm, and illustrate it with an example, on
how we can use SDPs to decide the feasibility of a system of polynomial
inequalities. Exactly as we did for the Nullstellensatz case, we can look for
the existence of a Positivstellensatz certificate of bounded degree D. Once
we assume that the degree D is fixed we can apply Theorem 3.1 and obtain
a reformulation as a semidefinite programming problem. We formalize this
description in the following algorithm:

Algorithm 3 Bounded degree Positivstellensatz [39, 40]

Input: A polynomial system {fi (x) = 0, gi (x) ≥ 0} and a Positivstellen-
satz bound D.
Output: Feasible, if {fi (x) = 0, gi (x) ≥ 0} is feasible over R, else In-
feasible.
for d = 0, 1, 2, . . . , D do
If there exist βi , sα ∈ R[x] such that −1 = i βi fi + α∈{0,1}n sα g α ,
P P

with sα SOS, deg(βi fi ) ≤ d, deg(sα g α ) ≤ d then return Infeasible.

d := d + 1.
end for
Return Feasible.

Notice that the membership test in the main loop of the algorithm
is, by the results described at the beginning of this section, equivalent to
a finite-sized semidefinite program. Similarly to the Nullstellensatz case,
the number of iterations (i.e., the degree of the certificates) serves as a
quantitative measure of the hardness in proving infeasibility of the system.
As we will describe in more detail in Section 3.4, in several situations one
can give further refined characterization on these degrees.
Example 9. Consider the polynomial system {f = 0, g ≥ 0}, where

f := x2 + x21 + 2 = 0, g := x1 − x22 + 3 ≥ 0.
20 J.A. DE LOERA, P.N. MALKIN AND P.A. PARRILO

By the Positivstellensatz, there are no solutions (x1 , x2 ) ∈ R2 if and only

if there exist polynomials t1 , s1 , s2 ∈ R[x1 , x2 ] that satisfy
s1 + s2 · g + t1 · f ≡ −1 , where s1 and s2 are SOS. (3.1)
At the D-th SDP relaxation of the polynomial problem {f = 0, g ≥
0}, one asks whether there exists a solution (t1 , s1 , s2 ) to (3.1) where the
polynomial s1 has degree ≤ D and the polynomials s2 , t1 have degree ≤
D − 2. For each fixed positive integer D this can be tested by a (possibly
large) semidefinite program. Solving this for D = 2, we find the infeasibility
certificate

2
2
s1 = 13 + 2 x2 + 23 + 6 x1 − 61 , s2 = 2, t1 = −6.
The resulting identity (3.1) proves the inconsistency of the system.
As outlined in the preceding paragraphs, there is a direct connec-
tion going from general polynomial optimization problems to SDP, via the
Positivstellensatz infeasibility certificates. Even though we have discussed
only feasibility problems here, there are obvious straightforward connec-
tions with optimization. For instance, by considering the emptiness of the
sublevel sets of the objective function, or using representation theorems
for positive polynomials, sequences of converging bounds indexed by cer-
tificate degree can be directly constructed; see e.g. [39, 23, 41]. These
schemes have been implemented in software packages such as SOSTOOLS
[42], GloptiPoly [17], and YALMIP [30].
3.2. Semidefinite programming relaxations. In the last section,
we have described the search for Positivstellensatz infeasibility certificates
formulated as a semidefinite programming problem. We now describe an al-
ternative interpretation, obtained by dualizing the corresponding semidefi-
nite programs. This is the exact analogue of the construction presented in
Section 2.2, and is closely related to the approach via truncated moment
sequences developed by Lasserre [23].
Recall that in the approach in Section 2.2, the linear relaxations were
constructed by replacing every monomial xα by a new variable λxα . Fur-
thermore, new redundant equations were obtained by multiplying an exist-
ing constraint f (x) = 0 by terms of the form xi , yielding xi f (x) = 0 (essen-
tially, generating the ideal of valid equations). In the inequality case, and as
suggested by the Positivstellensatz, new inequality constraints will be gen-
erated by both squarefree multiplication of the original constraints, and by
multiplication against sums of squares. That is, if gi (x) ≥ 0 and gj (x) ≥ 0
are valid inequalities, then so are gi (x)gj (x) ≥ 0 and gi (x)s(x) ≥ 0, where
s(x) is SOS. After substitution with the extended variables λ, we then ob-
tain a new system of linear equations and inequalities, with the property
that the resulting inequality conditions are semidefinite conditions. The
presence of the semidefinite constraints arises because we do not specify a
priori what the multipliers s(x) are, but only give their linear span.
 POLYNOMIALS IN COMBINATORIAL OPTIMIZATION 21

Example 10. Consider the problem discussed earlier in Example 9.

The corresponding relaxation is (for D = 2):
 
λ1 λx1 λx2
λx1 λx21 λx1 x2   0, λx2 +λx21 +2λ1 = 0, λx1 −λx22 +3λ1 ≥ 0,
λx2 λx1 x2 λx22

plus the condition λ1 > 0 (without loss of generality, we can take λ1 = 1).
This is a semidefinite programming problem, and in this case, its infeasi-
bility directly shows that the original system of polynomial inequalities does
not have a solution.
An appealing geometric interpretation follows from considering the
projection of the feasible set of these relaxations in the space of original
variables (i.e., λxi ). For the linear algebra relaxations of Section 2.2, we
obtain outer approximations to the affine hull of the solution set (an al-
gebraic variety), while the SDP relaxation described here constructs outer
approximations to the convex hull of the corresponding semialgebraic set.
This latter viewpoint will be further discussed in Section 3.3, for the case
of equations arising from combinatorial problems.
3.3. Theta bodies. Recall that traditional modeling of combinato-
rial optimization problems often uses 0/1 incidence vectors. The set S of
solutions of a combinatorial problem (e.g., the stable sets, traveling sales-
man tours) is often computed through the (implicit) convex hull of such
incidence vectors. Just as in the stable set and max-cut examples in Propo-
sition 1.1, the incidence vectors can be seen at the set of real solutions to a
system of polynomial equations: f1 (x) = f2 (x) = · · · = fm (x) = 0, where
f1 , . . . , fm ∈ R[x] := R[x1 , . . . , xn ]. Over the years there have been well-
known attempts to understand the structure of these convex hulls through
semidefinite programming relaxations (see [45, 33, 25, 32]) and in fact they
are closely related [26, 29]. Here we wish to summarize some recent results
that give appealing structural properties, in terms of the associated system
of equations (see [15, 14] for details).
Let us start with a historically important example: Given an undi-
rected finite graph G = (V, E), consider the set SG of characteristic vectors
of stable sets of G. The convex hull of SG , denoted by STAB(G), is the sta-
ble set polytope. As we mentioned already the vanishing ideal of SG is given
by IG := hx2i − xi (∀ i ∈ V ), xi xj (∀ {i, j} ∈ E)i which is a real radical
zero-dimensional ideal in R[x]. In [31], Lovász introduced a semidefinite
relaxation, TH(G), of the polytope STAB(G), called the theta body of G.
There are multiple descriptions of TH(G), but the one in [33, Lemma 2.17],
for instance, shows that TH(G) can be defined completely in terms of the
polynomial system IG . It is easy to show that STAB(G) ⊆ TH(G), and
remarkably, we have that STAB(G) = TH(G) if and only if the graph is
perfect. We will now explain how the case of stable sets can be generalized
to construct theta bodies for many other combinatorial problems.
22 J.A. DE LOERA, P.N. MALKIN AND P.A. PARRILO

We will construct an approximation of the convex hull of a finite set of

points S, denoted conv(S), by a sequence of convex bodies recovered from
“degree truncations” of the defining polynomial systems. In what follows
I will be a radical polynomial ideal. A polynomial f is non-negative
modulo I, written as f ≥ 0 mod I, if f (s) ≥ 0 for all s ∈ VR (I). More
strongly, the polynomial f is Pa sum of squares (sos) mod I if there
t
exists hj ∈ R[x] such that f ≡ j=1 h2j mod I for some t, or equivalently,
Pt
f − j=1 h2j ∈ I. If, in addition, each hj has degree at most k, then we
say that f is k-sos mod I. The ideal I is k-sos if every polynomial that
is non-negative mod I is k-sos mod I. If every polynomial of degree at
most d that is non-negative mod I is k-sos mod I, we say that I is (d, k)-
sos. We say that a polynomial ideal I ⊆ R[x] is THk -exact if every linear
polynomial that is non-negative over VR (I), the real variety of I, is a sum
of squares of polynomials of degree at most k modulo I.
Note that conv(VR (I)), the convex hull of VR (I), is described by the
linear polynomials f such that f ≥ 0 mod I. A certificateP for the non-
t
negativity of f mod I is the existence of a sos-polynomial j=1 h2j that
is congruent to f mod I. One can now investigate the convex hull of S
through the hierarchy of nested closed convex sets defined by the semidef-
inite programming relaxations of the set of (d, k)-sos polynomials.
Definition 3.1. Let I ⊆ R[x] be an ideal, and let k be a positive
integer. Let Σk ⊂ R[x] be the set of all polynomials that are k-sos mod I.
1. The k-th theta body of I is

THk (I) := {x ∈ Rn : f (x) ≥ 0 for every linear f ∈ Σk }.

2. The ideal I is THk -exact if the k-th theta body THk (I) coincides
with the closure of conv(VR (I)).
3. The theta-rank of I is the smallest k such that THk (I) coincides
with the closure of conv(VR (I)).
Example 11. Consider the ideal I = hx2 y − 1i ⊂ R[x, y]. Then
conv(VR (I)) = {(p1 , p2 ) ∈ R2 : p2 > 0}, and any linear polynomial that
√ over V√
is non-negative R (I) is of the form α + βy, where α, β ≥ 0. Since
αy + β ≡ ( αxy)2 + ( β)2 mod I, I is (1, 2)-sos and TH2 -exact.
Example 12. For the case of the stable sets of a graph G, one can
see that
 

 ∃ M  0, M ∈ R(n+1)×(n+1) such that 
M00 = 1,
 
TH1 (IG ) = y ∈ Rn : .

 M0i = Mi0 = Mii = yi ∀ i ∈ V 

Mij = 0 ∀ {i, j} ∈ E
 

It is known that TH1 (IG ) is precisely Lovász’s theta body of G. The ideal
IG is TH1 -exact precisely when the graph G is perfect.
By definition, TH1 (I) ⊇ TH2 (I) ⊇ · · · ⊇ conv(VR (I)). As seen in
Example 11, conv(VR (I)) may not always be closed and so the theta-body
 POLYNOMIALS IN COMBINATORIAL OPTIMIZATION 23

sequence of I can converge, if at all, only to the closure of conv(VR (I)).

But the good news for combinatorial optimization is that there is plenty of
good behavior for problems arising with a finite set of possible solutions.

3.4. Application: cuts and exact finite sets. We discuss now a

few important combinatorial examples. As we have seen in Section 2.5 for
3-colorability, and in the preceding section for stable sets, in some special
cases it is possible to give nice combinatorial characterizations of when
low-degree certificates can exactly recognize infeasibility. Here are a few
additional results for the real case:
Example 13. For the max-cut problem we saw earlier, the defining
vanishing ideal is I(SG) = hx2e − xe ∀ e ∈ E, xT ∀ T an odd cycle in Gi.
In this case one can prove that the ideal I(SG) is TH1 -exact if and only
if G is a bipartite graph. In general the theta-rank of I(SG) is bounded
above by the size of the max-cut in G. There is no constant k such that
THk (I(SG)) = conv(SG), for all graphs G. Other formulations of max-cut
are studied in [14].
Recall that when S ⊂ Rn is a finite set, its vanishing ideal I(S) is
zero-dimensional and real radical. In what follows, we say that a finite set
S ⊂ Rn is exact if its vanishing ideal I(S) ⊆ R[x] is TH1 -exact.
Theorem 3.2 ([15]). For a finite set S ⊂ Rn , the following are
equivalent.
1. S is exact.
2. There is a finite linear inequality description of conv(S) in which
for every inequality g(x) ≥ 0, g is 1-sos mod I(S).
3. There is a finite linear inequality description of conv(S) such that
for every inequality g(x) ≥ 0, every point in S lies either on the
hyperplane g(x) = 0 or on a unique parallel translate of it.
4. The polytope conv(S) is affinely equivalent to a compressed lattice
polytope (every reverse lexicographic triangulation of the polytope
is unimodular with respect to the defining lattice).
Example 14. The vertices of the following 0/1-polytopes in Rn are
exact for every n: (1) hypercubes, (2) (regular) cross polytopes, (3) hyper-
simplices (includes simplices), (4) joins of 2-level polytopes, and (5) stable
set polytopes of perfect graphs on n vertices.
More strongly one can say the following.
Proposition 3.1. Suppose S ⊆ Rn is a finite point set such that for
each facet F of conv(S) there is a hyperplane HF such that HF ∩conv(S) =
F and S is contained in at most t + 1 parallel translates of HF . Then I(S)
is THt -exact.
In [15] the authors show that theta bodies can be computed explicitly
as projections to the feasible set of a semidefinite program. These SDPs
are constructed using the combinatorial moment matrices introduced by
[28].
24 J.A. DE LOERA, P.N. MALKIN AND P.A. PARRILO

4. Recovering solutions in the feasible case. In principle, it is

possible to find the actual roots of the system of equations (and thus the
colorings, stable sets, or desired combinatorial object) whenever the relax-
ations are feasible and a few additional conditions are satisfied. Here we
discuss mostly the linear algebra relaxations case, but the semidefinite case
is very similar; see e.g. [18, 24] for this case.
We describe below how, under certain conditions, it is possible to re-
cover the solution of the original polynomial system from the relaxations
(linear or semidefinite) described in earlier sections. The main concepts
are very similar for both methodologies, and are based on the well-known
eigenvalue methods for polynomial equations; see e.g. [6, §2.4]. The key
idea for extracting solutions is the fact that from the relaxations one can
obtain a finite-dimensional representation of the vector space R/I and its
multiplicative structure, where I is the ideal hF iR (in the case of linear
relaxations). In order to do this, we need to compute a basis of the vec-
tor space R/I, and construct matrix representations for the multiplication
operators Mxi : f 7→ xi f . Then, we can use the eigenvalue/eigenvector
methods to compute solutions (see e.g., [10]).
A sufficient condition for the existence of a suitable basis of R/I is
given by Theorem 2.2. Under this condition, multiplication matrices Mxi
can be easily computed. In particular, if we have computed a set F ⊂ R
that satisfies the conditions of Theorem 2.2 by running FPNulLA, then
finding a basis of R/I and computing its multiplicative structure is straight-
forward using linear algebra (see e.g., [36]). By construction, the matrices
Mxi commute pairwise, and to obtain the roots one must diagonalize the
corresponding commutative algebra. It is well-known (see, e.g., [6]), that
this can be achieved by forming a random linear combination of these ma-
trices. This random matrix will generically have distinct eigenvalues, and
the corresponding matrix of eigenvectors will give the needed change of
basis. In the case of a finite field, it is enough to choose the random co-
efficients over an algebraic extension of sufficiently large degree, instead of
working over the algebraic closure (alternatively, the more efficient meth-
ods in [11] can be used). The entries of the diagonalized matrices directly
provide the coordinates of the roots.
Remark 4.1. The condition in Theorem (2.2) can in general be a
strong requirement for recovery of solutions, since it implies that we can
obtain all solutions of the polynomial system. In some occasions, it may be
desirable to obtain just a single solution, in which case weaker conditions
may be of interest.
Example 15. Consider the following polynomial system over F2 , that
corresponds to the 3-colorings of the six-node graph in Figure 4:
x3i + 1 = 0 ∀i ∈ V, x2i + xi xj + x2j = 0 ∀(i, j) ∈ E.
We add to these equations the symmetry-breaking constraint x0 = 1. After
running NuLLA with this system as an input, we obtain multiplication
 POLYNOMIALS IN COMBINATORIAL OPTIMIZATION 25
x0

x1

x3 x2

x5 x4

Fig. 4. Graph for Example 15.

matrices over F2 , of dimensions 4 × 4, given by:

     
0 0 1 1 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 1 0 0 0 1
M x1 = 0
 M x2 =   M x3 =  
1 1 0 1 0 1 1 1 1 0 1
1 1 0 1 0 1 1 0 1 0 1 1
   
1 1 0 0 0 1 0 0
1 0 0 0 1 1 0 0
M x4 = 0
 M x5 =  
0 1 1 0 0 0 1
0 0 1 0 0 0 1 1

Diagonalizing the corresponding commutative algebra, we obtain the change

of basis matrix given by
 
1 1 1 1
ω 2 ω ω ω 2 
T = 1 1 ω2 ω  ,


ω2 ω 1 1

where ω is a primitive root of 1, i.e., it satisfies w2 + w + 1 = 0. It can be

easily verified that all the matrices T −1 Mxi T are diagonal, and given by:

T −1 Mx1 T = diag[ω, ω 2 , ω, ω 2 ] T −1 Mx2 T = diag[ω 2 , ω, 1, 1]

T −1 Mx3 T = diag[1, 1, ω 2 , ω] T −1 Mx4 T = diag[ω, ω 2 , ω 2 , ω]
T −1 Mx5 T = diag[ω 2 , ω, ω, ω 2 ],

which correspond to the four possible 3-colorings of the graph. For instance,
from the second diagonal entry of each matrix we obtain the feasible coloring
(x0 , x1 , x2 , x3 , x4 , x5 ) → (1, ω 2 , ω, 1, ω 2 , ω).

REFERENCES

[1] E. Balas, S. Ceria, and G. Cornuéjols, A lift-and-project cutting plane al-

gorithm for mixed 0-1 programs, Mathematical Programming, 58 (1993),
pp. 295–324.
26 J.A. DE LOERA, P.N. MALKIN AND P.A. PARRILO

[2] J. Bochnak, M. Coste, and M.-F. Roy, Real algebraic geometry, Springer, 1998.
[3] M. Clegg, J. Edmonds, and R. Impagliazzo, Using the Groebner basis algorithm
to find proofs of unsatisfiability, in STOC ’96: Proceedings of the twenty-
eighth annual ACM symposium on Theory of computing, New York, NY,
USA, 1996, ACM, pp. 174–183.
[4] N. Courtois, A. Klimov, J. Patarin, and A. Shamir, Efficient algorithms for
solving overdefined systems of multivariate polynomial equations, in EURO-
CRYPT, 2000, pp. 392–407.
[5] D. Cox, J. Little, and D. O’Shea, Ideals, Varieties and Algorithms: An In-
troduction to Computational Algebraic Geometry and Commutative Algebra,
Springer Verlag, 1992.
[6] , Using Algebraic Geometry, vol. 185 of Graduate Texts in Mathematics,
Springer, 2nd ed., 2005.
[7] J. De Loera, C. Hillar, P. Malkin, and A. Woo, Algebraic certificates of com-
binatorial infeasibility and their algorithmic consequences, manuscript, (2009).
[8] J. De Loera, J. Lee, P. Malkin, and S. Margulies, Hilbert’s Nullstellensatz
and an algorithm for proving combinatorial infeasibility, in Proceedings of the
Twenty-first International Symposium on Symbolic and Algebraic Computa-
tion (ISSAC 2008), 2008.
[9] J. De Loera, J. Lee, S. Margulies, and S. Onn, Expressing combinatorial opti-
mization problems by systems of polynomial equations and the nullstellensatz,
to appear in the Journal of Combinatorics, Probability and Computing, (2008).
[10] A. Dickenstein and I. Emiris, eds., Solving Polynomial Equations: Founda-
tions, Algorithms, and Applications, vol. 14 of Algorithms and Computation
in Mathematics, Springer Verlag, Heidelberg, 2005.
[11] W. Eberly and M. Giesbrecht, Efficient decomposition of associative algebras
over finite fields, Journal of Symbolic Computation, 29 (2000), pp. 441–458.
[12] A. V. Gelder, Another look at graph coloring via propositional satisfiability, Dis-
crete Appl. Math., 156 (2008), pp. 230–243.
[13] E. Gilbert, Random graphs, Annals of Mathematical Statistics, 30 (1959),
pp. 1141–1144.
[14] J. Gouveia, M. Laurent, P. A. Parrilo, and R. R. Thomas, A new semidefi-
nite programming relaxation for cycles in binary matroids and cuts in graphs.
http://www.arxiv.org:0907.4518, 2009.
[15] J. Gouveia, P. A. Parrilo, and R. R. Thomas, Theta bodies for polynomial
ideals. http://www.arxiv.org:0809.3480, 2008.
[16] D. Grigoriev and N. Vorobjov, Complexity of Nullstellensatz and Positivstel-
lensatz proofs, Annals of Pure and Applied Logic, 113 (2002), pp. 153–160.
[17] D. Henrion and J.-B. Lasserre, GloptiPoly: Global optimization over polyno-
mials with MATLAB and SeDuMi, ACM Trans. Math. Softw., 29 (2003),
pp. 165–194.
[18] , Detecting global optimality and extracting solutions in GloptiPoly, in Pos-
itive polynomials in control, vol. 312 of Lecture Notes in Control and Inform.
Sci., Springer, Berlin, 2005, pp. 293–310.
[19] T. Hogg and C. Williams, The hardest constraint problems: a double phase
transition, Artif. Intell., 69 (1994), pp. 359–377.
[20] A. Kehrein and M. Kreuzer, Characterizations of border bases, Journal of Pure
and Applied Algebra, 196 (2005), pp. 251 – 270.
[21] A. Kehrein, M. Kreuzer, and L. Robbiano, An algebraist’s view on border bases,
in Solving Polynomial Equations: Foundations, Algorithms, and Applications,
A. Dickenstein and I. Emiris, eds., vol. 14 of Algorithms and Computation in
Mathematics, Springer Verlag, Heidelberg, 2005, ch. 4, pp. 160–202.
[22] J. Kollár, Sharp effective Nullstellensatz, Journal of the AMS, 1 (1988), pp. 963–
975.
[23] J. Lasserre, Global optimization with polynomials and the problem of moments,
SIAM J. on Optimization, 11 (2001), pp. 796–817.
 POLYNOMIALS IN COMBINATORIAL OPTIMIZATION 27

[24] J. Lasserre, M. Laurent, and P. Rostalski, A unified approach to computing

real and complex zeros of zero-dimensional ideals, in Emerging Applications
of Algebraic Geometry, M. Putinar and S. Sullivant, eds., vol. 149 of IMA
Volumes in Mathematics and its Applications, Springer, 2009, pp. 125–155.
[25] J. B. Lasserre, An explicit equivalent positive semidefinite program for nonlinear
0-1 programs, SIAM J. on Optimization, 12 (2002), pp. 756–769.
[26] M. Laurent, A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre
relaxations for 0–1 programming, Math. Oper. Res., 28 (2003), pp. 470–496.
[27] , Semidefinite relaxations for max-cut, in The Sharpest Cut: The Impact
of Manfred Padberg and His Work, M. Grötschel, ed., vol. 4 of MPS-SIAM
Series in Optimization, SIAM, 2004, pp. 257–290.
[28] , Semidefinite representations for finite varieties, Mathematical Program-
ming, 109 (2007), pp. 1–26.
[29] , Sums of squares, moment matrices and optimization over polynomials, in
Emerging Applications of Algebraic Geometry, M. Putinar and S. Sullivant,
eds., vol. 149 of IMA Volumes in Mathematics and its Applications, Springer,
2009, pp. 157–270.
[30] J. Löfberg, YALMIP: A toolbox for modeling and optimization in MATLAB, in
Proceedings of the CACSD Conference, Taipei, Taiwan, 2004.
[31] L. Lovász, Stable sets and polynomials, Discrete Math., 124 (1994), pp. 137–153.
[32] , Semidefinite programs and combinatorial optimization, in Recent advances
in algorithms and combinatorics, B. Reed and C. Sales, eds., vol. 11 of CMS
Books in Mathematics, Spring, New York, 2003, pp. 137–194.
[33] L. Lovász and A. Schrijver, Cones of matrices and set-functions and 0-1 opti-
mization, SIAM J. Optim., 1 (1991), pp. 166–190.
[34] S. Margulies, Computer Algebra, Combinatorics, and Complexity: Hilbert’s Null-
stellensatz and NP-Complete Problems, PhD thesis, UC Davis, 2008.
[35] M. Marshall, Positive polynomials and sums of squares, vol. 146 of Mathematical
surveys and monographs, American Math. Society, 2008.
[36] B. Mourrain, A new criterion for normal form algorithms, in Proc. AAECC,
vol. 1719 of LNCS, Springer, 1999, pp. 430–443.
[37] B. Mourrain and P. Trébuchet, Stable normal forms for polynomial system
solving, Theoretical Computer Science, 409 (2008), pp. 229 – 240. Symbolic-
Numerical Computations.
[38] Y. Nesterov, Squared functional systems and optimization problems, in High Per-
formance Optimization, J. F. et al eds., ed., Kluwer Academic, 2000, pp. 405–
440.
[39] P. A. Parrilo, Structured semidefinite programs and semialgebraic geometry
methods in robustness and optimization, PhD thesis, California Institute of
Technology, May 2000.
[40] , Semidefinite programming relaxations for semialgebraic problems, Mathe-
matical Programming, 96 (2003), pp. 293–320.
[41] P. A. Parrilo and B. Sturmfels, Minimizing polynomial functions, in Pro-
ceedings of the DIMACS Workshop on Algorithmic and Quantitative Aspects
of Real Algebraic Geometry in Mathematics and Computer Science (March
2001), S. Basu and L. Gonzalez-Vega, eds., American Mathematical Society,
Providence RI, 2003, pp. 83–100.
[42] S. Prajna, A. Papachristodoulou, P. Seiler, and P. A. Parrilo, SOSTOOLS:
Sum of squares optimization toolbox for MATLAB, 2004.
[43] G. Reid and L. Zhi, Solving polynomial systems via symbolic-numeric reduction
to geometric involutive form, Journal of Symbolic Computation, In Press,
Corrected Proof (2008).
[44] A. Schrijver, Theory of linear and integer programming, Wiley, 1986.
[45] H. Sherali and W. Adams, A hierarchy of relaxations between the continuous
and convex hull representations for zero-one programming problems, SIAM
Journal on Discrete Mathematics, 3 (1990), pp. 411–430.
28 J.A. DE LOERA, P.N. MALKIN AND P.A. PARRILO

[46] N. Z. Shor, Class of global minimum bounds of polynomial functions, Cybernetics,

23 (1987), pp. 731–734.
[47] G. Stengle, A Nullstellensatz and a Positivstellensatz in semialgebraic geometry,
Mathematische Annalen, 207 (1973), pp. 87–97.
[48] H. Stetter, Numerical Polynomial Algebra, SIAM, 2004.
[49] L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Review, 38
(1996), pp. 49–95.
[50] L. Zhang, zchaff v2007.3.12. Available at
http://www.princeton.edu/ chaff/zchaff.html, 2007.