arXiv:1710.05735v1 [math.NA] 12 Oct 2017

Nonnegative Polynomial with no Certificate of
Nonnegativity in the Simplicial Bernstein Basis
Christoffer Sloth
University of Southern Denmark
SDU Robotics
chsl@mmmi.sdu.dk
Abstract
This paper presents a nonnegative polynomial that cannot be represented with nonnegative coefficients in the simplicial Bernstein basis by
subdividing the standard simplex. The example shows that Bernstein
Theorem cannot be extended to certificates of nonnegativity for polynomials with zeros at isolated points.

1

Introduction

The positivity and nonnegativity of polynomials play an important role in many
problems such as Lyapunov stability analysis of dynamical systems [5, 7]. Therefore, much research has been conducted to exploit different certificates of positivity [9, 1]. The certificates of positivity include sum of squares that is extensively
used in different applications [5, 10].
The certification of nonnegativity for polynomials with zeros was addressed
in [3, 11], where the paper [3] characterizes polynomials that can be certified to
be nonnegative using Pólya’s Theorem.
This paper exploits a certificate of positivity in the Bernstein basis [4] that
has previously been applied within optimization and control [8, 2, 12]. In particular, a nonnegative polynomial is provided that cannot be represented with
nonnegative coefficients in the simplicial Bernstein basis by subdividing the
standard simplex.
The paper is organized as follows. Section 2 provides preliminaries on polynomials in Bernstein form, which are used in Section 3 that provides the example, and relies on results presented in Appendix A.

2

Preliminaries

This section provides preliminary results and notation on polynomials in the
Bernstein basis.
Let R[X] be the real
ring in n variables. For α = (α0 , . . . , αn ) ∈
Ppolynomial
n
Nn+1 we define |α| := i=0 αi .
We utilize Bernstein polynomials defined on simplices via barycentric coordinates.

1

Definition 1 (Barycentric Coordinates). Let λ0 , . . . , λn ∈ R[X] be affine polynomials and let v0 , . . . , vn ∈ Rn be affinely independent. If
n
X

λi = 1

and

i=0

x = λ0 (x)v0 + · · · + λn (x)vn

∀x ∈ Rn

then λ0 , . . . , λn are said to be barycentric coordinates associated to v0 , . . . , vn .
Let λ0 , . . . , λn be barycentric coordinates associated to v0 , . . . , vn . Then the
simplex generated by λ0 , . . . , λn is
4 := {x =

n
X

λi vi | λi (x) ≥ 0, i = 0, . . . , n} ⊂ Rn .

(1)

i=0

This work represents polynomials in the simplicial Bernstein basis, where
the basis polynomials are defined as follows.
Definition 2 (Bernstein Polynomial). Let d ∈ N0 , n ∈ N, α = (α0 , . . . , αn ) ∈
Nn+1
, and let λ0 , . . . , λn ∈ R[X] be barycentric coordinates associated to a
0
simplex ∆. The Bernstein polynomials of degree d on the simplex ∆ are
 
d
d
Bα =
λα
(2)
α
for |α| = d where
 
d!
d
=
α
α0 !α1 ! · · · αn !

and

λα :=

n
Y

i
λα
i .

i=0

Every polynomial P ∈ R[X] of degree no greater than d can be written
uniquely as
X
X
P =
bα (P, d, 4)Bαd =
bdα Bαd = bd B d ,
(3)
|α|=d

|α|=d

where bα (P, d, 4) ∈ R is a Bernstein coefficient of P of degree d with respect to
4. We say that (3) is a polynomial in Bernstein form.
From the definition of Bernstein polynomials on simplex 4 (Definition 2)
and (1) it is seen that for any d ∈ N and |α| = d
Bαd (x) ≥ 0

∀x ∈ 4.

This means that polynomial P in (3) is positive on 4 if bdα > 0 for all α ∈ Nn+1
where |α| = d. We call this a certificate of positivity. Similarly, we say that
bdα ≥ 0 for all α ∈ Nn+1 where |α| = d is a certificate of nonnegativity.
If a polynomial P of degree p cannot be certified to be positive in the Bernstein basis of degree p on simplex 4 then two strategies may be exploited to
refine the certificate. These are called degree elevation and subdivision and will
be outlined next.
To certify the positivity of a polynomial by degree elevation, one may represent the polynomial using Bernstein polynomials of a higher degree as in the
following theorem [6].
2

Theorem 1 (Multivariate Bernstein Theorem). If a nonzero polynomial P ∈
R[X1 , . . . , Xn ] of degree p ∈ N0 is positive on a simplex 4, then there exists
d ≥ p such that all entries of b(P, d, 4) are positive.
A similar result related to subdivision is presented in [6]; however, for simplicity the subdivision approach is explained by the following example. The
example shows how an initial simplex 4 may be subdivided into several simplices to certify the positivity of a polynomial on a given domain.
Example 1. Consider the following polynomial
P = X 2 + Y 2 − XY
on the standard simplex 4 with vertices v0 = (0, 0), v1 = (1, 0), v2 = (0, 1).
Polynomial P has the following nonzero Bernstein coefficients in the Bernstein
basis with respect to 4
b(0,2,0) = 1,

b(0,1,1) = −0.5,

b(0,0,2) = 1.

(4)

The nonnegativity of polynomial P cannot be certified directly by the above Bernstein coefficients since b(0,1,1) is negative; hence, simplex 4 must be subdivided
to obtain a certificate of nonnegativity. Consequently, we define a new vertex
ṽ1 = (1 − θ, θ) and a subdivision of 4 given by two simplices 4̃ and 4̂ with vertices v0 , v1 , ṽ1 and v0 , v2 , ṽ1 respectively. The subdivision is shown in Figure 1
and gives a collection of simplices, all with a common vertex at the zero of P .
ṽ1

v2
4̂

v1
4̃

v0
Figure 1: Simplex 4 with vertices v0 , v1 , v2 , simplex 4̃ with vertices v0 , v1 , ṽ1 ,
and simplex 4̂ with vertices v0 , v2 , ṽ1 .
The nonzero Bernstein coefficients of polynomial P on the two simplices are
(by Lemma 1)
1
(1 − θ)θ +
8
1
= (1 − θ)θ +
8

b̃(0,2,0) = 1,

b̃(0,1,1) = −1.5θ + 1,

b̃(0,0,2) =

b̂(0,2,0) = 1,

b̂(0,1,1) = 1.5θ − 0.5,

b̂(0,0,2)

1
4
1
4

It is seen that the nonnegativity of the polynomial can be certified by letting
θ = 0.5.
It should be noted that there exists nonnegative (sum of squares) polynomials that cannot be represented with nonnegative coefficients in the simplicial
Bernstein basis, i.e., it is not possible to certify the nonnegativity of any nonnegative polynomial by employing subdivisioning. This is exemplified in the
next section.
3

3

Counterexample

In this section, a nonnegative polynomial is presented for which there exists no
certificate of nonnegativity in the simplicial Bernstein basis.
Consider the polynomial
P = 21X14 +24X13 X2 −36X13 +18X12 X22 −24X12 X2 +18X12 +12X1 X23 −12X1 X22 +30X24 .

The graph of P on the standard simplex is shown in Figure 2.

30
20
10
0
1
1
0.5
x2

0.5
0

0

x1

Figure 2: Graph of the polynomial P on the standard simplex 4.
We aim at proving the nonnegativity of P on the standard simplex 4 with
vertices v0 = (0, 0), v1 = (1, 0), and v2 = (0, 1). The polynomial P can be
written as the following sum of squares



X1
18 −18 −12 −6
2 


 −18 21
12
0
  X1  ,
P = X1 X12 X1 X2 X22 
−12 12
18
6  X1 X2 
X22
−6
0
6
30
|
{z
}
=MP

where the matrix MP is positive definite; hence, the polynomial is positive
everywhere except from being zero at (x1 , x2 ) = (0, 0).
Polynomial P can be represented in the Bernstein basis as
X
P =
bα Bαd ,
|α|=d

where Bαd is the Bernstein basis defined on the standard simplex 4. The nonzero
coefficients of P are
b(2,2,0) = 3,

b(1,2,1) = 1,

b(1,1,2) = −1,

b(0,4,0) = 3,

b(0,0,4) = 30.

It is seen that one coefficient is negative (b(1,1,2) < 0); thus, the nonnegativity
of P cannot be directly certified.
Next we show that there exists no certificate of nonnegativity for the polynomial P in the Bernstein basis, since the coefficient with index (1, 1, 2) will
remain negative on one simplex of any triangulation of 4. In particular, the
coefficient remains negative on any nondegenerate simplex with vertex v0 , a

4

vertex on the line between v0 and v2 , and any third vertex in 4, i.e., for any
Bernstein basis defined on the simplex 4̃ with vertices
ṽ0 = v0
ṽ1 = β0 v0 + β1 v1 + β2 v2
ṽ2 = ρv0 + (1 − ρ)v2
where β0 + β1 + β2 = 1, β0 , β1 , β2 ≥ 0, β1 > 0, and ρ ∈ [0, 1). The simplices 4
and 4̃ are illustrated in Figure 3.
v1

v2
ṽ1
ṽ2
v0

Figure 3: Simplex 4 with vertices v0 , v1 , v2 and simplex 4̃ with vertices
v0 , ṽ1 , ṽ2 .
The polynomial P can be represented in the Bernstein basis as
X
P =
b̃α B̃αd ,
|α|=d

where B̃αd is the Bernstein basis defined on the standard simplex 4̃ and where
by Lemma 2 and Lemma 1 the coefficients bα and b̃γ are related as
b̃γ =


γ2 
X
γ2
ργ2 −k (1−ρ)k
γ2 − k

k=0

α −(γ +γ −k)

X
|α| = d
γ0 + γ2 − k ≤ α0
k ≤ α2

γ1 !β0 0 0 2
β1α1 β2α2 −k
bα
(α0 − (γ0 + γ2 − k))!α1 !(α2 − k)!

For the polynomial P , it is seen that
b̃(1,1,2) = β1 (1 − ρ)2 b(1,1,2) ,
which is negative for any admissible β1 and ρ (β1 > 0 and ρ ∈ [0, 1)), since
b(1,1,2) = −1. Therefore, there exists no certificate of nonnegativity of P on 4
in the simplicial Bernstein basis.

References
[1] A. Ahmadi and A. Majumdar. DSOS and SDSOS optimization: LP and
SOCP-based alternatives to sum of squares optimization. In proceedings of
the 48th Annual Conference on Information Sciences and Systems, pages
1–5, March 2014.

5

[2] M. Ben Sassi, R. Testylier, T. Dang, and A. Girard. Reachability analysis
of polynomial systems using linear programming relaxations. In Automated
Technology for Verification and Analysis, pages 137–151. Springer Berlin
Heidelberg, 2012.
[3] M. Castle, V. Powers, and B. Reznick. Pólya’s theorem with zeros. Journal
of Symbolic Computation, 46(9):1039–1048, 2011.
[4] R. T. Farouki. The Bernstein polynomial basis: A centennial retrospective.
Computer Aided Geometric Design, 29(6):379 – 419, 2012.
[5] D. Henrion and A. Garulli, editors. Positive Polynomials in Control, volume
312 of Lecture Notes in Control and Information Science. Springer Berlin
Heidelberg, 2005.
[6] R. Leroy. Certificates of positivity in the simplicial Bernstein basis. hal00589945, 2009.
[7] M. Marshall. Positive Polynomials and Sums of Squares, volume 146.
American Mathematical Society, 2008.
[8] C. Muoz and A. Narkawicz. Formalization of bernstein polynomials and
applications to global optimization. Journal of Automated Reasoning,
51(2):151–196, 2013.
[9] P. A. Parrilo. Semidefinite programming relaxations for semialgebraic problems. Math. Programming, 96(2):293–320, 2003.
[10] V. Powers. Positive polynomials and sums of squares: Theory and practice.
Real Algebraic Geometry, 2011.
[11] M. Schweighofer. Certificates for nonnegativity of polynomials with zeros
on compact semialgebraic sets. manuscripta mathematica, 117(4):407–428,
Aug 2005.
[12] C. Sloth and R. Wisniewski. Control to facet for polynomial systems.
In Proceedings of the 17th International Conference on Hybrid Systems:
Computation and Control, pages 123–132, 2014.

A

Useful Results

Lemma 1. Let P ∈ R[X]. Define a simplex 4 with vertices v0 , v1 , v2 ∈ R2 ,
and define the simplex 4̃ with vertices v0 , v1 , ṽ2 , where
ṽ2 = ρv0 + (1 − ρ)v2
and ρ ∈ [0, 1). Then P can be represented in two Bernstein bases as
X
X
P =
bα Bαd =
b̃γ B̃γd ,
|α|=d

(5)

|γ|=d

where Bαd is the Bernstein basis defined by 4, B̃γd is the Bernstein basis defined
by 4̃, and

γ2 
X
γ2
b̃γ =
ργ2 −k (1 − ρ)k b(γ0 +γ2 −k,γ1 ,k) .
γ2 − k
k=0

6

Proof. Let λ0 , λ1 , λ2 ∈ R[X] be barycentric coordinates associated to 4 and
λ̃0 , λ̃1 , λ̃2 ∈ R[X] be barycentric coordinates associated to 4̃. Then
λ0 = λ̃0 + ρλ̃2
λ1 = λ̃1
λ2 = (1 − ρ)λ̃2
and
α2 α2
1
λα = (λ̃0 + ρλ̃2 )α0 λ̃α
1 (1 − ρ) λ̃2 .

By binomial theorem
α

λ =


α0 
X
α0
k=0

=

α0 
X
α0
k=0

k


k

!
λ̃0α0 −k ρk λ̃k2

α2 α2
1
λ̃α
1 (1 − ρ) λ̃2

1 α2 +k
ρk (1 − ρ)α2 λ̃0α0 −k λ̃α
.
1 λ̃2

Therefore, the Bernstein bases Bγd and B̃γd are related as
Bαd

=


α0 
X
α2 + k
k=0

k

d
ρk (1 − ρ)α2 B̃(α
,
0 −k,α1 ,α2 +k)

which implies that coefficients bα and b̃α are related as

γ2 
X
γ2
b̃γ =
ργ2 −k (1 − ρ)k b(γ0 +γ2 −k,γ1 ,k) .
γ2 − k
k=0

Lemma 2. Let P ∈ R[X]. Define a simplex 4 with vertices v0 , v1 , v2 ∈ R2 ,
and define the simplex 4̃ with vertices v0 , ṽ1 , v2 ∈ R2 , where
ṽ1 = β0 v0 + β1 v1 + β2 v2
and β0 + β1 + β2 = 1, β0 , β2 ≥ 0, β1 > 0. Then P can be represented in two
Bernstein bases as
X
X
P =
bα Bαd =
b̃γ B̃γd
(6)
|α|=d

|γ|=d

where Bαd is the Bernstein basis defined by 4, B̃γd is the Bernstein basis defined
by 4̃, and
b̃γ =

X
|α| = d
α0 ≥ γ0
α2 ≥ γ2

γ1 !
β α0 −γ0 β1α1 β2α2 −γ2 bα .
(α0 − γ0 )!α1 !(α2 − γ2 )! 0

7

Proof. Let λ0 , λ1 , λ2 ∈ R[X] be barycentric coordinates associated to 4 and
λ̃0 , λ̃1 , λ̃2 ∈ R[X] be barycentric coordinates associated to 4̃. Then
λ0 = λ̃0 + β0 λ̃1
λ1 = β1 λ̃1
λ2 = β2 λ̃1 + λ̃2
and
λα = (λ̃0 + β0 λ̃1 )α0 (β1 λ̃1 )α1 (β2 λ̃1 + λ̃2 )α2 .
By binomial theorem

α0 
X
α0

λα =

k=0

X

=

k


|γ| = d
γ0 ≤ α0
γ2 ≤ α2



!
0 −k k k
λ̃α
β0 λ̃1
0

1 
β1α1 λ̃α
1


α2 
X
α2
j=0

α0
α0 − γ0



j


2 −j 
β2j λ̃j1 λ̃α
2



α2
β0α0 −γ0 β1α1 β2α2 −γ2 λ̃γ .
α2 − γ2

Therefore, the Bernstein bases Bγd and B̃γd are related as
Bαd =

X
|γ| = d
γ0 ≤ α0
γ2 ≤ α2

γ1 !
β α0 −γ0 β1α1 β2α2 −γ2 B̃γd ,
(α0 − γ0 )!α1 !(α2 − γ2 )! 0

which implies that coefficients bα and b̃α are related as
b̃γ =

X
|α| = d
α0 ≥ γ0
α2 ≥ γ2

γ1 !
β α0 −γ0 β1α1 β2α2 −γ2 bα .
(α0 − γ0 )!α1 !(α2 − γ2 )! 0

8

