Matteo Tacchi
email: matteo.tacchi@epfl.ch

Convergence of Lasserre's hierarchy: the general case

Keywords: Infinite dimensional optimization, semidefinite programming, Lasserre hierarchy, numerical analysis, convex optimization, duality theory

Lasserre's moment-SOS hierarchy consists in approximating instances of the generalized moment problem (GMP) with moment relaxations and sums-of-squares (SOS) strenghtenings that boil down to convex semidefinite programming (SDP) problems. Due to the generality of the initial GMP, applications of this technology are countless, and one can cite among them the polynomial optimization problem (POP), the optimal control problem (OCP), the volume computation problem, stability sets approximation problems, and solving nonlinear partial differential equations (PDE). The solution to the original GMP is then approximated with finite truncatures of its moment sequence. For each application, proving convergence of these truncatures towards the optimal moment sequence gives valuable insight on the problem, including convergence of the relaxed values to the original GMP's optimal value. This note proposes a general proof of such convergence, regardless the problem one is faced with, under simple standard assumptions. As a byproduct of this proof, one also obtains strong duality properties both in the infinite dimensional GMP and its finite dimensional relaxations.

Introduction

Let:

• K ⊂ R n , • ϕ α ∈ R[x], α ∈ A, • a α ∈ R, α ∈ A, • c ∈ R[x],
•

ψ β ∈ R[x], β ∈ B, • b β ∈ R, β ∈ B,
• A, B be countable index sets, and consider the generalized moment problem (GMP), as stated in [10, (1.1)]:

p ⋆ GM := sup c dµ (1)
s.t. µ ∈ M(K) + ϕ α dµ = a α α ∈ A ψ β dµ ≤ b β β ∈ B,
where M(K) + denotes the cone of (nonnegative) Borel measures supported on K, whose dual cone (w.r.t. the weak- * topology on measures) is the set C(K) + of nonnegative continuous functions on K.

Example (Generality of the problem).

• The K-moment problem [10, (3.1),(3.2)] is a particular instance of Problem (1):

p ⋆ z := sup 0 s.t. µ ∈ M(K) + x k dµ(x) = z k k ∈ Γ,
where Γ ⊂ N n . Feasibility of this problem means existence of a measure µ whose moments on K coincide with the z k ∈ R, k ∈ Γ.

• The polynomial optimization problem (POP) [9, (4.1)] is another instance of Problem (1):

p ⋆ f := -sup -f dµ s.t. µ ∈ M(K) + 1 dµ = 1,
where f ∈ R[x]. One can prove that p ⋆ f = inf{f (x) : x ∈ K}. • The volume computation problem [START_REF] Henrion | Approximate volume and integration for basic semialgebraic sets[END_REF] is also an instance of Problem (1):

p ⋆ K := sup 1 dµ s.t. µ ∈ M(K) + p dµ ≤ B p(x) dx p ∈ Q[B] + ,
where K ⊂ B ⊂ R n such that the B x k dx are known and Q[B] + := {p ∈ Q[x] : ∀x ∈ B, p(x) ≥ 0}. One can prove that p ⋆ K = vol K is the Lebesgue volume of K.

In 2014, the authors of [START_REF] Josz | Strong duality in lasserre's hierarchy for polynomial optimization[END_REF] proved that under specific conditions, the Lasserre hierarchy associated with the particular GMP instance known as the polynomial optimization problem (POP) has the strong duality property, which means that there is no duality gap between the moment relaxations and the sum-of-squares strengthenings that form the moment-SOS hierarchy.

Moreover, it is proved in [START_REF] Bernard | Moments, Positive Polynomials and Their Applications[END_REF]Theorem 5.6(b)] that if the POP has a unique minimizer x ⋆ , then the solutions to the corresponding moment hierarchy converge towards the moments of the Dirac measure δ x ⋆ such that for all Borel set A ⊂ R n , δ x ⋆ (A) = 1 if x ⋆ ∈ A 0 else. This technical note is a follow-up that intends to close the subject of strong duality and convergence of the Lasserre hierarchy, by proving a general strong result at the abstraction level of the generalized moment problem.

First, it is possible to slightly generalize Problem (1) by allowing for multiple decision variables:

p ⋆ GM := sup c • dµ (2)
s.t. µ ∈ M(K 1 ) + × . . . × M(K N ) + ϕ α • dµ = a α α ∈ A ψ β • dµ ≤ b β β ∈ B.
where

B is finite, c, ϕ α , ψ β ∈ R[x 1 ] × . . . × R[x N ] and c • dµ := N i=1 c i dµ i .
Remark 1 (Finitely many inequality constraints). The introduction of multiple decision variables allows one to restrict to finitely many inequality constraints. Indeed, in the context of the moment-SOS hierarchy, infinite dimensional inequality constraints are always under the form ν -Φµ ∈ M(Ω) + for some compact Ω ⊂ R n and some bounded operator Φ : M(K 1 ) × . . . × M(K N ) → M(Ω) between vector spaces of signed measures. This means that these infinite dimensional inequality constraints can be recast as equality constraints with an additional decision variable μ ∈ M(Ω) + : Φµ + μ = ν. For example, the aforementioned volume computation problem can be recast as

p ⋆ K = sup 1 dµ s.t. µ ∈ M(K) + , μ ∈ M(B) + x k dµ(x) + x k dμ(x) = B x k dx k ∈ N n .
Example (A most general extension). Problem (2) covers all existing applications of the Lasserre hierarchy so far, including for instance:

• The optimal control problem (OCP) [START_REF] Lasserre | Nonlinear optimal control via occupation measures and lmi-relaxations[END_REF],

• The controlled region of attraction problem [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF] (as well as its inner approximation version [START_REF] Korda | Inner approximations of the region of attraction for polynomial dynamical systems[END_REF] and its extension [START_REF] Korda | Convex computation of the maximum controlled invariant set for polynomial control systems[END_REF] to invariant sets),

• The reachable set problem [START_REF] Victor Magron | Semidefinite approximations of reachable sets for discrete-time polynomial systems[END_REF] (as well as its continuous time counterpart, formulated as the maximal positively invariant set inner approximation problem in [START_REF] Oustry | Inner approximations of the maximal positively invariant set for polynomial dynamical systems[END_REF]),

• The nonlinear conservation PDE problem [13, (45),( 46)].

Remark 2 (Duality).

In practice, instances of Problem (2) are formulated so that

∀t 1 , t 2 ∈ R, α 1 , α 2 , α 3 ∈ A, t 1 ϕ α1 + t 2 ϕ α2 = ϕ α3 ⇒ t 1 a α1 + t 2 a α2 = a α3
(and same for the ψ β and b β ). This compatibility with the linearity of optimization constraints allows to write a synthetic dual formulation to (2):

d ⋆ GM := inf x • a + y • b (3) s.t. v + w -c ∈ C(K 1 ) + × . . . × C(K N ) + v = α∈A x α ϕ α x = (x α ) α∈A ∈ R A s.t. {α ∈ A : x α = 0} is finite w = β∈B y β ψ β y = (y β ) β∈B ∈ (R + ) B
where a := (a α ) α∈A and b := (b β ) β∈B . In words, the decision variable v is in the vector space spanned by the ϕ α and w is in the convex cone spanned by the ψ β . x (resp. y) is the Lagrange multiplier corresponding to the equality (resp. inequality) constraints in [START_REF] Brezis | Functional Analysis, Sobolev Spaces and Partial Differential Equations[END_REF].

The aim of this technical note is to state and prove a most general convergence theorem for the hierarchy corresponding to Problem (2) (and its dual (3)). The Lasserre hierarchy technology is most often deployed under the following standard working assumption (see [START_REF] Josz | Strong duality in lasserre's hierarchy for polynomial optimization[END_REF]Assumptions 1 & 2]):

Assumption 1 (Ball constraints).
Suppose that there exists

g 1 ∈ R[x 1 ] m1 , . . . , g N ∈ R[x N ] mN such that for i ∈ N ⋆ N := {1, . . . , N }, g i,1 (x i ) = 1 ; g i,mi (x i ) = 1 -x i 2 K i = {x i ∈ R ni : g i (x i ) ≥ 0}, where if x = (x 1 , . . . , x n ) ∈ R n , x = x 2 1 + . . . + x 2 n . Remark 3 (Compactness).
Up to rescaling of the K i 's, it is always possible to enforce Assumption 1, as soon as they are compact basic semialgebraic sets.

Indeed let g ∈ R[x] m , K := {x ∈ R n : g(x) ≥ 0}. For R > 0, define K R := {x ∈ R n : g(x) ≥ 0, x 2 ≤ R 2 } = K ∩ B R , where B R := {x ∈ R n : x ≤ R} is the ball of radius R. In such setting, if K is compact then it is bounded, so that there exists R 0 > 0 s.t. ∀R ≥ R 0 , K ⊂ B R
, and thus K = K R . This shows that if K is compact, it is always possible to add a redundant ball constraint to its description.

Remark 4 (Archimedean property). More precisely, the standard condition for applying the moment-SOS hierarchy is actually that the K i 's have the Archimidean property, which we explain here. Considering the cone

Σ[x] := {p 2 1 + . . . + p 2 k : k ∈ N, p 1 , . . . , p k ∈ R[x]}
of sums of squares of polynomials, we define the quadratic module of g

∈ R[x] m as Σ(g) := {σ • g : σ ∈ Σ[x] m }. Then, K := {x ∈ R n : g(x) ≥ 0} is said to have the Archimedean property if ∃ R > 0 s.t. R 2 -• 2 ∈ Σ(g).
It is worth noticing, as SOS polynomials are by definition nonnegative, that by definition of K one has Σ(g) ⊂ R[K] + and thus the Archimedean property implies K ⊂ B R for some R > 0..

Remark 5 (Positivstellensatz).

The key instrument for the moment-SOS hierarchy is Putinar's Positivstellensatz [16, Theorem 1.3], which has a dual counterpart under the form of Putinar's Lemma [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF]Lemma 3.2]. If the Archimedean property holds, then Putinar's Lemma gives a sufficient hierarchy of LMI conditions for a multi-indexed sequence z = (z k ) k∈N n to represent the moments of a measure µ ∈ M(K i ) + , which will be instrumental for the moment hierarchy definition and convergence.

Conversely, under the same assumption, Putinar's Positivstellensatz ensures that Σ(g i ) is dense in C(K i ) + w.r.t. the uniform topology, so that

d ⋆ GM := inf x • a + y • b s.t. v + w -c ∈ Σ(g 1 ) + × . . . × Σ(g N ) + v = α∈A x α ϕ α x = (x α ) α∈A ∈ R A s.t. {α ∈ A : x α = 0} is finite w = β∈B y β ψ β y = (y β ) β∈B ∈ (R + ) B
Then, the isomorphism between sums of squares and positive semidefinite matrices, provided by [10, Proposition 2.1], allows to parameterize inequality constraints as LMI constraints.

Note that this means that when restricting the constraints to bounded degree in the hierarchy, only a finite number of constraints need to be checked.

Notations and theorem statement

We briefly recall the usual notations and definitions that are used in the Lasserre hierarchy framework. Then, we proceed to introduce the last assumptions that will be needed for the proof of our theorem.

The basic notions that are used to formulate the moment hierarchy are the Riesz functional and the localizing matrix.

Definition (Riesz functional).

Let z := (z k ) k∈N n ∈ R N n be a real sequence. We define, for p(x)

:= |k|≤d p k x k ∈ R[x], L z (p) := |k|≤d p k z k , where for k = (k 1 , . . . , k n ) ∈ N n , |k| := k 1 + . . . + k n .
The linear map L z : p → L z (p) is called the Riesz functional of z.

Remark 6 (Link between L z and integrals).

If z = (z k ) k∈N n ∈ R N n and µ ∈ M(K) + are such that ∀k ∈ N n z k = x k dµ,
then by definition for all p ∈ R[x]

p dµ = L z (p).
Notation (Bounded multi-indices).

For n, d ∈ N, we use the following notations:

N n d := {k ∈ N n : |k| ≤ d} and N n,d := card(N n d ) = n + d n , so that the space R d [x] of polynomials in n variables with degree at most d is isomorphic to R N n d and R N n,d . Definition (Localizing matrix). Let d, d g ∈ N, g ∈ R dg [x]. Let e d (x) := (e i (x)) 1≤i≤N n,d be a base of R d [x]. Let z = (z k ) |k|≤2d+dg ∈ R N n 2d+dg .
The degree d localizing matrix M d (g z) of z in g is defined as the size N n,d matrix representation in base e d (x) of the bilinear application

(p, q) ∈ R d [x] 2 -→ L z (g p q).
The localizing matrix is defined so that

if p(x) = p • e d (x) and q(x) = q • e d (x), p, q ∈ R N n,d , then L z (g p q) = p ⊤ M d (g z) q and L z (g p 2 ) = p ⊤ M d (g z) p.
Notation (Positive semidefinite matrices). We denote by:

• S n := {M ∈ R n×n : M ⊤ = M} the space of symmetric matrices,

• S n + := {M ∈ S n : ∀x ∈ R n , x ⊤ M x ≥ 0} the closed convex cone of positive semidefinite matrices, • if M ∈ S n , M 0 ⇐⇒ M ∈ S n
+ . These definitions allow to formulate the moment hierarchy associated to Problem (2):

p d GM := sup N i=1 L zi (c i ) (4)
s.t. z i ∈ R N n i 2d i ∈ N ⋆ N M d-dij (g i,j z i ) 0 i ∈ N ⋆ N , j ∈ N ⋆ mi N i=1 L zi (ϕ α,i ) = a α α ∈ A d N i=1 L zi (ψ β,i ) ≤ b β β ∈ B d ,
where d ij = ⌈deg g i,j /2⌉, and

A d := {α ∈ A : ∀i ∈ N ⋆ N , deg ϕ α,i ≤ 2d}, B d := {β ∈ B : ∀i ∈ N ⋆ N , deg ψ β,i
≤ 2d} are taken finite (which is possible using linearity of the Riesz functional, Remark 5 and finite dimensionality of

R d [x] = {p ∈ R[x] : deg p ≤ d}).
A vector z i ∈ R N n i 2d that is feasible for problem ( 4) is then called a pseudo-moment sequence. Remark 7 (SOS hierarchy).

The dual to the moment hierarchy is called the SOS hierarchy, and is written as follows:

d d GM := inf x • a + y • b (5) s.t. v + w -c ∈ Σ(g 1 ) × . . . × Σ(g N ) v = α∈A d x α ϕ α x = (x α ) α∈A d ∈ R A d w = β∈B d y β ψ β y = (y β ) β∈B d ∈ (R + ) B d ,
where a := (a α ) α∈A d and b := (b β ) β∈B d .

Remark 8 (Minimal degree for the hierarchy). It appears in ( 4) that p d GM is only defined for d ≥ d 0 , where

d 0 := max i∈{1,...,N } max j∈{1,...,mi} max(⌈deg c i /2⌉, d ij ).
We are finally able to formulate the last needed assumptions as well as our main theorem. First, convergence in the moment hierarchy is often obtained through an additional assumption on the mass of the involved measures: Assumption 2 (Uniformly bounded mass).

For i ∈ {1, . . . , N }, denote by z i ∈ R (N n i 2d ) the pseudo-moment sequence that represents µ i in the Lasserre hierarchy, and suppose that there exists C i > 0 s.t. if z i is feasible for the degree d relaxation of problem (2), then

z i,0 ≤ C i .
Eventually, our proof of convergence consists in proving that our hierarchy of pseudo-moment sequences has at least one accumulation point. So as to deduce actual convergence, we need a unique candidate for such accumulation point: Assumption 3 (Existence of a unique optimal solution).

Suppose that there exists a unique µ ⋆ ∈ M(K 1 ) + × . . . × M(K N ) + feasible and optimal for problem (2):

∀α ∈ A, ϕ α • dµ ⋆ = a α ∀β ∈ B, ψ β • dµ ⋆ ≤ b β and c • dµ ⋆ = p ⋆ GM .
Remark 9 (The question of uniqueness). Assumption 3 is crucial for the proof of convergence. However, if one removes it, existence of the optimal µ ⋆ could still be obtained from Assumption 2, through an infinite dimensional strong duality proof similar to what we present in the next section (which would bring no additional theoretical insight, so that we do not display it). The actual stake of this assumption is indeed the uniqueness assumption. Note that in most of the moment-SOS hierarchy applications, the GMP is designed in a way that enforces Assumption 3.

Our contribution consists in stating and proving a general theorem for convergence of the Lasserre hierarchy (4) corresponding to problem (2): Theorem 4 (Convergence of the general Lasserre hierarchy).

Under Assumptions 1, 2 and 3, there exist sequences z d i d≥d0 of feasible pseudo-moment sequences for the moment hierarchy (4) s.t.

N i=1 L z d i (c i ) = p d GM .
Then, for all k ∈ N n ,

z d i,k -→ d→∞ x k dµ ⋆ i (x).
In Remark 10 (Contribution w.r.t. [START_REF] Josz | Strong duality in lasserre's hierarchy for polynomial optimization[END_REF] and [START_REF] Bernard | Moments, Positive Polynomials and Their Applications[END_REF]).

Whereas [START_REF] Josz | Strong duality in lasserre's hierarchy for polynomial optimization[END_REF] and [10, Theorem 5.6(b)] respectively prove strong duality in the moment-SOS hierarchy and convergence of the resulting pseudo-moments towards the unique solution to the original POP, this contribution extends these results from the particular POP problem to all possible instances of the GMP, including the various examples mentioned in introduction, which should facilitate future contributions in the field of moment-SOS hierarchies.

Such generality is obtained by enforcing, in addition to the standard Assumptions 1 and 3 that were already introduced in [START_REF] Josz | Strong duality in lasserre's hierarchy for polynomial optimization[END_REF] and [10, Theorem 5.6(b)], of the boundedness Assumption 2 that guarantees strong duality in the GMP, a property that is trivially established in the context of POP but can become difficult to check in other situations, such as [START_REF] Victor Magron | Semidefinite approximations of reachable sets for discrete-time polynomial systems[END_REF] and [START_REF] Oustry | Inner approximations of the maximal positively invariant set for polynomial dynamical systems[END_REF].

Proof of Theorem 4

For the sake of simplicity and without loss of generality, we work on the simple case [START_REF] Barvinok | A Course in Convexity[END_REF] where N = 1, with B = ∅1 , whose corresponding hierarchy writes:

p d GM := sup L z (c) (6)
s.t. z ∈ R N n 2d M d-dj (g j z) 0 j ∈ N ⋆ m L z (ϕ α ) = a α α ∈ A d .
All the proofs are the same for N > 1, at the price of additional notations that do not bring any theoretical insight, so that we stick to the case N = 1. We first prove an easy lemma that gives all its importance to Assumption 1:

Lemma 5 (Pseudo moment sequences boundedness). Let d ∈ N\{0}, R > 0, z ∈ R N n 2d s.t. M d (z) 0 and M d-1 ((R 2 -• 2 ) z) 0. Then, min |k|≤d z 2k ≥ 0 and max |k|≤2d |z k | ≤ z 0 max(1, R 2d ). Proof. M d (z) 0 is equivalent to ∀p ∈ R d [x], L z (p 2 ) ≥ 0, (a)
while

M d-1 ((R 2 -• 2 ) z) 0 means that ∀p ∈ R d-1 [x], L z ((R 2 -• 2 ) p 2 ) ≥ 0. (b) (a) with p(x) = x k , |k| ≤ d yields z 2k ≥ 0. (b) with p(x) = 1 yields R 2 z 0 ≥ |k|=1 z 2k , since x 2 = n j=1 x 2 j = |k|=1 x 2k . Hence, since the z 2k are nonnegative, one has |k| = 1 ⇒ z 2k ≤ R 2 z 0 . Going forward, if |k| = 1, (b) with p(x) = x k yields R 2 z 2k ≥ |k ′ |=1 z 2(k+k ′ ) with z 2(k+k ′ ) ≥ 0 by (a), so that R 4 z 0 ≥ R 2 z 2k ≥ z 2(k+k ′ ) as long as |k| = |k ′ | = 1, and thus, if |k| = 2, R 4 z 0 ≥ z 2k . By induction, one has for k ∈ N n d that 0 ≤ z 2k ≤ R 2|k| z 0 ≤ z 0 max(1, R 2d ). (c) Let k, k ′ ∈ N n d . Then, (a) with p(x) = x k ± x k ′ yields 0 ≤ L z (p 2 ) = z 2k ± 2z k+k ′ + z 2k ′ so that |z k+k ′ | ≤ z 2k + z 2k ′ 2 ≤ max(z 2k , z 2k ′ ) (c) ≤ z 0 max(1, R 2d ). (d)
Eventually, any k ∈ N n 2d can be written

k = k ′ + k ′′ with k ′ , k ′′ ∈ N n d , so that it satisfies (d), and |z k | ≤ z 0 max(1, R 2d ).
This lemma proves several important facts, among which any nonzero feasible pseudo-moment vector z i for (4) satisfies z i,0 > 0 if Assumption 1 holds, and under Assumptions 1 and 2, for all d ∈ N, z i feasible for [START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF]

satisfies |z i,k | ≤ C i ∀k.
Remark 11 (Relaxing Assumption 1).

Actually, this lemma still holds if one replaces Assumption 1 with the Archimedean property. Indeed, suppose that R 2 -• 2 ∈ Σ(g) for some R > 0. Then, there exists σ

∈ Σ[x] m such that R 2 -• 2 = σ • g = m i=1 σ i g i = m i=1 ki j=1 p 2 i,j g i .
Then, let D := max i,j ⌈deg(p 2 i,j )/2⌉ and for i ∈ N ⋆ m let d i := d + D -1 and suppose M di (g i z) 0. In that case, for q ∈ R d-1 [x], one recovers (b):

L z ((R 2 -• 2 ) q 2 ) = m i=1 ki j=1 L z (g i p 2
i,j q 2 ) ≥ 0.

However, we chose to keep Assumption 1 instead of the Archimedean property, as the former is much easier to verify in practice and can always be enforced when the latter holds, at the price of adding a redundant ball constraint to the K i 's descriptions (see remarks 3 and 4).

A first consequence of Lemma 5 is the strong duality property in the hierarchy.

Proposition 6 (Strong duality in the hierarchy).

Suppose that each relaxation of Problem (1) has a feasible solution. In that case, under Assumptions 1 and 2, ∀d ≥ d 0 , p d GM = d d GM . Moreover, the degree d relaxation (6) of (1) has an optimal solution z d ∈ R N n 2d .

Proof. We rely on [1, Chapter IV: Theorem (7.2), Lemma (7.

3)] to prove our result. Consider the cone

K d := {(A d z, L z (c)) : z ∈ X d } ,
where A d z := (L z (ϕ α )) α∈A d and

X d := z ∈ R N n 2d : ∀j ∈ {1, . . . , m}, M d-dj (g j z) 0 .
According to [1, Theorem (7.

2)] a sufficient condition for our result to hold requires that p d GM < ∞ and K d is closed. Clearly,

p d GM ≤ N n,d0 max k∈N n c k max z max k∈N n 2d z k ≤ N n,d0 max k∈N n c k C < ∞.
Besides, [1, Lemma (7.

3)] states that for K d to be closed, it is sufficient to prove that X d has a compact, convex base, and that

∀z ∈ X d , (A d z, L z (c)) = (0, 0) =⇒ z = 0. ( * )
We first exhibit a compact convex base for X d . A base for a cone is defined as follows:

Definition (Convex base of a cone). Let X be a cone, i.e. a subset of a real vector space that is invariant under multiplication by nonnegative real numbers. P ⊂ X is said to be a base of X if the map

χ : (0, +∞) × P -→ X \ {0} (t, p) -→ t p is a bijection.
We are looking for such a base, with the additional properties that it should be convex (i.e. stable by barycenter operation) and compact (i.e., in this finite dimensional context, closed and bounded). Let

P d := {z = (z k ) k ∈ X d : z 0 = 1}.
P d is a base of X d in the sense that X d \{0} is isomorphic to (0, +∞)×P d through the bijective application χ d : (t, p) → t p, with χ -1 d (z) = (z 0 , z/z 0 ) (using Lemma 5 and Assumption 1, for any M d (z) and M d-1 ((1 -• 2 ) z) to be simultaneously positive semi-definite with z = 0, it is necessary that z 0 > 0).

P d is convex. Indeed, let p 1 , p 2 ∈ P d , t ∈ [0, 1], p := t p 1 + (1 -t) p 2 .
Then, by linearity of the localizing matrix operator,

∀g ∈ R d [x] M d-dg (g p) = t M d-dg (g p 1 ) + (1 -t) M d-dg (g p 2 ),
where d g = ⌈deg g/2⌉, so that its semidefinite positivity is preserved by convex combination, by convexity of S n + for any n ∈ N. Thus, p ∈ X d . Besides,

p 0 = t p 10 + (1 -t) p 20 = t + 1 -t = 1
so that p ∈ P d , which proves convexity. Eventually, we move on to showing compactness of P d . According to Lemma 5, the ball constraint in the description of K (Assumption 1) and the upper bound z 0 ≤ C (Assumption 2) yield boundedness of P d for the distance dist(z, z Since finite dimensional closed bounded sets are compact, this proves that P d is compact. It remains to prove ( * ). Let z ∈ X d s.t. A d z = 0 and L z (c) = 0. We want to prove that z = 0 so that ( * ) holds.

′ ) := max |k|≤2d |z k -z ′ k |.
Let

z 0 ∈ X d s.t. ∀α ∈ A d , L z0 (ϕ α ) = a α . Define for t ≥ 0 z t := z 0 + t z. Let t ≥ 0. Since X d is a convex cone, z t ∈ X d .
In addition, by construction of z and linearity of the operator z → L z (•), ∀α ∈ A d , L zt (ϕ α ) = L z0 (ϕ α ) = a α , so that Assumption 2 ensures that z t,0 ≤ C. However, z t,0 = z 0,0 + t z 0 .

Combined with the fact that z 0,0 ≥ 0 (with Lemma 5), this yields that for all t ≥ 0,

t z 0 ≤ C,
which is only possible if z 0 = 0, i.e. if z = 0 using again Lemma 5.

Eventually, we can end this section by proving Theorem 4. As announced at the beginning of this section, w.l.o.g we actually only do the proof for the case N = 1:

Theorem 7 (Convergence of the pseudo-moment sequences).

Under Assumptions 1, 2 and 3, there exists a sequence (z d ) d≥d0 of feasible pseudo-moment sequences for the hierarchy [START_REF] Josz | Strong duality in lasserre's hierarchy for polynomial optimization[END_REF] Proof. Existence of (z d ) d≥d0 follows from Proposition 6 (using Assumptions 1 and 2), so we focus on the proof of convergence. Let d ∈ N. For k ∈ N n , define

corresponding to Problem (1), s.t. L z d (c) = p d GM . Then, for all k ∈ N n , z d,k -→ d→∞ x k dµ ⋆ (x).
ẑd,k := z d,k if |k| ≤ 2d, 0 else, so that ẑd ∈ R N n with ẑd ℓ ∞ (N n ) := max k∈N n |ẑ d,k | = max |k|≤2d |z d,k | Lemma 5
≤ z d,0 ≤ C, using again Assumptions 1 and 2 (recall that in particular Assumption 1 sets R = 1 in the application of Lemma 5). Then, (ẑ d ) d∈N is a uniformly bounded sequence of

ℓ ∞ (N n ) := u ∈ R N n : max k∈N n |u k | < ∞ , which is the topological dual of ℓ 1 (N n ) := u ∈ R N n : k∈N n |u k | < ∞ .
r∈N : ∃ z ∞ ∈ ℓ ∞ (N n ) s.t. ∀u ∈ ℓ 1 (N n ), k∈N n u k z dr,k -→ r→∞ k∈N n u k z ∞,k . In particular, if k ∈ N n , u l := 0 if l = k, u k = 1 defines a u ∈ ℓ 1 (N n ) for which the above statement becomes z dr,k -→ r→∞ z ∞,k .
Thus, what we want to show is that for k ∈ N n , z ∞,k = x k dµ ⋆ (x) =: z ⋆ k , where we recall that µ ⋆ is the unique solution to [START_REF] Barvinok | A Course in Convexity[END_REF] given by Assumption 3.

Let α ∈ A, j ∈ N ⋆ m . Then, for all d ≥ d 0 and r ∈ N large enough, by feasibility of z dr for the relaxation of degree d r , one has

• 0 M d-dj (g j z dr ) = M d-dj (g j ẑdr ) -→ r→∞ M d-dj (g j z ∞ ) • a α = L z dr (ϕ α ) = L ẑdr (ϕ α ) -→ r→∞ L z∞ (ϕ α )
so that according to Putinar's Lemma [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF]Lemma 3.2], whose conditions hold by Assumption 1, z ∞ is the actual moment sequence of a measure µ ∞ that is feasible for problem [START_REF] Barvinok | A Course in Convexity[END_REF]. Then, one directly has [START_REF] Barvinok | A Course in Convexity[END_REF]. By Assumption 3, this yields µ ∞ = µ ⋆ , i.e. z ∞ = z ⋆ . Thus, (ẑ d ) d is bounded and has a unique weak- * accumulation point z ⋆ , which means that for any k ∈ N n , 4 Discussing the uniqueness Assumption 3

p ⋆ GM ≥ c dµ ∞ = L z∞ (c) = lim r→∞ L ẑdr (c) = lim r→∞ p dr GM ≥ p ⋆ GM since for any d ≥ d 0 p d GM ≥ p ⋆ GM (by construction of the moment relaxation). Hence, c dµ ∞ = p ⋆ GM , i.e. µ ∞ is optimal for problem
z d,k -→ d→∞ z ⋆ k = x k dµ ⋆ (x).
In practice, it is quite easy to enforce Assumptions 1 and 2, up to rescaling and addition of mass constraints. However, Assumption 3 may not always hold (especially in the case of polynomial optimization or PDE solutions), so that it is worth discussing what can be done without this Assumption. If Assumption 3 does not hold, then our contribution reduces to the following result:

Corollary 8 (to Theorem 7).

Under Assumptions 1 and 2, there exists a subsequence (z dr ) r∈N , where

(d r ) r∈N ∈ ([d 0 , ∞) ∩ N) N is
strictly increasing, of feasible pseudo-moment sequences for the hierarchy [START_REF] Josz | Strong duality in lasserre's hierarchy for polynomial optimization[END_REF], as well as

a measure µ ∞ ∈ M(K) + feasible for Problem (1), s.t. L z dr (c) = p dr GM , c dµ ∞ = p ⋆ GM and for all k ∈ N n , z dr,k -→ r→∞ x k dµ ∞ (x).
In particular, one still has p d GM -→ d→∞ p ⋆ GM . Moreover, this automatically yields strong duality

p d GM = d d GM and p ⋆ GM = d ⋆ GM and then dual convergence d d GM -→ d→∞ d ⋆ GM .
Proof. Going back to the proof of Theorem 7, most arguments are still valid, which lets us with a subsequence (z dr ) r∈N that converges towards the moments of an optimal µ ∞ . The only part that is not valid anymore without Assumption 3 is the identification between µ ∞ and µ ⋆ , and thus the convergence of the whole sequence (z d ) d≥d0 . Indeed, in such context, the pseudo-moment sequence might have several accumulation points µ ⋆ 1 , . . . , µ ⋆ M (or even an infinity of accumulation points), and either converge to one of them, or oscillate between them. The strong duality and value convergence results being independent from this, the rest of Theorem 7 is unchanged.

To illustrate this result, consider the POP problem f ⋆ := inf x∈[0,1] (1 -x)x, whose value is obviously f ⋆ = 0 with minimizers x ⋆ = 0 and x ⋆ = 1. We then write the corresponding GMP instance as well as its order d moment relaxation:

p ⋆ f := inf (1 -x)x dµ(x) (7a)
s.t. µ ∈ M([0, 1]) + 1 dµ(x) = 1, p d f := inf z 1 -z 2 (7b)
s.t. z = (z k ) 0≤k≤2d ∈ R N 2d M d (z) 0 M d-1 (x(1 -x)z) 0 M d-1 (1 -x 2 )z 0 z 0 = 1,
where [0, 1] is described as [0, 1] = {x ∈ R : 1 ≥ 0, (1 -x)x ≥ 0 and 1 -x 2 ≥ 0} so as for Assumption 1 to hold. Note that constraint 1 dµ = 1 automatically enforces Assumption 2 through its moment writing z 0 = 1. Now, the obvious solution to problem (7a) is p ⋆ f = 0 with minimizing set

M ⋆ := {µ ⋆ = t δ 1 + (1 -t) δ 0 : t ∈ [0, 1]}.
Indeed, M ⋆ parameterizes all possible probability measures supported on the set {0, 1} of minimizers of (1 -x)x (see figure 1). Thus, in this case, Assumption 3 does not hold.

We then proceed to study the moment relaxation (7b).

Proposition 9 (Finite convergence). For d ≥ 1, the minimizers of problem (7b) are in correspondance with the minimizers of problem (7a):

M d = x k dµ ⋆ (x) k∈N 2d : µ ⋆ ∈ M ⋆ .
This is called a finite convergence phenomenon, and it is very common with POP moment hierarchies [START_REF] Nie | Optimality conditions and finite convergence of Lasserre's hierarchy[END_REF]. We represent a possible optimal measure µ ⋆ = t δ 1 + (1 -t) δ 0 where t = 0.32 is the length of the red segment and (1 -t) = 0.68 is the length of the green one.

Proof. Let d ≥ 1. Let z = (z k ) 0≤k≤2d ∈ R N 2d be feasible for (7b). For k ∈ N 2d-2 , we define

u k := z k+1 -z k+2 , which yields a new vector u = (u k ) 0≤k≤2d-2 ∈ R 2d-1 . Then, M d-1 (u) = M d-1 (x(1 -x)z) 0. We next prove that M d-2 (1 -x 2 )u 0. Let p ∈ R d-2 [x]. L u (1 -x 2 )p 2 = L z (1 -x 2 )p 2 (1 -x)x = L z (1 + x)(1 -x) 2 p 2 x = L z (1 -x + 2x)(1 -x) 2 p 2 x = L z x(1 -x)(1 -x) 2 p 2 ≥0 since M d-1 (x(1-x)z) 0 + 2 L z x 2 (1 -x) 2 p 2 ≥0 since M d (z) 0 ≥ 0, which is the definition of M d-2 (1 -x 2 )u 0.
Then, applying Lemma 5 to u, we deduce that

0 ≤ max 1≤k≤2d-1 |z k -z k+1 | = max 0≤k≤2d-2 |u k | ≤ u 0 = z 1 -z 2 . (8)
This proves that p d f ≥ 0. On the other hand, z = (1, t, . . . , t) ∈ R N 2d , with t ∈ [0, 1], defines a feasible z (corresponding to the moments of optimal measure µ ⋆ = t δ 1 + (1 -t) δ 0 ) such that z 1 -z 2 = 0, which proves that p d f ≤ 0 and thus p d f = 0. Eventually, let z = (z k ) 0≤k≤2d be feasible and optimal for (7b): z 1 -z 2 = 0. Then, equation [START_REF] Korda | Inner approximations of the region of attraction for polynomial dynamical systems[END_REF] instantly yields that for all k ≥ 2, z k = z 1 . Moreover, according to Lemma 5 applied to z, for all k ≥ 1, z k = z 2 ∈ [0, 1]. In other words, for d ≥ 1 the set of minimizers for problem (7b) is exactly the set of truncated moment sequences of minimizers for problem (7a):

M d = {(z k ) 0≤k≤2d : z 0 = 1, z 1 ∈ [0, 1], ∀k ≥ 1, z k = z 1 }= x k dµ ⋆ (x) k∈N 2d : µ ⋆ ∈ M ⋆ ,
no matter the size of d ≥ 1.

Remark 12 (Notions of convergence).

Here it is important to distinguish between two different notions of convergence:

• Finite convergence of the hierarchy denotes the aforementioned phenomenon, when the minimizers of a finite degree relaxation all correspond to minimizers of the original GMP;

• One talks about pseudo-moment sequence convergence when any sequence (z d ) d of minimizers for (6) converges to the sequence of moments of a minimizer for [START_REF] Barvinok | A Course in Convexity[END_REF].

Theorem 4 ensures pseudo-moment sequence convergence under Assumptions 1-3. Corollary 8 states that removing Assumption 3 leads to having pseudo-moment sequence convergence only up to a subsequence (z dr ) r .

In our illustrative example one indeed has finite convergence, but there is no a priori reason that each step of the hierarchy will return an optimal pseudo-moment sequence corresponding to the same optimal measure, and one could have for example that for d ≥ 1,

z d = (1, d mod 2, . . . , d mod 2) ∈ R N 2d , where d mod 2 = 1 if d is odd 0 if d is even so that z d would be the truncated moment sequence corre- sponding to optimal solution µ ⋆ d = (d mod 2) δ 1 + (1 -d mod 2) δ 0 = δ d mod 2
. Such a (z d ) d would obviously not converge when the degree d tends to infinity. A natural question that arises then is: how does one modify the original GMP or the moment relaxations in order to retrieve pseudo-moment sequence convergence?

A trivial way to fix this issue is to fix the value of z 1 in the constraints of the GMP:

p ⋆ t := inf (1 -x)x dµ(x) (9a) s.t. µ ∈ M([0, 1]) + 1 dµ(x) = 1 x dµ(x) = t, p d t := inf z 1 -z 2 (9b) s.t. z = (z k ) 0≤k≤2d ∈ R N 2d M d (z) 0 M d-1 (x(1 -x)z) 0 M d-1 (1 -x 2 )z 0 z 0 = 1 z 1 = t,
for a given t ∈ [0, 1]. Then, the only solution to (9a) is

µ ⋆ = t δ 1 + (1 -t) δ 0 ,
so that Assumption 3 holds and one retrieves pseudo-moment sequence convergence (and finite convergence still holds), as the unique minimizer for (9b) is

z d = (1, t, . . . , t) = x k dµ ⋆ (x) 0≤k≤2d ∈ R N 2d .
Remark 13 (Enforcing uniqueness). It is not always possible to enforce Assumption 3 as we did here without knowing the GMP solution in advance. Another common heuristics to obtain a unique solution in the relaxations consists in adding a penalty in the cost function: instead of minimizing z 1 -z 2 in (7b), one could minimize z 1 -z 2 + ǫ Tr M d (z), for some ǫ ∈ R \ {0}. Then, depending on the sign of ǫ, one would obtain a unique solution z d = (1, . . . , 1) (ǫ < 0) corresponding to µ ⋆ = δ 1 , or z d = (1, 0, . . . , 0) (ǫ > 0) corresponding to µ ⋆ = δ 0 .

We finally get to numerically implement the moment hierarchy corresponding to our illustrating example. In the "fixed" cases, the behavior of the SDP solver is fixed, up to numerical errors. The interesting case is then problem [START_REF] Korda | Convex computation of the maximum controlled invariant set for polynomial control systems[END_REF]. We implemented the corresponding hierarchy of moment problems (7b) with increasing relaxation degree d ∈ N ⋆ 20 . First, not displayed is the fact that we indeed invariably obtained z 0 = 1.0000 and z k = z 1 (up to solver precision) for all k ≥ 2. We implemented the hierarchy in two different frameworks:

• GloptiPoly [START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF], a Matlab toolbox that models moment problems, interfaced with the SDP solvers SeDuMi (see the numerically computed values of z 1 in Table 1a) and Mosek (see Table 1b);

• MomentOpt [START_REF] Weisser | Polynomial and moment optimization in Julia and JuMP[END_REF], an open source Julia module, interfaced with the SDP solver CSDP (see the numerically computed values of z 1 in Table 1c). At first glance it would seem that the sequence (z d,1 ) d decreases when d increases, but looking at specific values shows that it is not the case. What we can deduce from Table 1 is that the sequence (z d,1 ) d seems to converge to 0, so that (z d ) d would converge towards µ ∞ = δ 0 , but we have no proof that it is actually the case. Moreover, the sequence z d = (1, 0, . . . , 0) is already feasible for the degree d = 1 relaxation, so that there is no reason, if the tendency were indeed to go to z 1 = 0, that such constraint is not satisfied already in the first steps of the hierarchy. Also, it is important to notice that the results we obtained are stable, meaning that running the same code always returns the same values for z 1 . In other words, the obtained values only depend on the solver. These tendencies then depend on how the interior point algorithm of the solver is implemented, which is out of the scope of the present work.

d

Conclusion

While usually it is only proved that the optimal values for the moment relaxations of the GMP monotonically converge towards the optimal value of the GMP, this note proves that the solutions of these moment relaxations converge to the actual solution of the GMP in ℓ ∞ 's weak- * topology, provided that some elementary assumptions hold. So far, such proof has only been provided for very specific instances of the GMP (see e.g. [10, Theorem 5.6(b)], [START_REF] Henrion | Approximate volume and integration for basic semialgebraic sets[END_REF]), while here the generic case is completely dealt with. Up to rescaling the problem (which also precludes ill behaviours in the numerical implementations), one can usually enforce quite easily that these conditions are met. As a byproduct of this proof, one also obtains strong duality both in the GMP and its corresponding hierarchy, generalizing the results of [START_REF] Josz | Strong duality in lasserre's hierarchy for polynomial optimization[END_REF]. Among the open questions this note answers, one can cite the weak- * convergence of the moment sequences associated to the OCP [START_REF] Lasserre | Nonlinear optimal control via occupation measures and lmi-relaxations[END_REF] and set approximation problems in [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF][START_REF] Oustry | Inner approximations of the maximal positively invariant set for polynomial dynamical systems[END_REF][START_REF] Victor Magron | Semidefinite approximations of reachable sets for discrete-time polynomial systems[END_REF], as well as the strong duality between the GMP formulation in [START_REF] Marx | A moment approach for entropy solutions to nonlinear hyperbolic partial differential equations[END_REF] and its dual, regardless of the formulation of such dual. Finally, this note should facilitate most proofs of convergence and strong duality related to future applications of Lasserre's moment-SOS hierarchy.

Finally, P d is

  closed as the intersection between the level-1 set of the continuous function z → z 0 and the closed cone X d . Indeed X d is closed as the pre-image of the closed cone S N n,d + m by the (continuous) linear map z → M d-dj (g j z) j∈{1,...,m} .

  In particular, one has p d GM -→ d→∞ p ⋆ GM . Moreover, this automatically yields strong duality p d GM = d d GM and p ⋆ GM = d ⋆ GM and then dual convergence d d GM -→ d→∞ d ⋆ GM .

  Eventually, since Assumptions 1 and 2 hold, Proposition 6 ensures strong duality p d GM = d d GM , so that putting together weak GMP duality and the strenghtening property, one has rule yields strong GMP duality p ⋆ GM = d ⋆ GM .

Figure 1 :

 1 Figure 1: Graph of the function x → (1 -x)x that we minimize.

  particular, one has p d GM -→

	d→∞	p ⋆ GM .
	Moreover, this automatically yields strong duality p d GM = d d GM and p ⋆ GM = d ⋆ GM , where d ⋆ GM and d d GM are the values of the duals (3) and (5), respectively, so that d d GM -→ d→∞ d ⋆ GM .

  Thus, the Banach-Alaoglu theorem [2, Theorem 3.16] yields a weak- * converging subsequence (ẑ dr )

Table 1 :

 1 0.1088 0.1116 0.0982 0.0937 0.0851 0.0762 0.0716 0.0674 0.0649 0.0620 (a) with GloptiPoly and SeDuMi. Numerical solutions of problem (7b)

		1	2	3	4	5	6	7	8	9	10
	z 1 0.3974 0.3094 0.2228 0.2020 0.2103 0.1960 0.1440 0.1400 0.1369 0.0953
	d	11	12	13	14	15	16	17	18	19	20
	z 1 d	1	2	3	4	5	6	7	8	9	10
	z 1 0.3259 0.3034 0.1782 0.1312 0.1092 0.1236 0.0976 0.0898 0.0861 0.0830
	d	11	12	13	14	15	16	17	18	19	20
	z 1 0.0763 0.0744 0.0666 0.0611 0.0564 0.0528 0.0499 0.0473 0.0450 0.0428
					(b) with GloptiPoly and Mosek.
	d	1	2	3	4	5	6	7	8	9	10
	z 1 0.3741 0.0553 0.0772 0.0340 0.0418 0.0280 0.0169 0.0148 0.0121 0.0137
	d	11	12	13	14	15	16	17	18	19	20
	z 1 0.0079 0.0107 0.0082 0.0078 0.0071 0.0074 0.0075 0.0071 0.0059 0.0057
					(c) with MomentOpt and CSDP.

Indeed as B is finite, there exists a finite value of d that captures all inequality constraints; arbitrarily setting this value to 0 does not change our proof for convergence.

Acknowledgements

The author would like to thank Didier Henrion and Jean Bernard Lasserre for fruitful discussions.

This work was funded by the French Company Réseau de Transport d'Électricité.


Marina Cazzola
email: marina.cazzola@unimib.it

Valentina Grazian
email: valentina.grazian@unimib.it

From a mathemagic trick to number bases: using cryptography and the software WIMS to stimulate algebraic thinking in primary school

Keywords: Primary school mathematics, algebraic thinking, educational software

Introduction

 [START_REF] Kieran | The core of algebra: Reflections on its main activities[END_REF]suggests that early algebraic thinking is linked to problem solving, modeling, working with generalizable patterns, justifying and proving, making predictions and conjectures, analyzing relationships, and identifying structure. Many studies reveal that algebraic thinking can be developed at an early stage, as long as it is stimulated by appropriate interventions by the teachers (e.g. [START_REF] Blanton | Characterizing a classroom practice that promotes algebraic reasoning[END_REF]. Indeed, the application of student-active methodologies plays a fundamental role in the teaching process, especially in mathematics, as described by [START_REF] Schoenfeld | Learning to think mathematically: Problem solving, metacognition, and sense-making in mathematics[END_REF]. In this view, our first aim of research is to provide support to improve teachers' practice toward engaging pupils in algebraic activities. We aim to achieve this goal by designing and sharing ready to use materials, which are realizing a problem-solving approach and involve modern technologies. The resulting effect on students' learning is our second aim of research: to examine if this type of instruction truly affects the pupils' capacity for justifying and proving.

We present an activity based on the modern cryptography technique of Hamming codes for error correction that is built around a magic trick and is supported by the software WIMS (WWW Interactive Multipurpose Server, e.g., see [START_REF] Cazzola | WIMS, a Community of Teachers, Developers and Users[END_REF]. The various tasks involved push the students into a learning path that can be described in short as follows:

• Participation in the magic trick • Question: "How does it work?" (problem solving, predictions and conjectures) • First analysis of the trick (analyzing relationships and identifying structure) • Sharing of observations (justifying and proving) • Conclusion (generalizations)

• Bridge to the study of number bases.

The last step is an added value of our activity: students approach a typical algebraic topic associating it to a fun and intriguing game, strengthening their motivation to learn about it. A detailed description of the experience can be found in [START_REF] Cazzola | Elementary cryptography games for primary school students through WIMS[END_REF].

Description of the activity

The game we present is called "7 questions and 1 lie". A volunteer is asked to think about a number from 0 to 15 and to answer 7 yes/no questions about it, with the chance to lie only once. Looking at the answers, the mathemagician will be able to guess not only the mysterious number, but also if there was a lie and the question it corresponds to. Once the pupils' attention is caught, the real work starts, leading the students to find an answer to the obvious question "how does it work?".

The solution involves the use of a particular scheme (Figure 1) containing 7 numbered circles. Each circle corresponds to the question with the associated number and the instruction is to blacken it if the answer is "yes" and to leave it blank otherwise. The analysis of the patterns will reveal the solution. Also, if we impose that a blackened circle corresponds to 1 and a blank one corresponds to 0, once the lies are detected and the coloring is fixed, the expression of the mysterious number in base 2 is given by the sequence of 0's and 1's given by the first 4 circles. This unusual approach to the study of number bases captures students' attention and motivates the pupils in discovering more about this algebraic topic. Our activity can be presented using pen and paper only but becomes even more interesting if supported by its digital version, which we elaborated using the software WIMS. The dedicated WIMS page contains the magic trick, a stepby-step solution and a series of games aimed at practicing the description of numbers using different number bases.

Our experience

We presented the activity to four classes of 8-9 years old Italian students, for a total of 78 pupils, in Spring 2021. We conducted classroom observations and collected written students' feedbacks. During the activity we recognized that pupils were actively engaged and carried out various examples of algebraic reasoning (especially in the form of making and motivating conjectures). This encourages us to further explore this approach and to deepen our investigation on its effects on pupils' argumentation abilities. Furthermore, we could observe that pupils and teachers reacted enthusiastically to the tasks, strengthening our belief that this kind of proposal can also contribute to the diffusion of problem-solving and student-centered methodologies in primary school education.

Figure 1 :

 1 Figure 1: Scheme to solve the "7 question and 1 lie" magic trick