Lorenzo Baldi

Bernard Mourrain

Exact Moment Representation in Polynomial Optimization

We investigate the problem of representing moment sequences by measures in the context of Polynomial Optimization Problems. This consists in finding the infimum of a real polynomial on a real semialgebraic set defined by polynomial inequalities. We analyze the exactness of Moment Matrix (MoM) relaxations, dual to the Sum of Squares (SoS) relaxations, which are hierarchies of convex cones introduced by Lasserre to approximate measures and positive polynomials. We investigate in particular flat truncation properties, which allow testing effectively when MoM exactness holds.

We consider the quadratic module Q generated by the inequalities. We show that the dual of the MoM relaxation coincides with the SoS relaxation extended with the real radical of the support of Q, and focus on the zero-dimensional case, generalizing results for equations defining a finite real variety. We deduce sufficient and necessary conditions for flat truncation, under the finite convergence assumption: flat truncation happens if and only if the support of the quadratic module associated with the minimizers is of dimension zero. We also bound the order of the relaxation at which flat truncation holds.

As corollaries, we conclude that flat truncation holds:

• when regularity conditions, known as Boundary Hessian Conditions, hold: this result implies that flat truncation and MoM exactness holds generically;

• when the support of the quadratic module Q is zero-dimensional;

• in singular cases, flat truncation holds for the MoM relaxation extended with the polar constraints when the real variety of polar points is finite.

Effective numerical computations illustrate these flat truncation properties.

Introduction

Let f , g 1 , . . . , g s ∈ R[X 1 , . . . , X n ] be polynomials in the indeterminates X 1 , . . . , X n with real coefficients. The goal of Polynomial Optimization is to find:

f * inf f (x) ∈ R | x ∈ R n , g i (x) ≥ 0 for i = 1, . . . , s , (1)
that is the infimum f * of the objective function f on the basic semialgebraic set S { x ∈ R n | g i (x) ≥ 0 for i = 1, . . . , s }. It is a general problem, which appears in many contexts (e.g. real solution of polynomial equations, . . . ) and with many applications. To cite a few of them: in graph theory [START_REF] Laurent | Finite convergence of sum-of-squares hierarchies for the stability number of a graph[END_REF], network optimization design [START_REF] Daniel | Sparsity-Exploiting Moment-Based Relaxations of the Optimal Power Flow Problem[END_REF], control [START_REF] Henrion | Convex Computation of the Region of Attraction of Polynomial Control Systems[END_REF], . . . See [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF] for a more comprehensive list.

To solve this NP-hard problem, Lasserre [START_REF] Lasserre | Global Optimization with Polynomials and the Problem of Moments[END_REF] proposed to use two hierarchies of finite dimensional convex cones depending on an order d ∈ N and he proved, for Archimedean quadratic modules, the convergence when d → ∞ of the optima associated to these hierarchies to the minimum f * of f on S. The first hierarchy replaces non-negative polynomials by Sums of Squares (SoS) and non-negative polynomials on S by polynomials of degree ≤ d in the truncated quadratic module Q 2d (g) generated by the tuple of polynomials g = g 1 , . . . , g s .

The second and dual hierarchy replaces positive measures by linear functionals ∈ L 2d (g) which are non-negative on the polynomials of the truncated quadratic module Q 2d (g). We will describe more precisely these constructions in section 2.1.

This approach has many interesting properties (see e.g. [START_REF] Bernard | An Introduction to Polynomial and Semi-Algebraic Optimization[END_REF], [START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF], [START_REF] Marshall | Positive Polynomials and Sums of Squares[END_REF]). It was proposed with the aim to recover the infimum f * and, if this infimum is reached, the set of minimizers {ξ ∈ S | f (ξ) = f * }. The extraction of minimizers is strongly connected to the so called flat truncation property, that will be the focus of the paper.

To tackle these challenges, one can first address the finite convergence problem, that is when the value f * can be obtained at a given order of the relaxation(s). The second problem is the exactness of the relaxations, which is the main topic of this paper. The Sum of Squares (SoS) exactness is when the non-negative polynomial ff * belongs to the truncated quadratic module Q 2d (g) for some d ∈ N. The Moment Matrix (MoM) exactness is when, for some d ∈ N, any optimal linear functional σ * ∈ L 2d (g) for f is coming from a positive measure supported on S. We are going to investigate in detail this MoM exactness property.

Several works have been developed over the last decades to address SoS representation problems. [START_REF] Parrilo | An Explicit Construction of Distinguished Representations of Polynomials Nonnegative Over Finite Sets[END_REF] showed that if the complex variety V C (I) defined by an ideal I generated by real polynomials is finite and I is radical, then ff * has a representation as a sum of squares modulo I. [START_REF] Laurent | Semidefinite representations for finite varieties[END_REF] showed the finite convergence property if the complex variety V C (I) is finite, and a moment sequence representation property, if moreover the ideal I is radical. [START_REF] Nie | Polynomial Optimization with Real Varieties[END_REF] showed that if the semialgebraic set S is finite, then the finite convergence property holds for a preordering defining S. [START_REF] Scheiderer | Distinguished representations of non-negative polynomials[END_REF] proved that ff * is in the quadratic module Q defining S modulo (ff * ) 2 if and only if ff * ∈ Q and then the SoS relaxation is exact. [START_REF] Marshall | Representations of Non-Negative Polynomials Having Finitely Many Zeros[END_REF], [START_REF] Marshall | Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization[END_REF] proved that, under regularity conditions at the minimizers, known as Boundary Hessian Conditions (BHC), ff * is in the quadratic module and the SoS exactness property holds. [START_REF] Nie | Minimizing Polynomials via Sum of Squares over the Gradient Ideal[END_REF], [START_REF] Demmel | Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals[END_REF] showed that, by adding gradient constraints when S = R n or KKT constraints when S is a general basic semialgebraic set, the SoS exactness property holds when the corresponding Jacobian ideal is radical. [START_REF] Nie | An exact Jacobian SDP relaxation for polynomial optimization[END_REF] showed that, by adding the Jacobian constraints, the finite convergence property holds under some regularity assumption. [START_REF] Nie | Certifying convergence of Lasserre's hierarchy via flat truncation[END_REF] showed that finite convergence and the flat truncation property are equivalent under generic assumptions, if the SoS relaxation is exact and strong duality holds. In [START_REF] Nie | Optimality conditions and finite convergence of Lasserre's hierarchy[END_REF], it is shown that BHC imply finite convergence and that BHC are generic. [START_REF] Kriel | On the Exactness of Lasserre Relaxations and Pure States Over Real Closed Fields[END_REF] showed the SoS exactness property if the quadratic module defining S is Archimedian and some strict concavity properties of f at the finite minimizers are satisfied.

Though many works focused on the SoS relaxation and the representation of positive polynomials with Sums of Squares, the MoM relaxation has been much less studied. We mention [START_REF] Bernard Lasserre | Semidefinite Characterization and Computation of Zero-Dimensional Real Radical Ideals[END_REF] and [START_REF] Lasserre | Moment matrices, border bases and real radical computation[END_REF], which prove that if S is finite, the value f * , the minimizers and the vanishing ideal of S can be recovered from moment matrices associated with the truncated preordering defining S; and [START_REF] Nie | Certifying convergence of Lasserre's hierarchy via flat truncation[END_REF], which shows that finite convergence and the flat truncation property are equivalent under generic assumptions, if the SoS relaxation is exact and strong duality holds.

From a methodological and practical point of view, flat truncation tests on moment matrices [START_REF] Curto | Flat Extensions of Positive Moment Matrices: Recursively Generated Relations[END_REF], [START_REF] Laurent | A Generalized Flat Extension Theorem for Moment Matrices[END_REF] are essentially the only known way to decide finite convergence, i.e. whether the minimum f * is reached at some order of the relaxation. But flat truncation also implies MoM exactness. Moreover, it allows extracting the finite minimizers from moment matrices [START_REF] Henrion | Detecting global optimality and extracting solutions in GloptiPoly[END_REF], [START_REF] Mourrain | Polynomial-Exponential Decomposition From Moments[END_REF], whereas SoS exactness does not yield the minimizers. Therefore a natural question, of theoretical and practical importance, is:

When flat truncation holds in a Polynomial Optimization Problem?

It is known that truncated minimizing (pseudo-)moment sequences are not always coming from measures, as shown for instance by Examples 2.7, 2.8, 2.9, 2.10, 2.11. Thus flat truncation does not hold in general. But surprisingly, for regular Polynomial Optimization Problems, this question remained open for more than a decade.

Contributions. Our first main contribution to this problem is given in Theorem 4.4. We prove that, under finite convergence assumption, flat truncation is equivalent to having the support of the quadratic module associated with the minimizers of dimension zero. Moreover, we give conditions on the order of the relaxation to have flat truncation.

As a corollary we deduce Theorem 4.7, where we show that flat truncation and MoM exactness hold for regular problems which satisfy the Boundary Hessian Conditions. It also provides new bounds on the order where flat truncation holds. This generalizes the results on finite convergence and SoS exactness proved in [START_REF] Marshall | Representations of Non-Negative Polynomials Having Finitely Many Zeros[END_REF], [START_REF] Marshall | Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization[END_REF], and [START_REF] Nie | Optimality conditions and finite convergence of Lasserre's hierarchy[END_REF]. It also shows that flat truncation and MoM exactness holds generically (Corollary 4.8).

Another consequence of Theorem 4.4, shown in Theorem 4.10, is that when the set S is finite, flat truncation holds if the quotient by the support of the quadratic module Q is of dimension zero. This generalizes results of [START_REF] Bernard Lasserre | Semidefinite Characterization and Computation of Zero-Dimensional Real Radical Ideals[END_REF] and [START_REF] Lasserre | Moment matrices, border bases and real radical computation[END_REF] on semi-definite moment representations on finite sets. Moreover, we provide new bounds on the order where flat truncation holds.

When the problem is not regular, we introduce polar equations, that can help achieving flat truncation and MoM exactness. In Theorem 4.14, we prove that if the real variety of polar points is finite then the relaxation extended with Jacobian constraints is MoM exact and the flat truncation property is satisfied. This generalizes the results of finite convergence and SoS exactness of the KKT and Jacobian relaxations under regularity conditions, proved in [START_REF] Nie | Minimizing Polynomials via Sum of Squares over the Gradient Ideal[END_REF], [START_REF] Demmel | Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals[END_REF], [START_REF] Nie | An exact Jacobian SDP relaxation for polynomial optimization[END_REF].

To prove these results, we investigate in detail the properties of truncated moment relaxations and their duals. In Theorem 3.4, we provide a new description of the dual of the MoM relaxation in terms of the initial SoS relaxation and the real radical of the support of the associated quadratic module Q. A key ingredient to analyze flat truncation is Theorem 3.21. When the quotient by the support of Q is of dimension zero, we prove that the (truncated) linear functionals in L d (g) coincide with the measures supported on S, that is the convex hull of the evaluations at the points of S. Moreover, the ideal generated by the annihilator of a generic element in L d (g) is the vanishing ideal of S.

The paper is structured as follows. In the next section of the introduction, we define the algebraic objects that we will use and recall their main properties. In Section 2, we describe in detail the notions of finite convergence and exactness for the Sum of Squares (SoS) and Moment Matrix (MoM) relaxations. We give several examples showing how these notions are related.

In Section 3, we investigate the properties of truncated moment sequences (Section 3.1), of their annihilators (Section 3.2) and we analyze when flat truncation holds and relate it with the regularity of S (Section 3.3).

In Section 4, we apply these results to Polynomial Optimization Problems (POPs). In Section 4.1, we prove necessary and sufficients conditions for flat truncation and analyze at which degree flat truncation holds and yields the minimizers. We prove that exactness and flat truncation hold for POPs satisfying the Boundary Hessian Conditions (Section 4.2), for finite semialgebraic sets (Section 4.3), and finally for POPs with polar constraints (Section 4.4).

For the numerical computations performed on the examples, which illustrate these developments, we use the Julia package MomentTools.jl1 with the SDP solvers Mosek and SDPA, based on interior point methods.

Notation

We provide here the basic definitions we need hereafter and refer to [START_REF] Marshall | Positive Polynomials and Sums of Squares[END_REF] and [START_REF] Mourrain | Polynomial-Exponential Decomposition From Moments[END_REF] for more details.

If A is a subset of a R-vector space V , we denote by cone(A) the convex cone generated by A, by conv(A) its convex hull and by A its linear span.

Let

R[X] R[X 1 , . . . , X n ] be the R-algebra of polynomials in n indeterminates X 1 , . . . , X n . We denote (h 1 , . . . , h r ) ⊂ R[X] the ideal generated by h 1 , . . . , h r ∈ R[X].
We say that the tuple of polynomials h = h 1 , . . . , h s is a graded basis of an ideal I if for all p ∈ I, there exists q

i ∈ R[X] with deg(q i ) ≤ deg(p) -deg(h i ) such that p = s i=1 h i q i . Equivalently, we have for all t ∈ N, h t {p = s i=1 h i q i | deg(q i ) ≤ t -deg(h i )} = I t {f ∈ I | deg f ≤ t}, i.
e. for all t the truncated ideal in degree t generated by h is equal to all the polynomials of degree ≤ t in the ideal. If h is not a graded basis, the inclusion h t ⊂ I t is strict. A graded basis of an ideal I = (h) can be computed as a Grobner basis using a monomial ordering ≺, which refines the degree ordering (see e.g. [START_REF] Cox | Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra[END_REF]). It can also be computed as a border basis for a monomial basis of least degree of R[X]/I (see e.g. [START_REF] Mourrain | Generalized normal forms and polynomials system solving[END_REF]). dim

R[X]

I will denote the Krull dimension of

R[X] I . If A ⊂ R[X] and t ∈ Ñ := N ∪ {∞}, A t { f ∈ A | deg f ≤ t }.
In particular R[X] t is the vector space of polynomials of degree ≤ t. When t = ∞, we will omit the index: A ∞ = A. By convention, ∞ is an idempotent element for all the operations +, * in the ordered ring Ñ.

Given a finite tuple of polynomials g = g 1 , . . . , g r , we define Πg j∈J g j : J ⊂ {1, . . . , r} = g 1 , . . . , g r , g 1 g 2 , . . . , g 1 • • • g r , the tuple of all the products of the g i 's, and ±g g 1 , -g 1 , . . . , g r , -g r .

If

A ⊂ R[X] we define S(A) x ∈ R n | f (x) ≥ 0 ∀f ∈ A . In particular we denote S(g) = x ∈ R n | g(x)
≥ 0 ∀g ∈ g (the basic semialgebraic set defined by g).

We denote by Pos

(S) = {f ∈ R[X] : ∀x ∈ S, f (x) ≥ 0} the cone of positive polynomials on S. Quadratic modules. Let Σ 2 = Σ 2 [X] f ∈ R[X] | ∃r ∈ N, g i ∈ R[X] : f = g 2 1 + • • • + g 2 r be the convex cone of Sum of Squares polynomials (SoS). Q ⊂ R[X] is called quadratic module if 1 ∈ Q, Σ 2 • Q ⊂ Q and Q + Q ⊂ Q. If in addition Q • Q ⊂ Q, Q is a preordering. For Q ⊂ R[X], we define supp Q Q ∩ -Q. If Q is a quadratic module then supp Q is an ideal.
We say that a quadratic module Q is finitely generated (f.g.

) if ∃g 1 . . . g l ∈ R[X] : Q = Q(g 1 , . . . , g l ) Σ 2 + Σ 2 • g 1 + • • • + Σ 2 • g l (it is the smallest quadratic module containing g 1 , . . . , g l ).
We say that a quadratic module

Q is Archimedean if ∃ 0 ≤ r ∈ R : r -X 2 ∈ Q. Notice that if Q is Archimedean then S(Q) is compact. For d ∈ Ñ and g ⊂ R[X], let Q d (g) s 0 + r j=1 s j g j ∈ R[X] d | r ∈ N, g j ∈ g, s 0 ∈ Σ 2 d , s j ∈ Σ 2 d-deg g j be the truncated quadratic module generated by g. Notice that Q d (g) ⊂ Q(g) d = Q(g) ∩ R[X] d ,
V , v ∈ V , σ ∈ V * , we denote σ |v = σ (v) the applica- tion of σ to v ∈ V . For A ⊂ V , we define A ⊥ σ ∈ V * | σ |a = 0 ∀a ∈ A and A ∨ σ ∈ V * | σ |a ≥ 0 ∀a ∈ A . Recall that (R[X]) * R[[Y]] R[[Y 1 , . . . , Y n ]],
with the isomorphism given by: (R

[X]) * σ → α∈N n σ |X α Y α α! ∈ R[[Y]], where { Y α α! } is dual to {X α }, i.e. Y α X β = α! δ α,β
. See [START_REF] Mourrain | Polynomial-Exponential Decomposition From Moments[END_REF] for more details. We can identify σ ∈ (R[X]) * with its sequence of coefficients (σ α ) α (called moments, in analogy to the case of a measure), where

σ α σ |X α . If t ≤ s ∈ Ñ and σ ∈ (R[X] s ) * , then σ [t] ∈ (R[X] t ) * denotes its restriction to R[X] t . Similarly if B ⊂ (R[X] s ) * then B [t] { σ [t] ∈ (R[X] t ) * | σ ∈ B }.
We give to R[X] and (R[X]) * the locally convex topology defined as follows.

If V = R[X] or V = (R[X]
) * and W ⊂ V is a finitely dimensional vector subspace, W is equipped with the Euclidean topology. We define U ⊂ V open if and only if U ∩ W is open in W for every finitely dimensional vector subspace W .

Measures. We will consider Borel measures with support included in S ⊂ R n , denoted as M(S), as linear fuctionals, i.e. M(S) ⊂ (R[X]) * . In this case the sequence (µ α ) α associated with a measure µ is the sequence of moments: µ α = X α dµ. Moreover M (1) (S) will denote the Borel probability measures supported on S. We recall a version of Haviland's theorem [START_REF] Marshall | Positive Polynomials and Sums of Squares[END_REF]th. 3

.1.2]: if σ ∈ (R[X]
) * , then σ ∈ M(S) if and only if ∀f ∈ Pos(S), σ |f ≥ 0. In particular we are interested in evaluations or Dirac measures:

if ξ ∈ R n then e ξ (f ) = e ξ f = f de ξ = f (ξ) for all f ∈ R[X].
Moment matrices. Let m g denote the multiplication operator by the polynomial g.

For t ≥ r ∈ Ñ, σ ∈ (R[X] r ) * and g ∈ R[X] t , we define the convolution of g and σ as g σ σ • m g ∈ (R[X] r-t ) * (i.e. g σ |f = σ |gf ∀f ) and the Hankel operator H t σ : R[X] t → (R[X] r-t ) * , g → g σ . If σ = (σ α ) α and g = α g α X α then g σ = ( β g β σ α+β ) α . Notice that g σ = 0 ⇐⇒ H g σ = 0.
We denote by Ann t (σ ) the annihilator of σ w.r.

∈ (R[X] 2t ) * is positive semidefinite (psd) ⇐⇒ H t σ is psd, i.e. H t σ (f ) f = σ f 2 ≥ 0 ∀f ∈ R[X] t (see [Sch17] or [Mar08] for basic properties of psd matrices). Recall that if σ ∈ (R[X] 2t ) * is psd and σ f 2 = 0 then ∀p ∈ R[X] t , σ |f p = 0, see [Las+13, lem. 3.12].
For d ∈ Ñ and g ⊂ R[X] d , we define:

L d (g) Q d (g) ∨ = { σ ∈ (R[X] d ) * | ∀q ∈ Q d (g) σ |q ≥ 0 } the cone
(g) = L d (g) ∨ .
An important construction is the restriction of positive linear functionals. For d ≥ k:

L d (g) [k] = { σ [k] | σ ∈ L d (g) }.
As L d (g) is defined by Linear Matrix Inequalities, it is a so called spectrahedron. Geometrically, L d (g) [k] is the projection of L d (g) onto the moments of degree ≤ k, i.e. it is a projected spectrahedron. Then for every d, L d (g) [k] is an outer, spectrahedral approximation of the cone M(S) [k] .

The case k = 1 is of particular geometric interest. Indeed, identifying moments of degree one and points of R n , one can see the section of L d (g) given by σ 0 = σ |1 = 1 as a spectrahedral outer approximation of the convex hull of S, see for instance [START_REF] Bernard | An Introduction to Polynomial and Semi-Algebraic Optimization[END_REF]ex. 4.4].

Real algebra. We list here for reader's convenience some results of real algebra that will be frequently used through the paper, and refer to [START_REF] Marshall | Positive Polynomials and Sums of Squares[END_REF] and [START_REF] Bochnak | Real Algebraic Geometry. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge / A Series of Modern Surveys in Mathematics[END_REF] for more details.

Definition 1.1 (Real Radical). Let I ⊂ R[X] be an ideal. The real radical of I, denoted R √ I is the ideal: R √ I { f ∈ R[X] | ∃m ∈ N, s ∈ Σ 2 with f 2m + s ∈ I } = (I + Σ 2 ) ∩ -(I + Σ 2 ).
We say that the ideal I is real or real radical if

I = R √ I.
Notice that R √ I is a radical ideal. We are in particular interested in the case

I = supp Q = Q ∩ -Q for an arbitrary quadratic module Q ⊂ R[X]. Lemma 1.2. Let Q ⊂ R[X]
(iii) dim R[X] I = dim R[X] R √ I
, where dim denotes the Krull dimension.

Proof. We briefly prove these known results for the sake of completeness and refer to [START_REF] Marshall | Positive Polynomials and Sums of Squares[END_REF] for more details.

For the first point, closure by addition is trivial. Closure by multiplication follows observing that for all f ∈ R[X] we have f = (

f +1 2 ) 2 -( f -1 2 ) 2 ∈ Σ 2 -Σ 2 .
For the second point, since R √ I is a radical ideal we have

√ I ⊂ R √ I.
Recall that √ I is the intersection of all the minimal prime ideals p lying over I. From [Mar08, prop. 2.1.7] we deduce that for such a minimal prime p, (M + p) ∩ -(M + p) = p and thus (Σ 2 + p) ∩ -(Σ 2 + p) = p, i.e. p is real radical, see Definition 1.1. As the intersection of real radical ideals is real radical, we see that

√

I is a real radical ideal and thus

√ I = R √ I.
The last point follows from the second point and the property of the Krull dimension: dim

R[X] I = dim R[X] √ I .
We will then use R supp Q to denote both the radical and the real radical of supp Q.

The real radical ideals can be used to describe the polynomials vanishing on a semialgebraic or algebraic set.

Theorem 1.3 (Real Nullstellensatz, [Mar08, note 2.2.2 (vi)]). Let S = S(g) be a basic closed semialgebraic set. Then for f ∈ R[X], f = 0 on S if and only if f ∈ R supp O(g). In other words,

I (S) = R supp O(g).
In particular, for an ideal

I ⊂ R[X] we have I (V R (I)) = R √ I.
The preordering O(g) can be replaced with the quadratic module Q(g) when the Krull dimension of the quotient

R[X] supp Q(g) is ≤ 1, as shown in the book of Marshall. Theorem 1.4 ([Mar08, cor. 7.4.2 (3)]). If dim R[X] supp Q(g) ≤ 1, then I (S) = R supp Q(g).
We will often use Theorem 1.4 in the case dim

R[X] supp Q(g) = 0.

Finite Convergence and Exactness

We describe now Lasserre SoS and MoM relaxations [START_REF] Lasserre | Global Optimization with Polynomials and the Problem of Moments[END_REF], and we define the exactness property. Hereafter we assume that the minimum f * of the objective function f is always attained on S, that is:

S min { x ∈ S | f (x) = f * } ∅.

Polynomial optimization relaxations

Lasserre's SoS relaxations. We define the SoS relaxation of order d of problem (1) as Q 2d (g) and the supremum:

f * SoS,d sup λ ∈ R | f -λ ∈ Q 2d (g) . ( 2
)
When necessary we will replace g by Πg (that is Q(g) by O(g)).

Lasserre's MoM ralaxations. To define the dual approximation of the polynomial optimization problem, we consider an affine hyperplane section of the cone L 2d (g):

L (1) 2d (g) σ ∈ L 2d (g) | σ |1 = 1 .
This will be the set of feasible (pseudo-)moment sequences of the MoM relaxation of order d. Notice that L 2d (g) is the cone over L

(1) 2d (g), since for σ ∈ L 2d (g) we have σ |1 = 0 ⇒ σ = 0 (see [Las+13, lem. 3.12]), and σ ∈ L 2d (g) 0 implies 1 σ |1 σ ∈ L

(1) 2d (g). The convex sets L

(1) 2d (g) are spectrahedra: they are defined by the Linear Matrix Inequalities

H d 2 σ 0, H N 1 g 1 σ 0, . . . , H N r g r σ 0, where N i = d - deg g i 2
. The convex set L

(1) d (g) is also called the state space of (R[X] d , Q d (g), 1) in [START_REF] Kriel | On the Exactness of Lasserre Relaxations and Pure States Over Real Closed Fields[END_REF]. The pure states are the extreme points of this convex set.

With this notation we define the MoM relaxation of order d of problem (1) as L 2d (g) and the infimum:

f * MoM,d inf σ |f ∈ R | σ ∈ L (1)
2d (g) .

(3)

We easily verify that f * SoS,d ≤ f * MoM,d ≤ f * . When necessary we will replace g by Πg (that is Q(g) by O(g)).

When

S min := {ξ ∈ S | f (ξ) = f * } ∅, the infimum f * MoM,d is reached since L (1)
2d (g) is closed and bounded. We are interested, in particular, in the linear functionals that realize this minimum.

Definition 2.1. Consider the problem of minimizing f ∈ R[X] on S(g). We define the set of functional minimizers at relaxation order d as the σ minimizing (3), i.e.:

L min 2d (g) σ ∈ L (1) 2d (g) | σ |f = f * MoM,
* SoS,d ≤ f * MoM,d ≤ f * . Moreover, if f * MoM,d = f * then L min 2d (g) = { σ ∈ L (1) 2d (g) | σ |f = f * }.
Definition 2.3 (SoS Exactness). We say that the SoS relaxation (Q 2d (g)) d∈N is exact for f if it has the finite convergence property and for all d big enough, we have ff * ∈ Q 2d (g) (in other words sup = max in the definition of f * SoS,d ). For the moment relaxation we can ask the property that every truncated functional minimizer is coming from a measure: Definition 2.4 (MoM Exactness). We say that the MoM relaxation (L 2d (g)) d∈N is exact for f on the basic closed semialgebraic set S if:

• it has the finite convergence property, and • for every k ∈ N, there exists d = d(k) ∈ N such that every truncated functional minimizer is coming from a probability measure supported on S, i.e. L min 2d (g) [k] ⊂ M (1) (S) [k] . If not specified, S will be the semialgebraic set S = S(g) defined by g.

MoM exactness may be considered as a particular instance of the so called Moment Problem (i.e. asking if σ ∈ R[X] * is coming from a measure) or of the Strong Moment Problem (i.e. asking that the measure has a specified support). More precisely, MoM exactness can be considered as a Truncated Strong Moment Property (since we are considering functionals restricted to polynomials up to a certain degree).

Notice that in the definition we require the property L min 2d(k) (g) [k] ⊂ M (1) (S) [k] to hold for every k, and in general the fact that the property is verified for particular k does not imply that it is verified for every k.

We show now an example where we investigate the properties of finite convergence and exactness.

Example 2.5. Consider the problem of minimizing f = X 2 on the semialgebraic set S = S(g

) = S(1 -X 2 -Y 2 , X + Y -1) ⊂ R 2 defined by g 1 = 1 -X 2 -Y 2 and g 2 = X + Y -1.
Clearly, the minimum is f * = 0 and the only minimizer is (0, 1). Notice that f -

f * = X 2 ∈ Q 2 (1 -X 2 -Y 2 , X + Y -1) and therefore f * SoS,1 = f * MoM,1 = f * = 0,
we have finite convergence and the SoS relaxation is exact. We now investigate MoM exactness. If a truncated moment sequence σ is coming from a probability measure µ ∈ M (1) (S) such that f dµ = f * , then the support of µ should be contained in the set of minimizers S min = { (0, 1) } of f . Thus µ = e (0,1) is the evaluation at (0, 1) (or in other words, the Dirac measure concentrated at (0, 1)). Its moments are easily computed: µ 00 = 1, µ 10 = 0, µ 01 = 1, µ 20 = 0, . . . . Analyzing the constraints on the degree one and two moments of an optimal moment sequence σ ∈ L min 2 (g), where

L min 2 (g) = { σ ∈ R[X] * 2 | H 1 σ 0, H 0 g 1 σ 0, H 0 g 2 σ 0, σ |1 = 1, σ |f = f * = 0} = { σ ∈ R[X] * 2 |          σ 00 σ 10 σ 01 σ 10 σ 20 σ 11 σ 01 σ 11 σ 02          0, σ 00 -σ 20 -σ 02 ≥ 0, σ 10 + σ 01 -σ 00 ≥ 0, σ 00 = 1, σ 20 = 0},
we deduce that σ 00 = 1, σ 10 = 0, σ 01 = 1, σ 20 = 0, σ 11 = 0 and σ 02 = 1: this shows that the only element of

L min 2 (g) is σ = e [2]
(0,1) . In particular notice that σ X 2 = σ (Y -1) 2 = 0. For any order d ≥ 1 and any element σ ∈ L min 2d (g), its truncation σ [2] is in

L min 2 (g) since σ [2] X 2 = σ X 2 = 0. This implies that σ X 2 = σ (Y -1) 2 = 0 and that ∀p ∈ R[X] d , σ |X p = σ |(Y -1)p = 0. We deduce from Proposition 3.16 that the moments of σ [d] = e [d]
(0,1) are coming from the Dirac measure e (0,1) . Therefore the relaxation is MoM exact.

Another equivalent way to certify MoM exactness is to check flat truncation (see Definition 3.18). For σ ∈ L min 2d (g) with d ≥ 2, we have computed the moments of degree ≤ 2. Since the moment matrices in degree ≤ 2:

H 0 σ = 1 , H 1 σ =          1 0 1 0 0 0 1 0 1         
have the same rank, the flat extension property is satisfied. This certifies that σ [2] = e

[2] (0,1) is coming from a measure supported at the minimizer of f on S and the MoM relaxation is exact, see Theorem 4.1.

In practice, to check the finite convergence, one tests the flat extension or the flat truncation property of moment matrices (see [START_REF] Curto | Flat Extensions of Positive Moment Matrices: Recursively Generated Relations[END_REF], [START_REF] Laurent | A Generalized Flat Extension Theorem for Moment Matrices[END_REF], [START_REF] Nie | Certifying convergence of Lasserre's hierarchy via flat truncation[END_REF]). But flat truncation certifies MoM exactness, and not only finite convergence. We will investigate flat truncation for POPs in Section 4.

Notice that in the previous example the rank condition is satisfied by the full sequence of moments of σ ∈ L min 2 (g) (flat extension). In general this is not true, as the high degree moments may be increasing the rank of the moment matrix, see for in instance [Nie13b, ex. 1.1]. Therefore it is necessary to discard the high degree moments, i.e. to consider L min 2d (g) [t] , for some t ≤ 2d, instead of simply L min 2d (g). This implies that we look for rank conditions on the moment matrix of the truncated moment sequence (i.e. flat truncation).

We recall results of strong duality, i.e. cases when we know that f * SoS,d = f * MoM,d , that we will be using. See also Proposition 3.9.

Theorem 2.6 (Strong duality). Let Q = Q(g) be a quadratic module and f the objective function. Then:

(i) if supp Q = 0 then ∀d: f * SoS,d is attained (i.e. f -f * SoS,d ∈ Q d (g)) and f * SoS,d = f * MoM,d [Mar08, prop. 10.5.1]; (ii) if r 2 -X 2 ∈ g then f * SoS,d = f * MoM,d for all d [JH16].
Remark. [START_REF] Josz | Strong duality in Lasserre's hierarchy for polynomial optimization[END_REF] applies when the ball constraint r 2 -X 2 appears explicitely in the description of S.

But if we consider a problem with MoM finite convergence and such that Q(g) is Archimedean, then we can use [START_REF] Josz | Strong duality in Lasserre's hierarchy for polynomial optimization[END_REF] to prove that we have also SoS finite convergence. Indeed, if

Q(g) is Archimedean there exists r, d such that r 2 -X 2 ∈ Q 2t (g). This means that Q 2d (g, r 2 -X 2 ) ⊂ Q 2d+2t (g). If we define: • f * SoS,d = sup λ ∈ R | f -λ ∈ Q 2d (g) • f * SoS,d = sup λ ∈ R | f -λ ∈ Q 2d (g, r 2 -X 2 )
and f * MoM,d , f * MoM,d the corresponding MoM relaxations, then:

f * MoM,d ≤ f * MoM,d = f * SoS,d ≤ f * SoS,d+t ≤ f * .
Then finite convergence of the MoM relaxation implies finite convergence of the SoS one.

We recall that we are assuming S min ∅ (in particular f * is finite: otherwise it may happen that f * SoS,d = -∞). Notice that if strong duality holds, then SoS finite convergence is equivalent to MoM finite convergence.

Examples and counterexamples

In this section, we give examples showing how the notions of finite convergence and exactness of the SoS and MoM relaxations are (and are not) related.

No finite convergence. The first example shows that SoS and MoM relaxations for polynomial optimization on algebraic curves do not have necessarily the finite convergence property.

Example 2.7 ([Sch00]). Let C ⊂ R n be a smooth connected curve of genus ≥ 1, with only real points at infinity. Let h = {h 1 , . . . , h s } ⊂ R[X] be a graded basis of I = I (C) = (h) . Then there exists f ∈ R[X] such that the SoS relaxation Q 2d (±h) and the MoM relaxation L 2d (±h) have no finite convergence and are not exact.

Indeed by [Sch00, Theorem 3.2], there exists

f ∈ R[X] such that f ≥ 0 on C = S(±h), which is not a sum of squares in R[C] = R[X]/I. Consequently, f Σ 2 [X] + I = Q(±h). As f ≥ 0 on C, its infimum f * is non-negative and we also have f -f * Q(±h).
Using Proposition 3.9 we deduce that Q 2d (±h) is closed, that there is no duality gap and that the supremum f * SoS,d is reached. Thus if the SoS relaxation has finite convergence then ff * ∈ Q 2d (±h) for some d ∈ N. This is a contradiction, showing that the SoS and the MoM relaxations have no finite convergence and cannot be SoS exact for f . In dimension 2, there are also cases where the SoS and MoM relaxations cannot have finite convergence or be exact.

Example 2.8 ([Mar08]). Let g 1 = X 3 1 -X 2 2 , g 2 = 1 -X 1 . Then S = S(g) is a compact semialgebraic set of dimension 2 and O(g) is Archimedean. We have f = X 1 ≥ 0 on S but X 1 O(g) (see [Mar08, Example 9.4.6(3)]
). The infimum of f on S is f * = 0. Assume that we have MoM finite convergence. By Theorem 2.6 and remark below, Q 2d (Πg) is closed, the supremum f * SoS,d is reached and strong duality holds:

f * SoS,d = f * MoM,d = f * = 0 for d ∈ N big enough. Then f -f * = f ∈ O(g):
but this is a contradiction. Therefore, the relaxations Q 2d (Πg) and L 2d (Πg) cannot have finite convergence and thus cannot be exact for f = X 1 .

The next example shows that non-finite convergence and non-exactnesss is always possible in dimension ≥ 3.

Example 2.9. Let n ≥ 3. Let Q be an Archimedean quadratic module generated by g

1 , . . . , g s ∈ R[X] such that S(g) ⊂ R n is of dimension m ≥ 3 and let h be a graded basis of R supp Q (in particular h = 0 if supp Q = 0 or if m = n, i.e. S(Q) is of maximal dimension), then there exists f ∈ R[X]
such that the SoS relaxation (Q 2d (g, ±h)) d∈N and MoM relaxation (L 2d (g, ±h)) d∈N do not have the finite convergence property (and thus are not exact).

Indeed by Proposition 3.9

f * SoS,d = f * MoM,d for d big enough and the supremum f * SoS,d is reached. By [Sch00, Prop. 6.1] for m ≥ 3, Pos(S(g)) = Pos(S(Q + (h))) Q + (h). So let f ∈ Pos(S(Q)) \ Q + (h) and let f * be its minimum on S(Q). Suppose that f -f * ∈ Q + (h), then f ∈ Q + (h) + f * = Q + (h), a contradiction.
Then the SoS and the MoM relaxations do not have the finite convergence property (and they are not exact).

SoS exactness, no MoM exactness.

Example 2.10. We want to find the global minimum of [d] . Such a linear functional exists because when n > 2 there are non-negative polynomials in R[X ] which are not sum of squares, such as the Motzkin polynomial (see [START_REF] Reznick | Some Concrete Aspects Of Hilbert's 17th Problem[END_REF]). As

f = X 2 1 ∈ R[X 1 , . . . , X n ] = R[X] for n ≥ 3. Let d ≥ 2, X = (X 2 , . . . , X n ) and σ ∈ L 2d (Σ 2 [X ]) such that σ M(R n-1 )
Q 2d (Σ 2 [X ]) is closed, such a polynomial can be separated from Q 2d (Σ 2 [X ]) by a linear functional σ ∈ L 2d (Σ 2 [X ]
), which cannot be the truncation of a measure (i.e. Σ2 [X ] does not have the truncated moment property). Define σ :

h → σ |h = σ |h(0, X 2 , . . . , X n ) . We have σ ∈ L 2d (Σ 2 [X]) = Σ 2 [X] ∨ 2d since σ ∈ L 2d (Σ 2 [X ]) = Σ 2 [X ] ∨ 2d . Obviously σ |f = 0 = f * (the minimum of X 2 1 ), f -f * = X 2 1 ∈ Σ 2
and the SoS relaxation is exact. Since σ is coming from a measure if and only if σ is coming from a measure, the MoM relaxation cannot be exact.

The previous example generalizes easily to quadratic modules Q with supp(Q) {0}, which do not have the (truncated) moment property, i.e. there exists σ ∈ L 2d (Q) such that σ M(S(Q)) [2d] . Taking f = h 2 with h ∈ supp(Q), h 0, we have σ |f = 0 = f * and the MoM relaxation cannot be exact since σ M(S(Q)) [2d] , while the SoS relaxation is exact (f -

f * = h 2 ∈ Q).
Example 2.10 is an example where the number of minimizers of f on S is infinite. We show that non exactness can happen also when the minimizers are finite (and even when S is finite!).

Example 2.11 ([Sch05a, ex. 3.2], [Sch05b, rem. 3.15], Example 3.5). We want to minimize the constant function f = 1 on the origin

S = S(Q) = {0}, where Q = Q(1 -X 2 -Y 2 , -XY , X -Y , Y -X 2 ) ⊂ R[X, Y ]. In this case supp Q = R supp Q = (0)
. Notice that the SoS relaxation is exact and the MoM relaxation has finite convergence, since f is a square. Now suppose that the MoM relaxation is exact, i.e. L min 2d (g

) [2k] = L (1) 2d (g) [2k] ⊂ M (1) (S) [2k] = {e [2k]
0 } for some d, k. Then for σ * ∈ L 2d (g) generic we have (Ann k (σ * )) = (Ann k (e 0 )) = (X, Y ). But from Theorem 3.12 we know that for d, k big enough (Ann k (σ * )) = R supp Q = (0), a contradiction. Then the MoM relaxation is not exact. Moreover the flat truncation property is not satisfied in this case: see Theorem 4.4. We investigate concretely this example for d = 1. We show in Figure 1 2 the plot of L 2 (g) [1] , that is the moments of degree one of the the linear functionals in dual cone of Q 2 (g). Notice that this is an outer approximation of e (0,0) ∈ L 2 (g) [1] or, identifying moments of degree one with points of R n , a convex outer approximation of S = {(0, 0)}.

One can also verify explicitly that L 2 (g) has nonempty interior, since σ = σ (ε) defined by σ 10 = 2ε, σ 01 = ε, σ 20 = ε 2 , σ 11 = -ε 2 and σ 02 = 1 2 lies in the interior of L 2 (g) for ε > 0 small enough. Notice that L 2 (g) [1] ⊃ L 3 (g) [1] ⊃ L 4 (g) [1]

⊃ • • • ⊃ {e [1]
(0,0) }, and we have convergence in this case since Q(g) is Archimedean. This nested outer approximations, shown in Figure 1 2 , never coincide with {e

[1] (0,0) }, as we have proven before.

SoS finite convergence, MoM exactness.

Example 2.12. [START_REF] Nie | Minimizing Polynomials via Sum of Squares over the Gradient Ideal[END_REF]). By Theorem 4.10 the flat truncation is satisfied and the MoM relaxation is exact, and by Theorem 2.6 and remark below the SoS has the finite convergence property (notice that

Let f = (X 4 Y 2 + X 2 Y 4 + Z 6 -2X 2 Y 2 Z 2 ) + X 8 + Y 8 + Z 8 ∈ R[X, Y , Z]. We want to optimize f over the gradient variety V R ∂f ∂X , ∂f ∂Y , ∂f ∂Z which is zero dimensional (see
Q(± ∂f ∂X , ± ∂f ∂Y , ± ∂f ∂Z ) = O(± ∂f ∂X , ± ∂f ∂Y , ± ∂f ∂Z ) is Archimedean since V R ∂f ∂X , ∂f ∂Y , ∂f ∂Z is compact). But the SoS relaxation is not exact, as shown in [NDS06].
Example 2.13. Let f = X 1 . We want to find its value at the origin, defined by X 2 = 0. As proved in [START_REF] Nie | Polynomial Optimization with Real Varieties[END_REF] there is finite convergence but not exactness for the SoS relaxation. On the other hand by Theorem 4.10 the flat truncation property is satisfied and the MoM relaxation is exact. (1) 2 (g) [1] and moment outer approximations of L (1) (g) [1] = {e We summarize the previous examples in Table 1 in terms of the properties of finite convergence (SoS f.c. and MoM f.c.) exactness (SoS ex. and MoM ex.) and the dimension m of the semialgebraic set S.

Geometry of Moment Representations

By Haviland's theorem (see [START_REF] Marshall | Positive Polynomials and Sums of Squares[END_REF]th. 3.1.2] and [Sch17, th. 1.12]) an infinite moment sequence or a linear functional σ ∈ (R[X]) * comes from a measure, if and only if σ is positive on positive polynomials. Since checking this is a computationally hard task, a motivation supporting Sum of Squares relaxations is to find (proper) subsets of positive polynomials that can have the same property, chosen in such a way that checking this condition is easy. Important results in this direction are theorems of Schmüdgen and Putinar. However, describing effectively complete moment sequences in L(Q) remains a challenging problem since L(Q) is an infinite dimensional cone. Therefore, it is natural to consider truncated moment problems in order to work in finite dimensional vector spaces. But the cones of truncated moment sequences do not share the properties of the truncated cones of complete moment sequences and special cares are needed.

In this section, we analyze in detail the properties of these finite dimensional truncated cones of moment sequences. We provide a new and explicitly description of the dual of the hierarchy of truncated moment sequences, in terms of a quadratic module (Theorem 3.4), and consequently prove properties of the cones L d (g) (Lemma 3.6) and of their generic elements (Theorem 3.12).

Finally we apply these results to the zero dimensional case (Theorem 3.21) and we investigate the connections with the flat truncation property (Section 3.3).

Truncated moment representations

For a finitely generated quadratic module

Q = Q(g) ⊂ R[X], we have L k (g) = Q k (g) ∨ = Q k (g) ∨ and L k (g) ∨ = Q k (g)
, where ∨ denotes the dual cone and the closure is taken w.r.t. the euclidean topology on R[X] k . Thus the following definition is natural for the study of the MoM relaxations. Definition 3.2. Let Q = Q(g) be a finitely generated quadratic module. We define

Q = d Q d (g).
Notice that Q depends a priori on the generators g of Q: we will prove that Q is a finitely generated quadratic module and that it does not depend on the particular choice of generators. Moreover notice that

Q ⊂ Q = d Q d (g) ⊂ d Q k (g) = Q, but these inclusions can be strict. Lemma 3.3. Let Q = Q(g) and J = R supp Q. Then for every d ∈ N there exists k ≥ d such that J d ⊂ Q k (g). Proof. We denote Q d (g) = Q [d] . Let m be big enough such that ∀f ∈ J = R supp Q = supp Q we have: f 2 m ∈ supp Q (if √ J = (h 1 , . . . , h t ) and h a i i ∈ I, we can take m such that 2 m ≥ a 1 + • • • + a t ). Let f ∈ J d with deg f ≤ d. Then f 2 m ∈ supp Q [k ] ⊂ Q [k ] for k ∈ N big enough. Using the identity [Sch05b, remark 2.2]: m -a = (1 - a 2 ) 2 + (1 - a 2 8 ) 2 + (1 - a 4 128 ) 2 + • • • + (1 - a 2 m-1 2 2 m -1 ) 2 - a 2 m 2 2 m+1 -2 , substituting a by - mf ε and multiplying by ε m , we have that ∀ε > 0, f + ε ∈ Q [k] for k = max{k , 2 m d} (the degree of the representation of f + ε does not depend on ε). This implies that f ∈ Q [k] .
We can now describe Q.

Theorem 3.4. Let Q = Q(g) be a finitely generated quadratic module and let J = R supp Q. Then Q = Q + J and supp Q = J. In particular, Q is a finitely generated quadratic module and does not depend on the particular choice of generators of Q.

Proof. We denote Q d (g) = Q [d] . By [Mar08, lemma 4.1.4] Q [d] + J d is closed in R[X] d , thus Q [d] ⊂ Q [d] + J d . Taking unions we prove that Q ⊂ Q + J.
Conversely by Lemma 3.

3 for d ∈ N and k ≥ d ∈ N big enough, J d ⊂ Q [k]
. Then, we have

Q [d] + J d ⊂ Q [k] + Q [k] ⊂ Q [k] + Q [k] ⊂ Q [k] . Taking unions on both sides gives Q + J ⊂ Q. Finally supp Q = supp(Q + J) = J by [Sch05b, lemma 3.16].
Remark. We proved that

Q = Q + R supp Q. We also have supp Q = R supp Q so that if supp Q is not real radical then Q Q. Example 2.
13 is such a case where supp Q R supp Q. We notice that, by Theorem 3.4 and [Sch05b, th. 3.17], if

Q is stable 3 then Q = Q. But the inclusion Q = Q + supp Q ⊂ Q can be
strict, as shown by the following example.

Example 3.5 ([Sch05a, ex. 3.2], [Sch05b, rem. 3.15], Example 2.11). Let Q = Q(1-X 2 -Y 2 , -XY , X - Y , Y -X 2 ) ⊂ R[X, Y ]. Notice that S = S(Q) = {0}
and that Q is Archimedean. Therefore by Theorem 3.1, Q = Pos({0}). We verify that supp Q = (0) and that

I (S) = supp Q = (X, Y ). Thus we have Q + supp Q = Q Q.
Theorem 3.4 suggests the idea that, when we consider the MoM relaxation, we are extending the quadratic module Q(g) to Q(g, ±h), where h are generators of R supp Q(g). We specify this idea in Lemma 3.6, Proposition 3.9 and Theorem 3.12, investigating the relations between the truncated parts of L d (g).

Lemma 3.6.

Let J = R supp Q(g). If (h) ⊂ J, deg h ≤ t, then ∃d ≥ t such that h t ⊂ Q d (g).
In this case:

L d (g) [t] ⊂ L t (g, ±h) ⊂ L t (g),
and in particular L d (g) [t] ⊂ L t (±h). Moreover, L d+2k (g) [t+k] ⊂ L t+k (±h) for all k ∈ N.

Proof. By Lemma 3.3, h t ⊂ (h) t ⊂ Q d (g) for some d ≥ t. Let h ∈ h and f ∈ R[X] t-deg h . Then ±f h ∈ Q d (g)
, and for σ ∈ L d (g), we have σ [t] f h = σ |f h = 0, i.e. L d (g) [t] ⊂ L t (g, ±h). The other inclusion L t (g, ±h) ⊂ L t (g) follows by definition.

For the second part, notice that h t+k ⊂ Q d+2k (g). Indeed, if p ∈ h t+k then p = i X α(i) p i , where

p i ∈ h t ⊂ Q d (g) and |α(i)| ≤ k. Writing X α(i) = ( X α(i) +1 2 ) 2 -( X α(i) -1 2 ) 2 , we deduce that p = i ( X α(i) +1 2 ) 2 p i + ( X α(i) -1 2 ) 2 (-p i ) ∈ Q d+2k (g), i.e. h t+k ⊂ Q d+2k (g).
Then we can conclude the proof as in the first part.

Remark. Lemma 3.6 says that the MoM relaxation (L 2d (g)) d∈N is equivalent to the MoM relaxation (L 2d (g, ±h)) d∈N , where (h) = R supp Q(g). Lemma 3.6 is an algebraic result, in the sense that supp Q(g) may be unrelated to the geometry S(g) that g defines. If some additional conditions hold (namely if we have only equalities, or a preordering, or a small dimension), it can however provide geometric characterizations.

Corollary 3.7. Suppose that S(g) ⊂ V R (h). Then for every t 0 ≥ deg h there exists t 1 ≥ t 0 such that:

L t 1 (Πg) [t 0 ] ⊂ L t 0 (±h).
In particular this holds when (h) = I (S(g)).

Moreover, L t 1 +2k (g) [t 0 +k] ⊂ L t 0 +k (±h) for all k ∈ N.

Proof. S(g) ⊂ V R (h) if and only if R (h) ⊂ I (S(g)) = R supp Q(Πg)
by the Real Nullstellensatz, Theorem 1.3. Then we can apply Lemma 3.6.

Corollary 3.8. Let Q = Q(g). Suppose that S(g) ⊂ V R (h) and dim R[X]
supp Q ≤ 1. Then for every t 0 ≥ deg h there exists t 1 ≥ t 0 such that (h) t 0 ⊂ Q t 1 (g). In this case:

L t 1 (g) [t 0 ] ⊂ L t 0 (±h),
ans in particular this holds when (h) = I (S(g)).

Moreover, L t 1 +2k (g) [t 0 +k] ⊂ L t 0 +k (±h) for all k ∈ N.

Proof. We prove it as Corollary 3.7, using Theorem 1.4 instead of the Real Nullstellensatz.

We mention now a strong duality result, that is useful to produce examples and counterexamples for exactness and finite convergence, This result, very similar to a result in [START_REF] Marshall | Optimization of Polynomial Functions[END_REF], generalizes the condition supp Q = 0 in Theorem 2.6. We conjecture that there is no duality gap when Q is reduced (i.e. supp Q = R supp Q) without adding the generators of the radical of the support. Proposition 3.9. Let Q = Q(g) be a finitely generated quadratic module, and let h be a graded basis of R supp Q. Then for any d we have

Q d (g, ±h) = Q d (g, ±h) is closed. Moreover, if we consider the extended relaxations Q 2d (g, ±h) and L 2d (g, ±h), then for any f ∈ R[X] such that f * > -∞ we have that f * SoS,d is attained (i.e. f -f * SoS,d ∈ Q 2d (g, ±h)
) and there is no duality gap:

f * SoS,d = f * MoM,d . Proof. By [Mar08, lemma 4.1.4], Q 2d (g, ±h) = Q 2d (g)+I 2d is closed. Therefore we have L 2d (g, ±h) ∨ = (Q 2d (g, ±h)) ∨∨ = Q 2d (g, ±h) = Q 2d (g, ±h)
, from which we deduce that there is not duality gap, by classical convexity arguments, as follows.

If

f ∈ R[X] such that f * > -∞, then λ ∈ R | f -λ ∈ Q 2d (g, ±h) is bounded from above. Since Q 2d (g, ±h) is closed f * SoS,d = sup λ ∈ R | f -λ ∈ Q 2d (g, ±h) is attained. If f * SoS,d < f * MoM,d , then f -f * MoM,d Q 2d (g, ±h)
. Thus there exists a separating functional σ ∈ L

Annihilators of truncated moment sequences

Recall that the annihilator Ann t (σ ) is the kernel of the moment matrix of σ (or of the Hankel operator). With the characterization of Q we can now describe these kernels of moment matrices associated to truncated positive linear functionals. We recall the definition of genericity in the truncated setting and equivalent characterizations.

Definition 3.10. We say that

σ * ∈ L d (g) is generic if rank H d σ * = max{rank H d η | η ∈ L d (g)}.
This genericity can be characterized as follows, see [START_REF] Lasserre | Moment matrices, border bases and real radical computation[END_REF]prop. 4.7].

Proposition 3.11. Let σ ∈ L 2d (g). The following are equivalent:

(i) σ is generic; (ii) Ann d (σ ) ⊂ Ann d (η) ∀η ∈ L 2d (g); (iii) ∀d ≤ d, we have: rank H d σ = max{rank H d η | η ∈ L 2d (g)}.
Remark. By Proposition 3.11 notice that ∀d ≤ d, if σ * ∈ L 2d (g) is generic then (σ * ) [2d ] is generic in L 2d (g) [2d ] . In particular, Ann

d (σ * ) ⊂ Ann d (η) ∀η ∈ L 2d (g).
The linear functionals in the relative interior of L d (g) are generic. If we use an SDP solver based on interior point method we will (approximately) get a moment sequence in the relative interior of the face L 2d (g) ∩ { σ |f = f * MoM,d }, which is then generic in this face. We will use generic linear functionals to recover the minimizers when we have exactness or the flat truncation property.

We are now ready to describe the annihilator of generic elements.

Theorem 3.12.

Let Q = Q(g) and J = R supp Q. Then for all d, t ∈ N big enough and for σ * ∈ L d (g) generic, we have J = (Ann t (σ * )). Moreover if Q = O is a preordering, then (Ann t (σ * )) = I(S(g)).
Proof. Let t ∈ N such that J is generated in degree ≤ t, by the graded basis h = h 1 , . . . , h s . From Lemma 3.3 we deduce that there exists d ∈ N such that

J 2t ⊂ Q d (g). Let σ * ∈ L d (g) generic.
We first prove that J ⊂ (Ann t (σ * )). By Proposition 3.11 we have Ann t (σ * ) = σ ∈L d (g) Ann t (σ ). Then it is enough to prove that J t ⊂ Ann t (σ ) for all σ ∈ L d (g).

By Lemma 3.6

L d (g) [2t] ⊂ L 2t (±h) ⊂ h ⊥ 2t . Then ∀f ∈ J t = h t , ∀p ∈ R[X] t , ∀σ ∈ L d (g), we have f p ∈ h 2t and σ [2t] f p = 0. This shows that H t σ (f )(p) = (f σ ) [t] p = σ |f p = 0, i.e. f ∈ Ann t (σ ) = ker H t σ . Conversely, we show that (Ann t (σ * )) ⊂ J for σ * generic in L d (g). Since J = supp Q = supp j Q j (g) (by Theorem 3.4) it is enough to prove that Ann t (σ * ) ⊂ Q d (g) ∩ -Q d (g) = supp Q d (g) = supp L d (g) ∨ .
Let f ∈ Ann t (σ * ) = σ ∈L k (g) Ann t (σ ) (we use again Proposition 3.11) and let σ ∈ L d (g). Then

σ |f = (f σ ) [t] 1 = H t σ (f )(1) = 0. In particular f ∈ L d (g) ∨ . We prove that -f ∈ L d (g) ∨ in the same way. Then f ∈ L d (g) ∨ ∩ -L d (g) ∨ = Q d (g) ∩ -Q d (g) = supp Q d (g)
, and finally we deduce from Definition 3.10 and Theorem 3.4 that Ann t (σ * ) ⊂ supp Q = J.

The second part follows from the first one and the Real Nullstelensatz, Theorem 1.3.

Theorem 3.12 shows the possibilities and the limits of MoM relaxations. For instance we cannot expect exactness of the MoM relaxation L 2d (g) for any objective function f (i.e. L 2d (g) [k] ⊂ M(S) [k] ) if R supp Q I (S): see Example 2.11.

In Proposition 3.13 we investigate the infinite dimensional case. We say that σ * ∈ L(Q) = Q ∨ is generic if Ann(σ * ) ⊂ Ann(σ ) for all σ ∈ L(Q), using Proposition 3.11 to have the analogy with the finite dimensional case. Proposition 3.13. Let Q be a quadratic module, S = S(Q) and σ * ∈ L(Q) = Q ∨ be generic. Then R supp Q ⊂ Ann(σ * ) ⊂ I (S). Moreover:

(i) if Q is Archimedean then Ann(σ * ) = I (S); (ii) if Q = O is a preordering, Ann(σ * ) = I (S); (iii) if I is an ideal of R[X] and σ * ∈ L(I) is generic, then Ann(σ * ) = R √ I.
Proof. For x ∈ S, notice that e x ∈ L(Q). Then, since σ * is generic: As L(I) = L(I + Σ 2 ), the last point follows from the previous one applied to

Ann(σ * ) ⊂ x∈S Ann(e x ) =
O = I + Σ 2 .
If we compare Theorem 3.12 and Proposition 3.13, we see that the description in the infinite dimensional setting is more complicated, as we don't always have the equality Ann(σ * ) = R supp Q, see the case of an Archimedean quadratic module. This happens because limit properties that appear in the infinite dimensional case do not show up in the truncated setting.

Regularity, moment sequences and flat truncation

In this section, we analyze the properties of moment sequences in L d (g) when S = S(g) is finite. We will use the results in this section to study the case of finitely many minimizers in Polynomial Optimization problems, and in particular flat truncation.

Let Ξ = {ξ 1 , . . . , ξ r } ∈ C n be a finite set of (complex) points and let I (Ξ) = { p ∈ C[X] | p(ξ i ) = 0 ∀i ∈ 1, . . . , r } be the complex vanishing ideal of the points Ξ. The Castelnuovo-Mumford regularity of an ideal I (resp. Ξ) is max i (deg S ii) where S i is the i th module of syzygies in a minimal resolution of I (resp. I (Ξ)). Let denote it by ρ(I) (resp. ρ(Ξ)).

It is well known that Ξ admits a family of interpolator polynomials (u i ) ⊂ C[X] such that u i (ξ j ) = δ i,j . The minimal degree ι(Ξ) of a family of interpolator polynomials is called the interpolation degree of Ξ. Since a family of interpolator polynomials (p i ) is a basis of C[X]/I (Ξ), the ideal I (Ξ) is generated in degree ≤ ι(Ξ) + 1 and ρ(Ξ) ≤ ι(Ξ) + 1. A classical result [Eis05, th. 4.1] relates the interpolation degree of Ξ with its regularity, and the minimal degree of a basis of C[X]/I (Ξ). This result can be stated as follows, for real points Ξ ⊂ R n : Proposition 3.14. Let Ξ = {ξ 1 , . . . , ξ r } ⊂ R r with regularity ρ(Ξ). Then the minimal degree ι(Ξ) of a basis of R[X]/I (Ξ) is ρ(Ξ) -1 and there exist interpolator polynomials u 1 , . . . , u r ∈ R[X] ρ(Ξ)-1 .

Another property that we will use is the following:

Proposition 3.15 ([BS87]). Any ideal I ⊂ R[X] has a graded basis in degree less than or equal to its regularity ρ(I).

In particular, for a set of points Ξ = {ξ 1 , . . . , ξ r }, the ideal I (Ξ) has a graded (resp. Grobner, resp. border) basis of degree equal to the regularity ρ(Ξ). The minimal degree of a monomial basis B of R[X]/I (Ξ) is ι(Ξ) = ρ(Ξ) -1. Such a finite basis B can be chosen so that it is stable by monomial division.

The next result shows that (resp. positive) moment sequences orthogonal to the vanishing ideal of the points, truncated above twice the regularity are coming from (resp. positive) measures: Proposition 3.16. Let Ξ = {ξ 1 , . . . , ξ r } ⊂ R n , I = I (Ξ) its real vanishing ideal and let ρ = ρ(Ξ) the regularity of Ξ. Proof. Let u 1 , . . . , u r ∈ R[X] t be interpolation polynomials of degree ≤ ρ -1 ≤ t (Proposition 3.14). Consider the sequence of vector space maps:

For t ≥ ρ -1, σ ∈ I ⊥ t if
0 → I t → R[X] t ψ -→ u 1 , . . . , u r → 0 p → r i=1 p(ξ i )u i , which is exact since ker ψ = {p ∈ R[X] t | p(ξ i ) = 0} = I t . Therefore we have R[X] t = u 1 , . . . , u r ⊕ I t . Let σ ∈ I ⊥ t . Then σ = σ -r i=1 σ |u i e [t] ξ i ∈ I ⊥ t is such that σ |u i = 0 for i = 1, . . . , r. Thus, σ ∈ u 1 , . . . , u r ⊥ ∩ I ⊥ t = ( u 1 , . . . , u r ⊕ I t ) ⊥ = R[X] ⊥ t , i.e. σ = 0 showing that I ⊥ t ⊂ e [t] ξ 1 , . . . , e [t]
ξ r . The reverse inclusion is direct since I t is the space of polynomials of degree ≤ t vanishing at ξ i for i = 1, . . . , r.

Assume that t ≥ ρ -1 and σ ∈ L 2t (I 2t ). Then σ ∈ I ⊥ 2t and σ p 2 ≥ 0 for any p ∈ R[X] t . By the previous analysis,

σ = r i=1 ω i e [2t] ξ i As 0 ≤ σ u 2 i = ω i for i = 1, . . . , r, we deduce that σ ∈ cone(e [t] ξ 1 , . . . , e [t]
ξ r ). We verify that the image of

H t σ : p ∈ R[X] t → r i=1 ω i p(ζ i ) e [t] ξ i is e [t] ξ 1 , . . . , e [t] ξ r , computing H t σ (u i ) for i = 1, . . . , r. Thus rank H t σ = dim e [t] ξ 1 , . . . , e [t] ξ r = r since (e [t]
ξ i ) i=1,...,r is the dual basis of (u i ) i=1,...,r .

We deduce another corollary, giving degree bounds for the case of a graded basis of a real radical ideal. Proposition 3.17. Let I = R √ I be a real radical ideal and h = h 1 , . . . , h m be a graded basis of I. Then for all d ≥ max i (deg h i ) and σ * ∈ L 2d (±h) generic, we have Ann d (σ * ) = I d .

Proof. Let d ≥ max i (deg h i ) and σ * ∈ L 2d (±h) generic. Then for all i we have (h i σ * ) [d-deg h i ] = 0. Now let p ∈ I d . Since h is a graded basis we have p = m i=1 p i h i , where deg

p i ≤ d -deg h i . Notice that (p σ * ) [d] = m i=1 (p i (h i σ *
)) [d] . As (h i σ * ) [d-deg h i ] = 0 we conclude (p σ * ) [d] = 0 and thus p ∈ Ann d (σ * ). Therefore

I d ⊂ Ann d (σ * ).
Conversely, let p ∈ Ann d (σ * ). For all ξ ∈ V (I) we have e We describe now a property, known as flat truncation, which allows to test effectively if truncated moment sequences are coming from sums of evaluations. This definition coincides with the definition of flat truncation used in [START_REF] Curto | Solution of the Truncated Complex Moment Problem for Flat Data[END_REF], [START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF] or [START_REF] Nie | Certifying convergence of Lasserre's hierarchy via flat truncation[END_REF]. We investigate more in detail rank conditions for the moment matrix of σ ∈ L d (g).

Lemma 3.19. If σ ∈ L d (g) is such that rank H t σ = rank H t+s σ = r with t + 1 ≤ t + s ≤ d 2 , then σ [t+s+ d 2 ] = ω 1 e [t+s+ d 2 ] ξ 1 + • • • + ω r e [t+s+ d 2 ] ξ r
for some points ξ i ∈ R n and weights ω i > 0, i = 1, . . . , r. Denoting Ξ = {ξ 1 , . . . , ξ r }, we also have Ann t+1 (σ ) = I (Ξ) t+1 and V (Ann t+1 (σ )) = Ξ (or, in other words, (Ann t+1 (σ )) = I (Ξ)).

Moreover, if t ≤ d 2 + sdeg(g), where deg(g) = max i=1,...,s deg(g i ), the inclusion Ξ ⊂ S(g) holds true. Proof. From [Lau09, th. 5.29], there exists unique Ξ = {ξ 1 , . . . , ξ r } ⊂ R n and ω 1 , . . . , ω r > 0 such that σ

[2(t+s)] = ω 1 e [2(t+s)] ξ 1 + • • • + ω r e [2(t+s)] ξ r
, (Ann t+s (σ )) = I (Ξ) and V (Ann t+s (σ )) = Ξ. In particular (Ann t+s (σ )) is a zero dimensional ideal and Ann t+s (σ ) ⊂ I(Ξ) t+s . Conversely, for any h ∈ I(Ξ) t+s , we have

σ h 2 = σ [2(t+s)] h 2 = r i=1 ω i e [2(t+s)] ξ i h 2 = r i=1 ω i h 2 (ξ i ) = 0.
Thus h ∈ Ann t+s (σ ) (see see [START_REF] Lasserre | Moment matrices, border bases and real radical computation[END_REF]lem. 3.12]) and I(Ξ) t+s = Ann t+s (σ ).

As rank H t σ = rank H t+1 σ = r, we deduce from above, that (Ann t+1 (σ )) = I(Ξ) is generated in degree ≤ t + 1 and that ρ(Ξ) ≤ t + 1. Therefore Ξ has interpolator polynomials u 1 , . . . , u r of degree ≤ t.

Let us show that the description of σ on polynomials of degree ≤ 2(t + s), can be extended to higher degree. For any h ∈ Ann t+s (σ ) = I(Ξ) s+t , i.e. such that σ h 2 = 0, and any p ∈ R[X] d 2 we have σ |hp = 0. This shows that σ ∈ (I (Ξ) t+s+ d 2 ) ⊥ . We deduce from Proposition 3.16 that

σ [t+s+ d 2 ] ∈ cone(e ξ 1 , . . . , e ξ r ) [t+s+ d 2 ] . This implies that σ [t+s+ d 2 ] = ω 1 e [t+s+ d 2 ] ξ 1 + • • • + ω r e [t+s+ d 2 ] ξ r
, evaluating

σ |u i = σ [t+s+ d 2 ] u i = ω i at the interpolator polynomials u 1 , . . . u r of Ξ of degree ≤ t. We show now that Ξ = {ξ 1 , . . . , ξ r } ⊂ S if t ≤ d 2 + s -deg(g)
. For i = 1, . . . , r and j = 1, . . . , m the polynomial u 2 i g j has degree ≤ 2t + deg(g)

≤ t + s + d 2 .
Then we obtain:

0 ≤ σ u 2 i g j = σ [t+s+ d 2 ] u 2 i g j = ω 1 e [t+s+ d 2 ] ξ 1 + • • • + ω r e [t+s+ d 2 ] ξ r u 2 i g j = g j (ξ i ),
showing that g j (ξ i ) ≥ 0 for all i and j, i.e. Ξ ⊂ S(g).

Remark. Lemma 3.19 can be used to test flat truncation in a simpler way when d is big, as we explain in the following. Assume for simplicity that 2d g = deg(g .

We now show that we can use flat truncation to describe semialgebraic sets with a finite number of points.

Theorem 3.20. If a positive linear functional σ

* ∈ L d (g) is such that (σ * ) [2(t+d g )] is generic in L d (g) [2(t+d g )]
(that is Ann t+d g (σ * ) ⊂ Ann t+d g (σ ) for all σ ∈ L d (g)) and σ * satisfies the flat truncation property at degree t ≤ d 2d g , then: (i) S = S(g) = {ξ 1 , . . . , ξ r } is non-empty and finite;

(ii) L d (g) [t+d g + d 2 ] = cone(e ξ 1 , . . . , e ξ r ) [t+d g + d 2 ] ;
(iii) t + 1 ≥ ρ(ξ 1 , . . . , ξ r ) and Ann t+1 (σ * ) = I (ξ 1 , . . . , ξ r ) t+1 = I (S) t+1 is the vanishing ideal of S truncated in degree t + 1.

(iv) I (S) 2(t+d g ) ⊂ Q d (g) and (Ann t+1 (σ * )) = R supp Q(g) = I (S). Proof. Let σ * ∈ L d (g) be such that (σ * ) [2(t+d g )] is generic in L d (g) [2(t+d g )] ,
and assume that rank

H t σ * = rank H t+d g σ * with t ≤ d 2 -d g . By Lemma 3.19 applied with s = d g , (σ * ) [t+d g + d 2 ] = ω 1 e [t+d g + d 2 ] ξ 1 + • • • + ω r e [t+d g + d 2 ] ξ r
with ω i > 0, Ξ = {ξ 1 , . . . , ξ r } ⊂ S, Ann t+1 (σ * ) = I(Ξ) t+1 and (Ann t+1 (σ * )) = I(Ξ).

Let h = h 1 , . . . , h m ⊂ Ann t+1 (σ * ) be a graded basis of I(Ξ) of degree ≤ t + 1. As (σ * ) [2(t+d g )] is generic, for any σ ∈ L d (g) we have Ann t+d g (σ * ) ⊂ Ann t+d g (σ ) and σ h 2 i = 0. Then for any .

p ∈ R[X] d g + d 2 we have σ |h i p = 0, proving that σ ∈ (h) ⊥ t+d g + d 2 = (I (Ξ) t+d g + d 2 ) ⊥ , i.e. L d (g) [t+d g + d 2 ] ⊂ (I (Ξ) t+d g + d 2 ) ⊥ .
Let us show that Ξ = S. For ζ ∈ S we have e

[t+d g + d 2 ] ζ ∈ L d (g) [t+d g + d 2 ] ⊂ (h) ⊥ t+d g + d 2
, and thus for

i = 1, . . . , m, e ζ h i = h i (ζ) = 0. This shows that ζ is a root of h and thus ζ ∈ Ξ. We conclude that Ξ = {ξ 1 , . . . , ξ r } = S. The inclusion I (S) 2(t+d g ) ⊂ Q d (g) follows from L d (g) [t+d g + d 2 ] ⊂ (h) ⊥ t+d g + d 2 . Indeed 2(t + d g ) ≤ t + d g + d 2 and thus L d (g) [2(t+d g )] ⊂ (h) ⊥ 2(t+d g ) . Now notice that (L d (g) [2(t+d g )] ) ∨ ⊂ Q d (g), using convex duality. Therefore dualizing L d (g) [2(t+d g )] ⊂ (h) ⊥
2t we obtain the desired inclusion. Moreover This theorem tells us that if the flat truncation property holds at degree t ≤ d 2d g , then any element of L d (g) truncated in degree t + d 2 + d g coincides with a positive measure supported in S = {ξ 1 , . . . , ξ r }.

I (S) 2(t+d g ) ⊂ Q d (g) ∩ -Q d (g) ⊂ supp Q = R supp Q, by
In the following theorem we show that when supp(Q) is a zero-dimensional ideal (and thus S is finite), the rank condition is satisfied for any moment matrix.

Theorem 3.21. Suppose that dim R[X] supp Q(g) = 0. Then S = S(g) is finite and there exists d ≥ 2(ρ -1 + d g ) such that I (S) 2(ρ-1+d g ) ⊂ supp Q d (g)
, where ρ = ρ(S) is the regularity of S, and for any σ ∈ L d (g) the flat truncation property holds at degree ρ -1.

Proof. Let I = supp Q(g) and J = R supp Q(g). From Lemma 1.2 we deduce dim R[X] J = dim R[X] I = 0 and by Theorem 1.4 we have I (S(g)) = R supp Q(g) = J. Then V R (J) = V R (I (S(g))) = S(g) = {ξ 1 , . . . , ξ r } is finite.
We choose a graded basis h of J with deg h ≤ ρ = ρ(ξ 1 , . . . , ξ r ) (by Proposition 3.15). By Corollary 3.8, there exists d ∈ N such that I (S) 2(ρ-1+d g ) ⊂ supp Q d (g). From Corollary 3.8 and Proposition 3.16 we deduce that positive linear functionals in L d (g) restricted to degree ≤ 2(ρ -1 + d g ) are conical sums of evaluations at ξ 1 , . . . , ξ r :

L d (g) [2(ρ-1+d g )] ⊂ L 2(ρ-1+d g ) (±h) = L 2(ρ-1+d g ) (J 2(ρ-1+d g ) ) = cone(e ξ 1 , . . . , e ξ r ) [2(ρ-1+d g )] ,
and for all σ ∈ L d (g), we have rank

H ρ-1 σ = rank H ρ-1+d g σ . Theorem 3.21 says that if dim R[X]
supp Q(g) = 0 then the minimal order for which we have flat truncation is not bigger than d ≥ 2(ρ -1 + d g ) such that I (S) 2(ρ-1+d g ) ⊂ supp Q d (g). This degree is related to the minimal d for which I (S) = R supp Q(g) is generated by supp Q d (g), that is, the minimal degree d such that I(S) ρ-1+d g ⊂ Ann d 2 (σ * ) for a generic σ * ∈ L d (g). Moreover, as in the remark after Lemma 3.19, we can replace ρ -1 + d g with ρ if d is big enough. Theorem 3.21 and Theorem 3.20 show that if dim

R[X]
supp Q(g) = 0 then S is a finite set of points and for a high enough degree d, all moment sequences in L d (g), truncated in degree twice the regularity are coming from a weighted sum of Dirac measures at these points. In particular, it is possible to recover all the points in S from a generic truncated moment sequence, see [START_REF] Henrion | Detecting global optimality and extracting solutions in GloptiPoly[END_REF], [START_REF] Abril | Border Basis relaxation for polynomial optimization[END_REF] and [START_REF] Mourrain | Polynomial-Exponential Decomposition From Moments[END_REF].

Remark. There exist examples with S(g) finite and dim

R[X] supp Q(g) > 1, see Example 3.5. However the hypotheses (i) dim R[X] supp Q(g) = 0; and (ii) S(g) is finite and dim R[X] supp Q(g) ≤ 1; are equivalent: (i) ⇒ (ii) is shown in the proof of Theorem 3.21, while (ii) ⇒ (i) follows from I (S(g)) = R supp Q(g) (see Theorem 1.4).
Results related to Theorem 3.21 and Theorem 3.20 were obtained in [START_REF] Bernard Lasserre | Semidefinite Characterization and Computation of Zero-Dimensional Real Radical Ideals[END_REF] and [START_REF] Lasserre | Moment matrices, border bases and real radical computation[END_REF], where they focus on the case of equations h defining a finite real variety. They prove that, for d big enough and for every positive linear functional σ ∈ L 2d (±h), the flat truncation property holds for H d σ , and that σ [2d] is a conic linear combination of evaluations at the points of V R (h). This can be deduced from Theorem 3.21, since in the case where V R (h) = {ξ 1 , . . . , ξ r } is non-empty and finite, dim

R[X] supp Q(±h) = 0.
In [START_REF] Bernard Lasserre | Semidefinite Characterization and Computation of Zero-Dimensional Real Radical Ideals[END_REF]rem. 4.9] it is also mentioned that the same can be proved for a preordering defining a finite semialgebraic set. This result can also be deduced from Theorem 3.21, since when S = S(g) = {ξ 1 , . . . , ξ r } is non-empty and finite, we have by the Real Nullstellensatz , dim

R[X] supp O(g) = dim R[X] R √ supp O(g) = dim R[X]
I (S(g)) = 0. But Theorem 3.21 is more general, as shown by the following example of a quadratic module, whose support is zero dimensional, but that is not a preordering.

Example 3.22 ([Mar08, ex. 7.4.5 (1)]). Let Q = Q(X, Y , 1 -X, 1 -Y , -X 4 , -Y 4 ) ⊂ R[X, Y ].
In this case supp Q, which contains X 4 and Y 4 , is zero dimensional and Q is not a preordering since XY Q. Theorem 3.21 applies in this case, but the results cannot be deduced from [START_REF] Bernard Lasserre | Semidefinite Characterization and Computation of Zero-Dimensional Real Radical Ideals[END_REF] or [START_REF] Lasserre | Moment matrices, border bases and real radical computation[END_REF].

As we will see, in Polynomial Optimization problems, flat truncation implies MoM exactness and thus finite convergence. Moreover, it allows extracting the minimizers from an optimal sequence.

Flat truncation in polynomial optimization problems

In this section, we analyze when flat truncation occurs in the Polynomial Optimization Problem, which consists of minimizing f ∈ R[X] on the basic semialgebraic set S = S(g) where g = g 1 , . . . , g s is a tuple of polynomials. Recall that we denote f * the minimum of f on S. We will consider the semialgebraic set

S min = S(g, ±(f -f * )) = S(g) ∩ {x ∈ R n | f (x) = f * }
and assume that it is nonempty.

Flat truncation degree

Hereafter, we analyze the degree at which flat truncation holds and yields the minimizers.

Theorem 4.1. Consider the problem of minimizing f on S(g). If the flat truncation property holds for a generic σ * ∈ L min 2d (g) at a degree t such that deg(f )

-d g -d ≤ t ≤ d -d g , then: (i) f * = f * MoM,d (i.e.

we have MoM finite convergence);

(ii) the set of minimizers S min = {ξ 1 , . . . , ξ r } is non-empty and finite;

(iii) ker H t+1 σ * = Ann t+1 (σ * ) = I (S min ) t+1 (i.e. the kernel of the truncated moment matrix equals the truncated ideal of the minimizers) and V (Ann t+1 (σ * )) = S min ;

(iv) L min d (g) [t+d g +d] = cone(e ξ 1 , . . . , e ξ r ) [t+d g +d] (i.e. all the minimizing truncated feasible moment sequences are conic sums of evaluations at the minimizers); (v)

with ξ i ∈ S = S(g), ω i > 0, Ann t+1 (σ * ) = I (ξ 1 , . . . ξ r ) t+1 = I (Ξ) t+1 and V (Ann t+1 (σ * )) = Ξ. Notice that f (ξ i ) ≥ f * since ξ i ∈ S.
We show now that S min = Ξ. As

σ * |1 = 1 we have r i=1 ω i = 1. Moreover f * MoM,d = σ * |f ≤ f * and since deg(f ) ≤ t + d g + d we obtain: f * ≥ σ * |f = (σ * ) [t+d g +d] f = r i=1 ω i e [t+d g +d] ξ i f = r i=1 ω i f (ξ i ) ≥ f * . This implies that f (ξ i ) = f * for i = 1, . . . , r. Therefore f * = f *
MoM,d and S min ⊃ Ξ. From Proposition 3.11 we have that σ * ∈ L min 2d (g) generic implies that (σ * ) [2(t+d g )] is generic in

L min 2d (g) [2(t+d g )] . Moreover (σ * ) [2(t+d g )] = r i=1 ω i e [2(t+d g )] ξ i ∈ L (1) 2d (g, ±(f -f * )) [2(t+d g )] since Ξ ⊂ S min = S(g, ±(f -f * )). Then, as L (1) 2d (g, ±(f -f * )) ⊂ L min 2d (g) and (σ * ) [2(t+d g )] is generic in L min 2d (g) [2(t+d g )] , we have ∀σ ∈ L 2d (g, ±(f -f * )) Ann t+d g (σ * ) ⊂ Ann t+d g (σ ), i.e. (σ * ) [2(t+d g )] is generic in L 2d (g, ±(f -f * )) [2(t+d g )] .
We can then conclude from Theorem 3.20 that S min = Ξ and L min d (g) [t+d g +d] = cone(e ξ 1 , . . . , e ξ r ) [t+d g +d] . Finally we show MoM exactness. For every d ≥ d and σ ∈ L min 2d (g), we have σ [2d] ∈ L min 2d (g) since σ |f = f * . Therefore σ has flat truncation in degree t and by Lemma 3.19, σ [t+d g +d ] is coming from a convex sum of Dirac measures at points in S (that are the minimizers ξ 1 , . . . , ξ r ). This shows that the moment relaxation is exact, since increasing d we increase also the truncation degree where σ coincides with a weighted sum of evaluations at the minimizers. Theorem 4.1 slightly relaxes previous degree conditions. In [Lau09, th. 6.18], the degree condition is deg(f ) ≤ 2t + 2d g ≤ t + d g + d. It also shows that the kernel of the moment matrix of a generic truncated moment sequence, Ann t+1 (σ * ), is the truncated vanishing ideal of the minimizers and that the relaxation is exact. This means that any element in L min 2d (g) truncated in any degree t is coming from a measure, provided d ≥ t is big enough.

A key ingredient in this analysis is Lemma 3.19. From Lemma 3.19 and the remark after it, the results of Theorem 4.1 hold true, if we replace the condition rank

H t σ * = rank H t+d g σ *
with rank H t σ * = rank H t+1 σ * and d big enough. We show in Example 4.2 that the condition rank H t σ * = rank H t+1 σ * is in general not sufficient to conclude that the points extracted from the moment matrix are inside the semialgebraic set. To the best of our knowledge, this is the first example where such a pathological behaviour is explicit.

Example 4.2. We consider the problem of minimizing f

= (1 + X)(X -1) 2 on S(1 -X 2 , -X 3 ) = [-1, 0].
Notice that the SoS relaxation is exact, since f * = 0 and:

(1 + X)(X -1) 2 = 1 2 (1 + X) 2 + 1 -X 2 (X -1) 2 ∈ Q 4 (1 -X 2 , -X 3 ).
This implies that f * SoS,2 = f * MoM,2 = f * . The only minimizer of f on S is -1, and I (-1) = (X + 1): therefore we would expect to get flat truncation at degree zero for a generic element, and in particular rank H 0 σ * = rank H 1 σ * = 1. But this is not the case if we consider the MoM relaxation of order 2. Indeed an explicit calculation shows that σ = 1 2 (e

[4] -1 + e [4]
1 ) ∈ L min 4 (g), and rank H 1 σ = rank H 2 σ = 2. Therefore a generic σ * ∈ L min 4 (g) cannot satisfy the rank condition for t = 0. More precisely, it is possible to show that L min 4 (g) = conv e

[4]

-1 , 1

-1 + e

[4] 1 ) . Therefore a generic σ * ∈ L min 4 (g) will also satisfy rank H 1 σ = rank H 2 σ = 2. We confirm numerically the computation above, using the package MomentTools.jl to compute f * and a generic σ * ∈ L min 4 (g): the moments that we obtain are This confirms the theoretical description and shows that the rank condition is numerically satisfied for t = 1. The points extracted from the matrix are ξ 1 ≈ 0.9997640487211856 and ξ 2 ≈ -1.0000000483192044: notice that ξ 1 S. This happens because the condition rank

σ * 0 = 0.9999999989784975, σ * 1 = -0.3530324749675295 σ * 2 = 0.9998474115299072 σ * 3 = -0.
H t σ * = rank H t+d g σ * is not satisfied (we cannot compute H t+d g σ * = H 3 σ * as 3 = t + d g > d = 2
). On the other hand, if we increase the order of the relaxation and compute σ * ∈ L min 6 (g) generic, we can verify flat truncation for t = 0 and the only point extracted is -1. Moreover notice, from Lemma 3.19 applied with s = 1 and the remark below, that it is enough to check rank

H 0 σ * = rank H 1 σ *
to verify that rank H t σ * = rank H t+d g σ * , since the condition 0 = t ≤ d + sdeg(g) = 1 is satisfied.

We have seen that flat truncation implies MoM exactness and a finite set of minimizers. We show now that, under the assumption of MoM finite convergence, flat truncation is equivalent to a zero dimensional support for the quadratic module Q + (ff * ) defining the minimizers.

We first need a technical lemma, that will be important to investigate the relationship between L min 2d (g) and L

(1) 2d (g, ±(ff * )). Indeed, notice that L

(1) 2d (g, ±(ff * )) ⊂ L min 2d (g), by definition, but the converse inclusion is not true in general, since for σ ∈ L min 2d (g) we only have σ |f = f * , and not

f -f * ∈ Ann d-deg(f ) 2 (σ ). Lemma 4.3. Let f ∈ Q 2k (g), σ ∈ L 2d (g) and t ∈ N with 0 ≤ t ≤ d -k. Then σ |f = 0 implies for all q ∈ R[X] t , σ |qf = 0. In other words, f ∈ Ann t (σ ).
Proof. We set g 0 = 1 for notation convenience. Let f = i s i g i = i,j p 2 i,j g i ∈ Q 2k (g), that is deg p 2 i,j g i ≤ 2k. We want to prove that for all q ∈ R[X] such that deg(q) ≤ t we have σ |qf = 0. In particular, it is enough to prove that: σ qp 2 i,j g i = 0 for all i, j and q ∈ R[X].

(5)

Now, notice that σ |f = 0 implies σ p 2 i,j g i = 0 for all i, j, and consider for all T ∈ R and h ∈ R[X] t+deg p i,j : 0 ≤ σ (p i,j -T h) 2 g i = T 2 σ h 2 g i + 2T σ hp i,j g i (we can apply σ to (p i,j -T h) 2 g i since deg(p i,j -T h) 2 g i ) ≤ 2t + 2k ≤ 2d). The polynomial T → T 2 σ h 2 g i + 2T σ hp i,j g i has therefore a double root at T = 0, and this implies σ hp i,j g i = 0 for all h ∈ R[X] t+deg p i,j . If we subsitute h = qp i,j , we deduce eq. ( 5), and thus f ∈ Ann t (σ ).

We can now prove the equivalence between the flat truncation and the zero dimensional support for the quadratic module Q + (ff * ) defining the minimizers. ) and δ ∈ N is such that ff * ∈ Q 2δ (g), flat truncation happens for σ * ∈ L min 2d (g) generic at degree ρ -1 when d is such that:

(i) ( R supp Q(g)) 2δ+2ρ+2D-deg(f )-2 ⊂ Q 2d (g); (ii) I (S min ) 2ρ+2D-2 ⊂ Q 2d (g) + (f -f * ) 2d ; (iii) δ + 2ρ + 2D -deg(f ) -2 ≤ d.
Proof. Let us assume without loss of generality that f * = 0. We first show that flat truncation implies dim

R[X]
supp(Q+(f )) = 0. As in the proof of Theorem 4.1, if σ * ∈ L min 2d (g) is generic satisfying flat truncation at degree t then (σ * ) [2(t+d g )] is a generic element of L 2d (g, ±f ) [2(t+d g )] . Since the flat truncation property is satisfied, we conclude from Theorem 3.20 that R supp(Q + (f )) = (Ann t+1 (σ * )) = I (S min ) and finally, applying Lemma 1.2, dim

R[X] supp(Q+(f )) = dim R[X] I (S min ) = 0. Conversely, if dim R[X]
supp(Q+(f )) = 0, we deduce from Theorem 3.21 that the flat truncation property is satisfied for any σ ∈ L 2d (g, ±f ) at degree ρ -1 = ρ(S(g, ±(ff * )) -1 = ρ(S min ) -1 for d such that I (S min ) 2(ρ-1+D) ⊂ Q 2d (g) + (f ) 2d . Let a = 2ρ -2 + 2D and σ * ∈ L min 2d (g) generic. We want to show that (σ * ) [a] ∈ L 2d (g, ±f ) [a] , so that we can conclude using Theorem 3.21. Since σ * ∈ L min 2d (g) ⊂ L 2d (g), it is sufficient to prove that: σ * |qf = 0 for all q of degree ≤ adeg(f ).

(6)

We prove now (6), starting from σ * |f = f * = 0. MoM finite convergence implies that σ |f ≥ 0 for all σ ∈ L 2d (g), and therefore f ∈ L 2d (g) ∨ = Q 2d (g). Let δ ≤ d be minimal such that f ∈ Q 2δ (g) and let h = h 1 , . . . h m be a graded basis of R supp Q. From [Mar08, lemma 4.1.4] we deduce that Q 2δ (g) + (h) 2δ is closed (as a subset of R[X] 2δ with the Euclidean topology), and therefore Q 2δ (g) ⊂ Q 2δ (g) + (h) 2δ . Thus:

f = g + h = s i=0 s i g i + m i=1 p i h i ∈ Q 2δ (g) + (h) 2δ ,
where we set g 0 = 1 for notation convenience, g = s i=0 s i g i ∈ Q 2δ (g) and h = m i=1 p i h i ∈ (h) 2δ . It is then enough to prove that σ * |qg = σ * |qh = 0 where deg(qg

) ≤ b, deg(qh) ≤ b for b = 2δ + a - deg(f ) = 2δ + 2ρ + 2D -deg(f ) -2.
We start by proving σ * |qh = 0. We deduce from lemma 3.6 that for d big enough we have (h) b ⊂ Q 2d (g) and L 2d (g) [b] ⊂ L b (±h). Therefore σ * |qh = (σ * ) [b] qh = 0. Now we prove that σ * |qg = 0. Since δ + (adeg(f )) ≤ d, we can apply Lemma 4.3 with g ∈ Q 2δ (g) and t = adeg(f ) ≥ deg(q), and conclude that σ * |qg = 0, as desired.

Therefore σ * |qf = σ * |qg + σ * |qh = 0 for all q of degree ≤ adeg(f ) and ( 6) is satisfied. This implies that (σ * ) [a] ∈ L 2d (g, ±f ) [a] . Therefore we can apply Theorem 3.21 to conclude that the flat truncation property is satisfied for σ * .

Let us briefly comment the degree conditions in Theorem 4.4.

(i) If S has nonempty interior, it is not necessary to check the first condition, since in this case supp Q = 0. More generally if the quadratic module is reduced, that is if R supp Q = supp Q, the first condition is automatically satisfied;

(ii) The second condition is the key one: it tells us that flat truncation happens when the ideal of the minimizers, truncated in the appropriate degree, can be described using the truncated quadratic module and the truncated ideal generated by ff * ;

(iii) The third condition is technical, derived from Lemma 4.3. It allows to move from L min 2d (g) to L 2d (g, ±(ff * )), where we can apply the results of the previous section.

We illustrate Theorem 4.4 in the following example, showing how it can help to predict the flat truncation degree.

Example 4.5. We continue Example 2.5. Notice that f -

f * = X 2 ∈ Q 2 := Q 2 (g) = Q 2 (1 -X 2 -Y 2 , X + Y -1) (i.e
. the SoS relaxation is exact) and then the MoM relaxation has finite convergence. Using Theorem 4.4, we analyse if flat truncation holds at some degree. We have

I (S min ) = (X, Y -1) ⊂ R supp(Q + (f -f * )) = R supp(Q + (X 2 )) where Q := Q(1 -X 2 -Y 2 , X + Y -1). Indeed: X = X 2 + (Y -1) 2 2 + 1 -X 2 -Y 2 2 + X + Y -1 ∈ Q 2 ⊂ Q 2 + (X 2 ) 2 -X + ε = ε 2 1 - X 2 ε 2 + (1 - X ε ) 2 ∈ Q 2 + (X 2 ) 2 ∀ε > 0 ⇒ -X ∈ Q 2 + (X 2 ) 2 1 -Y = 1 2 X 2 + (1 -Y ) 2 + 1 -X 2 -Y 2 ∈ Q 2 ⊂ Q 2 + (X 2 ) 2 Y -1 = X + Y -1 -X ∈ Q 2 + Q 2 + (X 2 ) 2 = Q 2 + (X 2 ) 2 that implies (X, Y -1) 1 ⊂ supp(Q 2 + (X 2 ) 2 ) ⊂ R supp(Q + (f -f * )) and thus dim R[X]
supp(Q+(X 2 )) = 0. Theorem 4.4 implies that flat truncation holds for a high enough order d of the MoM relaxation.

We investigate the degree conditions in Theorem 4.4 to prove that flat truncation happens for the MoM relaxation at order d = 1. We have I(S min ) = (X, Y -1), ρ = 1, d g = 1, deg(f ) = 2, D = 1 and δ = 1.

(i) As S has nonempty interior, supp Q = 0 and the first point (i) is satisfied.

(ii) Notice that 2(ρ -1 + D) = 2, and therefore we have to show that (X, Y -1) 2 ⊂ Q 2 + (X 2 ) 2 . Since we have shown above that (X,

Y -1) 1 ⊂ Q 2 + (X 2 ) 2 , it is enough to prove that ±X 2 , ±X(Y - 1), ±(Y -1) 2 ∈ Q 2 + (X 2 ) 2 . Now, ±X 2 , (Y -1) 2 ∈ Q 2 + (X 2
) 2 by definition. Finally:

-(Y -1) 2 = 1 -Y 2 -X 2 + X 2 + 2(X + Y -1) -2X ∈ Q 2 + Q 2 + (X 2 ) 2 = Q 2 + (X 2 ) 2 ±X(Y -1) = 1 2 (±X + (Y -1)) 2 -X 2 -(Y -1) 2 ∈ Q 2 + (X 2 ) 2 ,
concluding the proof of the second point (ii). SoS,d , then there is finite convergence (that is f * MoM,d = f * ) if and only if flat truncation is satisfied for every σ ∈ L min 2d (g) (or, equivalently, if it is satisfied for σ * ∈ L min 2d (g) generic). Theorem 4.4 applies for different cases, for instance when there is finite convergence but the SoS relaxation is not exact (see example 2.13). This is possible since our analysis investigates the closure of the quadratic modules we are considering. Furthermore, under genericity assumption, as a corollary of Theorem 4.4 we will show (in Theorem 4.7 and Corollary 4.8) that we have finite convergence, the SoS relaxation and MoM relaxation are exact and the flat truncation property is satisfied.

Another improvement made is the estimation of the order d of the relaxation that is sufficient to have flat truncation, answering a question in [START_REF] Nie | Certifying convergence of Lasserre's hierarchy via flat truncation[END_REF]. To the best of out knowledge, this is is the first result in this direction. These conditions depends on properties of the minimizers and the quadratic module Q 2d (g) that might be difficult to check a priori. However they may be analyzed in some specific cases, such as optimization problems with a single minimizer, to deduce more precise bounds.

Boundary Hessian Conditions

In this section, we show that if regularity conditions, known as Boundary Hessian Conditions (BHC), are satisfied, then the flat truncation property holds. These are conditions on the minimizers of a polynomial f on a basic semialgebraic set S introduced by Marshall in [START_REF] Marshall | Representations of Non-Negative Polynomials Having Finitely Many Zeros[END_REF] and [START_REF] Marshall | Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization[END_REF], which are particular cases of the so called local-global principle. Under these conditions, global properties of polynomials (e.g. f ∈ Q) can be deduced from local properties (e.g. checking the BHC at the minimizers of f on S(Q)). We refer to [START_REF] Scheiderer | Distinguished representations of non-negative polynomials[END_REF], [START_REF] Scheiderer | Sums of squares on real algebraic surfaces[END_REF] and [Mar08, ch. 9] for more details. We introduce BHC conditions following [START_REF] Nie | Optimality conditions and finite convergence of Lasserre's hierarchy[END_REF].

Definition 4.6 (Boundary Hessian Conditions). Consider a POP with inequality constraints g = g 1 , . . . , g r , equality constraints h = h 1 , . . . , h s and objective function f . Let V = V (h) ⊂ R n and suppose that Q = Q(g, ±h) is Archimedean. We say that the Boundary Hessian Conditions hold at a minimizer point ξ ∈ S(g, ±h) of f if ξ is a smooth point of V and:

(i) we can choose g i 1 = t 1 , . . . , g i k = t k that are part of a regular system of parameters t 1 , . . . , t m , m ≥ k, for V at ξ and for some neighbourhood U of ξ we have S(g i 1 , . . . , g i k , ±h) ∩ U = S(g, ±h) ∩ U ;

(ii) On V , locally at ξ we have that ∇f = a 1 ∇t 1 + • • • + a m ∇t m , where a i are strictly positive real numbers;

(iii) On V , locally at ξ we have that Hess(f )(0, . . . , 0, t k+1 , . . . t m ) is positive definite in t k+1 , . . . t m .

These conditions are related to standard conditions in optimization at a point ξ ∈ S (see e.g. [START_REF] Bertsekas | Nonlinear Programming[END_REF]). Hereafter, the active constraints at ξ ∈ S are the constraints g i 1 , . . . , g i m such that g i j (ξ) = 0. To simplify the description of these conditions, we consider a constraint ±g(x) ≥ 0 as a single (equality) constraint. Therefore an equality constraint defining the set S is an active constraint at a point ξ ∈ S.

• Constraint Qualification Condition (CQC): for the active constraints g i 1 , . . . , g i m at ξ, the gradients ∇g i 1 (ξ), . . . , ∇g i m (ξ) are linearly independent.

• Strict Complementary Condition (SCC): for the active constraints g i 1 , . . . , g i m at ξ, there exist a 1 , . . . , a m ∈ R with a j > 0 if g i j is not an equality constraint such that ∇f

(ξ) = a 1 ∇g i 1 (ξ) + • • • + a m ∇g i m (ξ).
• Second Order Sufficiency Condition (SOSC): for L(x) = f (x) -m j=1 a j g i j with a i > 0 if g i j (x) is not an equality constraint, we have ∀v ∈ ∇g i 1 (ξ), . . . ,

∇g i m (ξ) ⊥ , v 0, v t ∇ 2 L(ξ)v > 0.
If these conditions are satisfied at every minimizer ξ, then the BHC conditions are satisfied with the active sign constraints at ξ as regular parameters t 1 = g i 1 , . . . , t k = g i k , see [START_REF] Nie | Optimality conditions and finite convergence of Lasserre's hierarchy[END_REF].

Notice that when BHC hold, the minimizers are non-singular, isolated points and thus finite. It is proved in [START_REF] Marshall | Representations of Non-Negative Polynomials Having Finitely Many Zeros[END_REF] that if BHC holds at every minimizer of f on S(g) then ff * ∈ Q(g), which implies that the SoS relaxation is exact. [START_REF] Nie | Optimality conditions and finite convergence of Lasserre's hierarchy[END_REF] proved that the BHC at every minimizer of f , which hold generically, implies the SoS finite convergence property.

In this section, we prove that, if the BHC hold, then the flat truncation property holds.

Theorem 4.7. Let f ∈ R[X], Q = Q(g) be an Archimedean finitely generated quadratic module and assume that the BHC hold at every minimizer of f on S = S(g). Then the SoS relaxation is exact, the MoM relaxation has finite convergence and the flat truncation holds for σ * ∈ L min 2d (g) generic when d is big enough. If conditions (i)-(iii) in Theorem 4.4 are satisfied for the relaxation order d, then the flat truncation property holds. Proof. If BHC hold at every minimizer of f on S(g) then S min is finite andf -f * ∈ Q(g) (see [START_REF] Marshall | Representations of Non-Negative Polynomials Having Finitely Many Zeros[END_REF]), which implies that the SoS relaxation is exact and thus the MoM relaxation has finite convergence. Moreover if the BHC conditions hold at every minimizer of f on S, then dim

R[X] supp(Q+(f -f * )) = 0 (see the proof of [Mar06, th. 2.3],
where it is shown that the field of fractions of R[X] modulo any minimal prime ideal lying over supp(Q+

(f -f * )) is isomorphic to R, that implies dim R[X]
supp(Q+(f -f * )) = 0). Then we conclude applying Theorem 4.4.

We show now that flat truncation and moment exactness hold generically.

For polynomials f ∈ R[X] d and g 1 ∈ R[X] d 1 , . . . , g s ∈ R[X] d s ,
we say that a property holds generically (or that the property holds for generic f , g 1 , . . . , g s ) if there exists finitely many nonzero polynomials φ 1 , . . . , φ l in the coefficients of polynomials in R[X] d and R[X] d 1 , . . . , R[X] d s such that, when φ 1 (f , g) 0, . . . , φ l (f , g) 0, the property holds. Proof. By [Nie14, th. 1.2] BHC hold generically. We apply Theorem 4.7 to conclude.

Corollary 4.8. For f ∈ R[X] d and g 1 ∈ R[X] d 1 , . . . , g s ∈ R[X]
Here is an example where BHC holds.

Example 4.9 (Robinson form). We find the minimizers of Robinson form f = x 6 + y 6 + z 6 + 3x 2 y 2 z 2x 4 (y 2 + z 2 )y 4 (x 2 + z 2 )z 4 (x 2 + y 2 ) on the unit sphere h = x 2 + y 2 + z 2 -1. The Robinson polynomial has minimum f * = 0 on the unit sphere, and the minimizers on V R (h) are:

√ 3 3 (±1, ±1, ±1), √ 2 2 (0, ±1, ±1), √ 2 2 (±1, 0, ±1), √ 2 2 (±1, ±1, 0).
BHC are satisfied at every minimizer (see [Nie14, ex. 3.2]), flat truncation holds and we can recover the minimizers from Theorem 4.7. We estimate the bounds of Theorem 4.4 and compare with the numerical experiments. It is not necessary to check (i), since (h) = R supp Q(±h). For the point (ii), we estimate the regularity of the minimizers as the regularity of twenty generic points on a sphere, that is ρ = 5. Then 2ρ + 2D -2 = 14, and thus we expect flat truncation for d ≥ 7. For the point (iii), we need to have d ≥ δ + 2ρ + 2Ddeg(f ) -2 ≥ 3 + 10 + 6 -6 -2 = 11. However, in practice for this example we have flat truncation numerically at order 6 and not before (using the SDP solver SDPA).

We recover a good approximation of the minimizers at this order:

v, M = minimize(f, [h], [], X, 6) w, Xi = get_measure(M) Here f * MoM,6 ≈ v = -1.

Finite semialgebraic set

In this section we consider the case when S = S(g) = {ξ 1 , . . . , ξ r } ⊂ R n is non-empty and finite.

Theorem 4.10. Let Q = Q(g) and suppose that dim

R[X]

supp Q = 0. Then S is finite, the MoM relaxation has finite convergence and the flat truncation holds for σ * ∈ L min 2d (g) generic when d is big enough. If conditions (i)-(iii) in Theorem 4.4 are satisfied, then flat truncation holds at the relaxation order d.

Proof. Since dim R[X]

supp Q = 0, we deduce that S is finite and we have MoM finite convergence from Theorem 3.21, Theorem 3.20 and Theorem 4.1. Indeed if d is big enough then flat truncation is satisfied for any σ ∈ L 2d (g), in particular for σ * ∈ L min 2d (g) generic. We conclude applying Theorem 4.4.

As corollaries, we have that the conclusions of Theorem 4.10 hold:

• for the moment relaxation L 2d (Πg) when S = S(g) = S(Πg) is finite, since by the real Nullstellensatz,

dim R[X] supp Q(Πg) = dim R[X] supp O(g) = dim R[X] supp O(g) = dim R[X] I (S(g)) = 0.
See [START_REF] Nie | Polynomial Optimization with Real Varieties[END_REF]th. 4.1] and [LLR08, rem. 4.9].

• for the moment relaxation L d (g, ±h) when V R (h) is finite, since for

Q = Q(g, ±h), dim R[X] supp Q = dim R[X] supp Q = dim R[X] R supp Q ≤ dim R[X] R (h) = 0.
See [Nie13c, th. 1.1] and [START_REF] Bernard Lasserre | Semidefinite Characterization and Computation of Zero-Dimensional Real Radical Ideals[END_REF]. This includes Polynomial Optimization problems with binary variables and equations of the form X 2 i -X i = 0, for which MOM relaxations are of particular interest, see e.g. [START_REF] Laurent | A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0-1 Programming[END_REF].

Notice that, even if the SoS relaxation has the finite convergence property and the MoM relaxation is exact, it may not be SoS exact for a finite real variety, as shown in Example 2.12 and Example 2.13. v, M = minimize(f, differentiate(f,X), [], X, 4) w, Xi = get_measure(M, 2.e-2)

The approximation of the minimum f * = 0 is v = -1.6279 • 10 -9 , and the decomposition with a threshold of 2 • 10 -2 gives the following numerical approximation of the minimizer (the origin): ξ = (2.976731510689691 10 -17 ; -9.515032317137384 10 -19 ; 3.763401209219283 10 -18 ).

Gradient, KKT and Polar ideals

Another approach which has been investigated to make the relaxations exact, is to add equality constraints satisfied by the minimizers (and independent of the minimum f * ) to a Polynomial Optimization Program.

Theorem 4.14. Let Q = Q(g, ±h) and J = (h ) be the polar ideal, where h ⊂ R[X] is a finite set of generators. If dim R[X] supp(Q(g)+(h )) = 0 then MoM relaxation (L 2d (g, ±h )) d∈N has finite convergence and the flat truncation holds for σ * ∈ L min 2d (g, ±h ) generic when d is big enough. In particular this holds when V R (J) is finite.

Proof. Minimizers belongs to V R (J) by Lemma 4.13. Then MoM exactness follows from Theorem 4.10.

The assumption in [START_REF] Nie | Minimizing Polynomials via Sum of Squares over the Gradient Ideal[END_REF], [START_REF] Demmel | Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals[END_REF] and [START_REF] Nie | An exact Jacobian SDP relaxation for polynomial optimization[END_REF] for finite convergence and SoS exactness are smoothness conditions or radicality assumptions on the associated complex variety. In particular, Assumption 2.2 in [Nie13a, th. 2.3] requires the varieties defined by the active constraints to be non-singular to conclude finite convergence of the hierarchy. Our condition for finite convergence and flat truncation is of a different nature, since it is on the finiteness of the real polar variety. For instance we can apply Theorem 4.14 in Example 4.15, but Assumption 2.2 in [START_REF] Nie | An exact Jacobian SDP relaxation for polynomial optimization[END_REF] is not satisfied, since the minimizer is a singular point. Moreover notice that in our theorem we use only the defining inequalities g and not their products Πg, as done in [Nie13a, th. 2.3] (in other words, we only need the quadratic module and not the preordering).

In the following example, BHC are not satisfied. But adding the polar constraints, we obtain an exact relaxation with the flat truncation property.

Example 4.15 (Singular minimizer). We minimize f = X on the compact semialgebraic set S = S(X 3 -Y 2 , 1 -X 2 -Y 2 ). We have f * = 0 and the only minimizer is the origin, which is a singular point of the boundary of S. Thus BHC do not hold, and we cannot apply Theorem 4.7. We have dim

R[X]

supp(Q+(X)) = 0 since supp(Q+(X)) ⊃ (X, Y 2 ), but we cannot apply Theorem 4.4, as we don't have finite convergence of the SoS and MoM relaxations. Indeed X Q = Q(X 3 -Y 2 , 1 -X 2 -Y 2 ), since X Q(X 3 , 1 -X 2 ). This implies that the SoS and MoM relaxations do not have finite convergence, following Example 2.8. This example also shows that we cannot remove the hypothesis of MoM finite convergence in Theorem 4.4.

To get flat truncation, we add the polar equations, that define a finite real polar variety, as we show in the following. First notice that, since V (X 3 -Y 2 ) is singular, Assumption 2.2 in [START_REF] Nie | An exact Jacobian SDP relaxation for polynomial optimization[END_REF] is not satisfied and the finite convergence of the relaxation O 2d (g, ±h ) using the polar variety cannot be deduced from [Nie13a, th. 2.3]. The generators of the polar variety are h = (1-X 2 -Y 2 )(X 3 -Y 2 ), Y (1 -X 2 -Y 2 ), Y (X 3 -Y 2 ). The real roots are (-1, 0), (1, 0), (0, 0) and the two real intersections of 1 -X 2 -Y 2 = 0 and X 3 -Y 2 = 0. Therefore dim The approximation of the minimum f * = 0 is v = -0.0045, and the decomposition of the moment sequence with a threshold of 2 • 10 -3 gives the following approximation of the minimizer (the origin): ξ = (-0.004514367348787526, 2.1341684460860045 10 -21 ).

The error of approximation on ξ is of the same order than the error on the minimum f * .

Conclusion

We investigated the convex cones L d (g) dual to the truncated quadratic modules Q d (g) from a new perspective. We studied the kernels of moment matrices or annihilators of moment sequences in these cones and characterize the ideal they generate (Theorem 3.12). We focused on the zero dimensional case and its relationships with the flat truncation property (Theorem 3.20 and Theorem 3.21), that can be used to certify that a linear functional is coming from a measure.

The main contributions of the paper are the applications of the previous analysis to flat truncation in Lasserre's MoM relaxation for Polynomial Optimization. We studied the flat truncation property in this context (Theorem 4.1) and deduced new necessary and sufficient conditions for flat truncation (Theorem 4.4). These conditions can be used to show that, under regularity and thus genericity assumptions (Boundary Hessian Conditions), the flat truncation property is satisfied (Theorem 4.7, Corollary 4.8). We applied these results to Polynomial Optimization on finite sets (Theorem 4.10) and for singular cases, adding polar equations, to obtain flat truncation (Theorem 4.14).

Theorem 4.4 provides the first known degree bounds for the flat truncation property to hold, in terms of the inequalities g and the objective function f (in particular depending on the regularity of the minimizers). An interesting question would be to investigate if it is possible to improve these degree bounds. Another possible research direction is to investigate regularity conditions, simpler than Boundary Hessian Conditions, that imply flat truncation for MoM relaxation of a certain order d.

  be a quadratic module and I = supp Q. Then: (i) I is an ideal; (ii) √ I = R √ I, i.e. the radical of I is equal to the real radical of I;

Figure 1 :

 1 Figure 1: A generic point σ * ∈ L

  Theorem 3.1 ([Sch91],[Put93]). Let Q be an Archimedean finitely generated quadratic module and S = S(Q). Then L(Q) = M(S) = cone(e ξ : ξ ∈ S) and Q = Pos(S), where the closures are taken with respect tto the locally convex topology in R[X] * and R[X].

  , ±h) such that σ ff * MoM,d < 0, which implies that σ |f < f * MoM,d in contradiction with the definition of f * MoM,d . Consequently, f * SoS,d = f * MoM,d .

x∈SI

  (x) = I (S). Now observe that supp Q ⊂ Ann(σ * ) by definition. Since Ann(σ * ) is a real radical ideal (see[START_REF] Lasserre | Moment matrices, border bases and real radical computation[END_REF] prop. 3.13]), then R supp Q ⊂ Ann(σ * ). If Q is Archimedean, then by Theorem 3.1 L(Q) = M(S). In particular σ * is a measure µ ∈ M(S) supported on S: ∀f ∈ R[X], σ * |f = f dµ. Let h ∈ I (S) and f ∈ R[X]. Then: σ * |f h = f h dµ = 0 dµ = 0,i.e. h ∈ Ann(σ * ), which proves the reverse inclusion.If Q = O is a preordering then R supp O = I (S) by the Real Nullstellensatz, Theorem 1.3. Then Ann(σ * ) = I (S).

  (±h). Since σ * is generic, we have p ∈ Ann d (e ξ ). In particular e ξ p = p(ξ) = 0, and therefore p vanishes on all the points of V (I). Since I is real radical, p ∈ I ∩ R[X] d = I d and thus Ann d (σ * ) ⊂ I d , which concludes the proof.

  Theorem 3.4, and finally:(Ann t+1 (σ * )) = I (S) = (I (S) 2(t+d g ) ) ⊂ R supp Q(g) ⊂ R supp O(g) = I (S),where the last equality is the Real Nullstellenstatz, Theorem 1.3. This shows that (Ann t+1 (σ * )) = R supp Q(g) = I (S).

Theorem 4. 4 .

 4 Assume that we have MoM finite convergence. Then dim R[X] supp(Q+(f -f * )) = 0 if and only if there exists d such that a generic σ * ∈ L min 2d (g) has flat truncation. In particular, if ρ = ρ(S min ), D = max(d g , deg(f ) 2

(

  iii) We have 1 = δ + 2ρ + 2Ddeg(f ) -2 ≤ d = 1, and thus the third point (iii) is satisfied. Therefore flat truncation happens at degree ρ -1 = 0 for the MoM relaxation at order d = 1. Related properties have been previously investigated. It is shown in [Nie13b, th. 2.2] that, under genericity assumptions, if for an order d big enough we have f * SoS,d = f * MoM,d (strong duality) and sup = max in the definition of f *

  d s generic satisfying the Archimedean condition, the SoS relaxation is exact, the MoM relaxation has finite convergence and the flat truncation holds for σ * ∈ L min 2d (g) generic when d is big enough. If conditions (i)-(iii) in Theorem 4.4 are satisfied for the relaxation order d, then the flat truncation holds.

  Example 4.11 (Gradient ideal). We compute the minimizers of Example 2.13.Let f = (X 4 Y 2 + X 2 Y 4 + Z 6 -2X 2 Y 2 Z 2 ) + X 8 + Y 8 + Z 8 ∈ R[X, Y , Z].We want to minimize f over the gradient variety V R By Theorem 4.10, we deduce that flat truncation holds for an order of relaxation d high enough. In this example, we have ρ = 1, D = 4, deg(f ) = 8, δ ≥ 4, so that we expect flat truncation at an order d ≥ 4, from Theorem 4.4.

  and Theorem 4.14 implies flat truncation. We recover the minimizer considering the MoM relaxation of order 5:v, M = polar_minimize(f, [], [x^3-y^2,1-x^2-y^2], X, 5) w, Xi = get_measure(M, 2.e-3)

  t. in degree ≤ t, that is Ann t (σ ) = ker H t σ = {p ∈ R[X] t | p σ = 0}. The moment matrix of σ in degree t is the matrix H t σ = (σ α+β ) |α|≤t,|β|≤t of the Hankel operator H t σ with respect to the basis {X β } and { Y α α! }. Therefore the kernel of the moment matrix is the annihilator of σ . Notice that, if s ≤ t, we can identify the matrix of H s σ with the submatrix of H t σ indexed by monomials of degree ≤ s. The localizing matrix of g ∈ R[X] t is the matrix H t g σ = ((g σ ) α+β ) α,β = ( γ g γ σ α+β+γ ) α,β of the Hankel operator H t g σ . Positive linear functionals. We say that σ

  d . We now introduce two convergence properties that will be central in the article.Definition 2.2 (Finite Convergence). We say that the SoS relaxation (Q 2d (g)) d∈N (resp. the MoM relaxation L 2d (g)) d∈N has the Finite Convergence property for f if ∃k ∈ N such that for everyd ≥ k, f * SoS,d = f * (resp. f * MoM,d = f * ).Notice that if the SoS relaxation has finite convergence then the MoM relaxation has finite convergence too, since f

Table 1 :

 1 Summary of convergence results.

	m

Expl. SoS f. c. SoS ex. MoM f. c. MoM ex.

  and only if σ ∈ e

	σ ∈ L 2t (I 2t ), then σ ∈ cone(e	[2t] ξ 1 , . . . , e	[2t] ξ r ) and rank H t σ = r.	[t] ξ 1 , . . . , e [t] ξ r . Moreover if t ≥ ρ -1 and

  Then from Lemma 3.19 we deduce that σ restricted to polynomials of degree ≤ 2(t + d g ) is equal to a sum of evaluations at points of S

	with positive weights, and the flat truncation is satisfied: rank H t σ = rank H σ t+d g s = 1 and d ≥ t -2 + 2 deg(g), rank H t σ = rank H t+1 σ implies rank H t t+d g . In particular, when σ = rank H σ

). Then, if rank H t σ = rank H t+s σ with t ≤ d 2 + sdeg(g), then 2(t + d g ) = 2t + deg(g) ≤ t + s + d 2 .

  We deduce from Proposition 3.16 that σ [t+d g + d 2 ] ∈ cone(e ξ 1 , . . . , e ξ r ) [t+d g + d 2 ] . This shows that L d (g) [t+d g + d 2 ] ⊂ cone(e ξ 1 , . . . , e ξ r ) [t+d g + d 2 ] . On the other hand the inclusion L d (g) [t+d g + d 2 ] ⊃ cone(e ξ 1 , . . . , e ξ r ) [t+d g + d 2 ] holds true since Ξ ⊂ S. Therefore L d (g) [t+d g + d 2 ] = cone(e ξ 1 , . . . , e ξ r ) [t+d g + d 2 ]

  the MoM relaxation is exact.

	Proof. Let σ * ∈ L min 2d (g) be generic such that rank H t σ * = rank H d. Then by Lemma 3.19, (σ * ) [t+d g +d] = r [t+d g +d] i=1 ω i e ξ i	t+d g σ *	with deg(f ) ≤ t+d g +d and t+d g ≤

  27211 • 10 -7 and the minimizers with positive coordinates are (all the twenty minimizers are found):

	ξ 1 x 0.577351068999	ξ 2 8.812477930640 10 -12 0.707107158043 ξ 3	ξ 4 0.707107157553
	y 0.577351069076	0.707107158048	1.271729446125 10 -13 0.707107157555
	z 0.577351066102	0.707107158048	0.707107158042	2.478771201340 10 -9

https://gitlab.inria.fr/AlgebraicGeometricModeling/MomentTools.jl

the variables X, Y in the plots, done using SDPA, have been scaled by 100 to reduce floating points errors

Q(g) is stable if ∀d ∈ N there exists k ∈ N such that Q(g) ∩ R[X] d = Q k (g) ∩ R[X] d .

Acknowledgments. The authors thank D. Henrion and M. Laurent for useful discussions about the outer approximation of semialgebraic sets with moments of degree one and flat truncation properties, and the anonymous referees for their helpful suggestions for the improvement of the results and the presentation of the paper.

This work has been partially supported by European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Actions, grant agreement 813211 (POEMA).

For global optimization we can consider the gradient equations (see [START_REF] Nie | Minimizing Polynomials via Sum of Squares over the Gradient Ideal[END_REF]): obviously ∇f (x * ) = 0 for all the minimizers x * of f on S = R n . For constrained optimization we can consider Karush-Kuhn-Tucker (KKT) constraints, adding new variables (see [START_REF] Demmel | Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals[END_REF]) or projecting them to the variables X (Jacobian equations, see [START_REF] Nie | An exact Jacobian SDP relaxation for polynomial optimization[END_REF]). We shortly describe them.

Let g 1 , . . . , g r , h 1 , . . . , h s ∈ R[X] defining S = S(g, ±h), and let f ∈ R[X] be the objective function. Let Λ = (Λ 1 , . . . , Λ r ) and Γ = (Γ 1 , . . . , Γ s ) be variables representing the Lagrange multipliers associated with g and h. The KKT constraints associated to the optimization problem min f (x) : x ∈ S(g, ±h) are:

where the polynomials belong to R[X, Γ, Λ]. These are sufficient but not necessary conditions for x * ∈ S being a minimizer. For x ∈ S, we say that g i is an active constraint at x if g i (x) = 0. Let x * ∈ S and g i 1 , . . . g i k be the active constraints at x * . The KKT constraints are necessary if the Constraint Qualification Condition (CQC) holds, that is, if ∇h 1 (x * ), . . . , ∇h s (x * ), ∇g i 1 (x * ), . . . , ∇g i k (x * ) are linearly independent at the minimizer x * ∈ S (also called Linear Independence Constraint Qualification in [NW06, th. 12.1]). We cannot avoid the CQC hypothesis: for

, then x * = 0 is a minimizer, but the KKT equations are not satisfied at x * = 0. To avoid this problem we define the polar ideal. Observe from eq. ( 7) that, if KKT constraints are satisfied at x and • if g i is not an active constraint at x, then Λ i = 0;

• if g i 1 , . . . g i k are the active constraints at x, then the gradients ∇f (x), ∇h 1 (x), . . . , ∇h s (x), ∇g i 1 (x), . . . , ∇g i k (x) are linearly dependent.

Definition 4.12. For f , g 1 , . . . , g r , h 1 , . . . , h s ∈ R[X] as before, the polar ideal is defined as follows:

where rank Jac(f , h, g a 1 , . . . , g a k ) < l is the ideal generated by the l × l minors of the Jacobian matrix Jac(f , h, g a 1 , . . . , g a k ).

We could replace the generators of the ideal in this definition by polynomials defining the same variety. This variety, known also as Jacobian or augmented Jacobian variety, coincides with the one defined by h 1 , . . . , h m 1 , ϕ i , . . . , ϕ r in [START_REF] Nie | An exact Jacobian SDP relaxation for polynomial optimization[END_REF].

The improvement that we make from the KKT constraints is to consider conditions that are necessary for being a minimizer, similar to Fritz John Optimality Conditions (see [Ber99, sec. 3.3.5]). Indeed we prove in the next lemma that every minimizer belongs to V R (J). Lemma 4.13. Let x * be a minimizer of f on S = S(g, ±h). Then x * ∈ V R (J).

If the CQC hold at x * , then x * is a KKT point (see [NW06, th. 12.1]) and ∇f (x) = j γ j ∇h j (x) + j λ 2 j ∇g j (x) for some γ j and λ i in R. As λ k = 0 if g k is not an active constraint, we have that ∇f (x * ), ∇h 1 (x * ), . . . , ∇h r (x * ), ∇g i 1 ( * x), . . . , ∇g i k (x * ) are linearly dependent, where g i 1 , . . . g i k are the active constraints at x * . Thus rank Jac(f (x * ), h(x * ), g a 1 (x * ), . . . , g a k (x * )) < s + k + 1 if {i 1 , . . . , i k } ⊂ {a 1 , . . . , a k }.

On the other hand, if i j {a 1 , . . . , a k } then g i j (x * ) = 0. This implies x * ∈ V R (J). If the CQC do not hold at x * and g i 1 , . . . , g i k are the active constraints, then the gradients ∇h 1 (x * ), . . . , ∇h s (x * ) and ∇g i 1 (x * ), . . . , ∇g i k (x * ) are linearly dependent. This implies that ∇f (x * ), ∇h 1 (x * ), . . . , ∇h s (x * ) and ∇g i 1 (x * ), . . . , ∇g i k (x * ) are also linearly dependent, and we conclude as in the previous case.