Jean B Lasserre
email: lasserre@laas.fr

A NEW LOOK AT NONNEGATIVITY ON CLOSED SETS AND POLYNOMIAL OPTIMIZATION

Keywords: 1991 Mathematics Subject Classification. 90C25 28C15 closed sets, nonnegative functions, nonnegative polynomials, semidefinite approximations, moments

.

Introduction

This paper is concerned with a concrete characterization of continuous functions that are nonnegative on a closed set K ⊆ R n and its application for optimization purposes. By concrete we mean a systematic procedure, e.g. a numerical test that can be implemented by an algorithm, at least in some interesting cases. For polynomials, Stengle's Nichtnegativstellensatz [START_REF] Stengel | A Nullstellensatz and a Positivstellensatz in semialgebraic geometry[END_REF] provides a certificate of nonnegativity (or absence of nonnegativity) on a semi-algebraic set. Moreover, in principle, this certificate can be obtained by solving a single semidefinite program (although the size of this semidefinite program is far beyond the capabilities of today's computers). Similarly, for compact basic semi-algebraic sets, Schmüdgen's and Putinar's Positivstellensätze [START_REF] Schmüdgen | The K-moment problem for compact semi-algebraic sets[END_REF][START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF] provide certificates of strict positivity that can be obtained by solving finitely many semidefinite programs (of increasing size). Extensions of those certificates to some algebras of non-polynomial functions have been recently proposed in Lasserre and Putinar [START_REF] Lasserre | Positivity and optimization for semi-algebraic functions[END_REF] and in Marshall and Netzer [START_REF] Marshall | Positivstellensätze for real function algebras[END_REF]. However, and to the best of our knowledge, there is still no hierarchy of explicit (outer or inner) semidefinite approximations (with or without lifting) of the cone of polynomials nonnegative on a closed set K, except if K is compact and basic semi-algebraic (in which case outer approximations exist). Another exception is the convex cone of quadratic forms nonnegative on K = R n + for which inner and outer approximations are available; see e.g. Anstreicher and Burer [START_REF] Anstreicher | Computable representations for convex hulls of low-dimensional quadratic forms[END_REF], and Dür [START_REF] Dür | Copositive Programming: A survey[END_REF].

Contribution: In this paper, we present a different approach based on a new (at least to the best of our knowledge) and simple characterization of continuous functions that are nonnegative on a closed set K ⊆ R n . This characterization involves a single (but known) measure µ with supp µ = K, and sums of squares of polynomials. Namely, our contribution is twofold:

(a) We first show that a continuous function f is nonnegative on a closed set K ⊆ R n if and only if h 2 f dµ is nonnegative for all polynomials h ∈ R[x], where µ is a finite Borel measure 1 with supp µ = K. The measure µ is arbitrary if K is compact. If K is not compact then one may choose for µ the finite Borel measure:

-dµ = exp(i |x i |)dϕ if f is a polynomial, and -dµ = (1 + f 2 ) -1 exp(i |x i |)dϕ, if f is not a polynomial, where ϕ is any finite Borel measure with support exactly K. But many other choices are possible.

Equivalently, f is nonnegative on K if and only if every element of the countable family T of moment matrices associated with the signed Borel measure f dµ, is positive semidefinite. The absence of nonnegativity on K can be certified by exhibiting a polynomial h ∈ R[x] such that h 2 f dµ < 0, or equivalently, when some moment matrix in the family T is not positive semidefinite. And so, interestingly, as for nonnegativity or positivity, our certificate for absence of nonnegativity is also in terms of sums of squares. When f is a polynomial, these moment matrices are easily obtained from the moments of µ and this criterion for absence of nonnegativity complements Stengle's Nichtnegativstellensatz [START_REF] Stengel | A Nullstellensatz and a Positivstellensatz in semialgebraic geometry[END_REF] (which provides a certificate of nonnegativity on a semi-algebraic set K) or Schmüdgen and Putinar's Positivstellensätze [START_REF] Schmüdgen | The K-moment problem for compact semi-algebraic sets[END_REF][START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF] (for certificates of strict positivity on compact basic semi-algebraic sets). At last but not least, we obtain a convergent explicit hierarchy of semidefinite (outer) approximations with no lifting, of the cone C d of nonnegative polynomials of degree at most 2d. That is, we obtain a nested sequence

C 0 d ⊃ • • • C k d ⊃ • • • ⊃ C d such that each C k
d is a spectrahedron defined solely in terms of the vector of coefficients of the polynomial, with no additional variable (i.e., no projection is needed). Similar explicit hierarchies can be obtained for the cone of polynomials nonnegative on a closed set K (neither necessarily basic semi-algebraic nor compact), provided that all moments of an appropriate measure µ (with support exactly K) can be obtained. To the best of our knowledge, this is first result of this kind.

(b) As a potential application, we consider the problem of computing the global minimum f * of a polynomial f on a closed set K, a notoriously difficult problem. In nonlinear programming, a sequence of upper bounds on f * is usually obtained from a sequence of feasible points (x k ) ⊂ K, e.g., via some (local) minimization algorithm. But it is important to emphasize that for non convex problems, providing a sequence of upper bounds (f (x k )), k ∈ N, that converges to f * is in general impossible, unless one computes points on a grid whose mesh size tends to zero.

We consider the case where K ⊆ R n is a closed set for which one may compute all moments of a measure µ with supp µ = K. Typical examples of such sets are e.g. K = R n or K = R n + in the non compact case and a box, a ball, an ellipsoid, a simplex, or the vertices of an hypercube (or hyper rectangle) in the compact case. 1 A finite Borel measure µ on R n is a nonnegative set function defined on the Borel σ-algebra of R n (i.e., the σ-algebra generated by the open sets), such that µ

(∅) = 0, µ(R n ) < ∞, and µ( ∞ i=1 E i ) = ∞ i=1 µ(E i )
for any collection of disjoint measurable sets E i . Its support (denoted supp µ) is the smallest closed set K such that µ(R n \ K) = 0; see e.g. Royden [START_REF] Royden | Real Analysis[END_REF].

We then provide a hierarchy of semidefinite programs (with only one variable!) whose optimal values form a monotone nonincreasing sequence of upper bounds which converges to the global minimum f * . In fact, each semidefinite program is a very specific one as it reduces to solving a generalized eigenvalue problem for a pair of real symmetric matrices.. (Therefore, for efficiency one may use specialized software packages instead of a SDP solver.) However, the convergence to f * is in general only asymptotic and not finite (except when K is a discrete set in which case finite convergence takes place). This is in contrast with the hierarchy of semidefinite relaxations defined in Lasserre [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF][START_REF] Lasserre | Moments, Positive Polynomials and Their Applications[END_REF] which provide a nondecreasing sequence of lower bounds that also converges to f * , and very often in finitely many steps. Hence, for compact basic semi-algebraic sets these two convergent hierarchies of upper and lower bounds complement each other and permit to locate the global minimum f * in smaller and smaller intervals.

Notice that convergence of the hierarchy of convex relaxations in [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF] is guaranteed only for compact basic semi-algebraic sets, whereas for the new hierarchy of upper bounds, the only requirement on K is to know all moments of a measure µ with supp µ = K. On the other hand, in general computing such moments is possible only for relatively simple (but not necessarily compact nor semi-algebraic) sets.

At last but not least, the nonincreasing sequence of upper bounds converges to f * even if f * is not attained, which when K = R n , could provide an alternative and/or a complement to the hierarchy of convex relaxations provided in Schweighofer [START_REF] Schweighofer | Global optimization of polynomials using gradient tentacles and sums of squares[END_REF] (based on gradient tentacles) and in Hà and Pham [START_REF] Huy | Global optimization of polynomials using the truncated tangency variety and sums of squares[END_REF] (based on the truncated tangency variety), which both provide again a monotone sequence of lower bounds.

Finally, we also give a very simple interpretation of the hierarchy of dual semidefinite programs, which provides some information on the location of global minimizers.

Notation, definitions and preliminary results

A Borel measure on R n is understood as a positive Borel measure, i.e., a nonnegative set function µ on the Borel σ-algebra B (i.e., the σ-algebra generated by the open sets of R n ) such that µ(∅) = 0, and with the countably additive property

µ ∞ i=1 E i = ∞ i=1 µ(E i ),
for any collection of disjoint measurable sets (E i ) ⊂ B; see e.g. Royden [19, pp. 253-254].

Let R[x] be the ring of polynomials in the variables x = (x 1 , . . . , x n ), and Σ[x] ⊂ R[x] its subset of polynomials that are sums of squares (s.o.s.). Denote by R[x] d ⊂ R[x] the vector space of polynomials of degree at most d, which forms a vector space of dimension s(d) = n+d d , with e.g., the usual canonical basis (x α ) of monomials. Also, denote by Σ

[x] d ⊂ Σ[x] the convex cone of s.o.s. polynomials of degree at most 2d. If f ∈ R[x] d , write f (x) = α∈N n f α x α in
the canonical basis and denote by f = (f α ) ∈ R s(d) its vector of coefficients. Let S n denotes the vector space of p × p real symmetric matrices. For a matrix A ∈ S p the notation A 0 (resp. A ≻ 0) stands for A is positive semidefinite (resp. definite).

Moment matrix. With y = (y α ) being a sequence indexed in the canonical basis (x α ) of R[x], let L y : R[x] → R be the linear functional

f (= α f α x α ) → L y (f ) = α f α y α ,
and let M d (y) be the symmetric matrix with rows and columns indexed in the canonical basis (x α ), and defined by:

(2.1) M d (y)(α, β) := L y (x α+β ) = y α+β , α, β ∈ N n d with N n d := {α ∈ N n : |α| (= i α i ) ≤ d}. If y has a representing measure µ, i.e., if y α = x α dµ for every α ∈ N n , then f , M d (y)f = f (x) 2 dµ(x) ≥ 0, ∀ f ∈ R[x] d ,
and so M d (y) 0. A measure µ is said to be moment determinate if there is no other measure with same moments. In particular, and as an easy consequence of the Stone-Weierstrass theorem, every measure with compact support is determinate 2 . Not every sequence y satisfying M d (y) 0, d ∈ N, has a representing measure. However: Proposition 2.1 (Berg [START_REF] Berg | The multidimensional moment problem and semi-groups[END_REF]). Let y = (y α ) be such that M d (y) 0, for every d ∈ N. Then:

(a) The sequence y has a representing measure whose support is contained in the ball [-a, a] n if there exists a, c > 0 such that |y α | ≤ c a |α| for every α ∈ N n .

(b) The sequence y has a representing measure µ on R n if

(2.2) ∞ t=1 L y (x 2t i ) -1/2t = +∞, ∀ i = 1, . . . , n.
In addition, in both cases (a) and (b) the measure µ is moment determinate.

Condition (b) is an extension to the multivariate case of Carleman's condition in the univariate case and is due to Nussbaum [START_REF] Nussbaum | Quasi-analytic vectors[END_REF]. For more details see e.g. Berg [START_REF] Berg | The multidimensional moment problem and semi-groups[END_REF] and/or Maserick and Berg [START_REF] Maserick | Exponentially bounded positive definite functions[END_REF].

Localizing matrix. Similarly, with y = (y α ) and f

∈ R[x] written x → f (x) = γ∈N n f γ x γ ,
let M d (f y) be the symmetric matrix with rows and columns indexed in the canonical basis (x α ), and defined by:

(2.3) M d (f y)(α, β) := L y f (x) x α+β = γ f γ y α+β+γ , ∀ α, β ∈ N n d .
If y has a representing measure µ, then g, M d (f y)g = g 2 f dµ, and so if µ is supported on the set {x :

f (x) ≥ 0}, then M d (f y) 0 for all d = 0, 1, . . . because (2.4) g, M d (f y)g = g(x) 2 f (x) dµ(x) ≥ 0, ∀ g ∈ R[x] d .
2 To see this note that (a) two measures µ 1 , µ 2 on a compact set K ⊂ R n are identical if and only if K f dµ 1 = K f dµ 2 for all continuous functions f on K, and (b) by Stone-Weierstrass, the polynomials are dense in the space of continuous functions for the sup-norm.

Nonnegativity on closed sets

Recall that if X is a separable metric space with Borel σ-field B, the support supp µ of a Borel measure µ on X is the (unique) smallest closed set B ∈ B such that µ(X \ B) = 0. Given a Borel measure µ on R n and a measurable function f : R n → R, the mapping B → ν(B) := B f dµ, B ∈ B, defines a set function on B. If f is nonnegative then ν is a Borel measure (which is finite if f is µ-integrable); see e.g. Royden [19, p. 276 and p. 408]. If f is not nonnegative then setting B 1 := {x : f (x) ≥ 0} and B 2 := {x : f (x) < 0}, the set function ν can be written as the difference

(3.1) ν(B) = ν 1 (B) -ν 2 (B), B ∈ B,
of the two positive Borel measures ν 1 , ν 2 defined by

(3.2) ν 1 (B) = B1∩B f dµ, ν 2 (B) = - B2∩B f dµ, ∀B ∈ B.
Then ν is a signed Borel measure provided that either ν 1 (B 1 ) or ν 2 (B 2 ) is finite; see e.g. Royden [19, p. 271]. We first provide the following auxiliary result which is also of self-interest.

Lemma 3.1. Let X be a separable metric space, K ⊆ X a closed set, and µ a Borel measure on X with supp µ = K. A continuous function f :

X → R is nonnegative on K if and only if the set function B → ν(B) = K∩B f dµ, B ∈ B, is a positive measure.
Proof. The only if part is straightforward. For the if part, if ν is a positive measure then f (x) ≥ 0 for µ-almost all x ∈ K. That is, there is a Borel set G ⊂ K such that µ(G) = 0 and f (x) ≥ 0 on K \ G. Indeed, otherwise suppose that there exists a Borel set B 0 with µ(B 0 ) > 0 and f < 0 on B 0 ; then one would get the contradiction that ν is not positive because ν(B 0 ) = B0 f dµ < 0. In fact, f is called the Radon-Nikodym derivative of ν with respect to µ; see Royden [START_REF] Royden | Real Analysis[END_REF]Theorem 23,p. 276]. Next, observe that K \ G ⊂ K and µ(K \ G) = µ(K). Therefore K \ G = K because supp µ (= K) is the unique smallest closed set such that µ(X \ K) = 0. Hence, let x ∈ K be fixed, arbitrary. As

K = K \ G, there is a sequence (x k ) ⊂ K \ G, k ∈ N, with x k → x as k → ∞. But since f is continuous and f (x k ) ≥ 0 for every k ∈ N, we obtain the desired result f (x) ≥ 0.
Lemma 3.1 itself (of which we have not been able to find a trace in the literature) is a characterization of nonnegativity on K for a continuous function f on X. However, one goal of this paper is to provide a more concrete characterization. To do so we first consider the case of a compact set K ⊂ R n .

3.1. The compact case. Let K be a compact subset of R n . For simplicity, and with no loss of generality, we may and will assume that

K ⊆ [-1, 1] n . Theorem 3.2. Let K ⊆ [-1, 1
] n be compact and let µ be an arbitrary, fixed, finite Borel measure on K with supp µ = K, and with vector of moment y = (y α ), α ∈ N n . Let f be a continuous function on R n . Then:

(a) f is nonnegative on K if and only if

(3.3) K g 2 f dµ ≥ 0, ∀ g ∈ R[x],
or, equivalently, if and only if

(3.4) M d (z) 0, d = 0, 1, . . . where z = (z α ), α ∈ N n , with z α = x α f (x)dµ(x), and with M d (z) as in (2.1). If in addition f ∈ R[x] then (3.4) reads M d (f y) 0, d = 0, 1, . . ., where M d (f y) is the localizing matrix defined in (2.3). (b) If in addition to be continuous, f is also concave on K, then f is nonnegative on the convex hull co (K) of K if and only if (3.3) holds. Proof. The only if part is straightforward. Indeed, if f ≥ 0 on K then K ⊆ {x : f (x) ≥ 0} and so for any finite Borel measure µ on K, K g 2 f dµ ≥ 0 for every g ∈ R[x].
Next, if f is concave and f ≥ 0 on co (K) then f ≥ 0 on K and so the "only if" part of (b) also follows.

If part. The set function ν(B) = B f dµ, B ∈ B, can be written as the difference

ν = ν 2 -ν 2 of the two positive finite Borel measures ν 1 , ν 2 described in (3.1)-(3.2), where B 1 := {x ∈ K : f (x) ≥ 0} and B 2 := {x ∈ K : f (x) < 0}.
As K is compact and f is continuous, both ν 1 , ν 2 are finite, and so ν is a finite signed Borel measure; see Royden [19, p. 271]. In view of Lemma 3.1 it suffices to prove that in fact ν is a finite and positive Borel measure. So let z = (z α ), α ∈ N n , be the sequence defined by: d) , that is, M d (z) 0, where M d (z) is the moment matrix defined in (2.1). And so (3.3) implies M d (z) 0 for every d ∈ N.

(3.5) z α = K x α dν(x) := K x α f (x)dµ(x), ∀α ∈ N n . Every z α , α ∈ N n , is finite because K is compact and f is continuous. So the condition K g(x) 2 f (x) dµ(x) ≥ 0, ∀f ∈ R[x] d , reads g, M d (z)g ≥ 0 for all g ∈ R s(
Moreover, as K ⊆ [-1, 1] n , |z α | ≤ c := K |f |dµ, ∀ α ∈ N n .
Hence, by Proposition 2.1, z is the moment sequence of a finite (positive

) Borel measure ψ on [-1, 1] n , that is, as supp ν ⊆ K ⊆ [-1, 1] n , (3.6)
[-1,1] n x α dν(x) = [-1,1] n x α dψ(x), ∀α ∈ N n .
But then using (3.1) and (3.6) yields

[-1,1] n x α dν 1 (x) = [-1,1] n x α d(ν 2 + ψ)(x), ∀α ∈ N n , which in turn implies ν 1 = ν 2 + ψ because measures on a compact set are determi- nate. Next, this implies ψ = ν 1 -ν 2 (= ν) and so ν is a positive Borel measure on K. Hence by Lemma 3.1, f (x) ≥ 0 on K. If in addition f ∈ R[x], the sequence z = (z α ) is obtained as a linear combination of (y α ). Indeed if f (x) = β f β x β then z α = β∈N n f β y α+β , ∀ α ∈ N n ,
and so in (3.4), M d (z) is nothing less than the localizing matrix M d (f y) associated with y = (y α ) and f ∈ R[x], defined in (2.3), and (3.4) reads M d (f y) 0 for all d = 0, 1, . . . Finally, if f is concave then f ≥ 0 on K implies f ≥ 0 on co (K), and so the only if part of (b) also follows.

Therefore, to check whether a polynomial f ∈ R[x] is nonnegative on K, it suffices to check if every element of the countable family of real symmetric matrices (M d (f y)), d ∈ N, is positive semidefinite.

Remark 3.3. An informal alternative proof of Theorem 3.2 which does not use Lemma 3.1 is as follows. If f is not nonnegative on K there exists a ∈ K such that f (a) < 0, and so as K is compact, there is a continuous function, e.g, x → h(x) := exp(-c xa 2 ) close to 1 in some open neighborhood B(a, δ) of a, and very small in the rest of K. By the Stone-Weierstrass's theorem, one may choose h to be a polynomial. Next, the complement B(a, δ) c (= R n \ B(a, δ)) of B(a, δ) is closed, and so K ∩ B(a, δ) c is a closed set contained in K (hence smaller than K). Therefore µ(B(a, δ)) > 0 because otherwise µ(K ∩ B(a, δ) c ) = µ(K) which would imply that K ∩ B(a, δ) c is a support of µ smaller than K, in contradiction with supp µ = K. Hence, we would get the contradiction

h 2 f dµ ≈ h(a) 2 f (a) µ(B(a, δ)) < 0.
However, in the non compact case described in the next section, this argument is not valid.

3.2.

The non-compact case. We now consider the more delicate case where K is a closed set of R n , not necessarily compact. To handle arbitrary non compact sets K and arbitrary continuous functions f , we need a reference measure µ with supp µ = K and with nice properties so that integrals such as g 2 f dµ, g ∈ R[x], are well-behaved.

So, let ϕ be an arbitrary finite Borel measure on R n whose support is exactly K, and let µ be the finite Borel measure defined by:

(3.7) µ(B) := B exp - n i=1 |x i | dϕ(x), ∀ B ∈ B(R n ).
Observe that supp µ = K and µ satisfies Carleman's condition (2.2). Indeed, let z = (z α ), α ∈ N n , be the sequence of moments of µ. Then for every i = 1, . . . , n, and every k = 0, 1, . . ., using

x 2k i ≤ (2k)! exp |x i |, (3.8) L z (x 2k i ) = K x 2k i dµ(x) ≤ (2k)! K e |xi| dµ(x) ≤ (2k)! ϕ(K) =: (2k)! M.
Therefore for every i = 1, . . . , n, using (2k)! < (2k) 2k for every k, yields

∞ k=1 L z (x 2k i ) -1/2k ≥ ∞ k=1 M -1/2k ((2k)!) -1/2k ≥ ∞ k=1 M -1/2k 2k = +∞,
i.e., (2.2) holds. Notice also that all the moments of µ (defined in (3.7)) are finite, and so every polynomial is µ-integrable.

Theorem 3.4. Let K ⊆ R n be closed and let ϕ be an arbitrary finite Borel measure whose support is exactly K. Let f be a continuous function on

R n . If f ∈ R[x]
(i.e., f is a polynomial) let µ be as in (3.7) whereas if f is not a polynomial let µ be defined by

(3.9) µ(B) := B exp (-n i=1 |x i |) 1 + f (x) 2 dϕ(x), ∀ B ∈ B(R n ).
Then (a) and (b) of Theorem 3.2 hold.

For a detailed proof see §6.

It is important to emphasize that in Theorem 3.2 and 3.4, the set K is an arbitrary closed set of R n , and to the best of our knowledge, the characterization of nonnegativity of f in terms of positive definiteness of the moment matrices M d (z) is new. But of course, this characterization becomes even more interesting when one knows how the compute the moment sequence z = (z α ), α ∈ N n , which is possible in a few special cases only.

Important particular cases of nice such sets K include boxes, hyper rectangles, ellipsoids, and simplices in the compact case, and the positive orthant, or the whole space R n in the non compact case. For instance, for the whole space K = R n one may choose for µ in (3.7) the multivariate Gaussian (or normal) probability measure

µ(B) := (2π) -n/2 B exp(- 1 2 x 2 ) dx, B ∈ B(R n ),
which the n-times product of the one-dimensional normal distribution

µ i (B) := 1 √ 2π B exp(-x 2 i /2) dx i , B ∈ B(R),
whose moments are all easily available in closed form. In Theorem 3.4 this corresponds to the choice

(3.10) ϕ(B) = (2π) -n/2 B exp(-x 2 /2) exp(- n i=1 |x i |) dx, B ∈ B(R n ).
When K is the positive orthant R n + one may choose for µ the exponential probability measure

(3.11) µ(B) := B exp(- n i=1 x i ) dx, B ∈ B(R n + ),
which the n-times product of the one-dimensional exponential distribution

µ i (B) := B exp(-x i ) dx i , B ∈ B(R + ),
whose moments are also easily available in closed form. In Theorem 3.4 this corresponds to the choice

ϕ(B) = 2 n B exp(- n i=1 x i ) dx, B ∈ B(R n + ).
3.3. The cone of nonnegative polynomials. The convex cone C d ⊂ R[x] 2d of nonnegative polynomials of degree at most 2d (a nonnegative polynomial has necessarily even degree) is much harder to characterize than its subcone Σ[x] d of sums of squares. Indeed, while the latter has a simple semidefinite representation with lifting (i.e. Σ[x] d is the projection in R s(2d) of a spectrahedron 3 in a higher dimensional space), so far there is no such simple representation for the former. In addition, when d is fixed, Blekherman [START_REF] Blekherman | There are significantly more nonnegative polynomials than sums of squares[END_REF] has shown that after proper normalization, the "gap" between C d and Σ[x] d increases unboundedly with the number of variables.

We next provide a convergent hierarchy of (outer) semidefinite approximations (C k d ), k ∈ N, of C d where each C k d has a semidefinite representation with no lifting (i.e., no projection is needed and C k d is a spectrahedron). To the best of our knowledge, this is the first result of this kind.

Recall that with every f ∈ R[x] d is associated its vector of coefficients f = (f α ), α ∈ N n d , in the canonical basis of monomials, and conversely, with every f ∈ R s(d) is associated a polynomial f ∈ R[x] d with vector of coefficients f = (f α ) in the canonical basis. Recall that for every k = 1, . . .,

γ p := 1 √ 2π ∞ -∞ x p e -x 2 /2 dx = 0 if p = 2k + 1, k j=1 (2j -1) if p = 2k, as γ 2k = (2k -1)γ 2(k-1) for every k ≥ 1.
Corollary 3.5. Let µ be the probability measure on R n which is the n-times product of the normal distribution on R, and so with moments y = (y α ), α ∈ N n , (3.12)

y α = R n x α dµ = n i=1 1 √ 2π ∞ -∞ x αi e -x 2 /2 dx , ∀ α ∈ R n . For every k ∈ N, let C k d := {f ∈ R s(2d) : M k (f y)
0}, where M k (f y) is the localizing matrix in (2.3) associated with y and f ∈ R[x] 2d . Each C k d is a closed convex cone and a spectrahedron.

Then

C 0 d ⊃ C 1 d • • • ⊃ C k d • • • ⊃ C d and f ∈ C d if and only if its vector of coefficients f ∈ R s(2d) satisfies f ∈ C k d ,
for every k = 0, 1, . . .. Proof. Following its definition (2.3), all entries of the localizing matrix M k (f y) are linear in f ∈ R s(2d) , and so M k (f y) 0 is an LMI. Therefore C k d is a spectrahedron and a closed convex cone. Next, let K := R n and let µ be as in Corollary 3.5 and so of the form (3.7) with ϕ as in (3.10). Then µ satisfies Carleman's condition (2.2). Hence, by Theorem 3.4 with

K = R n , f is nonnegative on K if and only if (3.4) holds, which is equivalent to stating that M k (f y) 0, k = 0, 1, . . ., which in turn is equivalent to stating that f ∈ C k d , k = 0, 1, . . . So the nested sequence of convex cones C 0 d ⊃ C k d • • • ⊃ C d defines arbitrary close outer approximations of C d . In fact ∩ ∞ k=0 C k d is closed and C d = ∩ ∞ k=0 C k d .
It is worth emphasizing that each C k d is a spectrahedron with no lifting, that is, C k d is defined solely in terms of the vector of coefficients f with no additional variable (i.e., no projection is needed). 3 A spectrahedron is the intersection of the cone of positive semidefinite matrices with an affine-linear space. Its algebraic representation is called a Linear Matrix Inequality (LMI).

For instance, the first approximation C 0 d is just the set {f ∈ R s(2d) : f dµ ≥ 0}, which is a half-space of R s(2d) . And with n = 2,

C 1 d =              f ∈ R s(d) :        f dµ x 1 f dµ x 2 f dµ x 1 f dµ x 2 1 f dµ x 1 x 2 f dµ x 2 f dµ x 1 x 2 f dµ x 2 2 f dµ        0             
, or, equivalently, C 1 d is the convex basic semi-algebraic set:

f ∈ R s(2d) : f dµ ≥ 0 x 2 i f dµ f dµ ≥ x i f dµ 2 , i = 1, 2 x 2 1 f dµ x 2 2 f dµ ≥ x 1 x 2 f dµ 2 f dµ x 2 1 f dµ x 2 2 f dµ - x 1 x 2 f dµ 2 - x 1 f dµ 2 x 2 2 f dµ - x 2 f dµ 2 x 2 1 f dµ + 2 x 1 f dµ x 2 f dµ x 1 x 2 f dµ ≥ 0 ,
where we have just expressed the nonnegativity of all principal minors of M 1 (f y).

A very similar result holds for the convex cone C d (K) of polynomials of degree at most d, nonnegative on a closed set K ⊂ R n . Corollary 3.6. Let K ⊂ R n be a closed set and let µ be defined in (3.7) where ϕ is a an arbitrary finite Borel measure whose support is exactly K.

For every

k ∈ N, let C k d (K) := {f ∈ R s(d) : M k (f y) 0}, where M k (f y) is the localizing matrix in (2.3) associated with y and f ∈ R[x] d . Each C k d (K) is a closed convex cone and a spectrahedron. Then C 0 d (K) ⊃ C 1 d (K) • • • ⊃ C k d (K) • • • ⊃ C d (K) and f ∈ C d (K) if and only if its vector of coefficients f ∈ R s(d) satisfies f ∈ C k d (K)
, for every k = 0, 1, . . .. The proof which mimicks that of Corollary 3.5 is omitted. Of course, for practical computation, one is restricted to sets K where one may compute effectively the moments of the measure µ. An example of such a set K is the positive orthant, in which case one may choose the measure µ in (3.11) for which all moments are explicitly available. For compact sets K let us mention balls, boxes, ellipsoids, and simplices. But again, any compact set where one knows how to compute all moments of some measure with support exactly K, is fine.

To the best of our knowledge this is the first characterization of an outer approximation of the cone C d (K) in a relatively general context. Indeed, for the basic semi-algebraic set

(3.13) K = {x ∈ R n : g j (x) ≥ 0, j = 1, . . . , m },
Stengle's Nichtnegativstellensatz [START_REF] Stengel | A Nullstellensatz and a Positivstellensatz in semialgebraic geometry[END_REF] states that f ∈ R[x] is nonnegative on K if and only if

(3.14) p f = f 2s + q,
for some integer s and polynomials p, q ∈ P (g), where P (g) is the preordering4 associated with the g j 's. In addition, there exist bounds on the integer s and the degree of the s.o.s. weights in the definition of p, q ∈ P (g), so that in principle, when f is known, checking whether f ≥ 0 on K reduces to solving a single SDP to compute h, p in the nonnegativity certificate (3.14). However, the size of this SDP is potentially huge and makes it unpractical. Moreover, the representation of C d (K) in (3.14) is not convex in the vector of coefficients of f because it involves f 2s as well as the product pf .

Remark 3.7. If in Corollary 3.6 one replaces the finite-dimensional convex cone

C d (K) ⊂ R[x] d with the infinite-dimensional convex cone C(K) ⊂ R[x]
of all polynomials nonnegative on K, and

C k d (K) ⊂ R[x] d with C k (K) = {f ∈ R s(2k) : M k (f y)
0}, then the nested sequence of (increasing but finite-dimensional) convex cones C k (K), k ∈ N, provides finite-dimensional approximations of C(K).

Application to polynomial optimization

Consider the polynomial optimization problem (4.1)

P : f * = inf x { f (x) : x ∈ K }, where K ⊆ R n is closed and f ∈ R[x].
If K is compact let µ be a finite Borel measure with supp µ = K and if K is not compact, let ϕ be an arbitrary finite Borel measure with supp ϕ = K and let µ be as in (3.7). In both cases, the sequence of moments y = (y α ), α ∈ N n , is well-defined, and we assume that y α is available or can be computed, for every α ∈ N n .

Consider the sequence of semidefinite programs: For each d ∈ N, the semidefinite program (4.2) provides an upper bound on the optimal value f * only. We next show that the dual contains some information on global minimizers, at least when d is sufficiently large.

* d = inf σ K f σ dµ : K σ dµ = 1; σ ∈ Σ[x] d . (4.4) λ
So the dual problem (4.4) is to find a sum of squares polynomial σ of degree at most 2d (normalized to satisfy σdµ = 1) that minimizes the integral f σdµ, and a simple interpretation of (4.4) is as follows: With M (K) being the space of Borel probability measures on K, we know that

f * = inf ϕ∈M(K) K f dϕ. Next, let M d (µ) ⊂ M (K)
K (f (x) -λ d ) σ * (x)dµ(x) = 0. (b) If K is convex and f is convex, let x * d := x σ * (x)dµ(x). Then x * d ∈ K and f * ≤ f (x * d ) ≤ λ d , so that f (x * d ) → f * as d → ∞. Moreover, if the set {x ∈ K : f (x) ≤ f 0 } is compact for some f 0 > f * , then any accumulation point x * ∈ K of the sequence (x * d ), d ∈ N, is a minimizer of problem (4.1), that is, f (x * ) = f * .
Proof. (a) Any scalar λ < f * is a feasible solution of (4.2) and in addition, M d ((fλ) y) ≻ 0 because since K has nonempty interior and fλ > 0 on K,

g, M d ((f -λ) y) g = K (f (x) -λ)g(x) 2 µ(dx) > 0, ∀g ∈ R[x] d .
But this means that Slater's condition5 holds for (4.2) which in turn implies that there is no duality gap and (4.4) has an optimal solution σ * ∈ Σ[x] d ; see e.g. [START_REF] Vandenberghe | Semidefinite programming[END_REF]. And so,

K (f (x) -λ d ) σ * (x) dµ(x) = K f σ * dµ -λ d = 0.
(b) Let ν be the Borel probability measure on K defined by ν(B)

= B σ * dµ, B ∈ B.
As f is convex, by Jensen's inequality (see e.g. McShane [START_REF] Mcshane | Jensen's inequality[END_REF]),

K f σ * dµ = K f dν ≥ f K x dν = f (x * d ).
In addition, if K is convex then x * d ∈ K and so,

λ d ≥ f (x * d ) ≥ f * . Finally if for some f 0 > f * , the set H := {x ∈ K : f (x) ≤ f 0 } is compact,
∈ K such that x * d ℓ → x * as ℓ → ∞. Continuity of f combined with the convergence f (x * d ) → f * yields f (x * d ℓ ) → f (x * ) = f * as ℓ → ∞.
As the convergent subsequence (x * d ℓ ) was arbitrary, the proof is complete.

So in case where f is a convex polynomial and K is a convex set, Theorem 4.2 provides a means of approximating not only the optimal value f * , but also a global minimizer x * ∈ K.

In the more subtle nonconvex case, one still can obtain some information on global minimizers from an optimal solution σ * ∈ Σ[x] d of (4.4). Let ǫ > 0 be fixed, and suppose that d is large enough so that f * ≤ λ d ≤ f * + ǫ. Then, by Theorem 4.4(a),

K (f (x) -f * )σ * (x) dµ(x) = λ d -f * < ǫ.
As ff * ≥ 0 on K, necessarily the measure dν = σ * dµ gives very small weight to regions of K where f (x) is significantly larger than f * . For instance, if ǫ = 10 -2 and ∆ := {x ∈ K : f (x) ≥ f * + 1}, then ν(∆) ≤ 10 -2 , i.e., the set ∆ contributes to less than 1% of the total mass of ν. So if µ is uniformly distributed on K (which is a reasonable choice if one has to compute all moments of µ) then a simple inspection of the values of σ * (x) provides some rough indication on where (in

K) f (x) is close to f * .
The interpretation (4.4) of the dual shows that in general the monotone convergence is only asymptotic and cannot be finite. Indeed if K has a nonempty interior then the probability measure dν = σdµ cannot be a Dirac measure at any global minimizer x * ∈ K. An exception is the discrete case, i.e., when K is a finite number of points, like in e.g. 0/1 programs. Indeed we get:

Corollary 4.3. Let K ⊂ R n be a discrete set (x(k)) ⊂ R n , k ∈ J,
and let µ be the probability measure uniformly distributed in K, i.e.,

µ = 1 s s k=1 δ x(k) ,
where s = |J| and δ x denote the Dirac measure at the point x. Then the optimal value λ d of (4.2) satisfies λ d = f * for some integer d.

Proof. Let x * = x(j * ) (for some j * ∈ J) be the global minimizer of min{f (x) :

x ∈ K}. For each k = 1, . . . , s there exists a polynomial q k ∈ R[x] such that q k (x(j)) = δ k=j for every j = 1, . . . , s (where δ k=j denotes the Kronecker symbol).

The polynomials (q k ) are called interpolation polynomials. So let

σ * := sq 2 j * ∈ Σ[x], so that K f (x)σ * (x)dµ(x) = f (x(j * )) = f * and K σ * dµ = 1.
Hence as soon as d ≥ deg q j * , σ * ∈ Σ[x] d is a feasible solution of (4.4), and so from

f * = f σ * dµ ≥ λ * d ≥ λ d ≥ f * we deduce that λ * d = λ d = f * , the desired result.
There are several interesting cases where the above described methodology can apply, i.e., cases where y can be obtained either explicitly in closed form or numerically. In particular, when K is either:

• A box B := n i=1 [a i , b i ] ⊂ R n
, with µ being the normalized Lebesgue measure on B. The sequence y = (y α ) is trivial to obtain in closed form.

• The discrete set {-1, 1} n with µ being uniformly distributed and normalized. Again the sequence y = (y α ) is trivial to obtain in closed form. Notice that in this case we obtain a new hierarchy of semidefinite relaxations (with only one variable) for the celebrated MAXCUT problem (and any nonlinear 0/1 program). • The unit Euclidean ball B := {x : x 2 ≤ 1} with µ uniformly distributed, and similarly the unit sphere S := {x : x 2 = 1}, with µ being the rotation invariant probability measure on S. In both cases the moments y = (y α ) are obtained easily. • A simplex ∆ ⊂ R n , in which case if one takes µ as the Lebesgue measure then all moments of µ can be computed numerically. In particular, with d fixed, this computation can be done in time polynomial time. See e.g. the recent work of [START_REF] Baldoni | How to integrate a polynomial on a simplex[END_REF]. • The whole space R n in which case µ may be chosen to be the product measure ⊗ n i=1 ν i with each ν i being the normal distribution. Observe that one then obtains a new hierarchy of semidefinite approximations (upper bounds) for unconstrained global optimization. The corresponding monotone sequence of upper bounds converges to f * no matter if the problem has a global minimizer or not. This may be an alternative and/or a complement to the recent convex relaxations provided in Schweighofer [START_REF] Schweighofer | Global optimization of polynomials using gradient tentacles and sums of squares[END_REF] and Hà and Vui [START_REF] Huy | Global optimization of polynomials using the truncated tangency variety and sums of squares[END_REF] which also work when f * is not attained, and provide a convergent sequence of lower bounds.

• The positive orthant R n + , in which case µ may be chosen to be the product measure ⊗ n i=1 ν i with each ν i being the exponential distribution ν i (B) = R + ∩B e -x dx, B ∈ B. In particular if x → f (x) := x T Ax where A ∈ S n , then one obtains a hierarchy of numerical tests to check whether A is a copositive matrix. Indeed, if λ d is an optimal solution of (4.3) then A is copositive if and only if λ d ≥ 0 for all d ∈ N. Notice that we also obtain a hierarchy of outer approximations (COP d ) ⊂ S n of the cone COP of n × n copositive matrices. Indeed, for every A ∈ S n , let f A be the quadratic form x → f A (x) := x T Ax. Then, for every d, the set

COP d := {A ∈ S n : M d (f A y) 0 }
is a convex cone defined only in terms of the coefficients of the matrix A.

It is even a spectrahedron since M d (f A y) is a linear matrix inequality in the coefficients of A. And in view of Theorem 3.2(a), COP = d∈N COP d .

4.2.

Examples. In this section we provide three simple examples to illustrate the above methodology.

Example 1. Consider the global minimization on

K = R 2 + of the Motzkin-like polynomial x → f (x) = x 2 1 x 2 2 (x 2 1 + x 2 2 -1) whose global minimum is f * = -1/27 ≈ -0.037, attained at (x * 1 , x * 2 ) = (± 1/3, ± 1/3). Choose for µ the probability measure µ(B) := B e -x1-x2 dx, B ∈ B(R 2 +
), for which the sequence of moments y = (y ij ), i, j ∈ N, is easy to obtain. Namely y ij = i!j! for every i, j ∈ N. Then the semidefinite relaxations (4.2) yield λ 0 = 92, λ 1 = 1.5097, and λ 14 = -0.0113, showing a significant and rapid decrease in first iterations with a long tail close to f * , illustrated in Figure 1. Then after d = 14, one encounters some numerical problems and we cannot trust the results anymore.

If we now minimize the same polynomial f on the box [0, 1] 2 , one choose for µ the probability uniformly distributed on [0, 1] 2 , whose moments y = (y ij ), i, j ∈ N, are also easily obtained by y ij = (i + 1) -1 (j + 1) -1 . Then one obtains λ 0 = 0.222, λ 1 = -0.055, and λ 10 = -0.0311, showing again a rapid decrease in first iterations with a long tail close to f * , illustrated in Figure 2. illustrated in Figure 3; numerical problems occur after d = 15. However, this kind of problems where the global minimum f * is not attained, is notoriously difficult. Even the semidefinite relaxations defined in [START_REF] Huy | Global optimization of polynomials using the truncated tangency variety and sums of squares[END_REF] (which provide lower bounds on f * ) and especially devised for such problems, encounter numerical difficulties; see [START_REF] Huy | Global optimization of polynomials using the truncated tangency variety and sums of squares[END_REF]Example 4.8].

f * = min x {x T Qx : x ∈ {-1, 1} n }, where Q = (Q ij ) ∈ R n×n
is a real symmetric matrix whose all diagonal elements vanish. The measure µ is uniformly distributed on {-1, 1} n so that its moments are readily available. We first consider the equal weights case, i.e., Q ij = 1/2 for all (i, j) with i = j in which case f * = -⌊n/2⌋. With n = 11 the successive values for λ d , d ≤ 4, are displayed in Table 1 and λ 4 is relatively close to f * . Next we have generated five random instances of MAXCUT with n = 11 but Q ij = 0 with probability 1/2, and if Q ij = 0 it is randomly generated using the Matlab "rand" function. The successive values of λ d , d ≤ 4, are displayed in Table 2, and again, λ 4 is quite close to f *6 .

The above examples seem to indicate that even though one chooses a measure µ uniformly distributed on K, one obtains a rapid decrease in the first iterations and then a slow convergence close to f * . If on the one hand the convergence to f * is likely to be slow, on the other hand, one has to solve semidefinite programs (4.2) with only one variable! In fact solving the semidefinite program (4.3) is computing the smallest generalized eigenvalue associated with the pair of real symmetric matrices (M d (f y), M d (y)), for which specialized codes are available (instead of using a solver for semidefinite programs). However, one has to remember that the choice is limited to measures µ with supp µ = K and whose moments are available or easy to compute. Hence, the present methodology is so far limited to simple sets K as described before. Finally, analyzing how the convergence to f * depends on µ is beyond the scope of the present paper and is a topic of further research.

d d = 0 d = 1 d = 2 d = 3 d = 4 f * λ d 0 -1 -2.

Discusssion.

In nonlinear programming, sequences of upper bounds on the global minimum f * are usually obtained from feasible points x ∈ K, e.g., via some (local) minimization algorithm. But for non convex problems, providing a sequence of upper bounds that converges to the global minimum f * is in general impossible unless one computes points on a grid whose mesh size tends to zero. In the above methodology one provides a monotone nonincreasing sequence of upper bounds converging to f * for polynomial optimization problems on sets K, non necessarily compact but such that one may compute all moments of some finite Borel measure µ with supp µ = K. In fact, if there are only finitely many (say up to order 2d) moments available then one obtains a finite sequence of upper bounds.

In contrast to the hierarchy of semidefinite relaxations in e.g. [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF][START_REF] Lasserre | Moments, Positive Polynomials and Their Applications[END_REF] which provide lower bounds converging to f * when K is a compact basic semi-algebraic set, the convergence of the upper bounds to f * is only asymptotic and never finite, except when K is a discrete set. However, and even if we expect the convergence to be rather slow when close to f * , to our knowledge it is the first approach of this kind, and in a few iterations one may obtain upper bounds which (even if crude) complements the lower bounds obtained in [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF] (in the compact case).

Also note that to solve (4.3) several improvements are possible. For instance, we have already mentioned that it could be solved via specialized packages for generalized eigenvalue problems. Next, if instead of using the canonical basis of monomial (x α ), one now expresses the moment matrix M d (y) with rows and columns indexed in the basis of polynomials (p α ) ⊂ R[x] (up to degree d) orthogonal 7 with respect to µ, then M d (y) becomes the identity matrix. And so problem (4.3) reduces to a standard eigenvalue problem, namely that of computing the smallest eigenvalue of the (real and symmetric) localizing matrix M d (f y) (expressed in the basis of orthogonal polynomials)! And it turns out that computing the orthogonal polynomials is easy once the moment matrix M d (y) is available, since they can be obtained via computing certain determinants, as explained in e.g. [START_REF] Dunkl | Orthogonal Polynomials of Several Variables[END_REF][START_REF] Helton | Measures with zeros in the inverse of their moment matrix[END_REF].

Inverse problem from moments. Finally, observe that the above methodology perfectly fits inverse problems from moments, where precisely some Borel measure µ is known only from its moments (via some measurement device), and one wishes to recover (or approximately recover) its support K from the known moments; see e.g. the work of Cuyt et al. [START_REF] Cuyt | Mutlidimensional integral inversion with application in shape reconstruction[END_REF] and the many references therein. Hence if f ∈ R[x] is fixed then by definition ff * ≥ 0 (on K) provides a strong valid (polynomial) inequality for the unknown set K. So computing an optimal solution λ d of (4.2) for d sufficiently large, will provide an almost-valid polynomial inequality fλ d ≥ 0 for K. One may even let f ∈ R[x] d be unknown and search for the "best" valid inequality f (x)f * ≥ 0 where f varies in some family (e.g. linear or quadratic polynomials) and minimizes ome appropriate (linear or convex) objective function of its vector of coefficents f .

Conclusion

In this paper we have presented a new characterization of nonnegativity on a closed set K which is based on the knowledge of a single finite Borel measure µ with supp µ = K. It permits to obtain a hierarchy of spectrahedra which provides a nested sequence of outer approximations of the convex cone of polynomials of degree at most d, nonnegative on K. When used in polynomial optimization for certain "simple sets" K, one obtains a hierarchy of semidefinite approximations (with only one variable) which provides a nonincreasing sequence of upper bounds converging to the global optimum, hence a complement to the sequence of upper bounds provided by the hierarchy of semidefinite relaxations defined in e.g. [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF][START_REF] Lasserre | Moments, Positive Polynomials and Their Applications[END_REF] when K is compact and basic semi-algebraic. A topic of further investigation is to analyze the efficiency of such an approach on a sample of optimization problems on simple closed sets like the whole space R n , the positive orthant R n + , a box, a simplex, or an ellipsoid, as well as for some inverse problems from moments.

appendix

Proof of Theorem 3.4.

Proof. The only if part is exactly the same as in the proof of Theorem 3.2. For the if part, let z = (z α ) be the sequence defined in (3.5). The sequence z is well defined because x → x α f (x) is µ-integrable for all α ∈ N n . Indeed, if f is a polynomial (so that µ is defined in (3.7)) we have seen that all moments of µ are finite and since x α f (x) is a polynomial the result follows. If f is not a polynomial (so that µ is defined in (3.9)) then where M is as in (3.8) and assuming with no loss of generality that µ(K) ≤ M n(2(k + s))! (otherwise rescale ϕ). And so we have

L z (x 2k i ) -1/2k ≥ (2M n f 1 ) -1/2k (2(k + s))!) -1/2(k+s) (k+s)/k ≥ 1 2 (2(k + s))!) -1/2(k+s) (k+s)/k ≥ 1 2 1 2(k + s) (k+s)/k ,
where k ≥ k 0 is sufficiently large so that (2M n f 1 ) -1/2k ≥ 1/2. Therefore, If f is not a polynomial then µ is as in (3.9) and so

L z (x 2k i ) = x 2k i exp (- n i=1 |x i |) 1 + f 2 f (x) dϕ(x) ≤ x 2k i exp (-n i=1 |x i |) 1 + f 2 |f (x)| dϕ(x) ≤ x 2k i exp - n i=1 |x i | dϕ(x) ≤ (2k)!M, (6.2)
where we have used that |f |/(1 + f 2 ) ≤ 1 for all x, and x 2k i ≤ (2k)! exp |x i |. And so again, the sequence z satisfies Carleman's condition (2.2).

Next, as M d (z) 0 for every d ∈ N, by Proposition 2.1, z is the moment sequence of a measure ψ on R n and ψ is determinate. In addition, from the definition (3.5) of ν and z, we have and so, depending on whether f is a polynomial or not, we obtain L v (x 2k i ) ≤ 2M n f 1 (2(k + s))! as in (6.1) or L v (x 2k i ) ≤ (2k)!M as in (6.2). In both cases the sequence v satisfies Carleman's condition (2.2) and since M d (v) 0 for all d ∈ N, by Proposition 2.1, ν 1 is moment determinate. But then (6.4) yields ν 1 = ψ + ν 2 , or equivalently, ψ = ν 1ν 2 (= ν), that is, ν is a positive measure. The rest of the proof is exactly the same as for proof of Theorem 3.2.

(4. 2 )Theorem 4 . 1 .

 241 λ d = sup λ∈R {λ : M d (f λ y) 0 } where f λ ∈ R[x] is the polynomial x → f (x)λ. Notice that (4.2) has only one variable! Consider the hierarchy of semidefinite programs (4.2) indexed by d ∈ N. Then: (i) (4.2) has an optimal solution λ d ≥ f * for every d ∈ N n . (ii) The sequence (λ d ), d ∈ N, is monotone nonincreasing and λ d ↓ f * as d → ∞. Proof. (i) Since ff * ≥ 0 on K, by Theorem 3.2, λ := f * is a feasible solution of (4.2) for every d. Hence λ d ≥ f * for every d ∈ N. Next, let d ∈ N be fixed, and let λ be an arbitrary feasible solution of (4.2). From the condition M d (f λ y) 0, the diagonal entry M d (f λ y)(1, 1) must be nonnegative, i.e., λy 0 ≤ α f α y α , and so, as we maximize and y 0 > 0, (4.2) must have an optimal solution λ d . (ii) Obviously λ d ≤ λ m whenever d ≥ m, because M d (f λ y) 0 implies M m (f λ y) 0. Therefore, the sequence (λ d ), d ∈ N, is monotone nonincreasing and being bounded below by f * , converges to λ * ≥ f * . Next, suppose that λ * > f * ; fix k ∈ N, arbitrary. The convergence λ d ↓ λ * implies M k (f λ * y) 0. As k was arbitrary, we obtain that M d (f λ * y) 0 for every d ∈ N. But then by Theorem 3.2 or Theorem 3.4, fλ * ≥ 0 on K, and so λ * ≤ f * , in contradiction with λ * > f * . Therefore λ * = f * .

4. 1 .

 1 Duality. Let S d be the space of real symmetric s(d) × s(d) matrices. One may write the semidefinite program (4.2) as (4.3) λ d = sup λ {λ : λM d (y) M d (f y)}, which in fact is a generalized eigenvalue problem for the pair of matrices M d (y) and M d (f y). Its dual is the semidefinite program inf X∈S d { X, M d (f y) : X, M d (y) = 1; X 0 }, or, equivalently,

Theorem 4 . 2 .

 42 be the space of probability measures on K which have a density σ ∈ Σ[x] d with respect to µ. Then (4.4) reads inf ϕ∈M d (µ) Kf dϕ, which clearly shows why one obtains an upper bound on f * . Indeed, instead of searching in M (K) one searches in its subset M d (µ). What is not obvious at all is whether the obtained upper bound obtained in (4.4) converges to f * when the degree of σ ∈ Σ[x] d is allowed to increase! Suppose that f * > -∞ and K has nonempty interior. Then :(a) There is no duality gap between (4.2) and (4.4) and (4.4) has an optimal solution σ * ∈ Σ[x] d which satisfies

Figure 1 . 2 + 2 .Figure 2 .

 1222 Figure 1. Minimizing the Motzkin-like polynomial in R 2 +

Figure 3 .x 2 1 + ( 1 -x 1 x 2 ) 2 on R 2 + 3 .

 311223 Figure 3. Minimizing x 2 1 + (1x 1 x 2 ) 2 on R 2 +

Figure 4 .Example 4 .

 44 Figure 4. f (x) = 0.375 -5x + 21x 2 -32x 3 + 16x 4 on [0, 1] Example 4. We finally consider a discrete optimization problem, namely the celebrated MAXCUT problem

Figure 5 .Figure 6 .

 56 Figure 5. Minimizing 0.375 -5x + 21x 2 -32x 3 + 16x 4 on [0, 1]

K≤ f 1

 1 |x α f (x)| dµ(x) ≤ K |x α | exp(i |x i |) dϕ(x) ≤ ϕ(R n ) n i=1 α i !,where we have used that|x αi i | ≤ α i ! exp |x i |, and |f |/(1 + f 2 ) ≤ 1 for all x.As in the proof of Theorem 3.2, the set function B → ν(B) := B f dµ, B ∈ B, is a signed Borel measure because again ν can be written as the difference ν 1ν 2 of the two positive Borel measures ν 1 , ν 2 in (3.1)-(3.2). With same majorizations as above, both ν 1 and ν 2 are finite Borel measures and so ν is a finite signed Borel measure.The same arguments as in the proof of Theorem 3.2 show that M d (z) 0 for every d ∈ N. Next, the sequence z satisfies the generalized Carleman's condition (2.2).Indeed, first consider the case where f is a polynomial (and so µ is as in (3.7)). Let 1 ≤ i ≤ n be fixed arbitrary, and let 2s ≥ degf . Observe that whenever |α| ≤ k,|x| α ≤ |x j | k on the subset W j := {x ∈ R n \ [-1, 1] n : |x j | = max i |x i |}. And so, |f (x)| ≤ f 1 |x j | 2s for all x ∈ W j (and where f 1 := α |f α |). Hence, L z (x 2k i ) = K f (x) x 2k i dµ(x) ≤ K∩[-1,1] n |f (x)| x 2k i dµ(x) + f 1 µ(K) + M n f 1 (2(k + s))! ≤ 2M n f 1 (2(k + s))!, (6.1)

  equality follows from ∞ k=1 (2k) -1 = +∞. Indeed, ( 1 2(k+s) ) (k+s)/k = ( 1 2(k+s) )( 1 2(k+s) ) s/k and ( 1 2(k+s) ) s/k ≥ 1/2 whenever k is sufficiently large, say k ≥ k 1 . Hence the sequence z satisfies Carleman's condition (2.2).

  α dψ(x) = z α = K x α dν(x), ∀ α ∈ N n .But then using ν = ν 1ν 2 in (3.1)-(3.2), (6.3) reads (6.4)R n x α d(ψ + ν 2 )(x) = K x α dν 1 (x), ∀α ∈ N n . Let v = (v α ), α ∈ N n , be the sequence of moments associated with ν 1 . Of course, M d (v) 0 for all d ∈ N. Next, L v (x 2k i ) = B1 x 2k i f (x) dµ(x) ≤ K x 2k i |f (x)| dµ(x),

  and since λ d → f * , then f (x * d ) ≤ f 0 for d sufficiently large, i.e., x * d ∈ H for sufficiently large d. By compactness there is a subsequence (d ℓ ), ℓ ∈ N, and a point x *

Table 1 .

 1 MAXCUT: n = 11; Q(i, j) = 1 for all i = j.

					662 -3.22	-4	-5
	d	λ 0	λ 1	λ 2	λ 3	λ 4	f *
	Ex1 0 -1.928 -3.748	-5.22	-6.37 -7.946
	Ex2 0	-1.56 -3.103 -4.314 -5.282 -6.863
	Ex3 0 -1.910 -3.694 -5.078 -6.161 -8.032
	Ex4 0 -2.164 -4.1664 -5.7971 -7.06 -9.198
	Ex5 0 -1.825 -3.560 -4.945 -5.924 -7.467

Table 2 .

 2 MAXCUT: n = 11; Q random.

The preordering P (g) associated with the g j 's is the set of polynomials of the form α∈{0,1} m σα g α 1 1 • • • g αm m where σα ∈ Σ[x] for each α.

For an optimization problem infx{f 0 (x) : f j (x) ≥ 0, j = 1, . . . , m}, Slater's condition states that there exists x 0 such that f j (x 0 ) > 0 for every j = 1, . . . , m.

The optimal value f * has been computed using the GloptiPoly software[START_REF] Henrion | Gloptipoly 3: moments, optimization and semidefinite programming[END_REF] dedicated to solving the Generalized Problem of Moments

A family of univariate polynomials (p k ) ⊂ R[x] is orthogonal with respect to a finite measure µ on R if p i p k dµ = δ i=k . For extensions to the multivariate case see e.g.[START_REF] Dunkl | Orthogonal Polynomials of Several Variables[END_REF][START_REF] Helton | Measures with zeros in the inverse of their moment matrix[END_REF].