MIT 6.7220/15.084 — Nonlinear Optimization (Spring ‘25) Tue, Mar 11th 2025
Lecture 10
Polynomial optimization
Instructor: Prof. Gabriele Farina ( gfarina@mit.edu)★
As mentioned in Lecture 9, semidefinite programming has established itself as an extremely
important tool, with disparate applications in combinatorial optimization, control theory,
and machine learning. Under the appropriate assumptions (namely strict feasibility), semi7
definite programs can be solved efficiently, and strong commercial solvers are available. In
this lecture, we will see how semidefinite programming can be used to relax a large class of
nonconvex problems that includes combinatorial problems as well, and find globally optimal
solutions.
L10.1 Polynomial optimization problems
In this lecture, we focus on polynomial optimization problems,¹ that is, problems of the form
min
𝑥
s.t.
𝑓(𝑥)
𝑔𝑗(𝑥) ≥ 0 𝑗 = 1, ..., 𝑚
𝑥 ∈ ℝ𝑛,
where 𝑓 and the 𝑔𝑗 are 𝑛7variate polynomials with real coefficients, i.e., 𝑓, 𝑔𝑗 ∈ ℝ[𝑥]. This
class of problems is very expressive. To start, it contains nonconvex problems. For example,
these are just two small examples of feasible sets expressible via bivariate polynomials.
−2 −1 1 2 𝑥1
−2
−1
1
2
𝑥2
0 −1 1 2 𝑥1
−1
1
𝑥2
0
Ω1 ≔ {𝑥4
1 + 𝑥4
2 − 1
2𝑥3
1𝑥2 − 2𝑥2
2 − 𝑥2
1𝑥2
2 ≤ 1} Ω2 ≔ {1 − 4𝑥2
1 + 4𝑥1𝑥2
2 + 𝑥3
1 ≥ 0
(𝑥1 − 1
2 )2 + 𝑥2
2 ≤ 2.
This class of problems also contains combinatorial optimization problems known to be
hard, such as the maximum cut problem (see Lecture 1). The reason why combinatorial
optimization problems can easily be expressed by polynomial optimization problems is that
the condition 𝑥 ∈ {0, 1} can be equivalently written as the pair of polynomial constraints
𝑥(1 − 𝑥) ≤ 0, −𝑥(1 − 𝑥) ≤ 0.
The key takeaway of this lecture is that polynomial optimization problems can, under mild
assumptions, be converted into semidefinite programs. Two observations are immediate:
• Polynomial optimization problems are nonconvex, but semidefinite programs are
convex conic problems. It is a priori not obvious at all that the latter can be used to
solve the former.
• There is no free lunch: polynomial optimization problems are very expressive, and
can capture computationally hard problems. In contrast, semidefinite programs can
be solved in time polynomial in the dimension (under suitable hypotheses). The catch
is that the semidefinite program relaxations we will consider need to be, in the worst
case, of dimension exponential in the degree and number of variables of the polynomial
problem considered. In practice, however, very good results are achieved already for
relaxations of dimension way lower than what the theory predicts.
L10.2 The cone of nonnegative polynomials
To begin our exploration, let’s focus on the simplest of settings: unconstrained optimization.
In particular, suppose that we would like to find the minimum of a polynomial 𝑝(𝑥) in ℝ𝑛.
(Note that the question is meaningful only if the degree of 𝑝 is even, as otherwise 𝑝 is not
lower bounded.)
Computationally, the problem of computing the minimum of a generic polynomial 𝑝(𝑥) is
equivalent to the question of being able to check whether a generic polynomial 𝑞(𝑥) satisfies
𝑞(𝑥) ≥ 0 for all 𝑥 ∈ ℝ𝑛. In one direction, if we can compute min 𝑞(𝑥), then we can answer
whether 𝑞(𝑥) ≥ 0 by simply checking if the minimum is below or above 0. In the other
direction, if we can check whether 𝑞(𝑥) ≥ 0 for all 𝑥 ∈ ℝ𝑛, then we can compute min 𝑝(𝑥)
by performing a binary search over 𝑡, until we find the largest 𝑡 such that 𝑝(𝑥) − 𝑡 ≥ 0 for
all 𝑥 ∈ ℝ𝑛. For this reason, we will be interested in understanding more about the following
object.
Definition L10.1 (Cone of nonnegative polynomials). The cone of nonnegative polyno
mials is the set of all polynomials 𝑝 ∈ ℝ[𝑥] such that 𝑝(𝑥) ≥ 0 for all 𝑥 ∈ ℝ𝑛. We will
denote this set by ℝ[𝑥]≥0.
It is immediate to check [▷ You should check!] that the set ℝ[𝑥]≥0 is a closed convex cone.
L10.2.1 Complexity considerations
Unfortunately, deciding whether a polynomial is nonnegative in ℝ𝑛 is as hard as deciding
membership in the copositive cone, which is NP7hard [DG14].
Theorem L10.1. Deciding membership in the cone of nonnegative polynomials ℝ[𝑥]≥0
for any polynomial of degree ≥ 4 with 𝑛 ≥ 2 variables is computationally intractable.
Proof. By reduction from the problem of deciding if a symmetric matrix 𝑀 ∈ ℝ𝑛×𝑛 is
copositive (see Lecture 9), that is,
𝑧⊤𝑀 𝑧 ≥ 0 ∀𝑧 ∈ ℝ𝑛
≥0.
Indeed, consider the 𝑛7variate polynomial of degree 4 defined as
𝑝(𝑥1, ..., 𝑥𝑛) ≔
(
(((𝑥2
1
⋮
𝑥2
𝑛)
)))
⊤
𝑀
(
(((𝑥2
1
⋮
𝑥2
𝑛)
))).
If 𝑀 is copositive, this polynomial is nonnegative on ℝ𝑛, since the vector of squares
(𝑥2
1, ..., 𝑥2
𝑛) is always nonnegative. Conversely, if 𝑝 is nonnegative on ℝ𝑛, then since
(𝑥2
1, ..., 𝑥2
𝑛) spans all of ℝ𝑛
≥0, we have that 𝑀 is copositive. □
As a side remark, this is the second convex set we see for which membership—let alone
optimization—is intractable (the first being the copositive cone). This should serve as a
reminder that equating convexity with tractability can be a dangerous oversimplification.
L10.3 Sum-of-squares polynomials
Theorem L10.1 shows that even deciding membership in the cone of nonnegative polynomials
is hard in general, let alone optimizing over it. This begs the question of what is the largest
set of polynomials for which deciding nonnegativity is easy. The following cone will provide
an extremely important step in this direction.
Definition L10.2 (Sum7of7squares polynomials, Σ[𝑥]). An 𝑛7variate polynomial 𝑝 ∈ ℝ[𝑥]
is said to be a sumofsquares polynomial (or SOS for short) if it can be written as
𝑝(𝑥) = ∑
𝑘
𝑝𝑘(𝑥)2, 𝑥 ∈ ℝ𝑛
for appropriate polynomials 𝑝𝑘 ∈ ℝ[𝑥].
Remark L10.1. Only polynomials of even degree can be sum7of7squares. Furthermore, if
𝑝 has degree 2𝑑, then each of the 𝑝𝑘’s can only have degree at most 𝑑.
It is immediate to check [▷ you should check!] that the set of sum7of7squares polynomials is
a closed, convex, nonempty cone. Furthermore, every sum7of7squares polynomial is clearly
a nonnegative polynomial, so Σ[𝑥] ⊆ ℝ[𝑥]≥0. In general, the inclusion is strict, as there
exist polynomials that are nonnegative but not sum7of7squares. We will see a well7known
example, called the Motzkin polynomial, later in this lecture in Example L10.2.
L10.3.1 The connection to the positive semidefinite cone
Unlike the cone of nonnegative polynomials, the cone of sum7of7squares polynomials is easy
to characterize. The following theorem provides a very useful criterion for deciding whether
a polynomial is sum7of7squares.
Theorem L10.2. Membership in the cone of sum7of7squares polynomials can be deter7
mined by checking the feasibility of a semidefinite program. In particular, let 𝑝(𝑥) be
an arbitrary polynomial of degree 2𝑑 in 𝑛 variables, and let 𝑣𝑑 be the vector of all
monomials of degree up to 𝑑 that can be constructed using the variables 𝑥.
Then, 𝑝(𝑥) ∈ Σ[𝑥] if and only if there exists a positive semidefinite matrix 𝑄 such that
𝑝(𝑥) = (𝑣𝑑(𝑥))⊤𝑄𝑣𝑑(𝑥),
Proof. (⟹) Any polynomial of degree up to 𝑑 can be written as a linear combination of
the monomials in 𝑣𝑑. Hence, any sum7of7squares polynomial can be written in the form
𝑝(𝑥) = ∑
𝑘
(𝑣𝑑(𝑥)⊤𝛼𝑘)2
for some appropriate coefficient vectors 𝛼𝑘. But then, we can write
𝑝(𝑥) =
‖
‖
‖
‖
(
((((— 𝛼⊤
1 —
— 𝛼⊤
2 —
⋮ )
))))
⏟⏟⏟⏟⏟
≕ 𝐶
𝑣𝑑(𝑥)
‖
‖
‖
‖2
= (𝑣𝑑(𝑥))⊤𝐶 ⊤𝐶𝑣𝑑(𝑥). (1)
Since a matrix of the form 𝐶⊤𝐶 is positive semidefinite, this direction holds.
(⟸) Conversely, if 𝑝(𝑥) = (𝑣𝑑(𝑥))⊤𝑄𝑣𝑑(𝑥) for some positive semidefinite matrix 𝑄, we
can write 𝑄 = 𝐶⊤𝐶 for some 𝐶. But then, we can use (1) from right to left and extract
from the rows of 𝐶 the coefficients 𝛼𝑘 for the sum7of7squares representation of 𝑝(𝑥). □
Example L10.1. A bivariate polynomial 𝑝(𝑥1, 𝑥2) of degree 4 is a sum7of7squares poly7
nomial if and only if there exists 𝑄 ⪰ 0 such that
𝑝(𝑥1, 𝑥2) =
(
(((((((((((( 𝑥2
1
𝑥1𝑥2
𝑥2
2
𝑥1
𝑥2
1 )
))))))))))))
⊤
(
((((((((((((𝑞00
𝑞01
𝑞02
𝑞03
𝑞04
𝑞05
𝑞01
𝑞11
𝑞12
𝑞13
𝑞14
𝑞15
𝑞02
𝑞12
𝑞22
𝑞23
𝑞24
𝑞25
𝑞03
𝑞13
𝑞23
𝑞33
𝑞34
𝑞35
𝑞04
𝑞14
𝑞24
𝑞34
𝑞44
𝑞45
𝑞05
𝑞15
𝑞25
𝑞35
𝑞45
𝑞55)
))))))))))))
(
(((((((((((( 𝑥2
1
𝑥1𝑥2
𝑥2
2
𝑥1
𝑥2
1 )
))))))))))))
= (𝑞00)𝑥4
1 + (2𝑞01)𝑥3
1𝑥2 + (𝑞11 + 2𝑞02)𝑥2
1𝑥2
2 + (2𝑞12)𝑥1𝑥3
2 + (𝑞22)𝑥4
2
+ (2𝑞03)𝑥3
1 + (2𝑞04 + 2𝑞13)𝑥2
1𝑥2 + (2𝑞23 + 2𝑞14)𝑥1𝑥2
2 + (2𝑞24)𝑥3
2
+ (𝑞33 + 2𝑞05)𝑥2
1 + (2𝑞15 + 2𝑞34)𝑥1𝑥2 + (𝑞44 + 2𝑞25)𝑥2
2
+ (2𝑞35)𝑥1 + (2𝑞45)𝑥2 + (𝑞55).
In other words, 𝑝(𝑥1, 𝑥2) is SOS if and only if its coefficients match the expressions
computed in the previous line, for an appropriate positive semidefinite 𝑄.
Note that the coefficients of the polynomial 𝑣(𝑥)⊤𝑄𝑣(𝑥) are always a linear function of the
entries of the matrix 𝑄. Hence, we obtain the following corollary.
Corollary L10.1. The cone of 𝑛7variate sum7of7squares polynomials of degree 2𝑑 is a
linear transformation of the cone of 𝑠 × 𝑠 positive semidefinite matrices, where 𝑠 =
(𝑛+𝑑
𝑑 ) is the dimension of the vector 𝑣𝑑(𝑥).
L10.3.2 An approach to unconstrained polynomial optimization
By replacing the cone of nonnegative polynomials with the cone of sum7of7squares polyno7
mials, we can obtain an approximation for the minimum of a polynomial over ℝ𝑛. The
key idea is to find a value 𝑡 such that we can certify that 𝑝(𝑥) − 𝑡 ∈ Σ[𝑥]. In that case, it
immediately follows that 𝑝(𝑥) ≥ 𝑡 for all 𝑥 ∈ ℝ𝑛.
As a concrete example, suppose we would like
to approximate the minimum of the bivariate
polynomial of fourth degree
𝑝(𝑥1, 𝑥2) ≔ 𝑥4
1 + 𝑥4
2 − 1
2𝑥3
1𝑥2 − 2𝑥2
2 − 𝑥2
1𝑥2
2,
whose level sets are shown on the right.
If we could find a value 𝑡 such that we can
certify that 𝑝(𝑥1, 𝑥2) − 𝑡 ∈ Σ[𝑥], that would
immediately prove that 𝑝(𝑥1, 𝑥2) ≥ 𝑡 for all 𝑥 ∈
ℝ𝑛.
To certify that 𝑝(𝑥1, 𝑥2) − 𝑡 ∈ Σ[𝑥], we know
from Theorem L10.2 and Example L10.1 that
−2 −1 1 2 𝑥1
−2
−1
1
2
𝑥2
0
it suffices to find a positive semidefinite matrix 𝑄 ⪰ 0 that enables writing 𝑝(𝑥1, 𝑥2) − 𝑡 in
the form 𝑣2(𝑥)⊤𝑄𝑣2(𝑥). More explicitly, using the expansion from Example L10.1, we are
interested in solving the following semidefinite program.
max 𝑡
s.t. ∙ 𝑞00 = 1 (coeff. of 𝑥4
1)
∙ 2𝑞01 = −1
2 (coeff. of 𝑥3
1𝑥2)
∙ 𝑞11 + 2𝑞02 = −1 (coeff. of 𝑥2
1𝑥2
2)
∙ 2𝑞12 = 0 (coeff. of 𝑥1
1𝑥3
2)
∙ 𝑞22 = 1 (coeff. of 𝑥4
2)
∙ 2𝑞03 = 0 (coeff. of 𝑥3
1)
∙ 2𝑞04 + 2𝑞13 = 0 (coeff. of 𝑥2
1𝑥2)
∙ 2𝑞23 + 2𝑞14 = 0 (coeff. of 𝑥1
1𝑥2
2)
∙ 2𝑞24 = 0 (coeff. of 𝑥3
2)
∙ 𝑞33 + 2𝑞05 = 0 (coeff. of 𝑥2
1)
∙ 2𝑞15 + 2𝑞34 = 0 (coeff. of 𝑥1𝑥2)
∙ 𝑞44 + 2𝑞25 = −2 (coeff. of 𝑥2
2)
∙ 2𝑞35 = 0 (coeff. of 𝑥1)
∙ 2𝑞45 = 0 (coeff. of 𝑥2)
∙ 𝑞55 = −𝑡 (constant)
∙ 𝑄 = [𝑞𝑖𝑗] ⪰ 0.
Feeding the semidefinite program into a solver,² we find that the optimal objective has value
𝑡⋆ ≈ −2.08053, obtained by the positive semidefinite matrix
𝑄⋆ ≈
(
((((((((((( 1.0
−0.25
−0.579
0.0
0.0
−0.073
−0.25
0.159
0.0
0.0
0.0
0.135
−0.579
0.0
1.0
0.0
0.0
−1.062
0.0
0.0
0.0
0.146
−0.135
0.0
0.0
0.0
0.0
−0.135
0.124
0.0
−0.0734
0.135
−1.062
0.0
0.0
2.080 )
)))))))))))
⪰ 0.
This means that the polynomial 𝑝(𝑥1, 𝑥2) − 𝑡⋆ is proved to belong in Σ[𝑥], and therefore
𝑝(𝑥1, 𝑥2) ≥ −2.08053 for all 𝑥1, 𝑥2 ∈ ℝ. The following two questions are natural:
1. Is this value optimal (i.e., does it indeed match the minimum of 𝑝 over ℝ𝑛)?
2. And if not, what could we do to improve the bound?
We will address these questions in the next section.
L10.4 Characterizing global nonnegativity using the SOS cone
The SOS cone provides a computationally viable relaxation of the cone of nonnegative
polynomials. But how much do we lose by shifting our focus from nonnegative to SOS
polynomials? As it turns out, the set of nonnegative polynomials of degree up to 𝑑 can
be approximated arbitrarily closely by the using SOS polynomials of degrees potentially
exponential in 𝑑.
L10.4.1 When are the SOS and nonnegative polynomial cone equal?
In fact, in some cases, the cone of sum7of7squares polynomials is exactly equal to the cone
of nonnegative polynomials. This is the content of Hilbert’s theorem.
Theorem L10.3 (Hilbert). ℝ[𝑥]≥0 = Σ[𝑥] if and only if:
• 𝑛 = 1, no matter the degree 𝑑; or
• 𝑑 = 2, no matter the number of variables 𝑛; or
• 𝑛 = 2 and 𝑑 = 4.
The cases for 𝑛 = 1 can be shown easily starting from a factorization of the polynomial [▷
You should try to prove that special case!].
Remark L10.2. Hilbert’s theorem shows that in the example of Section L10.3.2 we were
not just randomly lucky: the polynomial we considered was bivariate and of degree 4;
hence, the condition 𝑝(𝑥) − 𝑡 ∈ Σ[𝑥] was exactly equivalent to 𝑝(𝑥) − 𝑡 ∈ ℝ[𝑥]≥0.
Other than the three settings above, in general the cone of sum7of7squares polynomials is a
strict subset of the cone of nonnegative polynomials. Explicit examples of polynomials that
are nonnegative and yet not sum7of7squares are known, as we show next.
Example L10.2 (Motzkin’s polynomial). The polynomial
𝑀 (𝑥1, 𝑥2) ≔ 𝑥4
1𝑥2
2 + 𝑥2
1𝑥4
2 − 3𝑥2
1𝑥2
2 + 1
is not a sum7of7squares polynomial, but it is nonnegative on ℝ2, since from the arith7
metic7geometric mean inequality we have
𝑥4
1𝑥2
2 + 𝑥2
1𝑥4
2 + 1
3 ≥ 3
√𝑥4
1𝑥2
2 ⋅ 𝑥2
1𝑥4
2 ⋅ 1 = 𝑥2
1𝑥2
2.
[▷ As an exercise, show that the Motzkin polynomial is not a sum7of7squares polynomial.
One approach is to write the semidefinite program certifying membership of the polynomial
in Σ[𝑥], and showing that it is infeasible.]
L10.4.2 Hilbert’s conjecture and Artin’s theorem
As discussed above, being sum7of7squares is sufficient but not necessary for a polynomial
to be nonnegative in general. One might then try to consider other sufficient conditions,
hoping to cast a wider and wider net encompassing all nonnegative polynomials.
For example, even if a polynomial 𝑝(𝑥) is not sum7of7squares, if we could find two sum7of7
squares polynomials 𝑞(𝑥), 𝑟(𝑥) such that
𝑝(𝑥) = 𝑞(𝑥)
𝑟(𝑥)
and 𝑟(𝑥) divides 𝑞(𝑥).
Example L10.3. The Motzkin polynomial can be written as (replacing 𝑥 ≔ 𝑥1, 𝑦 ≔ 𝑥2)
𝑥4𝑦2 + 𝑥2𝑦4 − 3𝑥2𝑦2 + 1 = 𝑥2𝑦2(𝑦2 + 𝑥2 − 2)2 + 𝑥2(𝑦2 − 1)2 + 𝑦2(𝑥2 − 1)2
𝑥2 + 𝑦2
where both the numerator and the denominator are sum7of7squares polynomials. [▷ You
should verify this!]
In his famous 17th problem, Hilbert conjectured that the condition above is necessary
for a polynomial to be nonnegative. This conjecture was proved by Artin in 1927 via the
Artin7Schreier theory. A celebrated result by Polyá later showed that for homogeneous
polynomials (i.e., those where every term has the same degree), without loss of generality
one can focus on denominators in the form 𝑟(𝑥) = (𝑥2
1 + ⋯ + 𝑥2
𝑛)𝑑′
for some 𝑑′ ∈ ℕ to check
positivity in ℝ𝑛 ∖ {0}. In general, to check positivity one can search for 𝑞, 𝑟 ∈ Σ[𝑥] such
that 𝑟(𝑥)𝑝(𝑥) = 1 + 𝑞(𝑥). To check nonnegativity, one can search for 𝑞, 𝑟 ∈ Σ[𝑥] and ℓ ∈ ℕ
such that 𝑟(𝑥)𝑝(𝑥) = 𝑝(𝑥)2ℓ + 𝑞(𝑥).
Combined, these results show that checking nonnegativity of polynomials of degree up to
𝑑 can be approximated arbitrarily closely by using SOS polynomials of degrees potentially
exponential in 𝑑. Concrete bounds are known (but are very pessimistic). For today, the
important thing is the message: SOS polynomials provide a complete characterization of
nonnegative polynomials, as long as one is willing to look into high7degree SOS polynomials.
L10.5 The constrained case: Putinar’s Positivstellensatz
Having understood more of the unconstrained case, we can now focus on the more general
case of polynomial optimization problems with constraints.
For simplicity, we focus on the case of polynomial optimization problems in which at least
one of the constraints 𝑔𝑗(𝑥) ≥ 0 defines a feasible set {𝑥 ∈ ℝ𝑛 : 𝑔𝑗(𝑥) ≥ 0} that is compact.
In this setting, the following important result serves as a bridge for how to use SOS
polynomials to solve polynomial optimization problems.
Theorem L10.4 (Putinar’s Positivstellensatz). Let
Ω ≔ {𝑥 ∈ ℝ𝑛 : 𝑔𝑗(𝑥) ≥ 0 ∀𝑗 = 1, ..., 𝑚},
where {𝑥 ∈ ℝ𝑛 : 𝑔𝑗(𝑥) ≥ 0} is compact for at least one 𝑗 ∈ {1, ..., 𝑚}. Any polynomial
𝑝 ∈ ℝ[𝑥] positive on Ω can be written in the form
𝑝 = 𝜎0 + ∑
𝑚
𝑗=1
𝜎𝑗𝑔𝑗
for appropriate SOS polynomials 𝜎𝑗 ∈ Σ[𝑥], 𝑗 = 0, ..., 𝑚.
More general versions that apply without the compactness restriction above are also known
(e.g., Stengle’s Positivstellensatz and Schmüdgen’s Positivstellensatz).
Again, bounds are known for the degree of the SOS polynomials that are needed in Putinar’s
theorem. In practice, however, very good results are achieved already for relaxations of
dimension way lower than what the theory predicts. In particular, to check whether 𝑝(𝑥) >
𝑡, we can try to see if there exist SOS polynomials 𝜎𝑗 of degree up to some 𝛾 ∈ ℕ, such
that 𝑝(𝑥) − 𝑡 = 𝜎0 + ∑𝑚
𝑗=1 𝜎𝑗𝑔𝑗. For each 𝜎𝑗, we will be looking for a corresponding positive
semidefinite matrix 𝑄𝑗 that enables writing 𝜎𝑗(𝑥) = 𝑣𝛾 (𝑥)⊤𝑄𝑗𝑣𝛾 (𝑥). Overall, for any given
𝛾 we will be writing a positive semidefinite program.
L10.5.1 An example
As a final example, suppose we want to find the minimum 𝑥7coordinate of any point (𝑥1, 𝑥2)
in the set
Ω2 ≔ {1 − 4𝑥2
1 + 4𝑥1𝑥2
2 + 𝑥3
1 ≥ 0
(𝑥 − 1
2 )2 + 𝑦2 ≤ 2.
shown in Section L10.1. In this case, we have
𝑔1(𝑥1, 𝑥2) ≔ 𝑥3
1 + 4𝑥1𝑥2
2 − 4𝑥2
1 + 1, 𝑔2(𝑥1, 𝑥2) ≔ −(𝑥1 − 1
2 )
2
− 𝑥2
2 + 2.
If we look for sum7of7square polynomials 𝜎0, 𝜎1, 𝜎2 ∈ Σ[𝑥] of degrees 2, 4, 6, 8, 10, we find
the following objective values.
Degree of 𝜎𝑗 Objective value
2 infeasible
4 −0.91421
6 −0.91421
8 −0.47283
10 −0.47283
The value −0.47283 is indeed the correct an7
swer, as you can see on the magnified plot on
the right.
−0.5 0.5 1 1.5 𝑥1
−1.5
−1
−0.5
0.5
1
1.5
𝑥2
0
L10.6 Further readings
The field of polynomial optimization is vast and has seen a lot of activity in the last few
decades. Several connections between polynomial optimization and real algebraic geometry
run deep. Several excellent books and surveys are available, including those of Lasserre, J.
B. [Las15], Blekherman, G., Parrilo, P. A., & Thomas, R. R. [BPT12], and Nie, J. [Nie23].
Bibliography for this lecture
[DG14] Dickinson, P. J., & Gijben, L. (2014). On the computational complexity of mem7
bership problems for the completely positive cone and its dual. Computational
Optimization and Applications, 57, 403–415.
[Las15] Lasserre, J. B. (2015). An introduction to polynomial and semialgebraic opti
mization (Vol. 52). Cambridge University Press.
[BPT12] Blekherman, G., Parrilo, P. A., & Thomas, R. R. (2012). Semidefinite optimiza
tion and convex algebraic geometry. SIAM.
[Nie23] Nie, J. (2023). Moment and Polynomial Optimization. SIAM.
Changelog
• Mar 13, 2025: Fixed typo (thanks Jonathan Huang!)
• Mar 13, 2025: Changed “sufficient” → “necessary” (thanks Anon. Helix! https://
piazza.com/class/m6lg9aspoutda/post/87)
• Mar 15, 2025: Fixed typo in Section L10.3.2: 𝑣4 → 𝑣2 (thanks Khizer Shahid!)
• Mar 19, 2025: Changed “reduction to” → “reduction from” in proof of Theorem L10.1
(thanks Alina Yang for the suggestion!)
★These notes are class material that has not undergone formal peer review. The TAs and I are grateful
for any reports of typos.
¹We consider constraints in the “≥” direction instead of the usual “≤” direction. This is just for notational
alignment with the literature.
²In my case, I used Clarabel (https://github.com/oxfordcontrol/Clarabel.rs).
Lecture 10
Polynomial optimization
Instructor: Prof. Gabriele Farina ( gfarina@mit.edu)★
As mentioned in Lecture 9, semidefinite programming has established itself as an extremely
important tool, with disparate applications in combinatorial optimization, control theory,
and machine learning. Under the appropriate assumptions (namely strict feasibility), semi7
definite programs can be solved efficiently, and strong commercial solvers are available. In
this lecture, we will see how semidefinite programming can be used to relax a large class of
nonconvex problems that includes combinatorial problems as well, and find globally optimal
solutions.
L10.1 Polynomial optimization problems
In this lecture, we focus on polynomial optimization problems,¹ that is, problems of the form
min
𝑥
s.t.
𝑓(𝑥)
𝑔𝑗(𝑥) ≥ 0 𝑗 = 1, ..., 𝑚
𝑥 ∈ ℝ𝑛,
where 𝑓 and the 𝑔𝑗 are 𝑛7variate polynomials with real coefficients, i.e., 𝑓, 𝑔𝑗 ∈ ℝ[𝑥]. This
class of problems is very expressive. To start, it contains nonconvex problems. For example,
these are just two small examples of feasible sets expressible via bivariate polynomials.
−2 −1 1 2 𝑥1
−2
−1
1
2
𝑥2
0 −1 1 2 𝑥1
−1
1
𝑥2
0
Ω1 ≔ {𝑥4
1 + 𝑥4
2 − 1
2𝑥3
1𝑥2 − 2𝑥2
2 − 𝑥2
1𝑥2
2 ≤ 1} Ω2 ≔ {1 − 4𝑥2
1 + 4𝑥1𝑥2
2 + 𝑥3
1 ≥ 0
(𝑥1 − 1
2 )2 + 𝑥2
2 ≤ 2.
This class of problems also contains combinatorial optimization problems known to be
hard, such as the maximum cut problem (see Lecture 1). The reason why combinatorial
optimization problems can easily be expressed by polynomial optimization problems is that
the condition 𝑥 ∈ {0, 1} can be equivalently written as the pair of polynomial constraints
𝑥(1 − 𝑥) ≤ 0, −𝑥(1 − 𝑥) ≤ 0.
The key takeaway of this lecture is that polynomial optimization problems can, under mild
assumptions, be converted into semidefinite programs. Two observations are immediate:
• Polynomial optimization problems are nonconvex, but semidefinite programs are
convex conic problems. It is a priori not obvious at all that the latter can be used to
solve the former.
• There is no free lunch: polynomial optimization problems are very expressive, and
can capture computationally hard problems. In contrast, semidefinite programs can
be solved in time polynomial in the dimension (under suitable hypotheses). The catch
is that the semidefinite program relaxations we will consider need to be, in the worst
case, of dimension exponential in the degree and number of variables of the polynomial
problem considered. In practice, however, very good results are achieved already for
relaxations of dimension way lower than what the theory predicts.
L10.2 The cone of nonnegative polynomials
To begin our exploration, let’s focus on the simplest of settings: unconstrained optimization.
In particular, suppose that we would like to find the minimum of a polynomial 𝑝(𝑥) in ℝ𝑛.
(Note that the question is meaningful only if the degree of 𝑝 is even, as otherwise 𝑝 is not
lower bounded.)
Computationally, the problem of computing the minimum of a generic polynomial 𝑝(𝑥) is
equivalent to the question of being able to check whether a generic polynomial 𝑞(𝑥) satisfies
𝑞(𝑥) ≥ 0 for all 𝑥 ∈ ℝ𝑛. In one direction, if we can compute min 𝑞(𝑥), then we can answer
whether 𝑞(𝑥) ≥ 0 by simply checking if the minimum is below or above 0. In the other
direction, if we can check whether 𝑞(𝑥) ≥ 0 for all 𝑥 ∈ ℝ𝑛, then we can compute min 𝑝(𝑥)
by performing a binary search over 𝑡, until we find the largest 𝑡 such that 𝑝(𝑥) − 𝑡 ≥ 0 for
all 𝑥 ∈ ℝ𝑛. For this reason, we will be interested in understanding more about the following
object.
Definition L10.1 (Cone of nonnegative polynomials). The cone of nonnegative polyno
mials is the set of all polynomials 𝑝 ∈ ℝ[𝑥] such that 𝑝(𝑥) ≥ 0 for all 𝑥 ∈ ℝ𝑛. We will
denote this set by ℝ[𝑥]≥0.
It is immediate to check [▷ You should check!] that the set ℝ[𝑥]≥0 is a closed convex cone.
L10.2.1 Complexity considerations
Unfortunately, deciding whether a polynomial is nonnegative in ℝ𝑛 is as hard as deciding
membership in the copositive cone, which is NP7hard [DG14].
Theorem L10.1. Deciding membership in the cone of nonnegative polynomials ℝ[𝑥]≥0
for any polynomial of degree ≥ 4 with 𝑛 ≥ 2 variables is computationally intractable.
Proof. By reduction from the problem of deciding if a symmetric matrix 𝑀 ∈ ℝ𝑛×𝑛 is
copositive (see Lecture 9), that is,
𝑧⊤𝑀 𝑧 ≥ 0 ∀𝑧 ∈ ℝ𝑛
≥0.
Indeed, consider the 𝑛7variate polynomial of degree 4 defined as
𝑝(𝑥1, ..., 𝑥𝑛) ≔
(
(((𝑥2
1
⋮
𝑥2
𝑛)
)))
⊤
𝑀
(
(((𝑥2
1
⋮
𝑥2
𝑛)
))).
If 𝑀 is copositive, this polynomial is nonnegative on ℝ𝑛, since the vector of squares
(𝑥2
1, ..., 𝑥2
𝑛) is always nonnegative. Conversely, if 𝑝 is nonnegative on ℝ𝑛, then since
(𝑥2
1, ..., 𝑥2
𝑛) spans all of ℝ𝑛
≥0, we have that 𝑀 is copositive. □
As a side remark, this is the second convex set we see for which membership—let alone
optimization—is intractable (the first being the copositive cone). This should serve as a
reminder that equating convexity with tractability can be a dangerous oversimplification.
L10.3 Sum-of-squares polynomials
Theorem L10.1 shows that even deciding membership in the cone of nonnegative polynomials
is hard in general, let alone optimizing over it. This begs the question of what is the largest
set of polynomials for which deciding nonnegativity is easy. The following cone will provide
an extremely important step in this direction.
Definition L10.2 (Sum7of7squares polynomials, Σ[𝑥]). An 𝑛7variate polynomial 𝑝 ∈ ℝ[𝑥]
is said to be a sumofsquares polynomial (or SOS for short) if it can be written as
𝑝(𝑥) = ∑
𝑘
𝑝𝑘(𝑥)2, 𝑥 ∈ ℝ𝑛
for appropriate polynomials 𝑝𝑘 ∈ ℝ[𝑥].
Remark L10.1. Only polynomials of even degree can be sum7of7squares. Furthermore, if
𝑝 has degree 2𝑑, then each of the 𝑝𝑘’s can only have degree at most 𝑑.
It is immediate to check [▷ you should check!] that the set of sum7of7squares polynomials is
a closed, convex, nonempty cone. Furthermore, every sum7of7squares polynomial is clearly
a nonnegative polynomial, so Σ[𝑥] ⊆ ℝ[𝑥]≥0. In general, the inclusion is strict, as there
exist polynomials that are nonnegative but not sum7of7squares. We will see a well7known
example, called the Motzkin polynomial, later in this lecture in Example L10.2.
L10.3.1 The connection to the positive semidefinite cone
Unlike the cone of nonnegative polynomials, the cone of sum7of7squares polynomials is easy
to characterize. The following theorem provides a very useful criterion for deciding whether
a polynomial is sum7of7squares.
Theorem L10.2. Membership in the cone of sum7of7squares polynomials can be deter7
mined by checking the feasibility of a semidefinite program. In particular, let 𝑝(𝑥) be
an arbitrary polynomial of degree 2𝑑 in 𝑛 variables, and let 𝑣𝑑 be the vector of all
monomials of degree up to 𝑑 that can be constructed using the variables 𝑥.
Then, 𝑝(𝑥) ∈ Σ[𝑥] if and only if there exists a positive semidefinite matrix 𝑄 such that
𝑝(𝑥) = (𝑣𝑑(𝑥))⊤𝑄𝑣𝑑(𝑥),
Proof. (⟹) Any polynomial of degree up to 𝑑 can be written as a linear combination of
the monomials in 𝑣𝑑. Hence, any sum7of7squares polynomial can be written in the form
𝑝(𝑥) = ∑
𝑘
(𝑣𝑑(𝑥)⊤𝛼𝑘)2
for some appropriate coefficient vectors 𝛼𝑘. But then, we can write
𝑝(𝑥) =
‖
‖
‖
‖
(
((((— 𝛼⊤
1 —
— 𝛼⊤
2 —
⋮ )
))))
⏟⏟⏟⏟⏟
≕ 𝐶
𝑣𝑑(𝑥)
‖
‖
‖
‖2
= (𝑣𝑑(𝑥))⊤𝐶 ⊤𝐶𝑣𝑑(𝑥). (1)
Since a matrix of the form 𝐶⊤𝐶 is positive semidefinite, this direction holds.
(⟸) Conversely, if 𝑝(𝑥) = (𝑣𝑑(𝑥))⊤𝑄𝑣𝑑(𝑥) for some positive semidefinite matrix 𝑄, we
can write 𝑄 = 𝐶⊤𝐶 for some 𝐶. But then, we can use (1) from right to left and extract
from the rows of 𝐶 the coefficients 𝛼𝑘 for the sum7of7squares representation of 𝑝(𝑥). □
Example L10.1. A bivariate polynomial 𝑝(𝑥1, 𝑥2) of degree 4 is a sum7of7squares poly7
nomial if and only if there exists 𝑄 ⪰ 0 such that
𝑝(𝑥1, 𝑥2) =
(
(((((((((((( 𝑥2
1
𝑥1𝑥2
𝑥2
2
𝑥1
𝑥2
1 )
))))))))))))
⊤
(
((((((((((((𝑞00
𝑞01
𝑞02
𝑞03
𝑞04
𝑞05
𝑞01
𝑞11
𝑞12
𝑞13
𝑞14
𝑞15
𝑞02
𝑞12
𝑞22
𝑞23
𝑞24
𝑞25
𝑞03
𝑞13
𝑞23
𝑞33
𝑞34
𝑞35
𝑞04
𝑞14
𝑞24
𝑞34
𝑞44
𝑞45
𝑞05
𝑞15
𝑞25
𝑞35
𝑞45
𝑞55)
))))))))))))
(
(((((((((((( 𝑥2
1
𝑥1𝑥2
𝑥2
2
𝑥1
𝑥2
1 )
))))))))))))
= (𝑞00)𝑥4
1 + (2𝑞01)𝑥3
1𝑥2 + (𝑞11 + 2𝑞02)𝑥2
1𝑥2
2 + (2𝑞12)𝑥1𝑥3
2 + (𝑞22)𝑥4
2
+ (2𝑞03)𝑥3
1 + (2𝑞04 + 2𝑞13)𝑥2
1𝑥2 + (2𝑞23 + 2𝑞14)𝑥1𝑥2
2 + (2𝑞24)𝑥3
2
+ (𝑞33 + 2𝑞05)𝑥2
1 + (2𝑞15 + 2𝑞34)𝑥1𝑥2 + (𝑞44 + 2𝑞25)𝑥2
2
+ (2𝑞35)𝑥1 + (2𝑞45)𝑥2 + (𝑞55).
In other words, 𝑝(𝑥1, 𝑥2) is SOS if and only if its coefficients match the expressions
computed in the previous line, for an appropriate positive semidefinite 𝑄.
Note that the coefficients of the polynomial 𝑣(𝑥)⊤𝑄𝑣(𝑥) are always a linear function of the
entries of the matrix 𝑄. Hence, we obtain the following corollary.
Corollary L10.1. The cone of 𝑛7variate sum7of7squares polynomials of degree 2𝑑 is a
linear transformation of the cone of 𝑠 × 𝑠 positive semidefinite matrices, where 𝑠 =
(𝑛+𝑑
𝑑 ) is the dimension of the vector 𝑣𝑑(𝑥).
L10.3.2 An approach to unconstrained polynomial optimization
By replacing the cone of nonnegative polynomials with the cone of sum7of7squares polyno7
mials, we can obtain an approximation for the minimum of a polynomial over ℝ𝑛. The
key idea is to find a value 𝑡 such that we can certify that 𝑝(𝑥) − 𝑡 ∈ Σ[𝑥]. In that case, it
immediately follows that 𝑝(𝑥) ≥ 𝑡 for all 𝑥 ∈ ℝ𝑛.
As a concrete example, suppose we would like
to approximate the minimum of the bivariate
polynomial of fourth degree
𝑝(𝑥1, 𝑥2) ≔ 𝑥4
1 + 𝑥4
2 − 1
2𝑥3
1𝑥2 − 2𝑥2
2 − 𝑥2
1𝑥2
2,
whose level sets are shown on the right.
If we could find a value 𝑡 such that we can
certify that 𝑝(𝑥1, 𝑥2) − 𝑡 ∈ Σ[𝑥], that would
immediately prove that 𝑝(𝑥1, 𝑥2) ≥ 𝑡 for all 𝑥 ∈
ℝ𝑛.
To certify that 𝑝(𝑥1, 𝑥2) − 𝑡 ∈ Σ[𝑥], we know
from Theorem L10.2 and Example L10.1 that
−2 −1 1 2 𝑥1
−2
−1
1
2
𝑥2
0
it suffices to find a positive semidefinite matrix 𝑄 ⪰ 0 that enables writing 𝑝(𝑥1, 𝑥2) − 𝑡 in
the form 𝑣2(𝑥)⊤𝑄𝑣2(𝑥). More explicitly, using the expansion from Example L10.1, we are
interested in solving the following semidefinite program.
max 𝑡
s.t. ∙ 𝑞00 = 1 (coeff. of 𝑥4
1)
∙ 2𝑞01 = −1
2 (coeff. of 𝑥3
1𝑥2)
∙ 𝑞11 + 2𝑞02 = −1 (coeff. of 𝑥2
1𝑥2
2)
∙ 2𝑞12 = 0 (coeff. of 𝑥1
1𝑥3
2)
∙ 𝑞22 = 1 (coeff. of 𝑥4
2)
∙ 2𝑞03 = 0 (coeff. of 𝑥3
1)
∙ 2𝑞04 + 2𝑞13 = 0 (coeff. of 𝑥2
1𝑥2)
∙ 2𝑞23 + 2𝑞14 = 0 (coeff. of 𝑥1
1𝑥2
2)
∙ 2𝑞24 = 0 (coeff. of 𝑥3
2)
∙ 𝑞33 + 2𝑞05 = 0 (coeff. of 𝑥2
1)
∙ 2𝑞15 + 2𝑞34 = 0 (coeff. of 𝑥1𝑥2)
∙ 𝑞44 + 2𝑞25 = −2 (coeff. of 𝑥2
2)
∙ 2𝑞35 = 0 (coeff. of 𝑥1)
∙ 2𝑞45 = 0 (coeff. of 𝑥2)
∙ 𝑞55 = −𝑡 (constant)
∙ 𝑄 = [𝑞𝑖𝑗] ⪰ 0.
Feeding the semidefinite program into a solver,² we find that the optimal objective has value
𝑡⋆ ≈ −2.08053, obtained by the positive semidefinite matrix
𝑄⋆ ≈
(
((((((((((( 1.0
−0.25
−0.579
0.0
0.0
−0.073
−0.25
0.159
0.0
0.0
0.0
0.135
−0.579
0.0
1.0
0.0
0.0
−1.062
0.0
0.0
0.0
0.146
−0.135
0.0
0.0
0.0
0.0
−0.135
0.124
0.0
−0.0734
0.135
−1.062
0.0
0.0
2.080 )
)))))))))))
⪰ 0.
This means that the polynomial 𝑝(𝑥1, 𝑥2) − 𝑡⋆ is proved to belong in Σ[𝑥], and therefore
𝑝(𝑥1, 𝑥2) ≥ −2.08053 for all 𝑥1, 𝑥2 ∈ ℝ. The following two questions are natural:
1. Is this value optimal (i.e., does it indeed match the minimum of 𝑝 over ℝ𝑛)?
2. And if not, what could we do to improve the bound?
We will address these questions in the next section.
L10.4 Characterizing global nonnegativity using the SOS cone
The SOS cone provides a computationally viable relaxation of the cone of nonnegative
polynomials. But how much do we lose by shifting our focus from nonnegative to SOS
polynomials? As it turns out, the set of nonnegative polynomials of degree up to 𝑑 can
be approximated arbitrarily closely by the using SOS polynomials of degrees potentially
exponential in 𝑑.
L10.4.1 When are the SOS and nonnegative polynomial cone equal?
In fact, in some cases, the cone of sum7of7squares polynomials is exactly equal to the cone
of nonnegative polynomials. This is the content of Hilbert’s theorem.
Theorem L10.3 (Hilbert). ℝ[𝑥]≥0 = Σ[𝑥] if and only if:
• 𝑛 = 1, no matter the degree 𝑑; or
• 𝑑 = 2, no matter the number of variables 𝑛; or
• 𝑛 = 2 and 𝑑 = 4.
The cases for 𝑛 = 1 can be shown easily starting from a factorization of the polynomial [▷
You should try to prove that special case!].
Remark L10.2. Hilbert’s theorem shows that in the example of Section L10.3.2 we were
not just randomly lucky: the polynomial we considered was bivariate and of degree 4;
hence, the condition 𝑝(𝑥) − 𝑡 ∈ Σ[𝑥] was exactly equivalent to 𝑝(𝑥) − 𝑡 ∈ ℝ[𝑥]≥0.
Other than the three settings above, in general the cone of sum7of7squares polynomials is a
strict subset of the cone of nonnegative polynomials. Explicit examples of polynomials that
are nonnegative and yet not sum7of7squares are known, as we show next.
Example L10.2 (Motzkin’s polynomial). The polynomial
𝑀 (𝑥1, 𝑥2) ≔ 𝑥4
1𝑥2
2 + 𝑥2
1𝑥4
2 − 3𝑥2
1𝑥2
2 + 1
is not a sum7of7squares polynomial, but it is nonnegative on ℝ2, since from the arith7
metic7geometric mean inequality we have
𝑥4
1𝑥2
2 + 𝑥2
1𝑥4
2 + 1
3 ≥ 3
√𝑥4
1𝑥2
2 ⋅ 𝑥2
1𝑥4
2 ⋅ 1 = 𝑥2
1𝑥2
2.
[▷ As an exercise, show that the Motzkin polynomial is not a sum7of7squares polynomial.
One approach is to write the semidefinite program certifying membership of the polynomial
in Σ[𝑥], and showing that it is infeasible.]
L10.4.2 Hilbert’s conjecture and Artin’s theorem
As discussed above, being sum7of7squares is sufficient but not necessary for a polynomial
to be nonnegative in general. One might then try to consider other sufficient conditions,
hoping to cast a wider and wider net encompassing all nonnegative polynomials.
For example, even if a polynomial 𝑝(𝑥) is not sum7of7squares, if we could find two sum7of7
squares polynomials 𝑞(𝑥), 𝑟(𝑥) such that
𝑝(𝑥) = 𝑞(𝑥)
𝑟(𝑥)
and 𝑟(𝑥) divides 𝑞(𝑥).
Example L10.3. The Motzkin polynomial can be written as (replacing 𝑥 ≔ 𝑥1, 𝑦 ≔ 𝑥2)
𝑥4𝑦2 + 𝑥2𝑦4 − 3𝑥2𝑦2 + 1 = 𝑥2𝑦2(𝑦2 + 𝑥2 − 2)2 + 𝑥2(𝑦2 − 1)2 + 𝑦2(𝑥2 − 1)2
𝑥2 + 𝑦2
where both the numerator and the denominator are sum7of7squares polynomials. [▷ You
should verify this!]
In his famous 17th problem, Hilbert conjectured that the condition above is necessary
for a polynomial to be nonnegative. This conjecture was proved by Artin in 1927 via the
Artin7Schreier theory. A celebrated result by Polyá later showed that for homogeneous
polynomials (i.e., those where every term has the same degree), without loss of generality
one can focus on denominators in the form 𝑟(𝑥) = (𝑥2
1 + ⋯ + 𝑥2
𝑛)𝑑′
for some 𝑑′ ∈ ℕ to check
positivity in ℝ𝑛 ∖ {0}. In general, to check positivity one can search for 𝑞, 𝑟 ∈ Σ[𝑥] such
that 𝑟(𝑥)𝑝(𝑥) = 1 + 𝑞(𝑥). To check nonnegativity, one can search for 𝑞, 𝑟 ∈ Σ[𝑥] and ℓ ∈ ℕ
such that 𝑟(𝑥)𝑝(𝑥) = 𝑝(𝑥)2ℓ + 𝑞(𝑥).
Combined, these results show that checking nonnegativity of polynomials of degree up to
𝑑 can be approximated arbitrarily closely by using SOS polynomials of degrees potentially
exponential in 𝑑. Concrete bounds are known (but are very pessimistic). For today, the
important thing is the message: SOS polynomials provide a complete characterization of
nonnegative polynomials, as long as one is willing to look into high7degree SOS polynomials.
L10.5 The constrained case: Putinar’s Positivstellensatz
Having understood more of the unconstrained case, we can now focus on the more general
case of polynomial optimization problems with constraints.
For simplicity, we focus on the case of polynomial optimization problems in which at least
one of the constraints 𝑔𝑗(𝑥) ≥ 0 defines a feasible set {𝑥 ∈ ℝ𝑛 : 𝑔𝑗(𝑥) ≥ 0} that is compact.
In this setting, the following important result serves as a bridge for how to use SOS
polynomials to solve polynomial optimization problems.
Theorem L10.4 (Putinar’s Positivstellensatz). Let
Ω ≔ {𝑥 ∈ ℝ𝑛 : 𝑔𝑗(𝑥) ≥ 0 ∀𝑗 = 1, ..., 𝑚},
where {𝑥 ∈ ℝ𝑛 : 𝑔𝑗(𝑥) ≥ 0} is compact for at least one 𝑗 ∈ {1, ..., 𝑚}. Any polynomial
𝑝 ∈ ℝ[𝑥] positive on Ω can be written in the form
𝑝 = 𝜎0 + ∑
𝑚
𝑗=1
𝜎𝑗𝑔𝑗
for appropriate SOS polynomials 𝜎𝑗 ∈ Σ[𝑥], 𝑗 = 0, ..., 𝑚.
More general versions that apply without the compactness restriction above are also known
(e.g., Stengle’s Positivstellensatz and Schmüdgen’s Positivstellensatz).
Again, bounds are known for the degree of the SOS polynomials that are needed in Putinar’s
theorem. In practice, however, very good results are achieved already for relaxations of
dimension way lower than what the theory predicts. In particular, to check whether 𝑝(𝑥) >
𝑡, we can try to see if there exist SOS polynomials 𝜎𝑗 of degree up to some 𝛾 ∈ ℕ, such
that 𝑝(𝑥) − 𝑡 = 𝜎0 + ∑𝑚
𝑗=1 𝜎𝑗𝑔𝑗. For each 𝜎𝑗, we will be looking for a corresponding positive
semidefinite matrix 𝑄𝑗 that enables writing 𝜎𝑗(𝑥) = 𝑣𝛾 (𝑥)⊤𝑄𝑗𝑣𝛾 (𝑥). Overall, for any given
𝛾 we will be writing a positive semidefinite program.
L10.5.1 An example
As a final example, suppose we want to find the minimum 𝑥7coordinate of any point (𝑥1, 𝑥2)
in the set
Ω2 ≔ {1 − 4𝑥2
1 + 4𝑥1𝑥2
2 + 𝑥3
1 ≥ 0
(𝑥 − 1
2 )2 + 𝑦2 ≤ 2.
shown in Section L10.1. In this case, we have
𝑔1(𝑥1, 𝑥2) ≔ 𝑥3
1 + 4𝑥1𝑥2
2 − 4𝑥2
1 + 1, 𝑔2(𝑥1, 𝑥2) ≔ −(𝑥1 − 1
2 )
2
− 𝑥2
2 + 2.
If we look for sum7of7square polynomials 𝜎0, 𝜎1, 𝜎2 ∈ Σ[𝑥] of degrees 2, 4, 6, 8, 10, we find
the following objective values.
Degree of 𝜎𝑗 Objective value
2 infeasible
4 −0.91421
6 −0.91421
8 −0.47283
10 −0.47283
The value −0.47283 is indeed the correct an7
swer, as you can see on the magnified plot on
the right.
−0.5 0.5 1 1.5 𝑥1
−1.5
−1
−0.5
0.5
1
1.5
𝑥2
0
L10.6 Further readings
The field of polynomial optimization is vast and has seen a lot of activity in the last few
decades. Several connections between polynomial optimization and real algebraic geometry
run deep. Several excellent books and surveys are available, including those of Lasserre, J.
B. [Las15], Blekherman, G., Parrilo, P. A., & Thomas, R. R. [BPT12], and Nie, J. [Nie23].
Bibliography for this lecture
[DG14] Dickinson, P. J., & Gijben, L. (2014). On the computational complexity of mem7
bership problems for the completely positive cone and its dual. Computational
Optimization and Applications, 57, 403–415.
[Las15] Lasserre, J. B. (2015). An introduction to polynomial and semialgebraic opti
mization (Vol. 52). Cambridge University Press.
[BPT12] Blekherman, G., Parrilo, P. A., & Thomas, R. R. (2012). Semidefinite optimiza
tion and convex algebraic geometry. SIAM.
[Nie23] Nie, J. (2023). Moment and Polynomial Optimization. SIAM.
Changelog
• Mar 13, 2025: Fixed typo (thanks Jonathan Huang!)
• Mar 13, 2025: Changed “sufficient” → “necessary” (thanks Anon. Helix! https://
piazza.com/class/m6lg9aspoutda/post/87)
• Mar 15, 2025: Fixed typo in Section L10.3.2: 𝑣4 → 𝑣2 (thanks Khizer Shahid!)
• Mar 19, 2025: Changed “reduction to” → “reduction from” in proof of Theorem L10.1
(thanks Alina Yang for the suggestion!)
★These notes are class material that has not undergone formal peer review. The TAs and I are grateful
for any reports of typos.
¹We consider constraints in the “≥” direction instead of the usual “≤” direction. This is just for notational
alignment with the literature.
²In my case, I used Clarabel (https://github.com/oxfordcontrol/Clarabel.rs).