Etienne De Klerk
email: e.deklerk@uvt.nl

Monique Laurent
email: m.laurent@cwi.nl

A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis

The generalized problem of moments is a conic linear optimization problem over the convex cone of positive Borel measures with given support. It has a large variety of applications, including global optimization of polynomials and rational functions, options pricing in finance, constructing quadrature schemes for numerical integration, and distributionally robust optimization. A usual solution approach, due to J.B. Lasserre, is to approximate the convex cone of positive Borel measures by finite dimensional outer and inner conic approximations. We will review some results on these approximations, with a special focus on the convergence rate of the hierarchies of upper and lower bounds for the general problem of moments that are obtained from these inner and outer approximations.

Introduction

The classical problem of moments asks when a measure is determined by a set of specified moments and variants of this problem were studied (in the univariate case) by leading 19th and early 20th century mathematicians, like Hamburger, Stieltjes, Chebyshev, Hausdorff, and Markov. We refer to [START_REF] Akhiezer | The classical moment problem[END_REF] for an early reference and to the recent monograph [START_REF] Schmüdgen | The moment problem[END_REF] for a comprehensive treatment of the moment problem.

The generalized problem of moments asks to optimize a linear function over the set of finite, positive Borel measures that satisfy certain moment-type conditions. More precisely, we consider continuous functions f 0 and f i (i ∈ [m]) where [m] = {1, . . . , m}, that are defined on a compact set K ⊂ R n . The generalized problem of moments (GPM) may now be defined as follows.1

Generalized problem of moments (GPM)

val := inf µ ∈M(K) + ∫ K f 0 (x)dµ(x) : ∫ K f i (x)dµ(x) = b i ∀i ∈ [m] , (1)
where

• M(K) + denotes the convex cone of positive, finite, Borel measures (i.e., Radon measures) supported on the set K;2 • The scalars b i ∈ R (i ∈ [m]) are given.

In this survey we will mostly consider the case where all f i 's are polynomials, and will always assume K ⊆ R n to be compact. Moreover, for some of the results, we will also assume that K is a basic semi-algebraic set and we will sometimes further restrict to simple sets like a hypercube, simplex or sphere.

The generalized problem of moments has a rich history; see, e.g., [START_REF] Akhiezer | The classical moment problem[END_REF][START_REF] Landau | Moments in Mathematics[END_REF][START_REF] Schmüdgen | The moment problem[END_REF] and references therein and [START_REF] Lasserre | The moment-SOS hierarchy[END_REF] for a recent overview of many of its applications. In the recent years modern optimization approaches have been investigated in depth, in particular, by Lasserre (see [START_REF] Lasserre | A semidefinite programming approach to the generalized problem of moments[END_REF], the monograph [START_REF] Lasserre | Positive Polynomials and Their Applications[END_REF] and further references therein). Among others, there is a well-understood duality theory, and hierarchies of inner and outer approximations for the cone M(K) + have been introduced that lead to converging upper and lower bounds for the problem [START_REF] Akhiezer | The classical moment problem[END_REF]. In this survey we will present these hierarchies and show how the corresponding bounds can be computed using semidefinite programming. Since several overviews are already available on general properties of these hierarchies (e.g., in [START_REF] Lasserre | Positive Polynomials and Their Applications[END_REF][START_REF] Lasserre | Introduction to Polynomial and Semi-Algebraic Optimization[END_REF][START_REF] Laurent | Sums of squares, moment matrices and optimization over In Emerging Applications of Algebraic Geometry[END_REF][START_REF] Laurent | Optimization over polynomials: Selected topics[END_REF]), our main focus here will be on recent results that describe their rate of convergence. We will review in particular in more detail recent results on the upper bounds arising from the inner approximations, and highlight some recent links made with orthogonal polynomials and cubature rules for integration.

1 We only deal with the GPM in a restricted setting; more general versions of the problem are studied in, e.g., [START_REF] Shapiro | On duality theory of conic linear problems, Semi-Infinite Programming: Recent Advances[END_REF].

2 Formally, we consider the usual Borel σ-algebra, say B, on R n , i.e., the smallest (or coarsest) σ-algebra that contains the open sets in R n . A positive, finite Borel measure µ is a nonnegativevalued set function on B, that is countably additive for disjoint sets in B. The support of µ is the set, denoted Supp(µ), and defined as the smallest closed set S such that µ(R n \ S) = 0.

The dual problem of the GPM

The GPM is an infinite-dimensional conic linear program, and therefore it has an associated dual problem. Formally we introduce a duality (or pairing) between the following two vector spaces:

1. the space M(K) of all signed, finite, Borel measures supported on K, 2. the space C(K) of continuous functions on K, endowed with the supremum norm • ∞ .

The duality (pairing) in question is provided by the nondegenerate bilinear form •, • : C(K) × M(K) → R, defined by

f , µ = ∫ K f (x)dµ(x) ( f ∈ C(K), µ ∈ M(K)).
Thus the dual cone of M(K) + w.r.t. this duality is the cone of continuous functions that are nonnegative on K, and will be denoted by C(K) + = (M(K) + ) * .

In our setting of compact K ⊂ R n , M(K) is also the dual space of C(K), i.e., M(K) may be associated with the space of linear functionals defined on C(K). In particular, due to the Riesz-Markov-Kakutani representation theorem (e.g. [56, §1.10]), every linear functional on C(K) may be expressed as

f → f , µ for a suitable µ ∈ M(K).
As a result, we have the weak * topology on M(K) where the open sets are finite intersections of elementary sets of the form {µ ∈ M(K) | α < f , µ < β}, for given α, β ∈ R, and f ∈ C(K), and the unions of such finite intersections. A sequence {µ k } ⊂ M(K) converges in the weak * topology, say µ k ⇀ µ, if, and only if, lim

k→∞ f , µ k = f , µ ∀ f ∈ C(K). (2)
As a consequence of (2), the cone M(K) + is closed and the set of probability measures in M(K) is closed. By Alaoglu's theorem, e.g. [2, Theorem III(2.9)], the following set (i.e., the unit ball in M(K)) is compact in the weak * topology of M(K):

{µ ∈ M(K) | | f , µ | ≤ 1 ∀ f ∈ C(K) with f ∞ ≤ 1} . (3)
Hence the set of probability measures in M(K) is compact, since it is a closed subset of the compact set in [START_REF] Bayer | The proof of Tchakaloff's theorem[END_REF], and thus it provides a compact base in the weak * topology for the cone M(K) + . This implies again that M(K) + is closed in this topology (using Lemma 7.3 in [2, Part IV]) and we will also use this fact to analyze duality in the next section.

Dual linear optimization problem of (1)

Using this duality setting, the dual conic linear program of (1) reads

val * := sup y ∈R m        i ∈[m] b i y i : f 0 - i ∈I y i f i ∈ C(K) +        , = sup y ∈R m        i ∈[m] b i y i : f 0 (x) - i ∈I y i f i (x) ≥ 0 ∀x ∈ K        . (4)
By the duality theory of conic linear optimization, one has the following duality relations; see, e.g., [2, Section IV.7.2] or [START_REF] Lasserre | Positive Polynomials and Their Applications[END_REF]Appendix C].

Theorem 1 Consider the GPM [START_REF] Akhiezer | The classical moment problem[END_REF] and its dual [START_REF] Ben Tal | Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications[END_REF]. Assume (1) has a feasible solution. One has val ≥ val * (weak duality), with equality val = val * (strong duality) if the cone

{( f 0 , µ , f 1 , µ , . . . f m , µ ) : µ ∈ M(K) + } is a closed subset of R m+1 . If, in addition, val > -∞ then (1) has an optimal solution.
We mention another sufficient condition for strong duality, that is a consequence of Theorem 1 in our setting. 1) has a feasible solution, and there exist z 0 , z 1 , . . . , z m ∈ R for which the function m i=0 z i f i is strictly positive on K (i.e., m i=0 z i f i (x) > 0 for all x ∈ K). Then, val = val * holds and (1) has an optimal solution.

Corollary 1 Assume (

Hence, if in problem (1) we optimize over the probability measures (i.e., with f 1 ≡ 1, b 1 = 1) then the assumptions in Corollary 1 are satisfied.

We indicate how Corollary 1 can be derived from Theorem 1. Consider the linear map L : M(K) → R m+1 defined by L(µ) = ( f 0 , µ , . . . , f m , µ ), which is continuous w.r.t. the weak* topology on M(K). First we claim Ker L∩M(K) + = {0}. Indeed, assume L(µ) = 0 for some µ ∈ M(K) + . Setting f = m i=0 z i f i , L(µ) = 0 implies f , µ = 0 and thus µ = 0 since f is strictly positive on K. Since the cone M(K) + has a compact convex base in the weak * topology and the linear map L is continuous, we can conclude that the image L(M(K) + ) is closed (using Lemma 7.3 in [2, Part IV]). Now we can conclude using Theorem 1.

Atomic solution of the GPM

If the GPM has an optimal solution, then it has a finite atomic optimal solution, supported on at most m points (i.e., the weighted sum of at most m Dirac delta measures). This is a classical result in the theory of moments; see, e.g., [START_REF] Rogosinski | Moments of non-negative mass[END_REF] (univariate case), [START_REF] Kemperman | The general moment problem, a geometric approach[END_REF] (which shows an atomic measure with m + 1 atoms using induction on m) and a modern exposition in [START_REF] Shapiro | On duality theory of conic linear problems, Semi-Infinite Programming: Recent Advances[END_REF] (which shows an atomic measure with m atoms). The result may also be obtained as a consequence of the following, dimension-free version of the Carathéodory theorem.

Theorem 2 (see, e.g., Theorem 9.2 in Chapter III of [START_REF] Barvinok | A course in Convexity[END_REF]) Let S be a convex subset of a vector space such that, for every line L, the intersection S ∩ L is a closed bounded interval. Then every extreme point of the intersection of S with m hyperplanes can be expressed as a convex combination of at most m + 1 extreme points of S.

Atomic solution of the (GPM)

Theorem 3 If the GPM (1) has an optimal solution then it has one which is finite atomic with at most m atoms, i.e., of the form µ * = m ℓ=1 w ℓ δ x (ℓ) where w ℓ ≥ 0, x (ℓ) ∈ K, and δ x (ℓ) denotes the Dirac measure supported at

x (ℓ) (ℓ ∈ [m]).
This result can be derived from Theorem 2 in the following way. By assumption, the GPM has an optimal solution µ * . Moreover, since it has one at an extreme point we may assume that µ * is an extreme point of the feasibility region M(K) + ∩ ∩ m i=1 H i of the program [START_REF] Akhiezer | The classical moment problem[END_REF], where H i is the hyperplane f i , µ = b i . Then the following set S = {µ ∈ M(K) + : µ(K) = µ * (K)} meets the condition of Theorem 2, since the set of probability measures in M(K) + is compact in the weak * topology, and any line in a topological vector space is closed (e.g. [2, p. 111]). Moreover, the extreme points of S are precisely the scaled Dirac measures supported by points in K (see, e.g., Section III.8 in [START_REF] Barvinok | A course in Convexity[END_REF]). In addition, µ * is an extreme point of the set S ∩ ∩ m i=1 H i and thus, by Theorem 2, µ * is a conic combination of m + 1 Dirac measures supported at points x (ℓ) ∈ K for ℓ ∈ [m + 1]. Finally, as in [START_REF] Shapiro | On duality theory of conic linear problems, Semi-Infinite Programming: Recent Advances[END_REF], consider the LP min

m+1 ℓ=1 w ℓ f 0 (x (ℓ) ) s.t. w ℓ ≥ 0 (ℓ ∈ [m + 1]), m+1 ℓ=1 w ℓ f i (x (ℓ) ) = b i (i ∈ [m])
whose optimum value is val. Then an optimal solution attained at an extreme point provides an optimal solution of the GPM (1) which is atomic with at most m atoms.

GPM in terms of moments

From now on we will assume the functions f 0 , f 1 , . . . , f m in the definition of the GPM (1) are all polynomials and the set K is compact. Then the GPM may be reformulated in terms of the moments of the variable measure µ. To be precise, given a multi-index α = (α 1 , . . . , α n ) ∈ N n the moment of order α of a measure µ ∈ M(K) + is defined as

m µ α (K) := ∫ K x α dµ(x).
Here we set

x α = x α 1 1 • • • x α n n .
We may write the polynomials f 0 , f 1 , . . . , f m in terms of the standard monomial basis as:

f i (x) = α∈N n d f i,α x α ∀i = 0, . . . , m,
where the f i,α ∈ R are the coefficients in the monomial basis, and we assume the maximum total degree of the polynomials f 0 , f 1 , . . . , f m to be at most d.

Throughout we let N d d = {α ∈ N n : |α| ≤ d} denote the set of multi-indices, with |α| = n i=1 α i , and R[x] d denotes the set of multivariate polynomials with degree at most d.

GPM in terms of moments

We may now rewrite the GPM (1) in terms of moments:

inf µ ∈M(K) +        α∈N n d f 0,α m µ α (K) : α∈N n d f i,α m µ α (K) = b i ∀i ∈ [m]        .
Here d is the maximum degree of the polynomials f 0 , f 1 , . . . , f m .

Thus we may consider the set of all possible truncated moments sequences:

m µ α (K) α∈N n d : µ ∈ M(K) + ,
and describe the inner and outer approximations for M(K) + in terms of this set.

Inner and outer approximations

We will consider two types of approximations of the cone M(K) + , namely inner and outer conic approximations.

Inner approximations

The underlying idea, due to Lasserre [START_REF] Lasserre | A new look at nonnegativity on closed sets and polynomial optimization[END_REF], is to consider a subset of measures µ in

M(K) + of the form dµ = h • dµ 0 ,
where h is a polynomial sum-of-squares density function, and µ 0 ∈ M(K) + is a fixed reference measure with Supp(µ 0 ) = K.

To obtain a finite dimensional subset of measures, we will limit the total degree of h to some value 2r where r ∈ N is fixed. The cone of sum-of-squares polynomials of total degree at most 2r will be denoted by Σ r , hence

Σ r = k i=1 p 2 i : k ∈ N, p i ∈ R[x] r , i ∈ [k] .
In this way one obtains the cones

M r µ 0 := {µ ∈ M(K) + : dµ = h • dµ 0 , h ∈ Σ r } (r = 1, 2, . . .) (5)
which provide a hierarchy of inner approximations for the set M(K) + :

M r µ 0 ⊆ M r+1 µ 0 ⊆ M(K) + .

Outer approximations

The dual GPM (4) involves the nonnegativity constraint

f 0 (x) - m i=1 y i f i (x) ≥ 0 ∀x ∈ K,
which one may relax to a sufficient condition that guarantees the nonnegativity of the polynomial f 0 -m i=1 y i f i on K. Lasserre [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF] suggested to use the following sufficient condition in the case when K is a basic closed semi-algebraic set, i.e., when we have a description of K as the intersection of the level sets of polynomials

g j ( j ∈ [k]): K = x ∈ R n : g j (x) ≥ 0 ∀ j ∈ [k] .
Namely, consider the condition

f 0 - m i=1 y i f i = σ 0 + k j=1 σ j g j ,
where each σ j is a sum-of-squares polynomial and the degree of each term σ j g j (0 ≤ j ≤ k) is at most 2r, so that the degree of the right-hand-side polynomial is at most 2r. Here we set g 0 ≡ 1 for notational convenience. Thus we replace the cone C(K) + by a cone of the type:

Q r (g 1 , . . . , g k ) :=      f : f = σ 0 + k j=1 σ j g j , σ j ∈ Σ r j , j = 0, 1, . . . , k      , (6)
where we set r j := r -deg(g j )/2 for all j ∈ {0, . . . , m}.

The cone Q r (g 1 , . . . , g k ) is known as the truncated quadratic module generated by the polynomials g 1 , . . . , g k . By definition, its dual cone consists of the signed measures µ supported on K such that ∫ K f dµ ≥ 0 for all f ∈ Q r (g 1 , . . . , g k ):

(Q r (g 1 , . . . , g k )) * = µ ∈ M(K) : ∫ K f (x)dµ(x) ≥ 0 ∀ f ∈ Q r (g 1 , .
. . , g k ) .

(7) This provides a hierarchy of outer approximations for the cone M(K) + :

M(K) + ⊆ (Q r+1 (g 1 , . . . , g k )) * ⊆ (Q r (g 1 , . . . , g k )) * .
We will also briefly consider the tighter outer approximations for the cone M(K) + obtained by replacing the truncated quadratic module Q r (g 1 , . . . , g k ) by the larger cone Q r j ∈J g j : J ⊆ [k] , thus the truncated quadratic module generated by all pairwise products of the g j 's (also known as the pre-ordering generated by the g j 's). Then we have

M(K) + ⊆ Q r j ∈J g j : J ⊆ [k] * ⊆ (Q r (g 1 , . . . , g k )) * .

Examples of GPM

The GPM (1) has many applications. Below we will list some examples that are directly relevant to this survey; additional examples in control theory, options pricing in finance, and others, can be found in [START_REF] Lasserre | A semidefinite programming approach to the generalized problem of moments[END_REF][START_REF] Lasserre | Positive Polynomials and Their Applications[END_REF][START_REF] Lasserre | The moment-SOS hierarchy[END_REF].

Global minimization of polynomials on compact sets

Consider the global optimization problem:

val = min x ∈K p(x) (8)
where p is a polynomial and K a compact set. This corresponds to the GPM (1) with m = 1, f 0 = p, f 1 = 1 and b 1 = 1, i.e.:

val = min µ ∈M(K) + ∫ K p(x)dµ(x) : ∫ K dµ(x) = 1 .
In the following sections we will focus on deriving error bounds for this problem when using the inner and outer approximations of M(K) + .

Global minimization of rational functions on compact sets

We may generalize the previous example to rational objective functions. In particular, we now consider the global optimization problem:

val = min x ∈K p(x) q(x) , (9)
where p, q are polynomials such that q(x) > 0 ∀ x ∈ K, and K ⊆ R n is compact. This problem has applications in many areas, including signal recovery [START_REF] Castella | Rational optimization for nonlinear reconstruction with approximate ℓ 0 penalization[END_REF] and finding minimal energy configurations of point charges in a field with polynomial potential [START_REF] Schwartz | The 5 electron case of Thomson's problem[END_REF].

It is simple to see that we may reformulate this problem as the GPM with m = 1 and f 0 = p, f 1 = q, and b 1 = 1, i.e.:

val = min µ ∈M(K) + ∫ K p(x)dµ(x) : ∫ K q(x)dµ(x) = 1 .
Indeed, one may readily verify that if x * is a global minimizer of the rational function p(x)/q(x) over K then an optimal solution of the GPM is given by µ * = 1 q(x * ) δ x * .

Polynomial cubature rules

Positive cubature (also known as multivariate quadrature) rules for numerical integration of a function f with respect to a measure µ 0 over a set K take the form

∫ K f (x)dµ 0 (x) ≈ N ℓ=1 w ℓ f (x (ℓ) ),
where the points x (ℓ) ∈ K and the weights w ℓ ≥ 0 (ℓ ∈ [N]) are fixed. The points (also known as the nodes of the cubature rule) and weights are typically chosen so that the approximation is exact for polynomials up to a certain degree, say d.

The problem of finding the points x (ℓ) ∈ K and weights w ℓ (ℓ ∈ [N]) giving a cubature rule exact at degree d may then be written as the following GPM:

val := inf µ ∈M(K) + ∫ K 1dµ(x) : ∫ K x α dµ(x) = ∫ K x α dµ 0 (x) ∀α ∈ N n d .
The key observation is that, by Theorem 3, this problem has an atomic solution supported on at most

N = |N n d | = n+d d points in K, say µ * = N ℓ=1 w ℓ δ x (ℓ)
, and this yields the cubature weights and points. This result is known as Tchakaloff's theorem [START_REF] Tchakaloff | Formules de cubature ḿecanique coefficients non négatifs[END_REF]; see also [START_REF] Bayer | The proof of Tchakaloff's theorem[END_REF][START_REF] Trefethen | Approximation, and Isotropy in the Hypercube[END_REF]. (In fact, our running assumption that K is compact may be relaxed somewhat in Tchakaloff's theorem -see, e.g. [START_REF] Putinar | A note on Tchakaloff's theorem[END_REF].)

Here we have chosen the constant polynomial 1 as objective function so that the optimal value is val = µ 0 (K). Other choices of objective functions are possible as discussed, e.g., in [START_REF] Ryu | Extensions of Gauss Quadrature Via Linear Programming[END_REF]. The GPM formulation of the cubature problem was used for the numerical calculation of cubature schemes for various sets K in [START_REF] Ryu | Extensions of Gauss Quadrature Via Linear Programming[END_REF].

Semidefinite programming reformulations of the approximations

The inner and outer approximations of the cone M(K) + discussed in Section 1.4 lead to upper and lower bounds for the GPM (1), which may be reformulated as finite-dimensional, convex optimization problems, namely semidefinite programming (SDP) problems. These are conic linear programs over the cone of positive semidefinite matrices, formally defined as follows.

Semidefinite programming (SDP) problem

Assume we are given symmetric matrices A 0 , . . . , A m (all of the same size) and

scalars b i ∈ R (i ∈ [m]
). The semidefinite programming problem in standard primal form is then defined as

p * := inf X 0 { A 0 , X : A i , X = b i ∀i ∈ [m]} ,
where •, • now denotes the trace inner product, i.e., the Euclidean inner product in the space of symmetric matrices, and X 0 means that X is a symmetric positive semidefinite matrix (corresponding to the Löwner partial ordering of the symmetric matrices).

The dual semidefinite program reads

d * := sup y ∈R m m i=1 b i y i : A 0 - m i=1 y i A i 0 .
Weak duality holds: p * ≥ d * . Moreover, strong duality: p * = d * holds, e.g., if the primal problem is bounded and admits a positive definite feasible solution X (or if the dual is bounded and has a feasible solution y for which A 0i y i A i is positive definite) (see, e.g., [START_REF] Barvinok | A course in Convexity[END_REF][START_REF] Ben Tal | Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications[END_REF]).

Next we recall how one can test whether a polynomial can be written as a sum of squares of polynomials using semidefinite programming. This well known fact plays a key role for reformulating the inner and outer approximations of M(K) + using semidefinite programs.

Checking sums of squares with SDP

Given an integer r ∈ N let [x] r = {x α : α ∈ N n r } consist of all monomials with degree at most r, thus the monomial basis of R[x] r .

Proposition 1 For a given n-variate polynomial h, one has h ∈ Σ r , if and only if the following polynomial identity holds:

h(x) = [x] ⊤ r M[x] r = α,β ∈N n r M α,β x α+β ,
for some positive semidefinite matrix:

M = M α,β α,β ∈N n r 0.
The above identity can be equivalently written as

h γ = α,β ∈N n r : α+β=γ M α,β ∀γ ∈ N n 2r . (10)

SDP upper bounds for GPM via the inner approximations

Recall that the inner approximations of the cone M(K) + restrict the measures on K to the subsets M r µ 0 in (5), i.e. to those measures µ of the form dµ = h • dµ 0 , where µ 0 is a fixed reference measure with Supp(µ 0 ) = K and h ∈ Σ r is a sum-of-squares polynomial density.

Replacing the cone M(K) + in the GPM (1) by its subcone M r µ 0 we obtain the parameter val (r) inner := inf

µ ∈M r µ 0 ∫ K f 0 (x)dµ(x) : ∫ K f i (x)dµ(x) = b i ∀i ∈ [m] , (11)
which provides a hierarchy of upper bounds for GPM:

val ≤ val (r+1) inner ≤ val (r)
inner . According to the above discussion these parameters can be reformulated as semidefinite programs involving the moments of the reference measure µ 0 . Indeed, we may write the variable density function as

h(x) = [x] T r M[x]
r with M 0 and arrive at the following semidefinite program (in standard primal form).

SDP formulation for the inner approximations based upper bounds

val (r) inner = inf M A 0 , M : A i , M = b i ∀i ∈ [m], M = (M α,β ) α,β ∈N n r 0 , (12)
where we set

A i = ∫ K f i (x)[x] r [x] T r dµ 0 (x) = ∫ K f i (x)x α+β dµ 0 (x) α,β ∈N n r (0 ≤ i ≤ m).
Moreover, writing each polynomial f i in the monomial basis as f i = γ f i,γ x γ one sees that the entries of the matrix A i depend linearly on the moments of the reference measure µ 0 , since

∫ K f i (x)x α+β dµ 0 (x) = γ f i,γ m µ 0 α+β+γ (K).
To be able to compute the above SDP one needs the moments of the reference measure µ 0 to be known on the set K. This is a restrictive assumption, since even computing volumes of polytopes is an NP-hard problem. One is therefore restricted to specific choices of µ 0 and K where the moments are known in closed form (or can be derived). In Table 1 we therefore give an overview of some known moments for the Euclidean ball and sphere, the hypercube, and the standard simplex. (See [START_REF] Folland | How to integrate a polynomial over a sphere?[END_REF] for an easy derivation of the moments on the ball and the sphere.) There we use the Gamma function:

Γ(k) = (k -1)!, Γ k + 1 2 = k - 1 2 k -1 - 1 2 • • • 1 2 √ π for k ∈ N. K m µ0 α (K) [0, 1] n n i=1 1 αi +1 ∆ n n i=1 αi ! ( n i=1 αi +n)! S n 2Γ(β1)•••Γ(βn ) Γ(β1+. . .+βn) if α ∈ (2N) n with β i = αi +1 2 for i ∈ [n] 0 otherwise B n 1 α1+. . .+αn+n 2Γ(β1)•••Γ(βn) Γ(β1+. . .+βn ) if α ∈ (2N) n with β i = αi +1 2 for i ∈ [n] 0 otherwise
Table 1 Examples of known moments for some choices of K ⊆ R n : ∆ n = {x ∈ R n + : n i=1 x i = 1} is the standard simplex and B n = {x ∈ R n : x ≤ 1} is the unit Euclidean ball, in which case µ 0 is the Lebesgue measure, and S n = {x ∈ R n : x = 1} is the unit Euclidean sphere in which case µ 0 is the (Haar) surface measure on S n .

If K is an ellipsoid, one may obtain the moments of the Lebesgue measure on K from the moments on the ball by an affine transformation of variables. Also, if K is a polytope, one may obtain the moments of the Lebesgue measure through triangulation of K, and subsequently using the formula for the simplex.

SDP lower bounds for GPM via the outer approximations

Here we assume that K is basic closed semi-algebraic, of the form

K = {x ∈ R n : g j (x) ≥ 0 ∀ j ∈ [k]}, where g 1 , . . . , g k ∈ R[x].
Recall that the dual cone of the truncated quadratic module generated by the polynomials g j describing the set K provides an outer approximation of M(K) + ; we repeat its definition [START_REF] Cools | An encyclopaedia of cubature formulas[END_REF] for convenience:

(Q r (g 1 , . . . , g k )) * = µ ∈ M(K) : ∫ K f dµ ≥ 0 ∀ f ∈ Q r (g 1 , . . . , g k ) ,
where the quadratic module Q r (g 1 , . . . , g k ) was defined in [START_REF] Castella | Rational optimization for nonlinear reconstruction with approximate ℓ 0 penalization[END_REF].

Replacing the cone M(K) + in the GPM (1) by the above outer approximations we obtain the following parameters val (r) out er := inf

µ ∈(Q r (g 1 ,...,g k )) * ∫ K f 0 (x)dµ(x) : ∫ K f i (x)dµ(x) = b i ∀i ∈ [m] , (13)
which provide a hierarchy of lower bounds for the GPM:

val (r) out er ≤ val (r+1) out er ≤ val.
Here too these parameters can be reformulated as semidefinite programs. Indeed a signed measure µ lies in the cone (Q r (g 1 , . . . , g k )) * precisely when it satisfies the condition

∫ K g j (x)σ j (x)dµ(x) ≥ 0 ∀ σ j ∈ Σ r j , ∀ j ∈ {0, . . . , k}, (14)
where r j = r -⌈deg(g j )/2⌉. Using Proposition 1, we may represent each sum-ofsquares σ j as j) [x] r j for some matrix M (j) 0 (indexed by N n r j ). Hence we have

σ j (x) = [x] ⊤ r j M (
∫ K g j (x)σ j (x)dµ(x) = ∫ K g j (x)[x] T r j M (j) [x] r j dµ(x) = B µ j , M (j) ,
after setting

B µ j = ∫ K g j (x)[x] r j [x] T r j dµ(x) = ∫ K g j (x)x α+β dµ(x) α,β ∈N n r j
.

Hence the condition ( 14) can be rewritten as requiring, for each j ∈ {0, 1, . . . , k}, B µ j , M (j) ≥ 0 for all postive semidefinite matrices M (j) indexed by N n r j , which in turn is equivalent to B µ j 0 (since the cone of positive semidefinite matrices is self-dual). Summarizing, the condition (14) on the variable measure µ can be rewritten as

B µ j = ∫ K g j (x)x α+β dµ(x) α,β ∈N n r j 0 ∀ j ∈ {0, 1, . . . , k}.
Finally, observe that only the moments of µ are playing a role in the above constraints. Therefore we may introduce new variables for these moments, say

y α = ∫ K x α dµ(x) ∀α ∈ N n 2r .
Writing the polynomials g j in the monomial basis as g j (x) = γ g j,γ x γ we arrive at the following SDP reformulation for the parameter val (r) out er .

SDP formulation for the outer approximations based lower bounds

With r j = r -⌈deg(g j )/2⌉ for j ∈ {0, 1, . . . , k} and d an upper bound on the degrees of f i for i ∈ {0, 1, . . . , m} we have

val (r) out er = inf (y α ) α∈N n 2r α∈N n d f 0,α y α : α∈N n d f i,α y α = b i ∀i ∈ [m], (15)
∫ K γ g j,γ y α+β+γ α,β ∈N n r j 0 ∀ j ∈ {0, 1, . . . , k} . (16)
If, in the definition (13) of val (r) out er , instead of the truncated quadratic module Q r (g 1 , . . . , g k ) we use the larger quadratic module Q r ( j ∈J g j : J ⊆ [k]) generated by the pairwise products of the g j 's, then we obtain a stronger bound on val, which we denote by val

out er = inf µ ∈(Q r ( j ∈J g j :J ⊆[k])) * ∫ K f 0 (x)dµ(x) : ∫ K f i (x)dµ(x) = b i (i ∈ [m]) (17
) and clearly we have val (r) out er ≤ val (r)

out er ≤ val.

The parameter val (r)

out er can also be reformulated as a semidefinite program, analogous to the program ( 15)-( 16), which however now involves 2 k + 1 semidefinite constraints instead of k + 1 such constraints in [START_REF] De Klerk | On the equivalence of algebraic approaches to the miniization of forms on the simplex[END_REF] and thus its practical implementation is feasible only for small values of k. On the other hand, as we will see later in Section 5.2, the bounds val (r) out er admit a much sharper error analysis than the bounds val (r) out er for the case of polynomial optimization.

Convergence results for the inner approximation hierarchy

In the rest of the paper we are interested in the convergence of the respective lower and upper SDP bounds on the optimal value of the GPM, as introduced in the previous section. We will first consider in this section the upper bounds for the GPM arising from the inner approximations, since much more is known about their rate of convergence than for the lower bounds arising from the outer approximations. We deal first with the special case of polynomial optimization and then indicate how some of the results extend to the general GPM.

The special case of global polynomial optimization

Here we consider a special case of the GPM, namely global optimization of polynomials on compact sets (i.e., problem ( 8)) and review the main known results about the error analysis of the upper bounds val (r) inner . After that in the next section we will explain how to extend this error analysis to the bounds for the general GPM problem.

Thus we now consider the problem

val = min x ∈K p(x), (18)
asking to find the minimum value of the polynomial p(x) = α∈N n d p α x α over a compact set K.

Recall the definition of the inner approximation based upper bound [START_REF] De Klerk | The complexity of optimizing over a simplex, hypercube or sphere: a short survey[END_REF], which can be rewritten here as

val (r) inner = min h ∈Σ r ∫ K p(x)h(x)dµ 0 (x) : ∫ K h(x)dµ 0 (x) = 1 ,
and its SDP reformulation from [START_REF] De Klerk | Bound-constrained polynomial optimization using only elementary calculations[END_REF], which now reads

val (r) inner = min A 0 , M : A 1 , M = 1, M = (M α,β ) α,β ∈N n r 0 , (19)
with

A 0 = ∫ K p(x)x α+β dµ 0 (x) α,β ∈N n r , A 1 = ∫ K x α+β dµ 0 (x) α,β ∈N n r ,
where as before µ 0 is a fixed reference measure on K.

A first observation made in [START_REF] Lasserre | A new look at nonnegativity on closed sets and polynomial optimization[END_REF] is that this semidefinite program [START_REF] De Klerk | An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution[END_REF] can in fact be reformulated as a generalized eigenvalue problem. Indeed, its dual semidefinite program reads max{λ : A 0 -λA 1 0}, whose optimal value gives again the parameter val (r) inner (since strong duality holds). Hence val (r) inner is equal to the smallest generalized eigenvalue of the system

A 0 v = λA 1 v, v 0. ( 20
)
Thus one may compute val (r) inner without having to solve an SDP problem. In fact, if instead of the monomial basis {x α : α ∈ R n 2r } we use a polynomial basis {b α (x)

: α ∈ N n 2r } of R[x]
2r that is orthonormal with respect to the reference measure µ 0 (i.e., such that ∫ K b α b β dµ 0 = 1 if α = β and 0 otherwise), then in the above semidefinite program [START_REF] De Klerk | An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution[END_REF] we may set A 1 = I to be the identity matrix and

A 0 = ∫ K p(x)b α (x)b β (x)dµ 0 (x) α,β ∈N n 2r , (21)
whose entries now involve the 'generalized' moments ∫ K b α (x)dµ 0 (x) of µ 0 . Then the parameter val (r) inner can be computed as the smallest eigenvalue of the matrix A 0 :

val (r) inner = λ min (A 0 ) where A 0 is as in (21). ( 22
)
This fact was observed in [START_REF] De Klerk | Worst-case examples for Lasserre's measure-based hierarchy for polynomial optimization on the hypercube[END_REF] and used there to establish a link with the roots of the orthonormal polynomials, permitting to analyze the quality of the bounds val (r) inner for the case of the hypercube K = [-1, 1] n , see below for details.

In Table 2 we list the known convergence rates of the parameters val (r) inner to the optimal value val of problem [START_REF] De Klerk | Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization[END_REF], i.e., we review the known upper bounds for the sequence {val (r) inner -val}, r = 1, 2, . . .

K ⊆ R n val (r ) i n n er -val measure µ 0 reference compact o(1)
positive finite Borel measure [START_REF] Lasserre | A new look at nonnegativity on closed sets and polynomial optimization[END_REF] compact, satisfies interior cone condition

O 1 √ r
Lebesgue measure [START_REF] De Klerk | Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization[END_REF] convex body O 1 r Lebesgue measure [START_REF] De Klerk | Comparison of Lasserre's measure-based bounds for polynomial optimization to bounds obtained by simulated annealing[END_REF] hypercube

[-1, 1] n Θ 1 r 2 n i=1 (1 -x 2 i ) -1/2 dx i [15]
unit sphere, p homogeneous O 1 r surface measure [START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF] Table 2 Known rates of convergence for the Lasserre hierarchy of upper bounds on val in [START_REF] De Klerk | Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization[END_REF] based on inner approximations.

We will give some details on the proofs of each of the four results listed in Table 2. After that we will mention an interesting connection with approximations based on cubature rules.

Asymptotic convergence

The first result in Table 2 states that lim r→∞ val (r) inner = val if K is compact and µ 0 ∈ M(K) + . It is a direct consequence of the following result.

Theorem 4 (Lasserre [START_REF] Lasserre | A new look at nonnegativity on closed sets and polynomial optimization[END_REF]) Let K ⊆ R n be compact, let µ 0 be a fixed, finite, positive Borel measure with Supp(µ 0 ) = K. and let f be a continuous function on R n . Then, f is nonnegative on K if and only if

∫ K g 2 f dµ 0 ≥ 0 ∀g ∈ R[x].
The asymptotic convergence of the bounds val (r) inner to val holds more generally for the minimization of a rational function p(x)/q(x) over K (assuming q(x) > 0 for all x ∈ K). Indeed, using the above theorem, we obtain min

x ∈K p(x) q(x) = sup t ∈R t s.t. p(x) ≥ tq(x) ∀x ∈ K = sup t ∈R t s.t. ∫ K p(x)h(x)dµ 0 (x) ≥ t ∫ K q(x)h(x)dµ 0 (x) ∀h ∈ Σ = inf h ∈Σ ∫ K p(x)h(x)dµ 0 (x) s.t. ∫ K q(x)h(x)dµ 0 (x) = 1.
Error analysis when K is compact and satisfies an interior cone condition

The second result in Table 2 fixes the reference measure µ 0 to the Lebesgue measure, and restricts the set K to satisfy a so-called interior cone condition.

Definition 1 (Interior cone condition)

A set K ⊆ R n satisfies an interior cone condition if there exist an angle θ ∈ (0, π/2) and a radius ρ > 0 such that, for every x ∈ K, a unit vector ξ(x) exists such that

{x + λy : y ∈ R n , y = 1, y T ξ(x) ≥ cos θ, λ ∈ [0, ρ]} ⊆ K.
For example, all full-dimensional convex sets satisfy the interior cone condition for suitable parameters θ and ρ. This assumption is used in [START_REF] De Klerk | Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization[END_REF] to claim that the intersection of any ball with the set K contains a positive fraction of the full ball, a fact used in the error analysis.

The main ingredient of the proof is to approximate the Dirac delta supported on a global minimizer by a Gaussian density of the form

G(x) = 1 (2πσ 2 ) n/2 exp -x -x * 2 2σ 2 , ( 23
)
where x * is a minimizer of p on K, and σ 2 = Θ(1/r). Then we approximate the Gaussian density G(x) by a sum-of-squares polynomial g r (x) with degree 2r. For this we use the fact that the Taylor approximation of the exponential function e -t is a sum of squares (since it is a univariate polynomial nonnegative on R).

Lemma 1 For any r ∈ N the univariate polynomial 2r k=0 (-1) k k! t k (in the variable t ∈ R), defined as the Taylor expansion of the function t ∈ R → e -t truncated at degree 2r, is a sum of squares of polynomials.

Based on this the polynomial

g r (x) = 1 (2πσ 2 ) n/2 2r k=0 (-1) k k! -x -x * 2 2σ 2 k
is indeed a sum of squares with degree 2r, which can be used (after scaling) as feasible solution within the definition of the bound val (r) inner . We refer to [START_REF] De Klerk | Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization[END_REF] for the details of the analysis.

Error analysis when K is a convex body

The third item in Table 2 assumes that K is now convex, compact and fulldimensional, i.e., a convex body. The key idea is to use the following concentration result for the Boltzman density (or Gibbs measure).3 The theorem still holds if p is convex, but not necessarily linear [START_REF] De Klerk | Comparison of Lasserre's measure-based bounds for polynomial optimization to bounds obtained by simulated annealing[END_REF]. The proof of the third item in Table 2 now proceeds as follows:

1. Construct a sum-of-squares polynomial approximation h r (x) of the Boltzman density H(x) by again using the fact that the even degree truncated Taylor expansion of e -t is a sum of squares (Lemma 1); namely, consider the polynomial

h r (x) = 2r k=0 (-1) k k! -p(x) T k (up to scaling).
2. Use this construction to bound the difference between val (r) inner and the Boltzman bound when choosing T = O(1/r).

3. Use the extension of the Kalai-Vempala result to get the required result for convex polynomials p. 4. When p is nonconvex, the key ingredient is to reduce to the convex case by constructing a convex (quadratic) polynomial p that upper bounds p on K and has the same minimizer on K, as indicated in the next lemma. with C p = max x ∈K ∇ 2 p(x) 2 , is quadratic, convex, and separable. Moreover, it satisfies: p(x) ≤ p(x) for all x ∈ K, and x * is a global minimizer of p over K.

Then, in view of the inequality

∫ K phdµ 0 ≥ ∫ K phdµ 0 ∀h ∈ Σ r , (24)
it follows that the error analysis in the non-convex case follows directly from the error analysis in the convex case. The details of the proof are given in [START_REF] De Klerk | Comparison of Lasserre's measure-based bounds for polynomial optimization to bounds obtained by simulated annealing[END_REF].

Error analysis for the hypercube

K = [-1, 1] n
The fourth result in Table 2 deals with the hypercube K = [-1, 1] n . A first key idea of the proof is that it suffices to show the O(1/r 2 ) convergence rate for a univariate quadratic polynomial. This follows from Lemma 2 above (and ( 24)), which implies that it suffices to analyze the case of a quadratic, separable polynomial. Hence we may further restrict to the case when K = [-1, 1] and p is a quadratic univariate polynomial.

In the univariate case, the key idea is to use the eigenvalue reformulation of the bound val (r) inner from [START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF]. There, we use the polynomial basis {b k : k ∈ N} consisting of the Chebyshev polynomials (of the first kind) which are orthonormal with respect to the Chebyshev measure dµ 0 on K = [-1, 1], indeed the measure used in Table 2.

Then one may use a connection to the extremal roots of these orthonormal polynomials. Namely, for the linear polynomial p(x) = x, the parameter val (r) inner coincides with the smallest root of the orthonormal polynomial b r+1 (with degree r + 1); this is a well known property of orthogonal polynomials, which follows from the fact that the matrix A 0 in ( 21) is tri-diagonal and the 3-terms recurrence for the Chebyshev polynomials (see, e.g., [23, §1.3]). When p is a quadratic polynomial, the matrix A 0 in the eigenvalue problem ( 22) is now 5-diagonal and 'almost' Toepliz, properties that can be exploited to evaluate its smallest eigenvalue. See [START_REF] De Klerk | Worst-case examples for Lasserre's measure-based hierarchy for polynomial optimization on the hypercube[END_REF] for details.

Error analysis for the unit sphere

The last result in Table 2 deals with the minimization of a homogeneous polynomial p over the unit sphere S n = {x ∈ R n : n i=1 x 2 i = 1}, in which case Doherty and Wehner [START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF] show a convergence rate in O(1/r). Their construction for a suitable sum-of-squares polynomial density in Σ r is in fact closely related to their analysis of the outer approximation based lower bounds val (r) out er . Doherty and Wehner [START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF] indeed show the following stronger result: val (r) innerval (r) out er = O(1/r), to which we will come back in Section 5.2 below.

Link with positive cubature rules

There is an interesting link between positive cubature formulas and the upper bound

val (r) inner = min h ∈Σ r ∫ K phdµ 0 : ∫ K hdµ 0 = 1 ,
which was recently pointed out in [START_REF] Martinez | Quadrature-based polynomial optimization[END_REF] and is summarized in the next result.

Theorem 6 (Martinez et al. [40]

) Let x (1) , . . . , x (N) ∈ K and weights w 1 > 0, . . . , w N > 0 give a positive cubature rule on K for the measure µ 0 , that is exact for polynomials of total degree at most d + 2r, where d > 0 and r > 0 are given integers. Let p be a polynomial of degree d.

Then, if h is a polynomial nonnegative on K and of degree at most 2r, one has

∫ K phdµ 0 ≥ min ℓ ∈[N]
p(x (ℓ) ).

In particular, the inner approximation bounds therefore satisfy

val (r) inner ≥ min ℓ ∈[N] p(x (ℓ) ).
The proof is an immediate consequence of the definitions, but this result has several interesting implications.

• First of all, one may derive information about the rate of convergence for the scheme min ℓ ∈[N] p(x (ℓ) ) from the error bounds in Table 2. For example, if K is a convex body, the implication is that min ℓ ∈[N] p(x (ℓ) )val = O(1/r). • Also, if a positive cubature rule is known for the pair (K, µ 0 ), and the number of points N meets the Tchakaloff bound N = n+2r+d 2r+d , then there is no point in computing the parameter val (r) inner . Indeed, as

val (r) inner ≥ min ℓ ∈[N]
p(x (ℓ) ) ≥ val, the right-hand-side bound is stronger and can be computed more efficiently.

Having said that, positive cubature rules that meet the Tchakaloff bound are only known in special cases, typically in low dimension and degree; see e.g. [START_REF] Cools | An encyclopaedia of cubature formulas[END_REF][START_REF] Trefethen | Approximation, and Isotropy in the Hypercube[END_REF][START_REF] Dai | Approximation Theory and Harmonic Analysis on Spheres and Balls[END_REF], and the references therein.

• Theorem 6 also shows why the last convergence rate in Table 2 is tight for K = [-1, 1] n . Indeed if we consider the univariate example p(x) = x and the Chebyshev probability measure dµ 0 (x)

= 1 π √ 1-x 2 dx on K = [-1, 1]
, then a positive cubature scheme is given by

x (ℓ) = cos 2ℓ -1 2N π , w ℓ = 1 N ∀ℓ ∈ [N],
and it is exact at degree 2N -1. This is known as the Chebyshev-Gauss quadrature, and the points are precisely the roots of the degree N Chebyshev polynomial of the first kind. Thus, with N = r + 1, in this case we have

val (r) inner ≥ min ℓ ∈[N] p(x (ℓ) ) = min ℓ ∈[N] cos (2ℓ -1)π 2N = cos (-π/(2N)) = -1+Ω 1
N 2 .
This explains that the Θ(1/r 2 ) result in Table 2 holds for p(x) = x. A different proof of this result is given in [START_REF] De Klerk | Worst-case examples for Lasserre's measure-based hierarchy for polynomial optimization on the hypercube[END_REF], where it is shown that for this example one actually has equality val (r) inner = cos (-π/(2N)). • Finally, Theorem 6 shows that there is not much gain in using a larger set of densities than Σ r in the definition of the inner approximations M r µ 0 since the statement of the theorem holds for any nonnegative polynomial h on K. For example, for the hypercube K = [-1, 1] n , if we use the larger set of densities

h ∈ Q r ( j ∈J (1 -x 2 j ) : J ⊆ [k]
) and the Chebyshev measure as reference measure µ 0 on [-1, 1] n , then we obtain upper bounds with convergence rate in O(1/r 2 ) [START_REF] De Klerk | Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization[END_REF]. This also follows from the later results in [START_REF] De Klerk | Worst-case examples for Lasserre's measure-based hierarchy for polynomial optimization on the hypercube[END_REF] where in addition it is shown that this convergence result is tight for linear polynomials. By the above discussion tightness also follows from Theorem 6.

Upper bounds using grid point sets

Of course one may also obtain upper bounds on val, the minimum value taken by a polynomial p over a compact set K, by evaluating p at any suitably selected set of points in K. This corresponds to restricting the optimization over selected finite atomic measures in the definition of val.

A first basic idea is to select the grid point sets consisting of all rational points in K with denominator r for increasing values of r ∈ N. For the standard simplex K = ∆ n and the hypercube K = [0, 1] n this leads to upper bounds that satisfy:

min x ∈K,r x ∈N n p(x) -min x ∈K p(x) ≤ C d r max x ∈K p(x) -min x ∈K p(x) for all r ≥ d, (25)
where C d is a constant that depends only on the degree d of p; see [START_REF] De Klerk | A PTAS for the minimization of polynomials of fixed degree over the simplex[END_REF] for K = ∆ n and [START_REF] De Klerk | Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube[END_REF] for K = [0, 1] n . A faster regime in O(1/r 2 ) can be shown when allowing a constant that depends on the polynomial p (see [START_REF] De Klerk | On the convergence rate of grid search for polynomial optimization over the simplex[END_REF] for ∆ n and [START_REF] De Klerk | Bound-constrained polynomial optimization using only elementary calculations[END_REF] for [0, 1] n ). Note that the number of rational points with denominator r in the simplex ∆ n is n+r-1 r

= O(n r ) and thus the computation time for these upper bounds is polynomial in the dimension n for any fixed order r. On the other hand, there are (r +1) n = O(r n ) such grid points in the hypercube [0, 1] n and thus the computation time of the upper bounds grows exponentially with the dimension n.

For a general convex body K some constructions are proposed recently in [START_REF] Piazzon | Markov inequalities, Dubiner distance, norming meshes and polynomial optimization on convex bodies[END_REF] for suitable grid point sets (so-called meshed norming sets) X d (ǫ) ⊆ K where d ∈ N and ǫ > 0. Namely, whenever p has degree at most d, by minimizing p over X d (ǫ) one obtains an upper bound on the minimum of p over K satisfying min

x ∈X d (ǫ ) p(x) -min x ∈K p(x) ≤ ǫ max x ∈K p(x) -min x ∈K p(x) ,
where the computation involves

|X d (ǫ)| = O d √ ǫ 2n
point evaluations, thus exponential in the dimension n for fixed precison ǫ.

In comparison, the computation of the upper bound val (r) out er relies on a semidefinite program involving a matrix of size n+r r = O(n r ), which is polynomial in the dimension n for any fixed order r.

The general problem of moments (GPM)

One may extend the results of the last section to the inner approximations for the general GPM [START_REF] Akhiezer | The classical moment problem[END_REF]. In other words, we now consider the upper bounds (11) obtained using the inner approximations of the cone M(K) + , which we repeat for convenience:

val (r) inner = inf h ∈Σ r ∫ K f 0 (x)h(x)dµ 0 (x) : ∫ K f i (x)h(x)dµ 0 (x) = b i ∀i ∈ [m] .
A first observation is that this program may not have a feasible solution, even if the GPM (1) does. For example, two constraints like

∫ 1 0 xdµ(x) = 0, ∫ 1 0 dµ(x) = 1
admit the Dirac measure µ = δ {0} as solution but they do not admit any solution of the form dµ = hdx with h ∈ Σ r for any r ∈ N. Thus any convergence result must relax the equality constraints of the GPM (1) in some way, or involve additional assumptions.

We now indicate how one may use the convergence results of the last section to derive an error analysis for the inner approximations of the GPM when relaxing the equality constraints.

Theorem 7 (De Klerk-Postek-Kuhn [START_REF] De Klerk | Distributionally robust optimization with polynomial densities: theory, models and algorithms[END_REF]) Assume that f 0 , . . . , f m are polynomials, K is compact and the GPM (1) has an optimal solution. Let b 0 := val denote the optimum value of ( 1) and for any integer r ∈ N define the parameter

∆ (r) := min h ∈Σ r max i ∈{0,1,...,m} ∫ K f i (x)h(x)dµ 0 (x) -b i .
Then the following assertions hold:

(1) lim r→∞ ∆ (r) = 0.

(2) ∆ (r) = O 1 r 1/4 if K satisfies an interior cone assumption and µ 0 is the Lebesgue measure;

(3)

∆ (r) = O 1 r 1/2 if K is a convex body and µ 0 is the Lebesgue measure; (4) ∆ (r) = O 1 r if K = [-1, 1] n and dµ 0 (x) = i (1 -x 2 i ) -1/2 dx i .
We will derive this from the convergence results for global polynomial optimization in Table 2. By assumption, problem (1) has an optimal solution and by Theorem 3 we may assume it has an atomic optimal solution µ * = ℓ λ ℓ δ x * ℓ with λ ℓ > 0 and x * ℓ ∈ K. We now sketch the proof. 1. For each atom x * ℓ of the optimal measure µ * consider the polynomial

p ℓ (x) = m i=0 f i (x) -f i (x * ℓ ) 2 ,
whose minimum value over K is equal to 0 (attained at x * ℓ ). 2. We apply the error analysis of the previous section to the problem of minimizing the polynomial p ℓ over K. In particular, the asymptotic convergence of the upper bounds implies that for any given ǫ > 0

∃r ∈ N ∃h ℓ ∈ Σ r s.t. ∫ K p ℓ (x)h ℓ (x)dµ 0 (x) ≤ ǫ 2 , ∫ K h ℓ (x)dµ 0 (x) = 1
and, therefore,

∫ K ( f i (x) -f i (x * ℓ )) 2 h ℓ (x)dµ 0 (x) ≤ ǫ 2 ∀i ∈ {0, . . . , m}. (26)
3. Using the Jensen inequality, one obtains

∫ K f i (x)h ℓ (x)dµ 0 (x) -f i (x * ℓ ) = ∫ K ( f i (x) -f i (x * ℓ ))h ℓ (x)dµ 0 (x) ≤ ǫ
for each i ∈ {0, . . . , m}.

We now consider the sum-of-squares density

h := ℓ λ ℓ h ℓ ∈ Σ r . Then we have b i = ∫ K f i (x)dµ * (x) = ℓ λ ℓ f i (x * ℓ )
for each i ∈ {0, . . . , m}. Moreover, the above argument shows that for any i ∈ {0, . . . , m}

∫ K f i (x)h(x)dµ 0 (x) -b i = ℓ λ ℓ ∫ K f i (x)h ℓ (x)dµ 0 (x) -f i (x * ℓ ) ≤ ǫ µ * (K)
with µ * (K) = ℓ λ ℓ . This shows that ∆ (r) ≤ ǫ µ * (K) and thus the desired asymptotic result (1). 5. The additional three claims ( 2)-( 4) follow in the same way using the results in Table 2. For instance, in case (1) when K satisfies an interior cone condition and µ 0 is the Lebesgue measure, we replace the estimate (26) by

∫ K ( f i (x) -f i (x * ℓ )) 2 h ℓ (x)dµ 0 (x) = O 1 √ r ,
which leads to ∆ (r) = O 1 r 1/4 (since we 'loose a square root' when applying Jensen inequality).

We may also use the relation with positive cubature rules discussed in the previous section (Theorem 6) to obtain the following cubature-based approximations for the GPM (1).

Corollary 2 Assume the GPM (1) admits an optimal solution and let d denote the maximum degree of the polynomials f 0 , . . . , f m . For any integer r ∈ N assume we have a cubature rule for (K, µ 0 ) that is exact for degree d + 2r, consisting of the points x (ℓ) ∈ K and weights w ℓ > 0 for ℓ ∈ [N], and define the parameter

∆ (r) cub := min ν max i ∈{0,1,...,m} ∫ K f i (x)dν -b i ,
where in the outer minimization we minimize over all atomic measures ν whose atoms all belong to the set {x (ℓ) : ℓ ∈ [N]}. Then the following assertions hold:

(1)

lim r→∞ ∆ (r) cub = 0; (2) ∆ (r) cub = O 1 r 1/4
if K satisfies an interior cone assumption and µ 0 is the Lebesgue measure;

(3)

∆ (r) cub = O 1 √ r if K is a convex body and µ 0 is the Lebesgue measure; 1. ∆ (r) cub = O 1 r if K = [-1, 1] n and dµ 0 (x) = i (1 -x 2 i ) -1/2 dx i .
This result follows from Theorem 7. Indeed, for any polynomial h ∈ Σ r , the polynomials f i h have degree at most d + 2r so that using the cubature rule we obtain

∫ K f i (x)h(x)dµ 0 (x) = N ℓ=1 w ℓ f i (x (ℓ) )h(x (ℓ) ) = ∫ K f i (x)dν(x),
where ν is the atomic measure with atoms x (ℓ) and weights α ℓ := w ℓ h(x (ℓ) ) for ℓ ∈ [N]. Therefore, the parameter ∆ (r) cub in Corollary 2 is upper bounded by the parameter ∆ (r) in Theorem 7. The claims (1)-( 4) now follow directly from the corresponding claims in Theorem 7.

Note that, for any fixed r ∈ N, in order to find the best atomic measure ν in the definition of ∆ (r) cub we need to find the best weights α ℓ (ℓ ∈ [N]) giving the measure ν = N ℓ=1 α ℓ δ x (ℓ) . This can be done by solving the following linear program:

∆ (r) cub = min t,α ℓ ∈R t s.t. α ℓ ≥ 0 (ℓ ∈ [N]), N ℓ=1 α ℓ f i (x (ℓ) ) -b i ≤ t ∀i ∈ {0, 1, . . . , m}.
(This is similar to an idea used in [START_REF] Ryu | Extensions of Gauss Quadrature Via Linear Programming[END_REF].)

Convergence results for the outer approximations

In this last section we consider the convergence of the lower bounds for the GPM [START_REF] Akhiezer | The classical moment problem[END_REF], that are obtained by using outer approximations for the cone of positive measures. We first mention properties dealing with asymptotic and finite convergence for the general GPM and after that we mention some known results on the error analysis in the special case of polynomial optimization.

Here we assume K is a compact semi-algebraic set, defined as before by

K = {x ∈ R n : g j (x) ≥ 0 ∀ j ∈ [k]},
where g 1 , . . . , g k ∈ R[x]. We will consider the following (Archimedean) condition:

∃r ∈ N ∃u ∈ Q r (g 1 , . . . , g k ) s.t. the set {x ∈ R n : u(x) ≥ 0} is compact. ( 27
)
This condition clearly implies that K is compact. Moreover, it does not depend on the set K but on the choice of the polynomials used to describe K. Note that it is easy to modify the presentation of K so that the condition [START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF] holds. Indeed, if we know the radius R of a ball containing K then, by adding to the description of K the (redundant) polynomial constraint g k+1 (x) := R 2 -n i=1 x 2 i ≥ 0, we can ensure that assumption [START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF] holds for this enriched presentation of K.

For convenience we recall the definition of the bounds val (r) out er from (13):

val (r) out er = inf µ ∈(Q r (g 1 ,...,g k )) * ∫ K f 0 (x)dµ(x) : ∫ K f i (x)dµ(x) = b i ∀i ∈ [m] ,
where we refer to ( 6) and ( 7) for the definitions of the truncated quadratic module Q r (g 1 , . . . , g k ) and of its dual cone (Q r (g 1 , . . . , g k )) * . We also recall the stronger bounds val (r) out er , introduced in (17), and obtained by replacing in the definition of val (r) out er the cone Q r (g 1 , . . . , g k ) by the larger cone Q r ( j ∈J g j : J ⊆ [k])), so that we have

val (r) out er ≤ val (r)
out er ≤ val.

Asymptotic and finite convergence

Here we present some results on the asymptotic and finite convergence of the lower bounds on val obtained by considering outer approximations of the cone M(K) + .

Asymptotic convergence

The parameters val (r) out er form a non-decreasing sequence of lower bounds for the optimal value val of problem [START_REF] Akhiezer | The classical moment problem[END_REF], which converge to it under assumption [START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF]. This asymptotic convergence result relies on the following representation result of Putinar [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF] for positive polynomials.

Theorem 8 (Putinar) Assume K is compact and assumption [START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF] holds. Any polynomial f that is strictly positive on K (i.e., f (x) > 0 for all x ∈ K) belongs to Q r (g 1 , . . . , g k ) for some r ∈ N.

The following result can be found in [START_REF] Lasserre | A semidefinite programming approach to the generalized problem of moments[END_REF][START_REF] Lasserre | Positive Polynomials and Their Applications[END_REF] for the general GPM and in [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF] for the case of global polynomial optimization.

Asymptotic convergence for the bounds val (r) out er Theorem 9 Assume K is compact and assumption [START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF] holds. Then we have val * ≤ lim r→∞ val (r) out er ≤ val, with equality: val * = lim r→∞ val (r) out er = val if, in addition, there exists z ∈ R m+1 such that m i=0 z i f i (x) > 0 for all x ∈ K.

This result follows using Theorem 8. Observe that it suffices to show the inequality:

val * ≤ sup r val (r) out er (as the rest follows using Corollary 1). For this let ǫ > 0 and let y ∈ R m be feasible for val * , i.e., f 0 (x) -m i=1 y i f i (x) ≥ 0 for all x ∈ K; we will show the inequality b T y ≤ sup r val (r) out er + ǫ µ(K). Then, letting ǫ tend to 0 gives b T y ≤ sup r val (r) out er and thus the desired result: val * ≤ sup r val (r) out er = lim r→∞ val (r) out er . As the polynomial f 0 + ǫi y i f i is strictly positive on K, it belongs to Q r (g 1 , . . . , g k ) for some r ∈ N in view of Theorem 8. Then, for any measure µ feasible for val (r) out er , we have

∫ K ( f 0 + ǫ -i y i f i )dµ ≥ 0, which implies b T y ≤ ∫ K f 0 dµ + ǫ µ(K)
and thus the desired inequality:

b T y ≤ val (r) out er + ǫ µ(K) ≤ sup r val (r) out er + ǫ µ(K).

When assuming only K compact (thus not assuming condition ( 27)), the following representation result of Schmüdgen [START_REF] Schmüdgen | The K-moment problem for compact semi-algebraic sets[END_REF] permits to show the asymptotic convergence of the stronger bounds val Theorem 10 (Schmüdgen) Assume K is compact. Any polynomial f that is strictly positive on K (i.e., f (x) > 0 for all x ∈ K) belongs to Q r ( j ∈J g j : J ⊆ [k]) for some r ∈ N. out er = val if, in addition, there exists z ∈ R m+1 such that m i=0 z i f i (x) > 0 for all x ∈ K.

Asymptotic convergence for the bounds val

Finite convergence

A remarkable property of the lower bounds val (r) out er is that they often exhibit finite convergence. Indeed, there is an easily checkable criterion, known as the flatness condition, that permits to conclude that the bound is exact: val (r) out er = val, and to extract an (atomic) optimal solution to the GPM. This is condition (28) below, which permits to claim that a given truncated sequence is indeed the sequence of moments of a positive measure; it goes back to work of Curto and Fialkow ( [START_REF] Curto | Solution of the truncated complex moment problem for flat data[END_REF], see also [START_REF] Lasserre | Positive Polynomials and Their Applications[END_REF][START_REF] Laurent | Sums of squares, moment matrices and optimization over In Emerging Applications of Algebraic Geometry[END_REF] for details). To expose it we use the SDP formulation ( 15)-( 16) for the parameter val (r) out er .

Finite convergence

Theorem 12 (see [START_REF] Lasserre | Positive Polynomials and Their Applications[END_REF]Theorem 4

.1]) Set d K := max{⌈deg(g j /2⌉ : j ∈ [k]} and let r ∈ N such that 2r ≥ max{deg( f i ) : i ∈ {0, . . . , m}} and r ≥ d K . Assume 1 α(G) = min x ∈∆ n x T (I n + A G )x, α(G) = max x ∈[0,1] n i ∈V x i - {i, j } ∈E x i x j , 2 √ 2 3 √ 3 1 - 1 α(G) = max y ∈R n ,z ∈R m        2 {i, j } ∈E z ij y i y j : (y, z) ∈ S n+m       
(see [START_REF] Motzkin | Maxima for graphs and a new proof of a theorem of Túran[END_REF][START_REF] Nesterov | Random walk in a simplex and quadratic optimization over convex polytopes[END_REF]). Here I n is the identity matrix of size n, A G is the adjacency matrix of G (with entries A ij = A ji = 1 if {i, j} ∈ E and 0 otherwise), E is the set of pairs of distinct elements i, j ∈ V such that {i, j} E and m = |E |.

Error analysis for the sphere

We first consider the case of the sphere K = S n = {x ∈ R n : n i=1 x 2 i = 1}. Then an error analysis for the bounds val (r) out er is known when p is a homogeneous polynomial.

First, one may reduce to the case when p has even degree. Indeed, as shown in [START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF], if p has odd degree d then we have max p(x) :

n i=1 x 2 i = 1 = d d/2 (d + 1) (d+1)/2 max x n+1 p(x) : n+1 i=1 x 2 i = 1 .
Another useful observation is that, for a homogeneous polynomial q of even degree d, q belongs to the truncated quadratic module of the sphere:

Q r ± 1 - n i=1 x 2 i = Σ r + 1 - n i=1 x 2 i R[x]
if and only if the polynomial q(x) n i=1 x 2 i r is a sum of squares of polynomials (see [START_REF] De Klerk | On the equivalence of algebraic approaches to the miniization of forms on the simplex[END_REF]). Therefore, when p is a homogeneous polynomial of even degree d = 2a, the parameter val (r) out er can be reformulated as val (r) out er = min t : t ∈ R,

t n i=1 x 2 i r - n i=1 x 2 i r-a p(x) ∈ Σ r . (30)
Based on this, the following error bounds for the parameters val (r) out er are shown in [START_REF] Faybusovich | Global optimization of homogeneous polynomials on the simplex and on the sphere[END_REF][START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF] (for general polynomials) and in [START_REF] De Klerk | A PTAS for the minimization of polynomials of fixed degree over the simplex[END_REF] (for even polynomials).

Theorem 15 Let p be a homogeneous polynomial of even degree d. We briefly discuss the approach in [START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF], which in fact provides an error analysis for the larger range val (r) innerval (r) out er . For an integer a let MSym((R n ) ⊗a ) denote the set of matrices acting on (R n ) ⊗a that are maximally symmetric, which means the associated 2a-tensor is fully symmetric (i.e., invariant under the action of the symmetric group Sym(2a)). Any homogeneous polynomial p of degree 2a can be written as p(x) = (x ⊗a ) T Z p x ⊗a for a (unique) Z p ∈ MSym((R n ) ⊗a ). Then, defining the polynomial p r (x) = ( i x 2 i ) r-a p(x), the program (30) can be reformulated as val (r) out er = min Z p r , M : M 0, Tr(M) = 1, M ∈ MSym((R n ) ⊗r ) .

Let M be an optimal solution to this program. As M 0 the polynomial (x ⊗r ) T M x ⊗r is a sum of squares. One can scale it to obtain h ∈ Σ r which provides a probability density function on S n , i.e., ∫ S n h(x)dµ 0 (x) = 1 (with µ 0 the surface measure on S n ), and thus val (r) inner ≤ ∫ S n h(x)dµ 0 . Using the orthogonal polynomial basis with respect to µ 0 (consisting of spherical harmonic polynomials), Doherty and Wehner [START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF] show a de Finetti type result, which permits to upper bound the range ∫ S n h(x)dµ 0 -Z p r , M and thus val (r) innerval (r) out er .

Error analysis for the simplex and the hypercube For the simplex K = ∆ n = {x ∈ R n : x i ≥ 0 (i ∈ [n]), 1 -n i=1 x i = 0} and the hypercube K = [0, 1] n = {x ∈ R n : x i ≥ 0, 1x i ≥ 0 (i ∈ [n])}, a refined error analysis is known only for the stronger bounds val (r) out er , where we use the larger quadratic module generated by all pairwise products of the constraints defining K.

Error analysis for the simplex

Theorem 16 [START_REF] De Klerk | A PTAS for the minimization of polynomials of fixed degree over the simplex[END_REF] Assume K = ∆ n and p is a homogeneous polynomial with degree d. Then we have min The above results show that in Theorem 14 one may choose the unknown constant to be c = 1 (roughly) if K is a hypercube or simplex. In both cases the proof relies on showing this error analysis for a weaker bound, which is obtained by using only nonnegative scalar multipliers (instead of sum-of-squares multipliers) in the definition of the quadratic module. See [START_REF] De Klerk | A PTAS for the minimization of polynomials of fixed degree over the simplex[END_REF][START_REF] De Klerk | Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube[END_REF] for details.

Concluding remarks

We conclude with a few remarks on available software and future research directions.

Software

The bounds based on the outer approximations (13) described here have been implemented in the software Gloptipoly3 [START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF]. The software can in fact deal with a more general version of the GPM (1) than presented here. Namely it can deal with the problem val = inf

µ i ∈M(K i ) + ∀i ∈{0}∪[m]
∫ K 0 f 0 (x)dµ 0 (x) :

∫ K i f i (x)dµ i (x) = b i ∀i ∈ [m] ,
where we have a variable measure µ i ∈ M(K i ) + for each index i ∈ {0, . . . , m}, with K i ⊆ R n being basic closed semi-algebraic sets defined by (possibly different) sets of polynomial inequalities. Due to the sizes of the resulting semidefinite programs that are solved, applicability is typically limited to n ≤ 20 variables and low order, say r ≤ 4. This is due to the fact the matrix variables in the semidefinite programs are roughly of order n+r r . Solving larger instances requires exploiting additional structure (like sparsity) leading to more economical semidefinite programs. We refer, e.g., to [START_REF] Lasserre | Positive Polynomials and Their Applications[END_REF] and references therein for further details.

Error bounds for the inner approximation hierarchy

The known error bounds for the inner approximation, presented earlier in Table 2, are for specific choices of the set K and reference measure µ 0 ∈ M(K) + . More work is required to understand the role of the reference measure in the convergence analysis, and to extend the regime in O(1/r 2 ) to more classes of sets K. In particular, an obvious choice is whether one can sharpen the analysis of the the convergence rate for the Euclidean unit sphere. As explained, such results would also have implications for grid search on cubature points on the sphere. Cubature on the sphere is a vast research topic (see, e.g., [START_REF] Dai | Approximation Theory and Harmonic Analysis on Spheres and Balls[END_REF]Chapter 6]), even in the special case of spherical t-designs [9, §6.5], where all cubature weights are equal and positive. Moreover, the complexity of polynomial optimization on spheres is not fully understood; indeed the problem is NP-hard, but allows polynomial-time approximation schemes in special cases (see [START_REF] De Klerk | A PTAS for the minimization of polynomials of fixed degree over the simplex[END_REF][START_REF] De Klerk | The complexity of optimizing over a simplex, hypercube or sphere: a short survey[END_REF]). Sharpening the analysis of the inner approximations for polynomial optimization over spheres may help to gain a more complete understanding.

Error bounds for the outer approximation hierarchy

The bounds based on the outer approximation presented here are more practically suited for computation, in particular since they (sometimes) enjoy finite convergence and permit to extract the global minimizers; moreover, as mentioned above, the dedicated software Gloptipoly3 is available for this purpose. On the other hand, the known results on the rate of convergence are somewhat disappointing (as discussed in Section 5.2), and in general much weaker than those known for the inner approximation. There is certainly room for a breakthrough here; new ideas are needed to obtain convergence rates that match the performance observed in practice.

Theorem 5 (

 5 Kalai-Vempala[START_REF] Kalai | Simulated annealing for convex optimization[END_REF]) If p is a linear polynomial, K is a convex set, T > 0 is a fixed 'temperature' parameter, and val = min x ∈K p(x), then we have∫ K p(x)H(x)dxval ≤ nT,where H(x) = exp(-p(x)/T ) ∫ K exp(-p(x)/T )dx is the Boltzman probability density supported on K.

Lemma 2

 2 Assume x * is a global minimizer of p over K. Then the following polynomial p(x) = p(x * ) + ∇p(x * ) T (xx * ) + C p xx * 2

  out er to val (in the same way as Theorem 9 follows from Putinar's theorem).

Theorem 11

 11 Assume K is compact. Then we have val * ≤ lim r→∞ val (r) out er ≤ val, with equality: val * = lim r→∞ val (r)

2 p

 2 (i) ([START_REF] Faybusovich | Global optimization of homogeneous polynomials on the simplex and on the sphere[END_REF][START_REF] Doherty | Convergence of SDP hierarchies for polynomial optimization on the hypersphere[END_REF]) There exist constants C n,d and r n,d (depending on n and d) such thatmin x ∈S n p(x)val (r) out er ≤ C n,d r for all integers r ≥ r n,d .(ii) ([START_REF] De Klerk | A PTAS for the minimization of polynomials of fixed degree over the simplex[END_REF]) If p is an even polynomial (i.e., of the form p = α∈N n d/α x 2α ), then the above holds where the constant C n,d depends only on d and r n,d = d.

L p 1 r

 1 for all r ≥ d, where C d > 0 is an absolute constant depending only on d.Error analysis for the hypercubeTheorem 17[START_REF] De Klerk | Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube[END_REF] Assume K = [0, 1] n . For any polynomial p with degree d we havemin x ∈[0,1] n p(x)val (r) out er ≤ n d d + 13 for all r ≥ d.

Acknowledgement

The authors would like to thank Fernando Mario de Oliveira Filho for insightful discussions on the duality theory of the GPM.

the program ( 15)- [START_REF] De Klerk | On the equivalence of algebraic approaches to the miniization of forms on the simplex[END_REF] defining the parameter val (r) out er has an optimal solution y = (y α ) α∈N n 2r that satisfies the following (flatness) condition: rankM s (y) = rankM s-d K (y) for some integer s s.t.

where M s (y) = (y α+β ) α,β ∈N n s and M s-d K (y) = (y α+β ) α,β ∈N n s-d K

.

Then equality val (r) out er = val holds and the GPM problem [START_REF] Akhiezer | The classical moment problem[END_REF] has an optimal solution µ ∈ M(K) + which is atomic and supported on rankM s (y) points in K.

Under the flatness condition [START_REF] Josz | Strong duality in Lasserre's hierarchy for polynomial optimization[END_REF] there is an algorithmic procedure to find the atoms and weights of the optimal atomic measure (see, e.g., [START_REF] Lasserre | Positive Polynomials and Their Applications[END_REF][START_REF] Laurent | Sums of squares, moment matrices and optimization over In Emerging Applications of Algebraic Geometry[END_REF] for details).

In addition, for the special case of the polynomial optimization problem (8), Nie [START_REF] Nie | Optimality conditions and finite convergence of Lasserre's hierarchy[END_REF] shows that the flatness condition is a generic property, so that finite convergence of the lower bounds val (r) out er to the minimum of a polynomial over K holds generically.

Note that analogous results also hold for the stronger bounds val (r) out er on val.

Error analysis for the case of polynomial optimization

We now consider the special case of global polynomial optimization, i.e., problem [START_REF] Curto | Solution of the truncated complex moment problem for flat data[END_REF], which is the case of GPM with only one affine constraint, requiring that µ is a probability measure on K:

Recall the definition of the bound val (r) out er from [START_REF] De Klerk | Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube[END_REF], which now reads

It can be reformulated via an SDP as in ( 15)-( 16), whose dual SDP reads

By weak duality val (r) out er is at least the optimum value of [START_REF] Kalai | Simulated annealing for convex optimization[END_REF]. Strong duality holds for instance if the set K has a non-empty interior (since then the primal SDP is strictly feasible), or if there is a ball constraint present in the description of the set K (as shown in [START_REF] Josz | Strong duality in Lasserre's hierarchy for polynomial optimization[END_REF]). Then, val (r) out er is also given by the program [START_REF] Kalai | Simulated annealing for convex optimization[END_REF], which is the case, e.g., when K is a simplex, a hypercube, or a sphere. As we saw above, the bounds val (r) out er converge asymptotically to the minimum value val taken by the polynomial p over the set K when condition [START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF] holds. We now indicate some known results on the rate of convergence of these bounds.

For a polynomial p = α p α x α ∈ R[x] d , we set

Error analysis for the bounds val (r) out er

Theorem 13 [START_REF] Nie | On the complexity of Putinar's positivstellensatz[END_REF] Assume K ⊆ (-1, 1) n . There exists a constant c > 0 (depending only on K) such that, for any polynomial p with degree d, we have

Note that this result displays a very slow convergence rate, which does not reflect the good behaviour of the bounds often observed in practice.

On the other hand, a sharper error analysis holds for the stronger bounds val (r) out er , obtained by using the larger set Q r ( j ∈J g j :

Error analysis for the bounds val (r) out er Theorem 14 [START_REF] Schweighofer | On the complexity of Schmüdgen's Positivstellensatz[END_REF] Assume K ⊆ (-1, 1) n . There exists a constant c > 0 (depending only on K) such that, for any polynomial p with degree d, we have valval (r) out er ≤ cd 4 n 2d L p 1 r 1/c for all integers r ≥ cd c n cd .

We now recap some known sharper results for the case of polynomial optimization over special sets K like the simplex, the hypercube and the sphere. As motivation recall that this already captures well known hard combinatorial optimization problems such as the maximum independence number in a graph.

Given a graph G = (V = [n], E) let α(G) denote the largest cardinality of an independent set in G, i.e., of a set I ⊆ V that does not contain any edge of E. In fact the parameter α(G) can be reformulated via polynomial optimization over the simplex ∆ n , the hypercube [0, 1] n , or the unit sphere S n . Indeed the following results are known: