Marta Abril Bucero

Bernard Mourrain

Exact relaxation for polynomial optimization on semi-algebraic sets

In this paper, we study the problem of computing the infimum of a real polynomial function f on a closed basic semialgebraic set S and the points where this infimum is reached, if they exist. We show that when the infimum is reached, a Semi-Definite Program hierarchy constructed from the Karush-Kuhn-Tucker ideal is always exact and that the vanishing ideal of the KKT minimizer points is generated by the kernel of the associated moment matrix in that degree, even if this ideal is not zero-dimensional. We also show that this relaxation allows to detect when there is no KKT minimizer. Analysing the properties of the Fritz John variety, we show how to find all the minimizers of f . We prove that the exactness of the relaxation depends only on the real points which satisfy these constraints. This exploits representations of positive polynomials as elements of the preordering modulo the KKT ideal, which only involves polynomials in the initial set of variables. The approach provides a uniform treatment of different optimization problems considered previously. Applications to global optimization, optimization on semialgebraic sets defined by regular sets of constraints, optimization on finite semialgebraic sets and real radical computation are given.

Introduction

The problem we consider in this paper is the following:

inf x∈R n f (x) (1) s.t. g 0 1 (x) = • • • = g 0 n 1 (x) = 0 g + 1 (
x) ≥ 0, . . . , g + n 2 (x) ≥ 0 where f, g 0 1 , . . . , g 0 n 1 , g + 1 , . . . , g + n 2 ∈ R[x] are polynomial functions in n variables x 1 , . . . , x n . Hereafter, we fix the set of constraints g = {g 0 1 , . . . , g 0 n 1 ; g + 1 , . . . , g + n 2 } = {g 0 ; g + } and denoted by S the basic semi-algebraic set defined by these constraints.

The points x * ∈ S which satisfy f (x * ) = inf x∈S f (x) are called the minimizers points of f on S. If the set of minimizers is not empty, we say that the minimization problem is feasible.

The objectives of the method we consider are to detect if the minimization problem is feasible and to compute the minimum value of f and the minimizer points where this minimum value is reached, when the problem is feasible. Though this global minimization problem is known to be NP-hard (see e.g. [START_REF] Nesterov | Squared functional systems and optimization problems[END_REF]), a practical challenge is to devise methods which can approximate or compute efficiently the solutions of the problem. About a decade ago, a relaxation approach has been proposed in [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF] (see also [START_REF] Parrilo | Semidefinite programming relaxations for semialgebraic problems[END_REF], [START_REF] Shor | Class of global minimum bounds of polynomial functions[END_REF]) to solve this difficult problem. Instead of searching points where the polynomial f reaches its minimum f * , a probability measure which minimizes the function f is searched. This problem is relaxed into a hierarchy of finite dimensional convex minimization problems, which can be solved by Semi-Definite Programming (SDP) techniques. The sequence of SDP minima converges to the minimum f * [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF]. This hierarchy of SDP problems can be formulated in terms of linear matrix inequalities on moment matrices associated to the set of monomials of degree t or less, for increasing values of t. The dual hierarchy can be described as a sequence of maximization problems over the cone of polynomials that are Sums of Squares (SoS). A feasibility condition is needed to prove that this dual hierarchy of maximization problems also converges to the minimum f * , i.e. that there is no duality gap.

This approach provides a very interesting way to approximate a global optimum of a polynomial function on S. But one may wonder if using this approach, it is possible to compute in a finite number of steps, this minimum and the minimizer points when the problem is feasible. From a computational point of view, the following issues need to be addressed:

(1) Is it possible to use an exact SDP hierarchy, i.e. which converges in a finite number of steps? (2) How can we recover all the points where the optimum is achieved if the optimization problem is feasible? To address the first issue, the following strategy has been considered: add polynomial inequalities or equalities satisfied by the points where the function f is minimum.

A first family of methods are used when the set S is compact or when the minimizer set can be bounded easily. By adding an inequality constraint, one can then transform S into a compact subset of R n , for which exact hierarchies can be used [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF], [START_REF] Marshall | Optimization of polynomial functions[END_REF]. It is shown in [START_REF] Laurent | Semidefinite representations for finite varieties[END_REF] that if the complex variety defined by the equalities g 0 = 0 is finite (and thus S is compact), then the hierarchy of relaxation problems introduced by Lasserre in [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF] is exact. It is also proved that there is no duality gap if the generators of this ideal satisfy some regularity conditions. In [START_REF] Nie | Polynomials optimization with real variety[END_REF], it is proved that if the real variety defined by the equalities g 0 = 0 is finite, then the hierarchy of relaxation problems introduced by Lasserre is exact, this answers an open question in [START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF].

In a second family of methods, equality constraints which are naturally satisfied by the minimizer points are added. These constraints are for instance the gradient of f when S = R n or the Karush-Kuhn-Tucker (KKT) constraints, obtained by introducing Lagrange multipliers. In [START_REF] Nie | Minimizing polynomials via sum of squares over gradient ideal[END_REF], it is proved that a relaxation hierarchy using the gradient constraints is exact when the gradient ideal is radical. In [START_REF] Marshall | Representations of non-negative polynomials, degree bounds and applications to optimization[END_REF], it is shown that this gradient hierarchy is exact, when the global minimizers satisfy the Boundary Hessian condition. In [START_REF] Demmel | Representations of positive polynomials on noncompact semialgebraic sets via kkt ideals[END_REF], it is proved that a relaxation hierarchy which involves the KKT constraints is exact when the KKT ideal is radical. In [START_REF] Ha | Representation of positive polynomials and optimization on noncompact semialgebraic sets[END_REF], a relaxation hierarchy obtained by projection of the KKT constraints is proved to be exact under a regularity condition on the real minimizer points 1 . In [START_REF] Nie | An exact jacobian SDP relaxation for polynomial optimization[END_REF], a similar relaxation hierarchy is shown to be exact under a stronger regularity condition for the complex points of associated KKT varieties. These regularity conditions require that the gradient of the active constraints evaluated at the points of S or of some complex varieties are linearly independent. Thus they cannot be used for general semi algebraic sets S, for instance when S is a real non-complete intersection variety.

Moreover, the assumption that the minimum is reached at a KKT point is required. Unfortunately, in some cases the set of KKT points of S can be empty. As we shall see, this obstacle can be removed using Fritz John variety (see [START_REF] John | Extremum problems with inequalities as side conditions[END_REF][START_REF] Mangasarian | The Fritz John necessary optimality conditions in the presence of equality and inequality constraints[END_REF]). There is not much work dedicated to this issue (see [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]).

The case where the infimum value is not reached has also been studied. In [START_REF] Schweighofer | Global optimization of polynomials using gradient tentacles and sums of squares[END_REF], relaxation techniques are studied for functions for which the minimum is not reached and which satisfy some special properties "at infinity". In [START_REF] Ha | Global optimization of polynomials using the truncated tangency variety[END_REF], tangency constraints are used in a relaxation hierarchy which converges to the global minimum of a polynomial, when the polynomial 1 The results of this paper are true but a problem appears in the proof which we fix in the present paper.

is bounded by below over R n . In [START_REF] Guo | Global optimization of polynomials using generalized critical values and sums of squares[END_REF], generic changes of coordinates and a partial gradient ideal are used in a relaxation hierarchy which also converges to the global minimum of f on R n .

In the cases studied so far, the exactness of the relaxation is proved under a genericity condition or a compactness property. From an algorithmic point of view, the flat extension condition of Curto-Fialkow [START_REF] Curto | Solution of the truncated complex moment problem for flat data[END_REF] is used in most of the works [START_REF] Henrion | Positive Polynomials in Control, chapter Detecting Global Optimality and Extracting Solutions in GloptiPoly[END_REF][START_REF] Laurent | Semidefinite representations for finite varieties[END_REF][START_REF] Lasserre | A unified approach for real and complex zeros of zerodimensional ideals[END_REF][START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF] to detect the exactness of the hierarchy, when the number of minimizers is finite. In [START_REF] Nie | Certifying convergence of Lasserre's hierarchy via flat truncation[END_REF], it is proved that the Curto-Fialkow flat extension criterion is eventually satisfied on truncated moment matrices under some regularity conditions or archimedean conditions. In [START_REF] Lasserre | Moment matrices, border bases and real radical computation[END_REF], a sparse extension [START_REF] Laurent | A generalized flat extension theorem for moment matrices[END_REF] of this flat extension condition is used to compute zero-dimensional real radical ideals.

The second issue is related to the problem of computing all the minimizer points, which is also important from a practical point of view. In [START_REF] Lasserre | A unified approach for real and complex zeros of zerodimensional ideals[END_REF], the kernel of moment matrices is used to compute generators of the real radical of an ideal. This method is improved in [START_REF] Lasserre | Moment matrices, border bases and real radical computation[END_REF] to compute a border basis of the real radical, involving SDP problems of significantly smaller size, when the real radical ideal is zero-dimensional. The case of positive dimensional real radical ideal is analysed in [START_REF] Rostalki | Algebraic moments,real root finding and related topics[END_REF] and [START_REF] Ma | A certificate for semidefinite relaxations in computing positive dimensional real varieties[END_REF]. The problem of computing the minimizer ideal for general optimization problems from exact relaxation hierarchies has not been addressed, though it is mentioned in [START_REF] Nie | Certifying convergence of Lasserre's hierarchy via flat truncation[END_REF] for zero-dimensional minimizer ideals Notice that Problem (1) can be attacked from a purely algebraic point of view. It reduces to the computation of a (minimal) critical value and polynomial system solvers can be used to tackle it (see e.g. [START_REF] Parrilo | Minimizing polynomial functions[END_REF], [START_REF] Greuet | Deciding reachability of the infimum of a multivariate polynomial[END_REF]). But in this case, the complex solutions of the underlying algebraic system come into play and additional computation efforts should be spent to remove these extraneous solutions. Semi-algebraic techniques such as Cylindrical Algebraic Decomposition or extensions [START_REF] Din | Computing the global optimum of a multivariate polynomial over the reals[END_REF] may also be considered here, providing algorithms to solve Problem (1), but suffering from similar issues. Contributions. Our aim is to show that for the general polynomial optimization problem (1), exact SDP relaxations can be constructed, which either detect that the problem is infeasible or compute the minimal value and the ideal associated to the minimizer points. The main contributions are the following:

• We prove that exact relaxation hierarchies depending on the variables x can be constructed for solving the optimization problem (1) (see Theorem 6.3 and Theorem 5.10). • We show that even if the minimizer points are not KKT points, we can find them using the Fritz John variety (see Section 3.3 and Section 3.4). We describe an approach, which splits this minimizer set into the KKT minimizer set and the singular minimizer set which can be recursively computed using the same method. • We prove that if the set of KKT minimizers is empty, the SDP relaxation will eventually be empty (Theorem 6.3). • We prove that the KKT minimizer ideal can be constructed from the moment matrix of an optimal linear form, when the corresponding relaxation is exact, even if the ideal is not zero-dimensional (Theorem 5.10). • We prove that the exactness of the relaxation depends only on the real points which satisfy these constraints (Theorem 5.10). • We provide a general approach which allows us to treat in a uniform way and to extend results on the representation of polynomials which are positive (resp. nonnegative) on the critical points (see [START_REF] Demmel | Representations of positive polynomials on noncompact semialgebraic sets via kkt ideals[END_REF] and Theorem 4.9) and on the exactness of relaxation hierarchies (see [START_REF] Nie | Minimizing polynomials via sum of squares over gradient ideal[END_REF], [START_REF] Ha | Global optimization of polynomials using the truncated tangency variety[END_REF], [START_REF] Lasserre | A unified approach for real and complex zeros of zerodimensional ideals[END_REF], [START_REF] Nie | An exact jacobian SDP relaxation for polynomial optimization[END_REF], [START_REF] Lasserre | Moment matrices, border bases and real radical computation[END_REF], [START_REF] Nie | Polynomials optimization with real variety[END_REF] and Theorem 6.2, Theorem 6.4, Theorem 6.5, Theorem 6.6).

Content. The paper is organized as follows. In Section 2, we recall algebraic concepts and describe the hierarchy of finite dimensional convex optimization problems considered.

In Section 3, we analyse the varieties associated to the critical points of the minimization problem. Section 4, is devoted to the representation of positive and non-negative polynomials on the critical points as sum of squares modulo the gradient ideal. In Section 5, we prove that when the order of relaxation is big enough, the sequence of finite dimensional convex optimization problems attains its limit and the minimizer ideal can be generated from the solution of our relaxation problem. In Section 6, we analyse some consequences of these results. Finally, Section 7 contains several examples which illustrate the approach.

Ideals, varieties, optimization and relaxation

In this section, we recall some algebraic concepts as ideals and varieties and we set our notation.

2.1. Ideals and varieties. Let K[x] be the set of the polynomials in the variables x = (x 1 , . . ., x n ), with coefficients in the field K. Hereafter, we choose

2 K = R or C. Let K denotes the algebraic closure of K. For α ∈ N n , x α = x α 1 1 • • • x αn n
is the monomial with exponent α and degree |α| = i α i . The set of all monomials in x is denoted M = M(x).

For t ∈ N ∪ {∞} and B ⊆ K[x], we introduce the following sets:

• B t is the set of elements of B of degree ≤ t, • B = f ∈B λ f f | f ∈ B, λ f ∈ K is the linear span of B, • (B) = f ∈B p f f | p f ∈ K[x], f ∈ B is the ideal in K[x] generated by B, • B t = f ∈Bt p f f | p f ∈ K[x] t-deg(f ) is the vector space spanned by {x α f | f ∈ B t , |α| ≤ t -deg(f )}, • Q + t = l i=1 p 2 i | l ∈ N, p i ∈ R[x]
t is the set of finite sums of squares of polynomials of degree ≤ t;

Q + = Q + ∞ . By definition B t ⊆ (B) ∩ K[x] t = (B) t ,
Q t (C) = { n 2 i=1 c 0 i h i + s 0 + n 2 j=1 c + j s j | h i ∈ R[x] 2t-deg(c 0 i ) , s 0 ∈ Q + t , s i ∈ Q + t-⌈deg(c + i )/2⌉ }. If C is such that C0 = C 0 and C+ = { (c + 1 ) ǫ 1 • • • (c + n 2 ) ǫn 2 | ǫ i ∈ {0, 1}}, Q t ( C) is also called the (truncated) preordering of C and denoted P t (C). When t = ∞, P(C) := P ∞ (C)
is the preordering of C. The (truncated) preordering generated by the positive constraints is denoted

P + (C) = P(C + ). Definition 2.2. Given t ∈ N ∪ {∞} and a set of constraints C ⊂ R[x], we define N t (C) := {Λ ∈ (R[x] 2t ) * | Λ(p) ≥ 0, ∀p ∈ Q t (C), Λ(1) = 1}.
When we replace Q t (C) by P t (C) in this definition, we denote the corresponding set by L t (C).

Given a set I ⊆ K[x] and a field L ⊇ K, we denote by

V L (I) := {x ∈ L n | f (x) = 0 ∀f ∈ I} its associated variety in L n . By convention V(I) = V K (I)
, where K is the algebraic closure of K. We also consider sets of homogeneous equations I and the varieties PV(I) (resp. PV R (I)) defined in the projective space P n (resp. the real projective space RP n ).

For a set V ⊆ K n , we define its vanishing ideal

I(V ) := {p ∈ K[x] | p(v) = 0 ∀v ∈ V }. For a set V ⊂ L n with L ⊇ K, V K = V ∩ K n . Hereafter, we take K = R and L = C, so that V(I) = V C (I), V R (I) = V(I) R = V(I) ∩ R n . Definition 2.3. For a set of constrains C = (C 0 ; C + ) ⊂ R[x], S(C) := {x ∈ R n | c 0 (x) = 0 ∀c 0 ∈ C 0 , c + (x) ≥ 0 ∀c + ∈ C + }, S + (C) := {x ∈ R n | c + (x) ≥ 0 ∀c + ∈ C}.
To describe the vanishing ideal of these sets, we introduce the following ideals:

Definition 2.4. For a set of constraints C = (C 0 ; C + ) ⊂ R[x], √ C 0 = {p ∈ R[x] | p m ∈ (C 0 ) for some m ∈ N \ {0}} R √ C 0 = {p ∈ R[x] | p 2m + q ∈ (C 0 ) for some m ∈ N \ {0}, q ∈ Q + } C + √ C 0 = {p ∈ R[x] | p 2m + q ∈ (C 0 ) for some m ∈ N \ {0}, q ∈ P + (C)}
These ideals are called respectively the radical of C 0 , the real radical of C 0 , the C + -radical of C 0 .

Remark 2.5.

If C + = ∅, then C + √ C 0 = R √ C 0 .
The following three famous theorems relate vanishing and radical ideals:

√ C 0 = I(V C (C 0 )). (ii) Real Nullstellensatz (see, e.g., [1, §4.1]) R √ C 0 = I(V R (C 0 )). (iii) Positivstellensatz (see, e.g., [1, §4.4]) C + √ C 0 = I(S(C)) = I(V R (C 0 ) ∩ S + (C)).
2.2. Relaxation hierarchy. The approach proposed by Lasserre in [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF] to solve Problem (1) consists in approximating the optimization problem by a sequence of finite dimensional convex optimization problems, which can be solved efficiently by Semi-Definite Programming tools. This sequence is called Lasserre hierarchy of relaxation problems. Let C be a set of constraints in R[x] such that S(C) = S(g). Hereafter, we consider the relaxation hierarchy associated to preordering sequences:

• • • ⊂ L t+1 (C) ⊂ L t (C) ⊂ • • • and • • • ⊂ P t (C) ⊂ P t+1 (C) ⊂ • • •
These convex sets are used to define extrema that approximate the solution of the minimization problem (1).

Definition 2.7. Let t ∈ N and let C be the set of constraints in R[x]. We define the following extrema:

• f * C = inf x∈S(C) f (x), • f µ t,C = inf {Λ(f ) s.t. Λ ∈ L t (C)}, • f sos t,C = sup {γ ∈ R s.t. f -γ ∈ P t (C)}.

By convention if the corresponding sets are empty, f

* C = -∞, f sos t,C = -∞ and f µ t,C = +∞. Remark 2.8. We have f sos t,C ≤ f µ t,C ≤ f * C . Indeed, if there exists γ ∈ R such that f -γ = q ∈ P t (C) then ∀Λ ∈ L t (C), Λ(f -γ) = Λ(f ) -γ = Λ(q) ≥ 0, which proves the first inequality.
Since for any s ∈ S, the evaluation

1 s : p ∈ R[x] → p(s) is in L t (C), we have 1 s (f ) = f (s) ≥ f µ t,C
. This proves the second inequality.

As L t+1 (C) ⊂ L t (C) and P t (C) ⊂ P t+1 (C) we have the following increasing sequences for t ∈ N:

• • • f µ t,C ≤ f µ t+1,C ≤ • • • ≤ f * C and • • • f sos t,C ≤ f sos t+1,C ≤ • • • ≤ f * C .
The foundation of Lasserre relaxation method is to show that these sequences converge to f * C , see [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF]. We are interested in constructing hierarchies for which, the minimum f * C is reached in a finite number of steps. Such hierarchies are called exact. We are also interested to compute the minimizers points. For that purpose, we introduce now the truncated Hankel operators, which play a central role in the construction of the minimizer ideal of f on S. Definition 2.9. For t ∈ N and a linear form Λ ∈ (R[x] 2t ) * , we define the truncated Hankel operator as the map

M t Λ : R[x] t → (R[x] t ) * such that M t Λ (p)(q) = Λ(p q) for p, q ∈ R[x] t . Its matrix in monomial bases of R[x] t and (R[x] t ) * is also called the moment matrix of Λ.
The kernel of the truncated Hankel operator is

(2) ker M t Λ = {p ∈ R[x] t | Λ(p q) = 0 ∀q ∈ R[x] t }. Given t ∈ N and C = {0} and Λ, Λ ′ ∈ R[x] *
2t , we easily check the following properties:

• ∀p ∈ R[x] t , Λ(p 2 ) = 0 implies p ∈ ker M t Λ . • ker M t Λ+Λ ′ = ker M t Λ ∩ ker M t Λ ′ .
The kernel of truncated Hankel operator is used to compute generators of the minimizer ideal, as we will see.

Varieties of critical points

Before describing how to compute the minimizer points, we analyse the geometry of this minimization problem and the varieties associated to its critical points. In the following, we denote by y = (x, u, v) and z = (x, u, v, s), the n + n 1 + n 2 and n + n 1 + 2n 2 variables of these problems. For any ideal J ⊂ R[z], we denote

J x = J ∩ R[x]. The projection of C n × C n 1 +2 n 2 (resp. C n × C n 1 + n 2 ) on C n is denoted π x .
3.1. The gradient variety. A natural approach to deal with constraints in optimization problems is to introduce Lagrangian multipliers. Replacing the inequalities g + i ≥ 0 by the equalities g + is 2 i = 0 (adding new variables s i ) and introducing new parameters for all the equality constraints yields the following minimization problem:

inf (x,u,v,s)∈R n ×R n 1 +2 n 2 f (x) (3) s.t. ∇F (x, u, v, s) = 0 where F (x, u, v, s) = f (x) -n 1 i=1 u i g i (x) -n 2 j=1 v j (g + j (x) -s 2 j ), u = (u 1 , ..., u n 1 ), v = (v 1 , ..., v n 2 ) and s = (s 1 , ..., s n 2 ).
Definition 3.1. The gradient ideal of F (z) is:

I grad = (∇F (z)) = (F 1 , ..., F n , g 0 1 , ..., g 0 n 1 , g + 1 -s 2 1 , ..., g + n 2 -s 2 n 2 , v 1 s 1 , ..., v n 2 s n 2 ) ⊂ R[z]
where

F i = ∂f ∂x i -n 1 j=1 u j ∂g 0 j ∂x i -n 2 j=1 v j ∂g + j ∂x i . The gradient variety is V grad = V(I grad ) and we denote V x grad = π x (V grad ). Definition 3.2. For any F ∈ R[z]
, the values of F at the (resp. real) points of V(∇F ) = V grad are called the (resp. real) critical values of F .

We easily check the following property:

Lemma 3.3. F | V grad = f | V grad .
Thus minimizing F on V grad is the same as minimizing f on V grad , that is computing the minimal critical value of F .

3.2.

The Karush-Kuhn-Tucker variety. In the case of a constrained problem, one usually introduce the Karush-Kuhn-Tucker (KKT) constraints:

Definition 3.4. A point x * is called a KKT point if there exists u 1 , . . . , u n 1 , v 1 , . . . , v n 2 ∈ R s.t. ∇f (x * ) - n 1 i=1 u i ∇g 0 i (x * ) - n 2 j=0 v j ∇g + j (x * ) = 0, g 0 i (x * ) = 0, v j g + j (x * ) = 0.
The corresponding minimization problem is the following:

inf (x,u,v)∈R n+n 1 n 2 f (x) (4) s.t. F 1 = • • • = F n = 0 g 0 1 = • • • = g 0 n 1 = 0 v 1 g + 1 = • • • = v n 2 g + n 2 = 0 g + 1 ≥ 0, . . . , g + n 2 ≥ 0
where

F i = ∂f ∂x i -n 1 j=1 u j ∂g 0 j ∂x i -n 2 j=1 v j ∂g + j ∂x i .
This leads to the following definitions:

Definition 3.5. The Karush-Kuhn-Tucker (KKT) ideal associated to Problem (1) is

(5)

I KKT = (F 1 , ..., F n , g 0 1 , ..., g 0 n 1 , v 1 g + 1 , ..., v n 2 g + n 2 ) ⊂ R[y]. The KKT variety is V KKT = V(I KKT ) ⊂ C n × C n 1 +n 2 and the real KKT variety is V R KKT = V KKT ∩ (R n × R n 1 +n 2 ). Its projection on x is V x KKT = π x (V KKT ), where π x is the projection of C n × C n 1 +n 2 onto C n .
The set of KKT points of S is denoted S KKT and a KKT-minimizer of f on S is a point

x * ∈ S KKT such that f (x * ) = min x∈S KKT f (x). Notice that V x,R KKT = π x (V KKT ) R = π x (V R KKT )
, since any linear dependency relation between real vectors can be realized with real coefficients.

The KKT ideal is related to the gradient ideal as follows:

Proposition 3.6.

I KKT = I grad ∩ R[y]. Proof. As s i (s i v i ) + v i (g + i -s 2 i ) = v i g + i ∀i = 1, ..., n 2 , we have I KKT ⊂ I grad ∩ R[y].
In order to prove the equality, we use the property that if K is a Groebner basis of I grad for an elimination ordering such that s ≫ x, u, v then K ∩ R[y] is the Groebner basis of I grad ∩ R[y] (see [START_REF] Cox | Ideals, Varieties, and Algorithms : An Introduction to Computational Algebraic Geometry and Commutative Algebra[END_REF]). Notice that s i (s

i v i ) + v i (g + i -s 2 i ) = v i g + i (i = 1, ..., n 2
) are the only S-polynomials involving the variables s 1 , . . . , s n 2 which may have a non-trivial reduction.

Thus K ∩ R[y] is also the Groebner basis of F 1 , ..., F n , g 0 1 , ..., g 0 n 1 , v 1 g + 1 , ..., v n 2 g + n 2 and we have (K) ∩ R[y] = I grad ∩ R[y] = I KKT .
The KKT points on S are related to the real points of the gradient variety as follows:

Lemma 3.7. S KKT = π x (V R grad ) = V x,R grad ∩ S + (g). Proof. A real point y = (x, u, v) of V R KKT lifts to a point z = (x, u, v, s) in V R grad , if and only if, g + i (x) ≥ 0 for i = 1, . . . , n 2 . This implies that V R KKT = π y (V R grad ) ∩ S + (g), which gives by projection the equalities S KKT = π x (V R grad ) ∩ S + (g) = π x (V R grad ) since a point x of V R grad satisfies g + j (x) ≥ 0 for j ∈ [1, n 2 ].
This shows that if a minimizer point of f on S is a KKT point, then it is the projection of a real critical point of F .

The Fritz John variety.

A minimizer of f on S is not necessarily a KKT point. More general conditions that are satisfied by minimizers were given by F. John for polynomial non-negativity constraints and further refined for general polynomial constraints [START_REF] John | Extremum problems with inequalities as side conditions[END_REF][START_REF] Mangasarian | The Fritz John necessary optimality conditions in the presence of equality and inequality constraints[END_REF]. To describe these conditions, we introduce a new variable u 0 and denote by y ′ the set of variables y

′ = (x, u 0 , u, v). Let F u 0 i = u 0 ∂f ∂x i -n 1 j=1 u j ∂g 0 j ∂x i -n 2 j=1 v j ∂g + j ∂x i . Definition 3.8. For any γ ⊂ [1, n 1 ], let (6)
I γ F J = (F u 0 1 , ..., F u 0 n , g 0 1 , ..., g 0 n 1 , v 1 g + 1 , ..., v n 2 g + n 2 , u i , i ∈ γ) ⊂ R[y ′ ].
For m ∈ N, the m th Fritz-John (FJ) ideal associated to Problem (1) is

(7) I m F J = ∩ |γ|=m I γ F J . Let V γ F J = V(I γ F J ) ⊂ C n × P n 1 +n 2 . The m th FJ variety is V m F J = V(I m F J ) = ∪ |γ|=m V γ F J , and the real FJ variety is V m,R F J = V m F J ∩ R n × RP n 1 +n 2 . Its projection on x is V m,x F J = π x (V m F J ) = π x (V m F J ). When m = max x∈S rank([∇g 0 1 (x), . . . , ∇g 0 n 1 (x)]), the m th FJ variety is denoted V F J .
Notice that this definition slightly differs from the classical one [START_REF] John | Extremum problems with inequalities as side conditions[END_REF][START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF][START_REF] Mangasarian | The Fritz John necessary optimality conditions in the presence of equality and inequality constraints[END_REF], which does not provide any information when the gradient vectors ∇g 0 i (x), i = 1 . . . n 1 are linearly dependent on S. Proposition 3.9. Any minimizer x * of f on S is the projection of a real point of V R F J . Proof. The proof is similar to Theorem 4.3.2 of [START_REF] Mangasarian | The Fritz John necessary optimality conditions in the presence of equality and inequality constraints[END_REF]. At a minimizer point x * (if it exists) We consider a maximal set of linearly independent gradients ∇g 0 j (x * ) for j ∈ γ (with |γ| ≤ m) and apply the same proof as [21][Theorem 4.3.2]. This shows that x * ∈ V γ,R F J ⊂ V R F J . Definition 3.10. We denote by V sing = V F J ∩ V(u 0 ) the intersection of V F J with the hyperplane u 0 = 0. We easily check that the "affine part" of V F J corresponding to u 0 = 0 is the variety V KKT . Thus, we have the decomposition

V F J = V sing ∪ V KKT , Its projection on C n decomposes as (8) V x F J = V x sing ∪ V x KKT . Let us describe more precisely the projection V x F J onto C n . For ν = {j 1 , . . . , j k } ⊂ [1, n 2 ], we define A ν = [∇f, ∇g 0 1 , . . . , ∇g 0 n 1 , ∇g + j 1 , . . . , ∇g + j k ] V ν = {x ∈ C n | g 0 1 (x) = 0, i = 1 . . . n 1 , g + j (x) = 0, j ∈ ν, rank(A ν ) ≤ m + |ν|}. Let ∆ ν 1 , . . . , ∆ ν lν be polynomials defining the variety {x ∈ C n | rank(A ν ) ≤ m + |ν|}. If n > m + |ν|
, these polynomials can be chosen as linear combinations of (m + |ν|+ 1)-minors of the matrix A ν , as described in [START_REF] Bruns | Determinantal rings[END_REF][START_REF] Nie | An exact jacobian SDP relaxation for polynomial optimization[END_REF]. If n ≤ m + |ν|, we take l ν = 0, ∆ ν i = 0. Let Γ F J be the union of g 0 and the set of polynomials [START_REF] Ha | Representation of positive polynomials and optimization on noncompact semialgebraic sets[END_REF] g ν,i := ∆ ν i j ∈ν g + j ,

for i = 1, . . . , l ν , ν ⊂ [0, n 2 ]. Lemma 3.11. V x F J = ∪ ν⊂[0,n 2 ] V ν = V(Γ F J ). Proof. For any x ∈ C n , let ν(x) = {j ∈ [1, n 2 ] | g + j (x) = 0}. Let y ′ be a point of V F J ,
x its projection on C n and ν(x) = ν = {j 1 , . . . , j k }. We have g + j (x) = 0, v j = 0 for j ∈ ν and ∆ ν i = 0 for i = 1, . . . , l ν . This implies that rank(A ν (x)) ≤ m + |ν| and there exists

(u 0 , u 1 , . . . , u n 1 , v 1 , . . . , v n 2 ) = 0 and γ ⊂ [1, n 1 ] of size |γ| ≤ m such that u 0 ∇f + u 1 ∇g 0 1 + • • • + u n 1 ∇g 0 n 1 + v 1 ∇g + j 1 + • • • + v n 2 ∇g + j k = 0, with u i = 0, i ∈ γ ⊂ [1, n 1 ]. Therefore x ∈ π x (V F J ), which proves that V(g 0 , g ν,i , ν ⊂ [0, n 2 ], i = 1 . . . l ν ) ⊂ π x (V F J ).
Conversely, if x ∈ π x (V F J ) then x ∈ V ν(x) ⊂ ∪ ν V ν which is defined by the polynomials g 0 1 , . . . , g 0 n 1 and g ν,i := ∆ ν i j ∈ν g + j , for i = 1, . . . , l ν , ν ⊂ [0, n 2 ]. Remark 3.12. The real variety π x (V R F J ) = V x F J ∩ R n can also be defined by g 0 and the set Φ F J of polynomials [START_REF] Henrion | Positive Polynomials in Control, chapter Detecting Global Optimality and Extracting Solutions in GloptiPoly[END_REF] g ν := ∆ ν j ∈ν

g + j where ∆ ν = det(A ν A T ν ),
for ν ⊂ [0, n 2 ] and n > m + |ν|, as described in [START_REF] Ha | Representation of positive polynomials and optimization on noncompact semialgebraic sets[END_REF].

Similarly the projection V x sing onto C n can be described as follows. For

ν = {j 1 , . . . , j k } ⊂ [1, n 2 ], B ν = [∇g 0 1 , . . . , ∇g 0 n 1 , ∇g + j 1 , . . . , ∇g + j k ] W ν = {x ∈ C n | g 0 1 (x) = 0, i = 1 . . . n 1 , g + j (x) = 0, j ∈ ν, rank(B ν ) ≤ m + |ν| -1}. Let Θ ν 1 , .
. . , Θ ν lν be polynomials defining the variety {x ∈ C n | rank(B ν ) ≤ m + |ν| -1} and let Γ sing be the union of g 0 and the set of polynomials [START_REF] John | Extremum problems with inequalities as side conditions[END_REF] σ ν,i := Θ ν i j ∈ν

g + j , for ν ⊂ [0, n 2 ], i = 1 . . . l ν .
We similar arguments, we prove the following Lemma 3.13. V x sing = ∪ ν⊂[0,n 2 ] W ν = V(Γ sing ). 3.4. The minimizer variety. By the decomposition (8) and Proposition 3.9, we know that the minimizer points of f on S are in [START_REF] Lasserre | Moment matrices, border bases and real radical computation[END_REF] S F J = S KKT ∪ S sing

where

S F J = π x (V R F J )∩S = π x (V R F J )∩S + (g), S KKT = π x (V R KKT )∩S = π x (V R KKT )∩S + (g), S sing = π x (V R sing ) ∩ S = π x (V R sing ) ∩ S + (g)
. Therefore, we can decompose the initial optimization problem (1) into two subproblems:

(1) find the infimum of f on S KKT ;

(2) find the infimum of f on S sing ; and take the least of these two infima. Since the second problem is of the same type as (1) but with the additional constraints σ ν,i = 0 described in [START_REF] John | Extremum problems with inequalities as side conditions[END_REF], we analyse only the first subproblem. The approach developed for this first sub-problem is applied recursively to the second subproblem, in order to obtain the solution of Problem (1). Definition 3.14. We define the KKT-minimizer set and ideal of f on S as:

S min = {x * ∈ S KKT s.t. ∀x ∈ S KKT , f (x * ) ≤ f (x)} I min = I(S min ) ⊂ R[x].
A point x * in S min is called a KKT-minimizer. Notice that I KKT ⊂ I min and that I min is a real radical ideal.

We have I min = (1), if and only if, the KKT-minimum f * is reached in S KKT .

If n 1 = n 2 = 0, I min is the vanishing ideal of the critical points x * of f (satisfying ∇f (x * ) = 0) where f (x * ) reaches its minimal critical value.

Remark 3.15. If we take f = 0 in the minimization problem [START_REF] Bochnak | Real Algebraic Geometry[END_REF], then all the points of S are KKT-minimizers and I min = I(S) = g + g 0 . Moreover, I KKT ∩ R[x] = (g 0 1 , . . . , g 0 n 1 ) = (g 0 ) since F 1 , . . . , F n , v 1 g + 1 , . . . , v n 2 g + n 2 are homogeneous of degree 1 in the variables u, v.

Representation of positive polynomials

In this section, we analyse the decomposition of polynomials as sum of squares modulo the gradient ideal. Hereafter, J grad is an ideal of R[z] such that V(J grad ) = V grad and C is a set of constraints in R[x] such that S + (C) = S + (g).

The first steps consists in decomposing V grad in components on which f has a constant value. We recall here a result, which also appears (with slightly different hypotheses) in [START_REF] Nie | Minimizing polynomials via sum of squares over gradient ideal[END_REF]Lemma 3

.3] 3 . Lemma 4.1. Let f ∈ R[x] and let V be an irreducible subvariety contained in V C (∇f ). Then f (x) is constant on V .
Proof. If V is irreducible in the Zariski topology induced from C[x], then it is connected in the strong topology on C n and even piecewise smoothly path-connected [START_REF] Shafarevich | Basic algebraic geometry[END_REF]. Let x, y be two arbitrary points of V . There exists a piecewise smooth path ϕ(t) (0 ≤ t ≤ 1) lying inside V such that x = ϕ(0) and y = ϕ(1). Without loss of generality, we can assume that ϕ is smooth between x and y in order to prove that f (x) = f (y). By the Mean Value Theorem, it holds that for some t 1 ∈ (0, 1) Re(f (y)f (x)) = Re(f (ϕ(t))) ′ (t 1 ) = Re((∇f (ϕ(t 1 )) * ϕ ′ (t 1 ))) = 0 since ∇f vanishes on V . Then Re(f (y)) = Re(f (x)). We have the same result for the imaginary part: for some t 2 ∈ (0, 1)

Im(f (y)) -Im(f (x)) = Im(f (ϕ(t))) ′ (t 2 ) = Im((∇f (ϕ(t 2 )) * ϕ ′ (t 2 ))) = 0
since ∇f vanishes on V . Then Im(f (y)) = Im(f (x)). We conclude that f (y) = f (x) and hence f is constant on V .

Lemma 4.2. The ideal J grad can be decomposed as

J grad = J 0 ∩J 1 ∩• • •∩J s with V i = V(J i ) and W i = π x (V i ) where π x (V i ) is the projection of V i on C n such that • f (V j ) = f j ∈ C, f i = f j if i = j, • W R i ∩ S + (C) = ∅ for i = 0, . . . , r, • W R i ∩ S + (C) = ∅ for i = r + 1, . . . , s, • f 0 < • • • < f r .
Proof. Consider a minimal primary decomposition of J grad :

J grad = Q 0 ∩ • • • ∩ Q s ′ ,
where Q i is a primary component, and V(Q i ) is an irreducible variety in C n+n 1 +2n 2 included in V grad . By Lemma 4.1, F is constant on V(Q i ). By Lemma 3.3, it coincides with f on each variety V(Q i ). We group the primary components Q i according to the values f 0 , . . . , f s of f on these components, into J 0 , . . . , J s so that f (V(J

j )) = f i with f i = f j if i = j.
We can number them so that π x (V i ) R ∩ S + (C) is empty for i = r + 1, . . . , s and contains a real point x i for i = 0, . . . , r. Notice that such a point x i is in S, since it satisfies g 0 (x i ) = 0 ∀g 0 ∈ C 0 and g + (x i ) ≥ 0 ∀g + ∈ C + . As it is the limit of the projection of points in V(J i ) on which f is constant, we have f i = f (x i ) ∈ R for i = 0, . . . , r. We can then order J 0 , . . . , J r so that f 0 < • • • < f r .

Remark 4.3. If the minimum of f on S is reached at a KKT-point, then we have f 0 = min x∈S f (x).

Remark 4.4. If V R grad = ∅, then for all i = 0, . . . , s, W R i ∩ S + (C) = ∅ and by convention, we take r = -1.

Lemma 4.5. There exist p

0 , . . . , p s ∈ C[x] such that • s i=0 p i = 1 mod J grad , • p i ∈ j =i J j , • p i ∈ R[x] for i = 0, . . . , r.
Proof. Let (L i ) i=0,...,s be the univariate Lagrange interpolation polynomials at the values f 0 , . . . , f s ∈ C and let q i (x) = L i (f (x)).

The polynomials q i are constructed so that

• q i (V j ) = 0 if j = i, • q i (V i ) = 1,
where V i = V(J i ). As the set {f r+1 , . . . , f s } is stable by conjugation and f 0 , . . . , f r ∈ R, by construction of the Lagrange interpolation polynomials we deduce that q 0 , . . . , q r ∈ R[x].

By Hilbert's Nullstellensatz, there exists N ∈ N such that q N i ∈ j =i J j . As s j=0 q N j = 1 on V grad and q N i q N j = 0 mod i J i = J grad for i = j, we deduce that there exists N ′ ∈ N such that

0 = (1 - s j=0 q N j ) N ′ mod J grad = 1 - s j=0 (1 -(1 -q N j ) N ′ ) mod J grad .
As the polynomial

p i = 1 -(1 -q N j ) N ′ ∈ C[x]
is divisible by q N j , it belongs to j =i J j . Since q j ∈ R[x] for j = 0, . . . , r, we have p j ∈ R[x] for j = 0, . . . , r, which ends the proof of this lemma.

Lemma 4.6. -1 ∈ P + (C) + ( i>r J x i ).

Proof.

As i>r π x (V i ) R ∩S + (C) = V R ( i>r J i ∩R[x])∩S + (C) = V R ( i>r J x i )∩S + (C) = ∅, we have I(V R ( i>r J x i ) ∩ S + (C)) = R[x] ∋
+ (C) + ( s i=0 J x i ) = P + (C) + J x grad . In this case, ∀p ∈ R[x], p = 1 4 ((p + 1) 2 -(p -1) 2 ) ∈ P + (C) + J x grad . If C 0 is chosen such that V (C 0 ) ⊂ V x
grad then S min = ∅ if and only if -1 ∈ P(C). We recall another useful result on the representation of positive polynomials (see for instance [START_REF] Demmel | Representations of positive polynomials on noncompact semialgebraic sets via kkt ideals[END_REF]):

Lemma 4.8. Let J ⊂ R[z] and V = V(J) such that f (V ) = f * with f * ∈ R + . There exists t ∈ N, s.t. ∀ǫ > 0, ∃ q ∈ R[x] with deg(q) ≤ t and f + ǫ = q 2 mod J.
Proof. We know that f +ǫ f * +ǫ -1 vanishes on V. By Hilbert's Nullstellensatz ( f +ǫ f * +ǫ -1) l ∈ J for some l ∈ N. From the binomial theorem, it follows that

(1 + ( f + ǫ f * + ǫ -1)) 1/2 ≡ l-1 i 1/2 k ( f + ǫ f * + ǫ -1) k def = q √ f * + ǫ mod J Then f + ǫ = q 2 mod J.
In particular, if

f * > 0 this lemma implies that f = (f -1 2 f * ) + 1 2 f * = q 2 mod J for some q ∈ R[x]. Theorem 4.9. Let C ⊂ R[x] be a set of constraints such that S + (C) = S + (g), let f ∈ R[x], let f 0 < • • • < f r
be the real KKT critical values of f on S and let p 0 , . . . , p r be the associated polynomials defined in Lemma 4.5.

(1) f -r i=0 f i p 2 i ∈ P + (C) + J x grad . (2) If f ≥ 0 on S KKT , then f ∈ P + (C) + J x grad .
(3) If f > 0 on S KKT , then f ∈ P + (C) + J x grad . Proof. By Lemma 4.5, we have

1 = ( s i=0 p i ) 2 = s i=0 p 2 i mod J grad . Thus f = s i=0 f p 2 i mod J grad . By Lemma 4.6, -1 ∈ P + (C) + ( j>r J x j ) so that f = 1 4 ((f + 1) 2 -(f -1) 2 ) ∈ P + (C) + ∩ j>r J x j and ( 13
)
i>r f p 2 i ∈ P + (C) + s j=0 J x j = P + (C) + J x grad .
As the polynomial (ff i ) p 2 i vanishes on V grad , we deduce that

f = r i=0 f i p 2 i + s i=r+1 f p 2 i + J x grad = r i=0 f i p 2 i + P + (C) + J x grad ,
which proves the first point. If f ≥ 0 on S KKT , then f i ≥ 0 for i = 0, . . . , r and r i=0 f i p 2 i ∈ P + (C) so that f ∈ P + (C) + J x grad , which proves the second point.

If f > 0 on S KKT by Lemma 4.8, we have f p

2 i = q 2 i mod J x grad with q i ∈ R[x], which shows that r i=0 f i p 2 i = r i=0 q 2 i mod J x
grad Therefore, r i=0 f i p 2 i ∈ P + (C) + J x grad and f ∈ P + (C) + J x grad by [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF], which proves the third point. This theorem involves only polynomials in R[x] and the points (2) and (3) generalize results of [START_REF] Demmel | Representations of positive polynomials on noncompact semialgebraic sets via kkt ideals[END_REF] on the representation of positive polynomials.

Let us give now a refinement of Theorem 4.9 with a control of the degrees of the polynomials involved in the representation of f as an element of P + (C) + J x grad .

Theorem 4.10. Let C ⊂ R[x] be a set of constraints such that V(C 0 ) ⊂ V x grad and S + (C) = S + (g). If f ≥ 0 on S KKT , then there exists t 0 such that ∀ǫ > 0,

f + ǫ ∈ P t 0 (C). Proof. Let J grad = (C 0 ) ∩ I grad ⊂ R[z], so that V(J grad ) = V grad since V(C 0 ) ⊂ V x
grad . Using the decomposition (13) obtained in the proof of Theorem 4.9, we can choose

t ′ 0 ∈ N and t 0 ≥ t ′ 0 ∈ N big enough such that deg(p i ) ≤ t 0 /2 and i>r f p 2 i ∈ P + t ′ 0 (C) + J grad ∩ R[x] t ′ 0 ⊂ P t 0 (C), since J x grad = (C 0 ) ∩ I x grad ⊂ (C 0 ). Then ∀ǫ > 0, (14)
i>r

(f + ǫ) p 2 i = i>r f p 2 i + i>r ǫ p 2 i ∈ P t 0 (C).
As ∀ ǫ > 0, f + ǫ > 0 on S KKT , i.e, f i + ǫ > 0 for i = 0, . . . , r, we deduce from Lemma 4.8 that if t 0 is big enough, we have [START_REF] Lasserre | Semidefinite characterization and computation of real radical ideals[END_REF] (f + ǫ) p

2 i = q 2 i mod C 0 t 0 ∩ R[x] with deg(q i ) ≤ t 0 /2 for i = 0, . . . , r.
Since 1 -s i=0 p 2 i = 0 mod (C 0 ), we can choose t 0 big enough so that ( 16)

(f + ǫ) - s i=0 (f + ǫ) p 2 i ∈ C 0 t 0 ∩ R[x].
From Equations ( 14), ( 15), ( 16), we deduce that if t 0 ∈ N is big enough, ∀ǫ > 0

f + ǫ ∈ P t 0 (C),
which concludes the proof of the theorem.

Finite convergence

In this section, we show that the sequence of relaxation problems attains its limit in a finite number of steps and that the minimizer ideal can be recovered from an optimal solution of the corresponding relaxation problem. We use the following notation:

• f * = inf x∈S KKT f (x) • S min = {x * ∈ S KKT | f (x * ) = f * }
We first show that S min = ∅ can be detected from an adapted relaxation sequence:

Proposition 5.1. Let C = (C 0 ; C + ) be a set of constraints of R[x], such that S min ⊂ S(C) and V(C 0 ) ⊂ V x KKT and C + = g + . Then S min = ∅, if and only if, there t 0 ∈ N such that ∀t ≥ t 0 , L t (C) = ∅.
Proof. Let J grad = (C 0 ) ∩ I grad and let C ′ be a set of constraints such that (C ′0 ) = J grad ∩ R[x] = J x grad and C ′+ = g + be a finite set. By hypothesis, V(J grad ) = V grad . We deduce from Corollary 4.7 that if S min = ∅, then

-1 ∈ P + (C ′ ) + (C ′0 ) ⊂ P(C) = ∪ t∈N P t (C).
Thus there exists t 0 such that -1 ∈ P t (C) for t ≥ t 0 , which implies that L t (C) = ∅, since if there exists Λ ∈ L t (C), then Λ(1) = 1 and Λ(-1) ≥ 0.

Conversely, suppose that S min = ∅ contains a point x * . As S min ⊂ S(C), for all t ∈ N the evaluation

1 x * at x * restricted to R[x] 2t is an element of L t (C) = ∅.
This proposition gives a way to check whether S min = ∅, using the relaxation sequence L t (C). We are now going to analyse the case where f has KKT minimizers on S.

From now on, we assume that S min = ∅. First, we recall a property similar to [15, Claim 4.7]:

Proposition 5.2. Let C = (C 0 ; C + ) be a set of constraints of R[x]. There exists t 0 ∈ N such that ∀t ≥ t 0 , ∀Λ ∈ L t (C), C + √ C 0 ⊂ (ker M t Λ ).
Proof. Let C 0 = {g 1 , . . . , g l } and let q 1 , . . . , q k be generators of J := C + √ C 0 . By the Positivestllensatz, for j ∈ 1, . . . , k, there exist m j ∈ N * and polynomials u

(j) r ∈ R[x] and σ j ∈ P + (C) such that q 2m j j + σ j = l r=1 u (j) r g r .
Let us take t 0 ∈ N big enough such that u (j) r g r ∈ C t 0 and σ j ∈ P + t 0 (C). Then for all t ≥ t 0 and all Λ ∈ L t (C), we have Λ(u (j) r g r ) = 0, Λ(q 2m j j ) ≥ 0, Λ(σ j ) ≥ 0 and Λ(q 2m j j ) + Λ(σ j ) = 0, which implies that Λ(q 2m j j ) = 0 and q j ∈ ker M t Λ . This proves that (q 1 , . . . , q l ) = J ⊂ (ker M t Λ ). Remark 5.3. With the same arguments, we can show that for any t ′ ∈ N, there exists

t ′ 0 ≥ t ′ such that ∀t ≥ t ′ 0 , ∀Λ ∈ L t (C), Q t ′ ⊂ ker M t Λ ,
where

Q = {q 1 , . . . , q k } generates J = C + √ C 0 .
The next result shows that in the sequence of optimization problems that we consider, the minimum of f on S KKT is reached from some degree.

Theorem 5.4. Let C be a set of constraints of R[x] such that S min ⊂ S(C) ⊂ V x,R
KKT . There exists t 1 ≥ 0 such that ∀t ≥ t 1 ,

(1)

f µ t,C = f * is reached for some Λ * ∈ L t (C), (2) ∀Λ * ∈ L t (C) with Λ * (f ) = f µ t,C = f * , we have p i ∈ ker M t Λ * , ∀i = 1, . . . , r, (3) if V(C 0 ) ⊂ V x KKT then f sos t,C = f µ t,C = f * . Proof. By Theorem 4.9(1) applied to f -f * , we can write f -f * ≡ r i=1 (f i -f * ) p 2 i + h + g. with h ∈ P + (C) and g ∈ I grad ∩ R[x] = √ I KKT ∩ R[x] ⊂ R √ I KKT ∩ R[x] (by Proposition 3.6). Since S(C) ⊂ V x,R KKT = π x (V R KKT ), we have R √ I KKT ∩ R[x] ⊂ I(S(C)) = C + (C 0
) by the Positivstellensatz. We deduce that g ∈ C + (C 0 ). By proposition 5.2, there exists t 1 ≥ t 0 such that for all t ≥ t 1 , for all Λ ∈ L t (C), Λ(g) = 0, Λ(h) ≥ 0.

Let us fix t ≥ t 1 and

Λ * ∈ L t (C) such that Λ * (f ) = f µ t,C . Then Λ * (f -f * ) = r i=1 (f i -f * )Λ * (p 2 i ) + Λ * (h). As f i -f * = f i -f 0 > 0, Λ * (p 2 i ) ≥ 0 and Λ * (h) ≥ 0 (h ∈ P + t (C)), we deduce that Λ * (f -f * ) = Λ * (f ) -f * ≥ 0.
As ∅ = S min ⊂ S(C), we have Λ * (f ) ≤ f * (by Remark 2.8), so that Λ * (f ) = f µ t,C = f * , which proves the first point. Hence for i = 1, . . . , r, Λ * (p 2 i ) = 0 and p i ∈ ker M t Λ * , which proves the second point.

To prove that f sos t,C = f * when V(C 0 ) ⊂ V x KKT , we apply Theorem 4.10 to ff * which is positive on S KKT . Let us take J grad = (C 0 ) ∩ I grad ⊂ R[z]. We denote by C the set of constraints such that C0 is a finite family of generators of J grad ∩ R[x] and C+ = C + . By Theorem 4.10, there exists t 0 such that ∀ǫ > 0,

f -f * + ǫ ∈ P t 0 ( C). As ( C0 ) = (C 0 ) ∩ I grad ⊂ (C 0 ), we can choose t 1 ≥ t 0 such that C t 0 ⊂ C t 1 and P t 0 ( C) ⊂ P t 1 (C). Then ∀t ≥ t 1 , f -f * + ǫ ∈ P t (C).
Hence by maximality, ∀ǫ > 0, f *ǫ ≤ f sos t,C . We deduce that f * ≤ f sos t,C , which implies that f sos t,C = f µ t,C = f * and proves the third point.

As for the construction of generators of C + √ I KKT (Proposition 5.2), we can construct generators of I min from the kernel of a truncated Hankel operator associated to any linear form which minimizes f , using the following propositions: Proposition 5.5. I min = (p 1 , ..., p r ) + C + I x KKT .

Proof. First of all, we proof that I z min = (p 1 , ..., p r ) + C + I grad = (p 1 , ..., p r ) + R I grad . Using the decomposition of Lemma 4.2 and the polynomials p i of Lemma 4.5, we have

V R grad = (V 0 ∪ V 1 ∪ • • • ∪ V s ) ∩ R n+n 1 +2 n 2 = V R 0 ∪ • • • ∪ V R r , By construction, I(V R 0 ) = I z min , p i (V R 0 ) = 0 for i = 1, . . . , s and p i ∈ R[x]
for i = 0, . . . , r. This implies that p i ∈ I z min for i = 1, . . . , r. As V R 0 ⊂ V R grad , we also have C + I grad ⊂ I z min . We have proved so far that (p 1 , . . . , p r ) + C + I grad ⊂ I z min . In order to prove the reverse inclusion, we denote by q 1 , . . . , q m a family of generators of the ideal I z min . Take one of these generators q j (1 ≤ j ≤ m). By construction, q j p 0 (V R 0 ) = 0 and q j p 0 (V R i ) = 0 for i = 1, . . . , r, which implies that q j p 0 ∈ C + I grad .

By Lemma 4.5, we have the decomposition

q j ≡ q j (p 0 + p 1 + • • • + p s ) mod I grad ⊂ C + I grad . Moreover (p r+1 + • • • + p s ) ∈ R[z] and vanishes on V R k for k = 0, . . . , r. Thus (p r+1 + • • • + p s ) ∈ C +
I grad and we deduce that q j ∈ (p 1 , . . . , p r ) + C + I grad . This proves the other inclusion and the first equality.

As

V R grad = V R grad ∩ S + (C) (Remark 3.7)
, by the Positivstellensatz, C + I grad = R I grad , which proves the second equality.

By the Positivstellensatz and Remark 3.7, we have

C + I grad ∩ R[x] = R I grad ∩ R[x] = I(π x (V R grad )) = I(π x (V KKT ) R ∩ S + (C)) = C + I x KKT . and
I min = I z min ∩ R[x] = (p 1 , ..., p r ) ∩ R[x] + C + I grad ∩ R[x] = (p 1 , ..., p r ) + C + I x KKT . which proves the equality. Theorem 5.6. For C ⊂ R[x] with S min ⊂ S(C) ⊂ V x,R
KKT , there exists t 2 ∈ N such that ∀t ≥ t 2 , for Λ * ∈ L t (C) with Λ * = f µ t,C , we have I min ⊂ (ker M t Λ * ).

Proof. To prove the inclusion we take t 2 = max{t 0 , t 1 } and we combine Proposition 5.5 with Proposition 5.2 for C ⊂ R[x] and Theorem 5.4.

We introduce now the notion of optimal linear form for f . Such a linear form allows us to compute I min . Proposition 5.7. For Λ * ∈ L t (C) and p ∈ R[x], the following assertions are equivalent:

(i) rankM t Λ * = max Λ∈Lt(C),Λ(p)=p µ t,C rankM t Λ . (ii) ∀Λ ∈ L t (C) such that Λ(p) = p µ t,C , ker M t Λ * ⊂ ker M t Λ . We say that Λ * ∈ L t (C) is optimal for p if

it satisfies one of the equivalent conditions (i)-(ii).

A proof of this proposition can be found in [START_REF] Lasserre | Moment matrices, border bases and real radical computation[END_REF](Proposition 4.7).

Remark 5.8. A linear form Λ * ∈ L t (C) optimal for p can be computed by solving a Semi-Definite Programming problem by an interior point method [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]. In this case, the solution Λ * obtained by convex optimization is in the interior of the face of linear forms that minimize f . The next result, which refines Theorem 5.6, shows that only elements in I min are involved in the kernel of a truncated Hankel operator associated to an optimal linear form for f . Theorem 5.9. Let t ∈ N such that f ∈ R[x] 2t and let C ⊂ R[x] 2t with S min ⊂ S(C). If Λ * ∈ L t (C) is optimal for f and such that Λ * (f ) = f * , then ker M t Λ * ⊂ I min . Proof. It is similar to proof of Theorem 4.9 in [START_REF] Lasserre | Moment matrices, border bases and real radical computation[END_REF].

The last result of this section shows that an optimal linear form for f yields the generators of the minimizer ideal I min in high enough degree.

Theorem 5.10. Let g ⊂ R[x] be a set of constraints with S min = ∅. For a set of constraints

C ⊂ R[x] with S min ⊂ S(C) ⊂ V x,R
KKT , there exists t 2 ∈ N (defined in Theorem 5.6) such that ∀t ≥ t 2 ,

•

f µ t,C = min x∈S KKT f (x) is reached for some Λ * ∈ L t (C), • ∀Λ * ∈ L t (C) optimal for f , we have Λ * (f ) = f * and (ker M t Λ * ) = I min , • if V(C 0 ) ⊂ V x KKT then f sos t,C = f µ t,C = f * . Proof.
We obtain the result as a consequence of Theorem 5.4, Theorem 5.6 and Theorem 5.9.

The same results hold if we replace C by any other finite set defining a real variety such that S min ⊂ S(C) ⊂ V x,R KKT . Remark 5.11. We can also replace the initial set of constraints g by any other set g defining the same semi-algebraic set S = S(g) = S(g) and consider the KKT variety associated to g.

Consequences

Let us describe now some consequences of these results in specific cases, which have been previously studied.

6.1. Global optimization. We consider here the case n 1 = n 2 = 0. Theorem 4.9 implies the following result (compare with [START_REF] Nie | Minimizing polynomials via sum of squares over gradient ideal[END_REF]):

Theorem 6.1. Let f ∈ R[x].
(1) If the real critical values of f are positive, then

f ∈ Q + + ( ∂f ∂x 1 , . . . , ∂f ∂x n ).
(2) If the real critical values of f are strictly positive, then

f ∈ Q + + ( ∂f ∂x 1 , . . . , ∂f ∂x n ).
In particular, if there is no real critical value, then

f ∈ Q + + ( ∂f ∂x 1 , . . . , ∂f ∂x n ).
A consequence of Proposition 5.1 and Theorem 5.10 is the following:

Theorem 6.2. Let f ∈ R[x] and C = { ∂f ∂x 1 , . . . , ∂f ∂x n }.
Then, there exists t 0 ∈ N, such that ∀t ≥ t 0 either L t (C) = ∅ and S min = ∅ or (1)

f sos t,C = f µ t,C = f * = min x∈R n f (x) is reached for some Λ * ∈ L t (C), (2
) ∀Λ * ∈ L t (C) optimal for f , ker M t Λ * generates I min . The first point of this theorem can also be found in [START_REF] Nie | Minimizing polynomials via sum of squares over gradient ideal[END_REF]. 6.2. General case. A direct consequence of Proposition 5.1 and Theorem 5.10 is the following:

Theorem 6.3. Let C ⊂ R[x] be a set of constraints such that • (C 0 ) = I KKT ∩ R[x], • C + = g + .
Then there exists t 0 ∈ N such that ∀t ≥ t 0 , either L t (C) = ∅ and S min = ∅ or

• f sos t,C = f µ t,C = min x∈S KKT f (x) is reached for some Λ * ∈ L t (C), • ∀Λ * ∈ L t (C) optimal for f , we have Λ * (f ) = f * and (ker M t Λ * ) = I min . The set C 0 is constructed so that V(C 0 ) = V x
KKT . As we have seen, the weaker condition

S min ⊂ S(C) ⊂ V x
KKT is sufficient to have an exact relaxation sequence. The generators C 0 of I KKT ∩ R[x] can be computed by elimination techniques (for instance by Groebner basis computation with a product order on monomials [START_REF] Cox | Ideals, Varieties, and Algorithms : An Introduction to Computational Algebraic Geometry and Commutative Algebra[END_REF]). 6.3. Regular case. We consider here a semi-algebraic set S such that its defining constraints intersect properly. For any

x ∈ C n , let ν(x) = {j ∈ [1, n 2 ] | g + j (x) = 0}.
Definition 6.4. We say that a set of constraints g = (g 0 1 , . . . g 0 n 1 ; g + 1 , . . . , g + n 2 ) is regular if for all points x ∈ S(g) with ν(x) = {j 1 , . . . , j k }, the vectors ∇g 0 1 (x), . . . , ∇g 0 n 1 (x), ∇g + j 1 (x), . . ., ∇g + j k (x) are linearly independent. This condition is used for instance in [START_REF] Ha | Representation of positive polynomials and optimization on noncompact semialgebraic sets[END_REF]

. It implies that ∀x ∈ S, |ν(x)| ≤ n -n 1 and that B ν(x) (x) is of rank n 1 + |ν(x)|. A stronger condition, called the C-regularity, corresponds to sets of constraints such that ∀x ∈ C n , B ν(x) (x) is of rank n 1 + |ν(x)|.
This condition is used for instance in [START_REF] Nie | An exact jacobian SDP relaxation for polynomial optimization[END_REF]. It is satisfied for semi-algebraic sets defined by "generic" constraints when n 1 ≤ n as shown in [START_REF] Nie | An exact jacobian SDP relaxation for polynomial optimization[END_REF].

If g is regular, then for all points x in S the rank of B ν(x) (x) is n 1 + |ν(x)| and S sing = ∅. The decomposition [START_REF] Lasserre | Moment matrices, border bases and real radical computation[END_REF] implies that S F J = S KKT and that all minimizer points of f on S are KKT points. If moreover g is C-regular, then V x F J = V(Γ F J ) = V x KKT . We deduce from Theorem 5.10 the following result: Theorem 6.5. Let g ⊂ R[x] be a regular set of constraints and let C ⊂ R[x] be the set of constraints such that

• C 0 = Γ F J defined in (9) (resp. C 0 = Φ F J defined in (10)), • C + = g + .
Suppose that min x∈S(g) f (x) is reached at some point of S(g). Then, there exists t 0 ∈ N such that ∀t ≥ t 0 , (1)

f µ t,C = f * = min x∈S(g) f (x) is reached for some Λ * ∈ L t (C), (2) ∀Λ * ∈ L t (C) optimal for f , ker M t Λ * generates I x min , (3) If g is C-regular and C 0 = Γ F J , then f sos t,C = f µ t,C = f * . By Lemma 3.11 and Remark 3.12, C is constructed so that S min ⊂ S(C) = S KKT ⊂ V x,R KKT .
Points (1) and (3) are proved for C 0 = Γ F J in [START_REF] Nie | An exact jacobian SDP relaxation for polynomial optimization[END_REF] under the condition that g is Cregular. These points can also be found in [START_REF] Ha | Representation of positive polynomials and optimization on noncompact semialgebraic sets[END_REF] for C 0 = g 0 ∪ Φ F J under the condition that g regular (but a problem appears in the proof: the vanishing of the polynomials Φ F J at a point x ∈ C n does not imply that rank A ν(x) (x) < n 1 + |ν(x)|).

In this case, the relaxation constructed with Γ F J (or Φ F J ) is exact and can be used to compute the minimizer ideals of f on the semi-algebraic set S. This gives a way to compute C + (C 0 ) (see also [START_REF] Ma | A certificate for semidefinite relaxations in computing positive dimensional real varieties[END_REF]), which generalizes the approach of [START_REF] Lasserre | A unified approach for real and complex zeros of zerodimensional ideals[END_REF], [START_REF] Lasserre | Moment matrices, border bases and real radical computation[END_REF] or [START_REF] Rostalki | Algebraic moments,real root finding and related topics[END_REF] to compute the real radical of an ideal.

Examples

This section contains examples that illustrate different aspects of our method. In the case of a finite number of minimizers for a function f on the semi-algebraic set S defined by the set of constraints g, the approach we describe leads to the following algorithm:

( 1). Thus V KKT = ∅. According to the decomposition [START_REF] Lasserre | Moment matrices, border bases and real radical computation[END_REF], S F J = S sing and we compute the minimum of x on S sing , which is defined by x 2 = 0: min x s.t x 2 = 0. Now according to section 6.4, the relaxation associated to this problem is exact and yields the solution x = 0.

1) Compute C ⊂ R[x] such that C 0 generates I KKT ∩ R[x] and C + = g + ; (2) t := ⌈ 1 2 max{deg(f ), deg(g 0 i ), deg(g + j )}⌉; (3) Compute Λ * ∈ L t (C)
is I KKT = (1 -3v 1 x 2 , v 1 x 3 ) = (
Example 7.2. We consider the following problem min f (x, y, z) = x 2 + y 2 + z 2 ;

s.t rank x + z + 1 x + y y + z x + y y + z x + z + 1 ≤ 1 or equivalently min f (x, y, z) = x 2 + y 2 + z 2 ; s.t (x + z + 1)(y + z) -(x + y) 2 = 0; (x + z + 1) 2 -(y + z)(x + y) = 0; (x + z + 1)(x + y) -(y + z) 2 = 0;
This corresponds to computing the closest point on a twisted cubic defined by 2 × 2 minors. The set of constraints g is not regular but S(g) = V R (g 0 ) is a smooth real variety.

In the first iteration of the algorithm, the order is 1, the size of the Hankel matrix M 1 Λ is 3, min Λ(f ) = 1 and there is no duality gap. The flat extension condition is satisfied for M 1 Λ and thus we have found the minimum. The algorithm stops and we obtain I min = (x, y -1, z). The points that minimize f are {(x = 0, y = 1, z = 0)}.

Example 7.3. We consider the Motzkin polynomial, min f (x, y) = 1 + x 4 y 2 + x 2 y 4 -3x 2 y 2 which is non negative on R 2 but not a sum of squares in R[x, y]. We compute its gradient ideal, I grad (f ) = (-6xy 2 + 2xy 4 + 4x 3 y 2 , -6yx 2 + 2yx 4 + 4y 3 x 2 ), which is not zerodimensional.

In the first iteration of the algorithm, the order is 3, the size of the Hankel matrix M 3 Λ is 10, min Λ(f ) = -216. The flat extension condition is not satisfied hence we try with degree 4.

In the second iteration the order is 4, the size of the Hankel matrix M 4 Λ is 15, min Λ(f ) = 0, there is no duality gap. The flat extension condition is satisfied for M 4 Λ and we have found the minimum. The algorithm stops and we obtain I min = (x 2 -1, y 2 -1). The points that minimize f are {(x = 1, y = 1), (x = 1, y = -1), (x = -1, y = 1), (x = -1, y = -1)}.

For this example Gloptipoly must go until order 9 in order to satisfy the flat extension condition.

Example 7.4. We consider the Robinson polynomial min f (x, y) = 1 + x 6x 4x 2 + y 6y 4y 2x 4 y 2x 2 y 4 + 3x 2 y 2 which is non negative on R 2 but not a sum of squares in R[x, y]. We compute its gradient ideal, I grad (f ) = (6x 5 -4x 3 -2x -4x 3 y 2 -2xy 4 + 6xy 2 , 6y 5 -4y 3 -2y -4y 3 x 2 -2yx 4 + 6yx 2 ) which is not zero-dimensional.

In the first iteration, the order is 3, the size of the Hankel matrix M 3 Λ is 10, min Λ(f ) = -0.93. The flat extension condition is not satisfied hence we try with degree 4.

In the second iteration the degree is 4, the size of the Hankel matrix M 4 Λ is 15, min Λ(f ) = 0. There is no duality gap. The flat extension condition is satisfied for M 3 Λ and we have found the minimum.

The algorithm stops and we obtain I min = (x 3x, y 3y, x 2 y 2x 2y 2 + 1). The points that minimize f are {(x = 1, y = 1), (x = 1, y = -1), (x = -1, y = 1), (x = -1, y = -1), (x = 1, y = 0), (x = -1, y = 0), (x = 0, y = 1), (x = 0, y = -1)}.

For this example, Gloptipoly must go until order 7 in order to satisfy the flat extension condition.

Example 7.5. We consider the homogeneous Motzkin polynomial with a perturbation ǫ = 0.005, min f (x, y, z) = x 4 y 2 + x 2 y 4 -3x 2 y 2 z 2 + z 6 + ǫ(x 2 + y 2 + z 2 ); s.t h(x, y, z) = 1x 2y 2z 2 ≥ 0 This example coming from [START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF]Example 6.25] is a case where the constraints g define a compact semi-algebraic set, but the direct relaxation using the associated quadratic module or preordering is not exact.

We add the projection of the KKT ideal and we have the similar problem min x 4 y 2 + x 2 y 4 -3x 2 y 2 z 2 + z 6 + 0.005(x 2 + y 2 + z 2 ); s.t -4zx 4 y -20zx 2 y 3 + 12x 2 yz 3 -0.06zy 5 + 12.06yz 5 = 0; -20zx 3 y 2 -4zxy 4 + 12xy 2 z 3 -0.06zx 5 + 12.06xz 5 = 0; (4x 3 y 2 + 2xy 4 -6xy 2 z 2 + 0.03x 5 )(-x 2y 2z 2 + 1) = 0; (2x 4 y + 4x 2 y 3 -6x 2 yz 2 + 0.03y 5 )(-x 2y 2z 2 + 1) = 0; (-6x 2 y 2 z + 6.03z 5 )(-x 2y 2z 2 + 1) = 0;

where the first three equations are the 2 × 2 minors of the Jacobian matrix of f and h and the last three equations are the gradient ideal of f multiplied by h.

In the first iteration the order is 5, the size of the Hankel matrix M 5 Λ is 167, min Λ(f ) = 0, there is no duality gap. The flat extension condition is satisfied for M 5 Λ and we have found the minimum. The algorithm stops and we obtain I min = (x, y, z). The point that minimize f is (0, 0, 0).

For this example, the flat extension condition does not hold with Gloptipoly if ǫ ≤ 0.01.

Finally with these two last examples we show that even the minimizer ideal I min is not zero-dimensional we can recover it from a solution of the relaxation problem.

Example 7.6. We consider Motzkin polynomial over the unit ball: min f (x, y, z) = x 4 y 2 + x 2 y 4 -3x 2 y 2 z 2 + z 6 ; s.t h(x, y, z) = 1x 2y 2z 2 ≥ 0

The polynomial f is homogeneous and non negative on R 3 but not a sum of squares in R[x, y, z].

We add the projections of KKT ideal and we have the similar problem min x 4 y 2 + x 2 y 4 -3x 2 y 2 z 2 + z 6 ; s.t -4xy 5 + 12xy 3 z 2 + 4yx 5 -12x 3 yz 2 = 0; -4zx 4 y -20zx 2 y 3 + 12x 2 yz 3 + 12yz 5 = 0; -20zx 3 y 2 -4zxy 4 + 12xy 2 z 3 + 12xz 5 = 0; (4x 3 y 2 + 2xy 4 -6xy 2 z 2 )(-x 2y 2z 2 + 1) = 0; (2x 4 y + 4x 2 y 3 -6x 2 yz 2 )(-x 2y 2z 2 + 1) = 0; (-6x 2 y 2 z + 6z 5 )(-x 2y 2z 2 + 1) = 0;

where the first three equations are the 2 × 2 minors of the Jacobian matrix of f and h and the last three equations are the gradient ideal of f multiplied by h.

In the first iteration the order is 5, the size of the Hankel matrix M 5 Λ is 156, min Λ(f ) = 0, there is no duality gap. We compute the kernel of this matrix: ker M 5 Λ = z(y 2z 2 ), x(y 2z 2 ), z(x 2z 2 ), y(x 2z 2 ) . It generates the minimizer ideal I min = (z(y 2z 2 ), x(y 2z 2 ), z(x 2z 2 ), y(x 2z 2 )) defining 6 lines: (y ± z, x ± z), (x, z), (y, z). Here V(I min ) is not included in S. In the first iteration, the order is 2, the size of the Hankel matrix M 2 Λ is 10, min Λ(f ) = -1, there is no duality gap. We compute the kernel of this matrix: ker M 2 Λ = x 2 + y 2 -4, x(z + 1), y(z + 1), z(z + 1), (z + 1) which generates the minimizer ideal I min = (x 2 + y 2 -4, z + 1), defining a circle which is the intersection of the torus with a tangent plane. Notice that the multiplicity of this intersection has been removed in I min .

Theorem 2 . 6 .

 26 Let C = (C 0 ; C + ) be a set of constraints of R[x]. (i) Hilbert's Nullstellensatz (see, e.g., [3, §4.1])

Corollary 4 . 7 .

 47 If S min = ∅, then -1 ∈ P + (C) + J x grad .Proof. If S min = ∅, then f has no real KKT critical value on S(C) and r = -1. Lemma 4.6 implies that -1 ∈ P

Example 7 . 7 .

 77 We consider minimization of a linear function on a torus:min f (x, y, z) = z s.t 9 -10x 2 -10y 2 + 6z 2 + x 4 + 2x 2 y 2 + 2x 2 z 2 + 2y 2 z 2 + y 4 + z 4 = 0

we define the (truncated) quadratic module of C by

  ′ ⊂ R[x], we say that C ⊂ C ′ if C 0 ⊂ C ′0 and C + ⊂ C ′+ .

	but the inclusion may be strict.
	By convention, a set of constrains C = {c 0 1 , . . . , c 0 n 1 ; c + 1 , . . ., c + n 2 } ⊂ R[x] is a finite set of polynomials composed of a subset C 0 = {c 0 1 , . . . , c 0 n 1 } corresponding to the equality con-straints and a subset C + = {c + 1 , . . . , c + n 2 } corresponding to the non-negativity constraints. For two set of constraints C, C Definition 2.1. For t ∈ N ∪ {∞} and a set of constraints C = {c 0 1 , . . . , c 0 n 1 ; c + 1 , . . ., c + n 2 } ⊂ R[x],

  optimal for f (solving a finite dimensional SDP problem by an interior point method); (4) Check the convergence certificate for M t Λ * (by flat extension[START_REF] Henrion | Positive Polynomials in Control, chapter Detecting Global Optimality and Extracting Solutions in GloptiPoly[END_REF][START_REF] Laurent | A generalized flat extension theorem for moment matrices[END_REF]); (5) If it is not satisfied, then t := t + 1 and repeat from step (2);Otherwise compute K := ker M t Λ * . Output f * = Λ * (f ) and the generators K of I min .

	Example 7.1. We consider the "ill-posed" problem
	min x s.t x 3 ≥ 0.
	The ideal I KKT

For notational simplicity, we consider only these two fields, but R and C can be replaced respectively by any real closed field and any field containing its algebraic closure.

In its proof, the Mean Value Theorem is applied for a complex valued function, which is not valid. We correct the problem in the proof of Lemma

4.1.

6.4. Zero dimensional real variety. Let g ⊂ R[x] be a set of constraints such that V R (g 0 ) is finite and let S := S(g). By remark 5.11, we can assume that S is defined by a set of constraints g such that (g 0 ) is radical. Then ∀x ∈ V(g 0 ) = V(g 0 ), the Jacobian matrix Bν(x) (x) associated to g0 is of rank n. Therefore we have V(g 0 ) = V(g 0 ) = V x KKT and any point of S is a KKT -point: S = S F J = S KKT . Consequently, we deduce from Theorem 5.10 the following result: Theorem 6.6. Let g = (g 0 , g + ) ⊂ R[x] be a set of constraints such that V R (g 0 ) is finite. Then there exists t 0 ∈ N such that ∀t ≥ t 0 ,

(1)

This answers an open question in [START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF]. The first point was also solved in [START_REF] Nie | Polynomials optimization with real variety[END_REF] using dedicated techniques. 6.5. Smooth real variety. We consider a set of constraints g = {g 0 1 , . . . , g 0 [START_REF] Henrion | Positive Polynomials in Control, chapter Detecting Global Optimality and Extracting Solutions in GloptiPoly[END_REF]), or the union ∆ n-d of g 0 and the set of (nd + 1) × (nd + 1) minors of the Jacobian matrix of {f, g 0 1 , . . . , g 0 n 1 }, which contain the first column ∇f define the variety S KKT .

We deduce from Theorem 5.10, the following result:

is an equidimensional and smooth variety of dimension d.

Let C ⊂ R[x] be the set of constraints such that C 0 = Γ F J defined in (9) (or C 0 = Φ F J defined in [START_REF] Henrion | Positive Polynomials in Control, chapter Detecting Global Optimality and Extracting Solutions in GloptiPoly[END_REF], C 0 = ∆ n-d ) Then there exists t 0 ∈ N such that ∀t ≥ t 0 , either L t (C) = ∅ and S min = ∅ or (1)

) ∀Λ * ∈ L t (C) optimal for f , ker M t Λ * generates I min . 6.6. Known minimum. In the case where we know the minimum f * of f on the basic closed semi-algebraic set S, we take g ′ with g ′0 = {g 0 , f -f * } and g ′+ = g + . Let S = S(g), S ′ = S(g ′ ). By construction S min ⊂ S ′ and S ′ = S ′ KKT and V(g 0 ) ⊂ V x KKT (g ′0 ). Theorem 5.10 applied to g ′ implies the following result:

Λ * generates I min . 6.7. g + -radical computation. In the case where f = 0, by Remark 3.15 all the points of S are KKT points and minimizers of f so that S min = S = S KKT . Moreover, I x KKT = (g 0 1 , . . . , g 0 n 1 ) since F 1 , . . . , F n , v 1 g + 1 , . . . , v n 2 g + n 2 are homogeneous of degree 1 in the variables u 1 , . . . , u n 1 , v 1 , . . . , v n 2 . We deduce the following result: Theorem 6.9. Let g = {g 0 1 , . . . , g 0 n 1 ; g + 1 , . . . , g + n 2 } ⊂ R[x]. There exists t 2 ∈ N such that ∀t ≥ t 2 , ∀Λ * ∈ L t (g) optimal for 0, we have (ker M t Λ * ) = I(S) = g + (g 0 ).


N Menad
email: n.menad@brgm.fr

S Guignot

J A Van Houwelingen

NEW CHARACTERISATION METHOD OF ELECTRICAL AND ELECTRONIC EQUIPMENT WASTES (WEEE)

Innovative separation and beneficiation techniques of various materials encountered in

Electrical and Electronic Equipment Wastes (WEEE) is a major improvement for its recycling. Mechanical separation-oriented characterization of WEEE was conducted in an attempt to evaluate the amenability of mechanical separation processes. Properties such as liberation degree of fractions (plastics, metals ferrous and non-ferrous), which are essential for mechanical separation, are analysed by means of a grain counting approach. Two different samples from different recycling industries were characterised in this work. The first sample is a heterogeneous material containing different types of plastics, metals (ferrous and nonferrous), Printed Circuit Board (PCB), rubber and wood. The second sample contains a mixture of mainly plastics. It is found for the first sample that all aluminium particles are free (100%) in all investigated size fractions. Between 92 and 95% of plastics are present as free particles; however, 67% in average of ferromagnetic particles are liberated. It can be observed that only 42% of ferromagnetic particles are free in the size fraction larger than 20 mm. Particle shapes were also quantified manually particle by particle. The results show that the particle shapes as a result of shredding, turn out to be heterogeneous, thereby complicating mechanical separation processes. In addition, the separability of various materials was ascertained by a sink-float analysis and eddy current separation. The second sample was separated by automatic sensor sorting in four different products: ABS, PC-ABS, PS and rest product. The fractions were characterised by using the methodology described in this paper.

The results show that the grade and liberation degree of the plastic products ABS, PC-ABS and PS are close to 100%. Sink-float separation and infrared plastic identification equipment confirms the high plastic quality. On the basis of these findings, a global separation flow sheet is proposed to improve the plastic separation of WEEE.

Introduction

WEEE needs increasing Reuse, Recycling and Recovery (3R). In Europe, the amount of WEEE generated is 12 million ton per year [START_REF] Lehtinen | Challenges of WEEE on Reverse Logistics: A Case Study on a Collection Network in Finland[END_REF]. Only 2.2 million ton is treated representing about 18% (Government gazette, 2011). The end of life equipment contains hazardous materials such as PCB (PolyChloroBiphenyl), cadmium and mercury. It also contains valuable materials such as ferrous and non-ferrous metals, engineering plastics, precious metals, platinum group metals and rare earths elements. WEEE will increase in the coming decades with an expected rate of at least 4% per year, about three times higher than the growth of the average municipal waste [START_REF] Gramatyka | Recycling of waste electric and electronic equipment[END_REF]. Much of WEEE is exported to Africa, China and India and disassembled under inadequate working conditions [START_REF] Veasey | Handling WEEE waste flows on the effectiveness of producer responsibility in a globalizing world[END_REF]. More than 78% of European WEEE is currently land filled or incinerated (Government gazette, 2011). This publication will demonstrate improved re-use, recycling and recovery (3R) through better size reduction, smart sensor sorting and advanced density separation. WEEE contains a large amount of different engineering plastics that need further separation with advanced separation techniques in order to produce high added value plastics. WEEE also contains the recoverable metals such as, aluminium, copper, lead, zinc, metals alloys, precious metals (gold and silver), and platinum group metals, and rare earth elements which are currently hardly recycled (Sm, Eu, Y, Gd and Dy) [START_REF] Menad | Identification and recovery of rare metals in electrical and electronic scrap[END_REF].

The prices of these metals are expected to increase by 15% annually due to increased demand, quotas, supply shortages and limited numbers of suppliers (Government gazette, 2011).

In order to develop and implement both environmentally friendly and economically viable recycling processes, in-depth characterization of this specific material stream, oriented towards mechanical separation amenability, is necessary. It has been demonstrated that it is valuable to recycle WEEE in spite of the fact that the content of precious metals (Au, Ag, Pd) gradually decreases. Alternatively, a full material recovery involving ferromagnetic, nonferrous metals, precious metals and non-metallic, through mechanical separation, may be applicable both economically and technically.

Mechanical separation-oriented characterization is studied of two samples provided by recycling industries: a heterogeneous sample S1 and a plastic sample S2. The characterization consisted of determination of the composition, the particle size distribution, the degree of liberation through a particle counting, particle shape quantification, plastic identification by a hand held detector based on infrared (IR) spectroscopy and a separability investigation through a sink-float analysis, magnetic and eddy current separation. The identification of flame retardants in the plastics was carried out with a hand held X-ray fluorescence (XRF) device.

Materials and procedure

Materials

Two different samples are provided by WEEE processing plants, S1 and S2. For the first sample the input consists of category 2, 4 and 6 of the WEEE Directive 2002/96/EC of 27 January 2003. A sample of 100 kg was taken after shredding with a hammer mill with a slotted discharge opening of 100X60 mm. This sample is very heterogeneous containing plastics, electric wires, wood and ferrous and non-ferrous metals. Sample S2 contains different types of plastics from WEEE obtained through disassembly of pc-monitors. A big bag of S2 was shredded with a slow rotating shearing type shredder. S2 was characterized and as part of the analyses separated by automatic sensor sorting in four different fractions: ABS, PC-ABS, PS and a rest product.

Procedure

The methodology of characterisation used in this investigation is given in Fig. 1. The sampled materials are screened. The size fractions obtained are characterised by the following steps:

1. Determination of colour, particle shape and liberation degree.

2. The plastic type is identified by IR and the flame retardant elements in the plastic by XRF hand held instruments. The density is determined by using sink float analysis.

3. Ferrous and non-ferrous metals are quantified by using magnetic and eddy current separators respectively.

Composition

The composition is determined by manual sorting supported by a hand magnet, a hand held IR device and a hand held XRF device. Shredded WEEE in general consists of ferrous and nonferrous metals, plastics, printed circuit boards, glass, cable, paper and wood, which are easily recognized. The composition determines the material flows when separated after shredding.

Particle size distribution

The particle size distribution (PSD) was determined by screening. Sample S1 was classified into the fractions +2, 2-10, 10-20 and +20 mm. Sample S2 (plastics) is classified into +5, 5-10, 10-20, and +20 mm. The products obtained from each size fraction are subjected to characterisation using the steps shown in Fig. 1. Different shredding methods are of influence to the PSD and subsequent separation options.

Shape factor quantification

The identification and quantification of different particle shapes of the investigated samples was performed manually. The quantitative criterion is expressed in terms of F-Shape given as follow:

max min D D Shape F = - (1)
Where max D is defined as the longest diameter of one particle obtained by selecting the largest of the Ferret diameters, and min D represents the shortest among samples Ferret diameters. According to this definition a sphere has a shape factor of 1. Since particles after shredding have irregular shapes, the shape factor will be far lower than 1. Ferrous metals often appear as sheet metal or as strip, disc or axle, copper as wire and plastics as a plate shaped material or foil. The shape factor then is lower than 1. In case of plastic foils, the factor can be lower than 0.01. After mild shredding without a discharge, grid the shape factor is smaller than after shredding with a discharge grid. Repeated shredding with smaller discharge openings will cause the shape factor of materials to converge to 1. Material handling, sorting and separation will be facilitated by more uniform particles

Colour identification

The colour determination of the plastic particles was made visually. The colours red, black, grey and yellow are found. The plastics with the same colour are weighed separately and the weight % was calculated for each fraction. The colour of plastics is an important property for sorting. Black plastics are currently recognized by FTIR (a slow laboratory analyses) and not by fast IR sensors, maybe in future a method is found for sorting. The coloured plastics can be sorted by fast NIR in their various polymer types. Additives like flame retardants (bromine, phosphor, antimony) or pigments are recognized by XRF in coloured and black plastics. For the recycler the possibility is open to apply selective sorting into coloured and black housing for instance of monitors or TVs respectively. Sensor sorting devices often are equipped with an IR sensor and a colour sensor combined.

Liberation degree determination

The liberation of different materials after size reduction of WEEE is essential for separation.

The liberation of this material is relatively large after the first shredding. A proven and simple method to quantify the liberation degree is counting the liberated and non-liberated particles of the sample using the following equation.

∑ = + = N 1 i li fi fi N N N N LD (2)
Where, LD denotes the mean liberation degree, N is the number of the counted samples, and fi N indicates the locked particles of the same material in the ith sample. In the present investigation two different samples of 2 kg were analysed and the liberation degree was calculated according to this equation.

Determination of plastic density by sink-float distribution

The determination of the density with heavy liquids is a method to sort plastic types into density classes. This method is extensively utilized to characterize the density of plastics. The heterogeneity of materials and the difference in density makes dry or wet separation processes efficient, economically viable and environmentally friendly.

A substantial share of the materials in electronic scrap consist is plastics with a density generally lower than 2.0 g/cm 3 . Characterization by density separation was conducted. The floats and the final sinks are weighed. In addition IR plastic detection was used to determine the plastic types.

Density separation is presently the most practised method to recover plastics from WEEE.

However, the density classes produced still contain different types of plastics. Various densities overlap which are the result of additives like flame retardants, fillers and different plastic types [START_REF] Kobler | Successful recovery of end of life electronics plastics using RPI's skin flotation technology[END_REF]. As shown in Fig. 2, the brominated, phosphated, and ABS-PVC flame retardant families are found overlapping in the 1.16 to 1.25 density range. Plastics obtained from the size fractions of 20 mm, -20/10mm and -10/2mm were analysed.

The identification of flame retardants was performed by using a hand held XRF device. The XRF analyser quantifies the halogen elements contained in the plastic. The identification of plastic with IR is only possible if the plastic is not black or coloured. Automatic mechanical sensor sorting becomes available with modern fast and smart sensor sorting equipment based on IR.

The IR plastic detector (Fig. 3) is developed by Polychromix and is using the micro-electromechanical-system (MEMS) permitting the assembly of a spectrometer without mobile parts and a low energy consumption. These characteristics are ideal for the manufacture of portable hand held instruments.

The hand held XRF device operates on the principle of x-ray fluorescence, which uses X-rays to excite the atoms in a sample and measures the fluorescent X-rays re-emitted by the material. The analyser rapidly determines the elements present as well as their relative concentrations. For samples with known ranges of chemical composition, such as common grades of metal alloys, the analyser can also rapidly identify most sample types. The instrument is valuable for a wide range of applications, including scrap recycling, PMI (Positive Material Identification), metal fabrication, electronic component testing, solder analysis, lead paint testing, RoHS and WEEE compliance.

Ferrous and non-ferrous metals quantification

Ferrous metals are recovered by magnetic separation. Different methods are applied. The industry mostly is equipped with cross belt electro magnets. The magnet is positioned across the conveyor belt. The distance of the magnet to the belt is of influence for the composition of the magnetic fraction. Also head pulley magnets are used. Ferrous materials recovered consist of iron, galvanized and tin coated steel, ceramic ferrites and magnet material (motors, coils, transformers). Some stainless steel alloys are weakly magnetic, some are non-magnetic. The organisation of magnetic separation throughout the WEEE processing plant decides the recovery of ferrous metals and its grades.

Eddy current separation is used in the recycling industries for the recovery of non-ferrous metals from end-of-life vehicles (ELV), electrical and electronic waste (WEEE), construction and demolition waste (C&DW), municipal solid waste incinerator bottom ashes (MSWI) and municipal solid waste (MSW) [START_REF] Veasey | Handling WEEE waste flows on the effectiveness of producer responsibility in a globalizing world[END_REF]. The principle of eddy current separation is based on an alternating magnetic field that is inducing a force on a conductor causing it to be deflected from non-conductors (Fig. 4). The repulsion force in combination with the product belt speed and the optimization of the product splitter plate provides a means for the effective separation. A rapidly rotating magnetic drum is positioned inside a non-metallic drum which rotates with the conveyor belt speed. The metal particles mostly have an irregular shape which causes an irregular force and deflection. Eddy current separation is used to separate non-ferrous metals (> 2mm) from plastic materials. Fig. 4 shows the eddy current separator used in this study (left) and a cross section of the separation principle. Occasionally ferrous materials are separated into a magnetic fraction mainly consisting of small particles that are not catched in previous magnetic separation.

Fig. 4

Eddy current metal concentrates area further processed by a sink-float plant to separate aluminium from copper and other metals. Copper based metal concentrates are sold to metallurgy for copper recovery by smelting and refining. Aluminium is sold to secondary aluminium smelters. A careful recipe of scrap with pure aluminium is required to produce specific alloys. The concentrate of printed circuit boards produced in WEEE scrap processing plants is sold to copper metallurgy. Concentrates are sampled and assayed by a surveyor, the sample is crushed, the polymer part is incinerated. The remaining part (metals and inerts) is melted together with fluxes and a fixed amount of aluminium as a collector of metals. After solidification the separated metal phase and slag phase are analysed by XRF for the presence of Cu, Au, Ag, Pd and other elements of interest. The seller and buyer make up a contract and the payment is made according to the formula (P.J. Lewis, C.G. Streets, 1978):

Smelter Value = (M-UD)*(P-RC)-TC-X+Y

where M is the Cu concentrate in percentage; UD the unit deduction (set by smelter) in percentage, mostly 1-2%; P the copper notation at London Metal Exchange (LME); RC the refining charge; TC the treatment charge; X the penalties for elements over a threshold value; Y is the payments for Au, Ag, Pd (with their specific refining cost, unit deductions).

Results and discussion

Two different samples from different recycling industries are characterised. Sample S1 is a heterogeneous material containing different types of plastics, metals (ferrous and nonferrous), printed circuit boards (PCB), rubber, wood, etc. (fig. 5). Sample S2 contains mostly plastics with high content of ABS (fig. 6).

Composition of the samples S1 and S2

Table 1 shows the composition of both samples. 64% of S1 is +20mm, containing 33% plastics, 8% electric wires, 7.7% ferrous materials, 10% non-ferrous metals and 2.4% PCBs.

The size fraction +10 mm representing 19% contains 10% plastics, 4% ferrous materials, electric wires (0.5%), 2% non-ferrous metals and others (1.8%). Fraction 2-10 mm (12.4%) contains mostly plastics (6.8%) and some metals (1.9%). The fraction <2 mm (4.7%) contains only fines (4%).

S2 contains mostly plastics. 97% is present in the fraction +20 mm containing around 95% plastics, 0.6% PCB and 0.8% others. The fractions +10 mm and 5-10 mm represent respectively, 2%, 0.3%. These fractions contain mostly plastics.

Table 1

Particle size distribution

The PSD is presented in Fig. 7 where the cumulative wt% against the particle diameters of both samples is summarised. It can be seen that the d90 of S1 is close to 5 mm and more than 95% of S2 consists of particles +20 mm and containing mostly plastics. The difference in PSD for S1 and S2 is caused by a different type of shredder. For S1 a fast rotating hammer mill was used with a fixed grid and for S2 a slow rotating shear shredder.

Particle shape

The particle shape characterisation is very important because it has an effect on the separation processes. It is well-known that diversified shapes have a market impact on materials handling. The sample S1 which is heterogeneous material was subjected to determination of F-shapes for each particle. The results show that the Factor-shape of the investigated particles is less than of 0.7 (1.0 is equal to a sphere). This indicates that most particles have a rectangular form.

Colour identification

The identification of colour of different size fractions containing plastics was done visually particle by particle. It can be noted that the grey, white and black colours are predominant in these plastics. Other colours such as red, blue and green were found in small percentages.

Liberation degree

The liberation degree method was performed on S1 containing free and non-free particles.

Using the equation ( 2), the liberation degree of ferromagnetic, Al, Cu and plastics in the sample S1 are grouped in Table 2.

Table 2 All aluminium particles are free (100%) in the four size fractions. Between 92 and 95% of plastics are present as free particles; however 67% and 52% in average of ferromagnetic and copper particles are liberated respectively. It can be observed that only 42% of ferromagnetic particles are free in the size fraction 20 mm.

Curve of specific density

A density distribution of the plastics is acquired with a range of denser fluids starting with water. Different salts can be used to dissolve in water to reach the required density classes.

Figure 8 shows the cumulative wt% float and sink of plastics from S1 plotted against the density of separation. It is shown that more than 60% of plastics float at 1.2 g/cm 3 and about 85% has a density higher than 1.1 g/cm 3 .

Fig. 8

Plastics quantification

The characterization of plastic types was performed on sample S1 with a combination of sink float separation and NIR plastic detection. The results show that the plastics present in S1

with size fraction +20 mm contain more than 38% ABS and most of them have a density of 1.0-1.1 g/cm 3 . The plastic composite ABS/PA/PC is mostly present in the size fraction of 10-20 mm with a density of 1.19-1.31 g/cm 3 . The three investigated size fractions (+20 mm, -20/10 mm and -10/2 mm) contain respectively 35%, 53% and 50% of black plastics which are not identified with NIR. PVC is less present in S1 (1.6% at +20 mm and 1.2% at -10/2mm).

About 1.7% of PET plastics are detected in the size fraction of -10/2 mm. The polycarbonate plastics are detected in all fractions (6%, 2% and 2%).

Quantification of plastics treated with flame retardant

Plastics with flame retardant (FR), such as ABS, ABS/PA/PC, ABS/PC and black plastics were analysed with the XRF hand held analyser. The element bromine was detected in different types of plastics. The results for bromine can be checked against those of antimony since the two are always found together. The presence of antimony follows that of the bromine element. The results obtained show that 80% of ABS contains FR. ABS/PC and black plastics are only partly treated with FR. Some of them are completely treated with FR.

Eddy current separation

The optimisation of the eddy current separator was carried out by testing the pure mixture of aluminium and plastics with different forms and particle sizes. The following parameters were varied: particle size of feed material, speed of shell, conductivity, and position of splitter blade. S1 and S2 were subjected to this technique to recover the non-ferrous metals. The results show:

For sample S1

The raw material of S1 was screened in the following size fractions: +40 mm, -40 +20 mm, -20 +10 mm and -10mm. These fractions were subjected to separation by using magnetic and eddy current separation considering the optimal parameters. The results obtained from these separations and the recovery rates of ferrous, non-ferrous, plastics, dust foams and printed circuit boards (PCB) from S1 are presented in Table 3.

The magnetic fractions obtained from each size fraction are not clean except for the coarse fraction. This is due to the presence of particles of metals mixed with non-magnetic particles (plastics, ceramics etc.). It can also be seen that most plastics and non-ferrous (aluminium, copper, lead) are recovered in the non-conductor and conductor fractions respectively.

From Table 3, it can be seen that the recovery rates of plastics are important in the fractions of 20-40 mm and 10-20 mm with less ferrous products (3 and 6% respectively).

Table 3 Therefore the printed circuit boards are only present in these fractions. About 15% and 11% of ferrous can be recovered from the coarse and fine fractions respectively. It is important to underline that all foamed products may be recovered from the fine fractions (23%).

From these tests, the following characterisation of the sample S1 may be estimated: 8% ferrous, 8% of non-ferrous, 79% plastics, 4% foam and 1.3% PCB.

Sample S2

The sample was sorted by magnetic and eddy current separators. The results show that the magnetic fractions of the investigated size fractions are not clean, the recovery rate of these products ranges from 50 to 63% for the fractions -10, 10-20 and 20-40 mm. However, it is about 85% in the coarse fraction (40mm). This is due to presence of free scrap particles in this fraction. On the other hand, the non-conductor fractions are mostly clean where the recovery rate of plastics is higher than 95% in all fractions. The quantity of non-ferrous products is very low, this is confirmed by eddy current separation, where the only coarse fraction (40mm) constitutes about 1%. Table 4 shows that 56% of S2 have particle size of 20-40mm, and between 85% and 99% of plastics can be recovered from all fractions.

Table 4 It can also be seen that only the coarse fraction contains non-ferrous. Other products like ceramics, wood and pieces of glass are present in these fractions (0.5 -3%). Most of ferrous particles are present in the coarse fraction (40mm), and about 1-3% in other fractions. From these tests, the following characterisation of S2 is calculated: 4% ferrous, 0.2% non-ferrous, 93% plastics and 2.0% others.

S2 was sorted by an industrial scale NIR sensor separator and the produced plastic fractions ABS, PC-ABS, PS and a rest fraction were characterised according to the steps shown in Fig. 1. The plastics contained in the sorted fractions ABS, PC-ABS, PS and a rest product are checked and identified by a hand held NIR device. The results are shown in Table 5. According to the characterisation results of the investigated samples, the flow sheet given in Fig. 9 is suggested to recover all components contained in electric and electronic wastes with high quality.

Conclusions

The WEEE samples S1 and S2 were characterised by using the methodology developed by BRGM and Recycling Consult. The techniques used are: classification in three size fractions, determination of composition, liberation degree, colour, shape factor, sink float analysis and identification of plastic types followed by determination of flame retardant containing in the plastics by using a hand held NIR device and a hand held XRF device. Separation of ferrous and non-ferrous metals was made by magnetic and eddy current separators. S2 was subjected to a commercial NIR sensor sorter. From this investigation, it can be concluded that:

1. The analyses approach for WEEE samples proved valuable. The analyses were split between laboratory analyses and separation with commercial equipment. The results are combined and checked with hand held devices.

2. More than 60% of S1 is larger than 20 mm. It contains more than 50% plastics which are predominantly in the size fraction +20 mm. The printed circuit boards represent about 5% and most of them are in the coarse fraction. The characterisation shows more than 12% ferrous metals, and most of them are in the coarse fractions. The same estimation is made for non-ferrous materials. This sample contains around 5% fine particles (-2 mm). The majority of electric wires are concentrated in the size fraction +20mm (8%).

3. S2 contains mostly plastics. About 97% of the sample is present in the size fraction +20 mm containing around 95% plastics, 0.6% PCB (printed circuit board) and 0.8% others. The size fractions of 10 mm and 5 mm represent respectively 2%, 0.3% of the sample. These fractions contain mostly plastics.

These fractions contain mostly plastics. Separation is conducted with a commercial sensor sorter. High recoveries and grades are achieved for ABS and PC-ABS.

4. Black plastics are not detected by NIR to determine the type.

Fig. 1

 1 Fig.1

Fig. 2 2

 2 Fig. 2

Fig. 3

 3 Fig.3

  Fig.5

Fig. 7

 7 Fig. 7

Table 5

 5 The PC-ABS fraction contains about 89% PC-ABS, 7.5% PC and 2% ABS in the size fractions +20 mm and 10-20 mm. This sample contains 0.2% not identified plastics and 1% other materials. Phazir plastic detector confirms the purity of the two first sorted samples, ABS sample (94-96%) and PC-ABS (89%). However, the PS plastic sample is not pure and contains 74% PS, 21% ABS, 2% PC-ABS and 2% not identified plastics. The size fraction of 20 mm is constituted on 67% ABS and about 72% ABS are found in the size fraction of 10 mm in the rest product. Less non-identify plastics (almost black) are present in this size fraction. About 10% PS as well as PC-ABS are representing in both size fractions of the rest product.

Acknowledgement

The authors would like to acknowledge the European Executive Agency for Competitiveness & Innovation (EACI) for financial support and giving us the possibility to work on this project. The authors would also like to express their appreciation for helpful discussions within the working group and all companies involved (PROMIKRON, PHB-Waalwijk and DOLPHIN Metal Separation) for providing input materials.


S Guignot

N Menad
email: n.menad@brgm.fr

F Bodenan

P Wavrer

N Kanari

P Russo

USE OF AUTO SHREDDER RESIDUES GENERATED BY POST SHREDDER TECHNOLOGY IN METALLURGICAL FURNACES

A total of 11 Million vehicles are annually discarded in the EU-25. This represents a total of 9 Million tonnes of waste that has to be managed properly. The EU Directive 2000/53/EC, which aims at reducing the use of hazardous substances in vehicles, to facilitate their dismantling and to increase the recovery and use of recycled materials in car manufacturing. Currently between 75 and 85% of End-of-Life Vehicles (ELV) are recycled, mostly for the metal content. The aim of the Directive is to increase the weight of re-use and recovery to 95% by 2015. The common process to recover value-added materials from the car hulks associates shredding followed by an air classification, leading to a heavy fraction from which ferrous and non-ferrous materials are extracted, and a light fraction, mainly composed of plastics and residuals metals. This fraction undergoes Post-Shredder Treatments, to extract 30-50 wt % of materials valued as energy source in various processes of combustion. Among the remaining materials, two fractions are of great interest for iron and steel making industries: -one contains various plastics mixed with rubbers and traces of metals (copper). This fraction could be used as reducing agent to substitute the coke in blast and electric arc furnaces -a second fraction (-2mm) is rich in iron oxides (18 to 38%) and could be recycled in blast furnace to replace a part of the charged ores. In this respect, the chemical composition of each fraction is critical, and the following elements: Cl, Cu, Zn are to be specifically removed. Indeed, chlorinated compounds (such as PVC) can release corrosive compounds metal chlorides in the dusts, detrimental to the installations. Copper can contaminate and spoil the cast-iron produced. Zinc favors the development of scabs that modify the flow configuration inside the metallurgical furnaces.

The whole objective of the presented work is to define further sequences of separation processes to meet the requirement associated with a use in metallurgical furnaces of these two fractions, as reducing agents and recycled material respectively. This paper will present the results of chemical and mineralogical characterization of fractions sampled on an industrial line of treatment of automotive residues. The results feed two mass balance models of a blast furnace and an electric arc furnace, to determine the amount of each fractions injectable in both furnaces considering the requirements for a smooth processing of a high-quality pig iron. Two global processes of separation, each dedicated to a given fraction, are also defined with the aim at increasing the quantity introduced in the furnaces.