Florian Bugarin

Didier Henrion

Jean-Bernard Lasserre

Minimizing the sum of many rational functions *

Keywords: rational optimization, global optimization, semidefinite relaxations, sparsity. AMS MSC 2010: 46N10, 65K05, 90C22, 90C26

We consider the problem of globally minimizing the sum of many rational functions over a given compact semialgebraic set. The number of terms can be large (10 to 100), the degree of each term should be small (up to 10), and the number of variables can be relatively large (10 to 100) provided some kind of sparsity is present. We describe a formulation of the rational optimization problem as a generalized moment problem and its hierarchy of convex semidefinite relaxations. Under some conditions we prove that the sequence of optimal values converges to the globally optimal value. We show how public-domain software can be used to model and solve such problems. Finally, we also compare with the epigraph approach and the BARON software.

Introduction

Consider the optimization problem

f * := inf x∈K N i=1 f i (x) (1)
over the basic semi-algebraic set

K := {x ∈ R n : g j (x) ≥ 0, j = 1, . . . , m }, (2)
for given polynomials g j ∈ R[x], j = 1, . . . , m, and where each term f i : R n → R is a rational function

x → f i (x) := p i (x) q i (x) , with p i , q i ∈ R[x] for each i = 1, . . . , N.

Problem (1) is a fractional programming problem of a rather general form. Nevertheless, we assume that the degree of each f i and g j is relatively small (up to 10), but the number of terms N can be quite large (10 to 100). For dense data, the number of variables n should also be small (up to 10). However, this number can be also relatively large (10 to 100) provided that the problem data exhibits some kind of structured sparsity (to be specified later). Even though problem (1) is of independent interest, our initial motivation came from some applications in computer vision, where such problems are typical. These applications will be described elsewhere.

In such a situation, the fractional programming problem (1) is quite challenging. Indeed, we make no assumption on the polynomials p i , q i whereas even with a relatively small number of fractions and under convexity (resp. concavity) assumptions on p i (resp. q i ), problem ( 1) is hard to solve, especially if one wants to compute the global minimum.

In addition, we are interested in solving problem (1) globally, that is, we do not content ourselves with a local optimum satisfying first order optimality conditions, as is typically the case with standard local optimization algorithms such as Newton's method or its variants. If problem [START_REF] Ali | A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems[END_REF] is too difficult to solve globally (because of ill-conditioning and/or a large a number of variables or terms in the objective function), we would like to have at least a valid lower bound on the global minimum, since upper bounds can be obtained with local optimization algorithms.

In the literature, problem (1) is often called a sum-of-ratios program. Without assumptions, it is NP-complete [START_REF] Freund | Solving the sum-of-ratios problem by an interior-point method[END_REF]. Surveys on methods for solving this problem have been made in [START_REF] Schaible | Fractional programming: the sum-of-ratios case[END_REF] and then [START_REF] Wu | Solving the sum-of-ratios problem by a stochastic search algorithm[END_REF]. The reader can especially refer to [START_REF] Wu | Solving the sum-of-ratios problem by a stochastic search algorithm[END_REF]Table 1]. According to this survey, many attempts make restrictive assumptions either on the concavity or linearity of the ratios. When the ratios are nonlinear, the most popular methods are based on Branch and Bound approaches, see e.g. [START_REF] Benson | Using concave envelopes to globally solve the nonlinear sum of ratios problems[END_REF]. Because this problem often occurs in computer vision, many practical studies have been carried out. These studies aim at solving problem [START_REF] Ali | A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems[END_REF] in the quadratic case [START_REF] Kahl | Practical global optimization for multiview geometry[END_REF], or at certifying a posteriori if a solution is global or not [START_REF] Hartley | Verifying global minima for L2 minimization problems in multiple view geometry[END_REF].

In this paper, we would like to approach the fractional programming problem (1) as a generalized moment problem solved with its hierarchy of convex semidefinite programming (SDP) relaxations:

• One possible approach is to reduce all fractions p i /q i to same denominator q and obtain a single rational fraction to minimize. Then one may try to apply the hierarchy of SDP relaxations defined in [START_REF] Jibetean | Global optimization of rational functions: a semidefinite programming approach[END_REF], see also [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]Section 5.8]. But such a strategy is not appropriate because the degree of q is potentially large and even if n is small, one cannot even implement the first relaxation of the hierarchy, due to present limitations of SDP solvers. Moreover, in general this strategy also destroys potential sparsity patterns present in the original formulation [START_REF] Ali | A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems[END_REF], and so precludes from using an appropriate version (for the rational fraction case) of the sparse semidefinite relaxations introduced in [START_REF] Waki | Sums of squares and semidefinite programming relaxations for polynomial optimization problemswith structured sparsity[END_REF] whose convergence was proved in [START_REF] Lasserre | Convergent SDP relaxations in polynomial optimization with sparsity[END_REF] under some conditions on the sparsity pattern, see also [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]Sections 4.6 and 5.3.4].

• Another possibility is to introduce additional variables r i (that we may call lifting variables) with associated constraints p i (x) q i (x) ≤ r i , i = 1, . . . , N, and solve the equivalent problem:

f * := inf (x,r)∈ K N i=1 r i (3)
which is now a polynomial optimization problem in the new variables(x, r) ∈ R n × R N , and where the new feasible set K = K ∩ {(x, r) ∈ R n+N : r i q i (x)p i (x) ≥ 0} is modeling the epigraphs of the rational terms. This approach is an extension of the approach in [START_REF] Jibetean | Global optimization of rational functions: a semidefinite programming approach[END_REF] (it coincides if N = 1). Potential sparsity patterns in the x variables are preserved and if K is compact one may in general obtain upper and lower bounds r i , r i on the r i so as to make K compact by adding the quadratic (redundant) constraints (r i -r i )(r i -r i ) ≥ 0, i = 1, . . . , N, and apply a sparse version of semidefinite relaxations [START_REF] Jibetean | Global optimization of rational functions: a semidefinite programming approach[END_REF]. However, in doing so one introduces N additional variables, and this may have an impact on the overall performance, especially if N is large. In the sequel this approach is referred to as the epigraph approach.

The goal of the present paper is to overcome the above difficulties in the following two situations: either n is relatively small, or n is relatively large but some sparsity is present, i.e., each f i and each g j in ( 1) is concerned with only a small subset of variables. In the approach that we propose, we do not need the epigraph liftings. The idea is to formulate (1) as an equivalent infinite-dimensional linear problem which a particular instance of the generalized moment problem (GMP) as defined in [START_REF] Lasserre | A semidefinite programming approach to the generalized problem of moments[END_REF], with N unknown measures (where each measure is associated with a fraction p i /q i ). In turn this problem can be easily modeled and solved with our public-domain software GloptiPoly 3 [START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF], a significant update of GloptiPoly 2 [START_REF] Henrion | GloptiPoly: global optimization over polynomials with Matlab and SeDuMi[END_REF]. In the sequel this approach is referred to as the GMP approach. A collection of numerical experiments shows the potential of our GMP approach, especially in comparison with the epigraph approach. Numerical results also show that our results compare favorably with BARON software.

The outline of the paper is as follows. In Section 2 we introduce the SDP relaxations first in the case where n is small and with no sparsity pattern. Then in Section 3 we extend the SDP relaxations to the case that n is relatively large but some sparsity is present and can be exploited. In Section 4 we show how the GMP formulation can be exploited to model the SDP relaxations of problem (1) easily with GloptiPoly 3. The last section is devoted to a comparison with the epigraph approach and with the BARON solver on some numerical experiments.

Dense SDP relaxations

Consider the fractional programming problem (1) over the semi-algebraic set [START_REF] Benson | Global optimization algorithm for the nonlinear sum of ratios problem[END_REF]. We assume that f * > -∞ and the two polynomials:

p(x) := N i=1 p i (x) N j =i q j (x) (4) q(x) := N i=1 q i (x), (5)
are relatively prime. Hence, without loss of generality, q i > 0 on K for each i = 1, . . . , N. Indeed, by reducing the cost function to a common denominator, we obtain :

N i=1 f i (x) = p(x) q(x) . (6)
So, if i 0 ∈ N exists, such that q i 0 changes its sign on K, then q changes its sign on K. Thus, according to [13, Corollary 1 and Theorem 2], f * = -∞, which contradicts our hypothesis. Moreover, we assume that n, the number of variables in problem (1), is small, say up to 10.

GMP formulation

Consider the infinite dimensional linear problem f := inf

µ i ∈M(K) N i=1 K p i dµ i s.t. K q 1 dµ 1 = 1 K x α q i dµ i = K x α q 1 dµ 1 , ∀α ∈ N n , i = 2, . . . , N, (7)
where M(K) is the space of finite Borel measures supported on K.

Theorem 2.1 Let K ⊂ R n in (2) be compact, and assume that q i > 0 on K, i = 1, . . . , N.

Then f = f * .

Proof: We first prove that f * ≥ f . As f = i p i /q i is continuous on K, there exists a global minimizer x * ∈ K with f (x * ) = f * . Define µ i := q i (x * ) -1 δ x * , i = 1, . . . , N, where δ x * is the Dirac measure at x * . Then obviously, the measures (µ i ), i = 1, . . . , N, are feasible for [START_REF] Curto | Recursiveness, positivity, and truncated moment problems[END_REF] with associated value

N i=1 K p i dµ i = N i=1 p i (x * )/q i (x * ) = f (x * ) = f * .
Conversely, let (µ i ) be a feasible solution of [START_REF] Curto | Recursiveness, positivity, and truncated moment problems[END_REF]. For every i = 1, . . . , N, let dν i be the measure q i dµ i , i.e.

ν i (B) := K∩B q i (x)dµ i (x)
for all sets B in the Borel σ-algebra of R n , and so the support of ν i is K. As measures on compact sets are moment determinate, see the Appendix, the moments constraints of [START_REF] Curto | Recursiveness, positivity, and truncated moment problems[END_REF] imply that ν i = ν 1 , for every i = 2, . . . , N, and from K q 1 dµ 1 = 1 we also deduce that ν 1 is a probability measure on K. But then

N i=1 K p i dµ i = N i=1 K p i q i q i dµ i = N i=1 K p i q i dν 1 = K N i=1 p i q i dν 1 = K f dν 1 ≥ K f * dν 1 = f * ,
where we have used that f ≥ f * on K and ν 1 is a probability measure on K.

We next make the following assumption meaning that the set K admits analgebraic certificate of compactness.

Assumption 2.1 The set K ⊂ R n in ( 2) is compact and the quadratic polynomial x → M -|x| 2 can be written as

M -|x| 2 = σ 0 + m j=1 σ j g j ,
for some polynomials σ j ∈ R[x], all sums of squares of polynomials.

Remark 2.1 If Assumption (2.1) is not satisfied (or cannot be checked easily) and if we know some M > 0 such that:

K ⊂ x : x 2 ≤ M , (8)
then it suffices to add the redundant quadratic constraint Mx 2 ≥ 0 in the definition of K.

A hierarchy of dense SDP relaxations

Let y i = (y iα ), α ∈ N n , be a real sequence indexed in the canonical basis (x α ) of R[x], i = 1, . . . , N, and for every k ∈ N, let N n k := {α ∈ N n : j α j ≤ k}. Define the moment matrix M k (y i ) of order k, associated with y, whose entries indexed by multi-indices β (rows) and γ (columns) read

[M k (y i )] β,γ := y i(β+γ) , ∀ β, γ ∈ N n k , i = 1, . . . , N,
and so are linear in y i . Similarly, given a polynomial g(x) = α g α x α , define the localizing matrix M k (g y i ) of order k, associated with y and g, whose entries read

[M k (g y i )] β,γ := α g α y i(α+β+γ) , ∀ β, γ ∈ N n k , i = 1, . . . , N.
In particular, matrix M 0 (g y i ) is identical to L y i (g) where for every i, L y i : R[x] → R is the Riesz linear functional defined by:

g → L y i (g) := α∈N n g α y iα , ∀g ∈ R[x].
Let:

u i := ⌈(deg q i )/2⌉, i = 1, . . . , N,
r j := ⌈(deg g j )/2⌉, j = 1, . . . , m, and r := max j r j , and with no loss of generality assume that u 1 ≤ u 2 ≤ . . . ≤ u N . Consider the hierarchy of semidefinite programming (SDP) relaxations:

f * k = inf y i N i=1 L y i (p i ) s.t. M k (y i ) 0, i = 1, . . . , N M k-r j (g j y i ) 0, i = 1, . . . , N, j = 1, . . . , m L y 1 (q 1 ) = 1, L y i (x α q i ) = L y 1 (x α q 1 ), ∀α ∈ N n 2(k-u i ) , i = 2, . . . , N, (9)
with 2k u N .

Theorem 2.2 Let Assumption 2.1 hold and consider the hierarchy of SDP relaxations [START_REF] Freund | Solving the sum-of-ratios problem by an interior-point method[END_REF]. Then it follows that

(a) f * k ↑ f * as k → ∞.
(b) Moreover, let (y k i ) be an optimal solution of (9), such that

rank M k (y k i ) = rank M k-r (y k i ) =: R, i = 1, . . . , N. if R = 1 then f * k = f * , if R > 1 then each y k
i has a representating measure µ i supported on R points x l (i) ∈ K, l = 1, . . . , R, which can be extracted. If x l (i) = x l (j) for all i = j and every l, then f * k = f * .

Proof: Let us first prove statement (a). As K is compact, with no loss of generality we may and will assume that K ⊂ {x : Mx 2 ≥ 0} for some M > 0, and we also assume that the quadratic redundant constraint Mx 2 ≥ 0 constraint is part of the description of K, modeled by the constraint g 1 (x) ≥ 0.

Then the semidefinite constraint M k-1 (g

1 y i ) 0 implies 0 ≤ L y i (x 2ℓ t g 1 (x)) = ML y i (x 2ℓ t ) -L y i (x 2ℓ+2 t ) - n s =t L y i (x 2ℓ t x 2 s ) ≥0 ,
for all 0 ≤ ℓ ≤ k -1, and all t = 1, . . . , n. Hence, an easy induction yields that for any feasible solution y i one has:

M y i0 ≥ L y i (x 2 t ); M 2 (y i0 ) ≥ L y i (x 4 t ); • • • ; M k y i0 ≥ L y i (x 2k t ), (10)
for every t = 1, . . . , n.

Next by [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]Proposition 3.6], if M k (y i ) 0 then

|y iα | ≤ max[y i0 , [max t L y i (x 2k t )] ], ∀α with |α| ≤ 2k. ( 11
)
Next as q 1 > 0 on K (compact) then q 1 > δ on K for some δ > 0, and so by Putinar's Theorem [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF] there exists k 0 such that

q 1 -δ = σ 0 + m j=1 σ j g j ,
for some SOS polynomials σ j such that degσ j g j ≤ 2k for all j (with g 0 = 1). Applying L y i and using L y i (q 1 ) = 1, yields:

1 -y i0 δ = L y i m j=0 σ j g j = m j=0
L y i (σ j g j ) ≥ 0, as soon as k ≥ k 0 . And so y i0 ≤ δ -1 , which in view of ( 10)- [START_REF] Henrion | GloptiPoly: global optimization over polynomials with Matlab and SeDuMi[END_REF] yields

|y iα | ≤ max[δ -1 , M k δ -1 ] =: S k , ∀α with |α| ≤ 2k.
And in fact, a soon as k ≥ k 0 ,

|y iα | ≤ max[δ -1 , M |α| δ -1 ] =: S |α| , ∀α.
So for every k ≥ k 0 , the feasible set is compact which ensures the existence of an optimal solution y k i . So let y k i be a nearly optimal solution as in Theorem 2.2(a). Complete the finite sequence y k i with zeros to make it an infinite sequence indexed in N n (instead of N n 2k ). As soon as k ≥ k 0 define the new sequence

w k i = ((w k i ) α ), α ∈ N n , by w k iα = y k iα /S |α| ,
so that |w k iα | ≤ 1 for all α, and all k ≥ k 0 . Hence every element w k i is an element of the unit ball B of the Banach space ℓ ∞ of infinite sequences, uniformly bounded. Equipped with the usual sup-norm, ℓ ∞ is the topological dual of ℓ 1 . And so by Banach-Alaoglu's Theorem the unit ball of ℓ ∞ being compact (and sequentially compact) in the weak-⋆ topology σ(ℓ ∞ , ℓ 1 ), there exists a subsequence k t and an infinite sequence w i ∈ B such that w kt i → w i as t → ∞, for the weak-⋆ topology, and in particular pointwise convergence holds, i.e., lim

t→∞ w kt iα = w iα , ∀α ∈ N n .
Recalling the definition of w k i , one may define an infinite sequence y i by:

y iα := w iα S |α| , α ∈ N n ,
to obtain:

lim t→∞ y kt iα = S |α| lim t→∞ w kt iα = S |α| w iα =: y iα , ∀α ∈ N n .
Statement (b) follows from the flat extension theorem of Curto and Fialkow [START_REF] Curto | Recursiveness, positivity, and truncated moment problems[END_REF], see e.g. [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]Theorem 3.7] or [START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF]Section 5], so that each measure ν i is supported on R points of K.

Remark 2.2 Note that Theorem 2.2 is a generalization of [START_REF] Jibetean | Global optimization of rational functions: a semidefinite programming approach[END_REF]Theorem 9]. However, when N is large, [START_REF] Jibetean | Global optimization of rational functions: a semidefinite programming approach[END_REF]Theorem 9] is unsuitable to solve (1). Indeed, the dual hierarchy of SDP relaxations used in [START_REF] Jibetean | Global optimization of rational functions: a semidefinite programming approach[END_REF]Theorem 9] is given by:

inf y L y ( p) s.t. L y ( q) = 1 M k (y) 0 M k-r j (g j y) 0, j = 1, . . . , m, (12)
with 2k deg( q) and p, q defined by (6). If N is large, then the degree of p and q is large and the corresponding relaxations cannot be solved by conventional SDP solvers (see e.g. [START_REF] Borchers | CSDP, a C library for semidefinite programming[END_REF][START_REF] Benson | DSDP5 user guide -Software for semidefinite programming[END_REF][START_REF] Yamashita | A high-performance software package for semidefinite programs: SDPA 7[END_REF][START_REF] Toh | Solving semidefinite-quadratic-linear programs using SDPT3[END_REF][START_REF] Sturm | Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones[END_REF]).

Sparse SDP relaxations

In this section we assume that the number n of variables in problem (1), is large, say from 10 to 100, and moreover we also assume that some sparsity pattern is present in the polynomial data.

GMP formulation

Let I 0 := {1, . . . , n} = ∪ N i=1 I i with possible overlaps, and let R[x k : k ∈ I i ] denote the ring of polynomials in the variables x k , k ∈ I i . Denote by n i the cardinality of I i .

One will assume that K ⊂ R n in (2) is compact, and one knows some

M > 0 such that x ∈ K ⇒ M -|x| 2 ≥ 0. For every i ≤ N, introduce the quadratic polynomial x → g m+i (x) = M -k∈I i x 2
k . The index set {1, . . . , m + N} has a partition ∪ N i=1 J i with J i = ∅ for every i = 1, . . . , N. In the sequel we assume that for every i = 1, . . . , N,

p i , q i ∈ R[x k : k ∈ I i ] and for every j ∈ J i , g j ∈ R[x k : k ∈ I i ]. Next, for every i = 1, . . . , N, let K i := {z ∈ R n i : g k (z) ≥ 0, k ∈ J i } so that K in (2) has the equivalent characterization K = {x ∈ R n : (x k , k ∈ I i ) ∈ K i , i = 1, . . . , N}.
Similarly, for every i, j ∈ {1, . . . , N} such that i = j and I i ∩ I j = ∅,

K ij = K ji := {(x k , k ∈ I i ∩ I j ) : (x k , k ∈ I i ) ∈ K i ; (x k , k ∈ I j ) ∈ K j }.
Let M(K) be the space of finite Borel measures on K, and for every i = 1, . . . , N, let π i : M(K) → M(K i ) denote the projection on K i , that is, for every µ ∈ M(K):

π i µ(B) := µ({x : x ∈ K; (x k , k ∈ I i ) ∈ B}), ∀B ∈ B(K i )
where B(K i ) is the usual Borel σ-algebra associated with K i .

For every i, j ∈ {1, . . . , N} such that i = j and

I i ∩ I j = ∅, the projection π ij : M(K i ) → M(K ij
) is also defined in an obvious similar manner. For every i = 1, . . . , N -1 define the set:

U i := { j ∈ {i + 1, . . . , N} : I i ∩ I j = ∅ },
and consider the infinite dimensional problem f := inf

µ i ∈M(K i ) N i=1 K i p i dµ i s.t. K i q i dµ i = 1, i = 1, . . . , N π ij (q i dµ i ) = π ji (q j dµ j ), ∀j ∈ U i , i = 1, . . . , N -1. ( 13
)
Definition 3.1 Sparsity pattern (I i ) N i=1 satisfies the running intersection property if for every i = 2, . . . , N:

I i i-1 k=1 I k ⊆ I j , for some j ≤ i -1. (14)
Remark 3.1 : In general, the running intersection property ( 14) holds for sparsity patterns associated with many rational estimation problems in engineering (e.g. computer vision). Indeed, these problems are formulated as least squares problems where each residual is the difference between an observed parameter q i and a rational function f (x, r i ) recalibrated to reflect the observed behaviour:

min (x,r)∈R n ×R lN N i=1 q i -f (x, r i ) 2 2 . ( 15
)
In this formulation, unknowns are x ∈ R n and each r i ∈ R l , i = 1, . . . , N. The vector x represents the parameters of the model. The vector r ∈ R lN represents the input observations. Classicaly, these variables are fixed. However, as is often the case in computer vision, it is necessary to reestimate r in order to increase the accuracy of the final model. Let Proof: That f ≤ f * is straightforward. As K is compact and q i > 0 on K for every i = 1, . . . , N, f * = N i=1 f i (x * ) for some x ∈ K. So let µ be the Dirac measure δ x * at x * and let ν i be the projection

I 0 := { 1, 2, . . . , l r 1 , l + 1, . . . , 2l
π i µ of µ on K i . That is ν i = δ (x * k ,k∈I i ) , the Dirac measure at the point (x * k , k ∈ I i ) of K i .
Next, for every i = 1, . . . , N,define the measure dµ i := q i (x * ) -1 dν i . Obviously, (µ i ) is a feasible solution of (13) because µ i ∈ M(K i ) and q i dµ i = 1, for every i = 1, . . . , N, and one also has:

(x * k , k ∈ I i ∩ I j ) = π ij µ i = π ji µ j , ∀j = i such that I j ∩ I i = ∅.
Finally, its value satisfies

N i=1 K i p i dµ i = N i=1 p i (x * )/q i (x * ) = f * ,
and so f ≤ f * .

We next prove the converse inequality f ≥ f * . Let (µ i ) be an arbitrary feasible solution of (13), and for every i = 1, . . . , N, denote by ν i the probability measure on K i with density q i with respect to µ i , that is,

ν i (B) := K i ∩B q i (x) dµ i (x), ∀B ∈ B(K i ).
By definition of the linear program [START_REF] Jibetean | Global optimization of rational functions: a semidefinite programming approach[END_REF], π ij ν i = π ji ν j for every couple j = i such that I j ∩ I i = ∅. Therefore, by [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]Lemma B.13] there exists a probability measure ν on K such that π i ν = ν i for every i = 1, . . . , N. But then

N i=1 K i p i dµ i = N i=1 K i p i q i dν i = N i=1 K i p i q i dν = K N i=1 p i q i dν ≥ f *
and so f ≥ f * .

A hierarchy of sparse SDP relaxations

Let y = (y α ) be a real sequence indexed in the canonical basis (x α ) of R[x]. Define the Riesz linear functional L y : R[x] → R, by:

f = α∈N n f α x α → α∈N n f α y α , ∀f ∈ R[x].
For every i = 1, . . . , N, let

N (i) := { α ∈ N n : α k = 0 if k ∈ I i }; N (i) k := { α ∈ N (i) : i α i ≤ k }.
An obvious similar definition of N (ij) (= N (ji) ) and

N (ij) k (= N (ji)
k ) applies when considering

I j ∩ I i = ∅.
For every i = 1, . . . , N, let y i = (y iα ) be a given sequence indexed in the canonical basis of R[x]. The sparse moment matrix M k (y i , I i ) associated with y i , has its rows and columns indexed in the canonical basis (x α ) of R[x k : k ∈ I i ], and with entries:

M k (y i , I i ) α,β = L y i (x α+β ) = y i(α+β) , ∀ α, β ∈ N (i) k .
Similarly, for a given polynomial h ∈ R[x k : k ∈ I i ], the sparse localizing matrix M k (h y i , I i ) associated with y i and h, has its rows and columns indexed in the canonical basis (x α ) of R[x k : k ∈ I i ], and with entries:

M k (h y i , I i ) α,β = L y i (h x α+β ) = γ∈N (i) h γ y i(α+β+γ) , ∀ α, β ∈ N (i) k .
With K ⊂ R n defined in (2), let r j := ⌈(degg j )/2⌉, for every j = 1, . . . , m + N. Consider the hierarchy of semidefinite relaxations:

f * k = inf y 1 ,...,y N N i=1 L y i (p i ) s.t. M k (y i , I i ) 0, i = 1, . . . , N M k-r j (g j y i , I i ) 0, ∀j ∈ J i , i = 1, . . . , N L y i (q i ) = 1, i = 1, . . . , N L y i (x α q i ) = L y j (x α q j ) = 0, ∀α ∈ N (ij) , ∀j ∈ U i , i = 1, . . . , N -1 with |α| + max[degq i , degq j ] ≤ 2k. ( 16
)
Theorem 3.2 Let K ⊂ R n in (2) be compact. Let the sparsity pattern (I i ) N i=1 satisfy the running intersection property, and consider the hierarchy of semidefinite relaxations defined in [START_REF] Kuno | A branch-and-bound algorithm for maximizing the sum of several linear ratios[END_REF]. Then:

(a) f * k ↑ f * as k → ∞. (b)
If an optimal solution y * = (y * 1 , . . . , y * N ) of ( 16) satisfies

rank M k (y * i , I i ) = rank M k-v i (y * i , I i ) =: R i , ∀i = 1, . . . , N,
(where v i = max j∈J i [r j ]), and

rank M k (y * i , I i ∩ I j ) = 1, ∀j ∈ U i , i = 1, . . . , N -1,
then f * k = f * and one may extract finitely many global minimizers.

Proof: The proof is similar to that of Theorem 2.2 and also to that of [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]Theorem 4.7].

One first proves that ( 16) has a feasible solution and f * k > -∞ for sufficiently large k. Next, let y k = (y k 1 , . . . , y k N ) be a nearly optimal solution of (16), i.e.

f * k ≤ N i=1 L y k i (p i ) ≤ f * k + 1 k .
(Again K ⊂ {x : |x| 2 ≤ M} for some M because K is compact. So if such a scalar M is known, one may include the redundant quadratic constraint M -|x| 2 ≥ 0 in the definition of K, in which case existence of an optimal solution to ( 16) is guaranteed.)then there exists a subsequence (k ℓ ) and a sequence y = (y 1 , . . . , y N ), such that lim ℓ→∞

y k ℓ iα = y iα , ∀α ∈ N (i) , i = 1, . . . , N.
Of course, for every i = 1, . . . , N, y i is a sequence (y iα ), α ∈ N n , but only the entries y iα , α ∈ N (i) , are relevant and all the other entries can be set to zero.

From this pointwise convergence it easily follows that for every i = 1, . . . , N and j ∈ J i ,

M k (y i , I i ) 0, M k (g j y i , I i ) 0, j ∈ J i ; i = 1, . . . , N.
Now observe that each set K i ⊂ R n i satisfies Assumption 2.1. Therefore, by Putinar's theorem, see [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF] or [19, Theorem 2.14], the sequence y i = (y iα ), α ∈ N (i) (i.e., the subsequence of y i ignoring the entries y iα , α ∈ N (i) ), has a representing measure µ i supported on K i . Again, by pointwise convergence, L y i (q i )(= L y i (q i )) = 1, for every i = 1, . . . , N, and

L y i (q i x α ) = K i x α q i (x) dµ i dν i (x) = K j x α q j (x) dµ j dν j (x) , ∀α ∈ N (ij) , ∀j ∈ U i . (17)
Therefore, for every i = 1, . . . , N, dν i := q i (x)dµ i is a finite Borel probability measure supported on K i . As measures on compact sets are moment determinate, see the Appendix, (17) yields:

π ij ν i = π ji ν j , ∀(i, j), j ∈ U i .
Therefore, by [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]Lemma B.13] there exists a probability measure ν on K such that π i ν = ν i for every i = 1, . . . , N. But then

f * ≥ lim ℓ→∞ f * k ℓ = lim ℓ→∞ N i=1 L y k ℓ i (p i ) = N i=1 K i p i dµ i = N i=1 K i p i q i q i dµ i = N i=1 K i p i q i dν i = K N i=1 p i q i dν ≥ f * .
As the converging subsequence was arbitrary, and (f * k ) is monotone non decreasing, we finally get f * k ↑ f * . In addition, ν is an optimal solution of (13) with optimal value f * = f . The proof of (b) is as in [START_REF] Lasserre | Convergent SDP relaxations in polynomial optimization with sparsity[END_REF] and uses the flat extension theorem of Curto and Fialkow, see [START_REF] Curto | Recursiveness, positivity, and truncated moment problems[END_REF] or [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]Theorem 3.7], from which, the sequence (y * ) i = (y * iα ), α ∈ N (i) , has an atomic representing measure supported on R i points of K i , for every i = 1, . . . , N.

GloptiPoly and examples

In this section we show that the generalized moment problem (GMP) formulation of rational optimization problem (1) has a straightforward Matlab implementation when using our software GloptiPoly 3 [START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF]. Rather than explaining the approach in full generality with awkward notations, we describe three simple examples.

Illustrative univariate examples 4.1.1 Wilkinson-like rational function

Consider the elementary univariate rational optimization problem

f * = sup x∈R f (x), f (x) = N i=1 p i (x) q i (x) = N i=1 1 x 2 + i
with N an integer. The only real critical point is x = 0, at which the objective function takes its maximum

f * = f (0) = N i=1 1 i .
Reducing to the same denominator

f (x) = i j =i (x 2 + j) i (x 2 + i) = p(x 2 ) q(x 2 )
yields the well-known Wilkinson polynomial q whose squared root moduli are the integers from 1 to N. This polynomial was described in the mid 1960s by J.H. Wilkinson to illustrate the difficulty of computing (numerically) roots of polynomials. If we choose e.g. N = 20, reduction to the same denominator is hopeless since the constant coefficient in monic polynomial q is 20! = 2432902008176640000. The GMP formulation [START_REF] Curto | Recursiveness, positivity, and truncated moment problems[END_REF] of this problem reads (up to replacing "inf" with "sup" in the objective function):

sup µ i ∈M(R) N i=1 R p i dµ i s.t. R q 1 dµ 1 = 1 R x α q i dµ i = R x α q 1 dµ 1 , ∀α ∈ N n , i = 1, . . . , N.
Our Matlab script to model and solve this problem is given in Appendix 7.1.

At the first SDP relaxation we obtain a rank-one moment matrix corresponding to a Dirac at x * = 0 with f * = 3.5977 which is consistent with Maple's output:

> f := sum(1/(x^2+i), i=1..20); > evalf(subs(x = 0, f)); 3.5977 Note that for this example Assumption 2.1 is violated, since we optimize over the unbounded set K = R. In spite of this, we could solve the problem globally because for univariate problems, compactness of the feasible set is not required.

Relevance of the compactness assumption

With the next elementary example we would like to emphasize the practical impact of optimization on a bounded set K (and the smaller, the better). Consider the univariate problem

f * = inf x∈K f (x), f (x) = 1 + x + x 2 1 + x 2 + 1 + x 2 1 + 2x 2 . ( 18
)
First let K = R. The numerator of the gradient of f (x) has two real roots, one of which being the global minimum located at x * = -1.4215 for which f * = 1.1286. The GloptiPoly script given in Appendix 7.2 models and solves the SDP relaxations of orders k = 0, . . . , 9 of the GMP formulation of [START_REF] Lasserre | A semidefinite programming approach to the generalized problem of moments[END_REF]. We retrieve the following monotonically increasing sequence of lower bounds f * k (up to 5 digits) obtained by solving the SDP relaxations (9): 1 shows that the convergence of the hierarchy of SDP relaxations is rather slow for this very simple example. This is due to the fact that one optimizes over the unbounded set K = R. In Figure 1 we display the sequences of lower bounds obtained by solving the SDP relaxations of problem (18) on compact sets K = [-R, R] for R = 2, 3, . . . , 10. Clearly, the smaller is R the faster is the convergence.

order k bound f * k order k bound f * k 1 1.0000 4

Exploiting sparsity with GloptiPoly

Even though version 3 of GloptiPoly may exploit problem sparsity, there is no illustration of this feature in the software user's guide [START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF]. In this section we provide such a simple example. Note also that GloptiPoly does not detect sparsity for a given problem, in contrast with SparsePOP which includes a routine to detect structural sparsity patterns by using a heuristic to build up chordal extensions of some graph [START_REF] Waki | SparsePOP: a sparse semidefinite programming relaxation of polynomial optimization problems[END_REF] associated with the problem data. However, SparsePOP is not designed to handle directly rational optimization problems.

Consider the elementary example of [17, Section 3.2]:

inf x∈R 4 x 1 x 2 + x 1 x 3 + x 1 x 4 s.t. x 2 1 + x 2 2 ≤ 1 x 2 1 + x 2 3 ≤ 2 x 2 1 + x 2 4 ≤ 3
for which the variable index subsets I 1 = {1, 2}, I 2 = {1, 3}, I 3 = {1, 4} satisfy the running intersection property [START_REF] Kahl | Practical global optimization for multiview geometry[END_REF] in Definition 14. Note that this problem is a particular case of (1) with a polynomial objective function.

Without exploiting sparsity, the GloptiPoly script to solve this problem is given in Appendix 7.3.1. GloptiPoly certifies global optimality with a moment matrix of size 15, and 3 localizing matrices of size 5. The script exploiting sparsity, given in Appendix 7.3.2, associates variables with several measures µ i , in a manner consistent with subsets I i . GloptiPoly certifies global optimality with 3 moment matrices of size 6, and 3 localizing matrices of size 3. Remark 4.1 GloptiPoly is a Matlab interface which constructs LMI relaxations of a given GMP. The corresponding LMI relaxation can then be solved via any SDP solver interfaced via YALMIP [START_REF] Löfberg | Yalmip : A toolbox for modeling and optimization in MATLAB[END_REF]. So, for the same optimization problem converted by Gloptipoly, the number of function evaluations and the number of iterations depend on the solver used. For this reason, we believe that the latter two quantities cannot be considered as representative values in this context. However, the number of function evaluations and the number of iterations are directly related to the size of the problem converted by GloptiPoly. This size is represented by the sizes of moment matrices and localizing matrices.

Comparison with the epigraph approach

Recall the epigraph optimization problem:

f * := inf (x,r)∈ K N i=1 r i (3)
with:

K = K ∩ {(x, r) ∈ R n+N : r i q i (x) -p i (x) ≥ 0}.
Note that the epigraph approach is consistent with the running intersection property [START_REF] Kahl | Practical global optimization for multiview geometry[END_REF]. Indeed, let I 0 = {1, 2, . . . , n + N} be the set of indices which correspond to the variables {r 1 , . . . , r N , x 1 , . . . , x n }. Then, I 0 := N i=1 I i with I i = {i, N + 1, . . . , N + n} and, because I i ∩ I j = {N + 1, . . . , N + n} ∀i = j, the sparsity pattern (I i ) i=1,...,N verifies the running intersection property. Consequently (see e.g. [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]Theorem 5.9]), if k is the relaxation order, the size of the moment matrix can be reduced from n+N +k n+N to n+1+k n+1 . Thus, in the sequel, we use this sparsity pattern in the epigraph approach to reduce the number of variables of the SDP relaxation.

In most of the examples that we have processed, the epigraph approach described in the Introduction (consisting of introducing one lifting variable for each rational term in the objective function) was less efficient than the GMP approach. Typically, the order of the SDP relaxation (and hence its size) required to certify global optimality is larger with the epigraph approach than with the GMP approach.

When testing the epigraph approach, we have also observed that numerically, it is better to replace the inequality constraints r i q i (x)p i (x) ≥ 0 with equality constraints r i q i (x)p i (x) = 0 in the definition of semi-algebraic set K in (3). For the example of Section 4.1.1 the epigraph approach with inequalities certifies global optimality at order k = 5, whereas the epigraph approach with equalities requires k = 1.

Note that for all problems presented in this subsection, there is no sparsity pattern to exploit because all variables appear in each term of the sum.

Eighth-degree function

As a typical illustration of the issues faced with the epigraph approach,consider the example with eighth-degree terms

min x∈R 2 f (x) := 10 i=1 (x 1 + x 2 )(x 2 1 + x 2 1 x 2 2 + x 4 2 + i 2 ) -(ix 2 2 + 1)(x 4 1 + x 2 2 + 2i) (x 4 1 + x 2 2 + 2i)(x 2 1 + x 2 1 x 2 2 + x 4 2 + i 2 ) , s.t. x 2 i 10 ( 19
)
which is cooked up to have several local optima and sufficiently high degree to prevent reduction to the same denominator. The GMP approach yields a certificate of global optimality with x * 1 = -0.60490, x * 2 = -2.2053, f * = -6.2844 at order k = 6 in a few seconds on a standard PC. In contrast, the epigraph approach does not provide a certificate for an order as high as k = 7, and requires more than one minute of CPU time.

Kowalik's function

In order to illustrate this behaviour, the two approaches are compared on the Kowalik problem [START_REF] Ali | A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems[END_REF]. This academic problem is a minimization in the least squares sense, given by: The GMP approach yields a certificate of global optimality at order k = 3 in 10.7 seconds on a standard PC. The obtained solution matches with the known global minimizer to four significant digits. In contrast, the epigraph approach does not provide a certificate within a reasonable time. To obtain an approximation of the global minimizer, the search domain is reduce to the ball {x ∈ R 4 : n i=1 (x i -0.21) 2 0.21} which contains the global solution certified by the GMP approach. Then, as the global minimizer is unique, the vector of first order moments provides an approximation of the global minimizer. In fact this vector converges to the unique optimal solution (see [START_REF] Schweighofer | Optimization of polynomials on compact semialgebraic sets[END_REF]). Table 2 shows the certified solution obtained by the GMP approach and the approximation given by the minimization of the epigraph problem on the ball {x ∈ R 4 : n i=1 (x i -0.21) 2 0.21}. In addition to high computational times, Table 2 also shows that the resulting approximation is far from the global minimizer. Note that to ensure the convergence of the sequence of

min x∈R 2 f (x) := 11 k=1 a k - x 1 (1 + x 2 b k ) (1 + x 3 b k + x 4 b 2 k ) 2 , s.t. (x i -0.21) 2 0.21 2 (

Method

x * Table 2: Solution certified by the GMP approach at k = 3 versus the approximation given by the minimization of the epigraph problem on the ball {x ∈ R 4 :

n i=1 (x i -0.21) 2 0.21} at k = 3.
the solutions of the SDP relaxations of the epigraph formulation to the global minimizer, the lifting variables must be bounded. For solving problem [START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF], the lifting variables were bounded by using the following constraints:

r 2 k a k - x * 1 (1 + x * 2 b k ) (1 + x * 3 b k + x * 4 b 2 k ) 2 , k = 1, . . . , 11. (21)
Consequently, an additional information is given to the epigraph approach (but not given in the GMP approach). However, even with this additional information, the GMP approach still provides better results.

De Jong's functions

Consider the modified De Jong's rational function minimization problem [START_REF] Pujol | A highly efficient function optimization with genetic programming[END_REF], given by:

min x∈R 2 f (x) := - N i=1 1 (10x 1 + a i ) 2 + (10x 2 + b i ) 2 + c i 2 s.t. x 2 1 + (x 2 + 0.1) 2 0.85 (22)
with:

a = (-4 0 4 -4 0 4 -4 0 4 -4 0 4 -4 0 4), b = (-4 -4 -4 -1 -1 -1
2.5 2.5 2.5 6 6 6 9 9 9), c = 14.

(23) N x * 1 x * 2 f *
order k times (s) 9 -0.4000 -0.2500 -6.037 6 4.40s 12 -0.4000 -0.6000 -10.56 8 11.4s 15 -0.4000 -0.9000 -16.40 13 81.7s

Table 3: Solutions, certification orders and computational times given by the GMP approach for problem [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF].

The certified solutions obtained by the GMP approach are given in Table 3. As we already mentioned, the lifting variables of the epigraph formulation must be bounded. In most examples that we have processed, these bounds play an important role in the accuracy of the algorithm. If the bounds are properly set, the convergence speed and the accuracy of the solutions can be equivalent to that of the GMP approach. However, finding tight bounds on each lifting variable is a difficult problem a priori. In practice, a simple way to proceed is to bound each lifting variable thanks to the following constraints:

r 2 i   max x∈K |p i (x)| min x∈K q i (x)   2 , ∀i = 1 . . . N. (24)
For problem [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF], these constraints reduce to:

r 2 i i 4 c 2 , ∀i = 1 . . . N. (25)
For N = 9, 12, 15 we observe the same behaviour: the epigraph approach never provides a certified solution. However, because the global minimizer is unique, again the vector of first order moments provides an approximation of the global minimizer. Table 4 summarizes the approximations given by the epigraph approach, the orders k of the SDP relaxation from which the vector of first order moments is read, and the computational times required to solve this relaxation. This table shows off a significant gap between the approximation given by the epigraph approach and the certified solution given by the GMP approach. Note that, due to the increasing size of the relaxations, we have observed numerical instabilities of the SDP solver SeDuMi [START_REF] Sturm | Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones[END_REF] used in Gloptipoly. These instabilities were observed for k > 3 with N = 9 and k > 2 with N = 12, 15.

N

Comparison with BARON solver

In the previous examples, we have compared the GMP approach with the epigraph approach. However, it is also possible to solve directly this particular class of problems by using standard software packages. Among these methods, a reviewer of a previous version of this paper suggested to compare the GMP approach with BARON software [START_REF] Tawarmalani | A polyhedral branch-and-cut approach to global optimization[END_REF] publicly available on the NEOS server [START_REF] Czyzyk | The NEOS Server[END_REF]. We used the version 14.0.3 (built: LNX-64) of BARON available on NEOS, and the GMP experiments were run on our own computer with GloptiPoly version 3.7 on Matlab 2014 on an IntelCore i7 2.2GHz (4 cores) with 16GB RAM.

Shekel's foxholes

In order to compare the GMP approach with the BARON solver on some benchmark problems, consider the modified Shekel foxholes minimization problem [START_REF] Bersini | Results of the first international contest on evolutionary optimisation[END_REF]:

min x∈R n f (x) := - N i=1 1 n j=1 (x j -a ij ) 2 + c i s.t. n i=1 (x i -5) 2 60 ( 26
)
whose data a ij , c i , i = 1, . . . , N, j = 1, . . . , n are given. These functions have been designed to have many local minima. Note that it is not possible to exploit problem sparsity in this case, since all variables appear in each term of the sum [START_REF] Tawarmalani | A polyhedral branch-and-cut approach to global optimization[END_REF]. We know the unique global minima for the set of data [START_REF] Ali | A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems[END_REF][START_REF] Kuno | A branch-and-bound algorithm for maximizing the sum of several linear ratios[END_REF]. For this set, N is fixed to 30. Note that, in order to avoid numerical problems, a suitable scaling is done to make critical points fit within the ball {x ∈ R n : n i=1 (x i -0.5) 2 0.6}. In the case n = 5, the GMP approach yields a certificate of global optimality at order k = 3 in about 84 seconds on a standard PC. The extracted minimizer is:

x * GM P = (8.025, 9.151, 5.114, 7.621, 4.564), [START_REF] Toh | Solving semidefinite-quadratic-linear programs using SDPT3[END_REF] which matches with the known unique global minimizer to four significant digits. This point can be refined if given an initial guess for a local optimization method: if we use a standard quasi-Newton BFGS algorithm, we obtain after a few iterations a point matching the known unique global minimizer to eight significant digits. Comparatively, BARON provides an approximation of the unique global minimum with four correct significant digits in 1000 seconds which by default is set as a time limit on the NEOS server. The solver interrupts because the limit time is reached, with a solver status equal to 3. Consequently, the obtained approximation is not certified and detected as a local minimum. Moreover, if this limit is decreased to 100 seconds, the approximation remains equal to the unique global minimum with four significant digits but always detected as a local minimum. To obtain a certified solution, the time limit must be increased to approximately 2500 seconds.

In the case n = 10, for which the global minimum is given in [1, is a good approximation to the minimizer, with four correct significant digits. If necessary, this point can be used as an initial guess in some (local) optimization algorithm.

Comparatively, BARON provides an approximation of the unique global minimum with four correct significant digits in 3600 seconds which we set as a time limit on the NEOS server. The solver interrupts because the limit time is reached, with a solver status equal to 3. Consequently, the obtained approximation is not certified and detected as a local minimum. Moreover, if this limit is decreased to 300 seconds, the approximation remains equal to the unique global minimum with four significant digits but always detected as a local minimum.

Rosenbrock's functions

Consider the rational optimization problem

f * = max x∈R n n-1 i=1 1 100(x i+1 -x 2 i ) 2 + (x i -1) 2 + 1 (28)
which has the same critical points as the well-known Rosenbrock problem min

x∈R n n-1 i=1 (100(x i+1 -x 2 i ) 2 + i -1) 2 )
whose geometry is troublesome for local optimization solvers. Note that a sparsity pattern can be exploited to reduce the number of variables in the SDP relaxations. It can been easily shown that the global maximum f * = n-1 of problem ( 28) is achieved at x * i = 1, i = 1, . . . , n. Our experiments with local optimization algorithms reveal that standard quasi-Newton solvers or functions of the Optimization toolbox for Matlab, called repeatedly with random initial guesses, typically yield local maxima quite far from the global maximum.

With our GMP approach, after exploiting sparsity and adding bound constraints x 2 i ≤ 16, i = 1, . . . , n, we could solve problem [START_REF] Waki | Sums of squares and semidefinite programming relaxations for polynomial optimization problemswith structured sparsity[END_REF] with a certificate of global optimality for n up to 1000. A certificate of global optimality is obtained at order k = 1 with typical CPU times ranging from 10 seconds for n = 100 to 500 seconds for n = 1000.

By varying n from 20 to 1000 and submitting the corresponding problems to BARON on the NEOS solver, we observe the following behavior. First, BARON finds a solution (i.e. with a termination status equal to 1) with typical CPU times ranging from less than one second to 500 seconds. Second, BARON finds the global maximum in most of cases except for the values of n summarized on Table 5. Moreover, for n 640 (except for n = 860), all solutions provided by BARON are wrong since all satisfy x 1 = -0.995 ( = 1) and x k = 1 for all k = 1 (the expected values of the global maximum). Consequently, it may be seen that problem [START_REF] Waki | Sums of squares and semidefinite programming relaxations for polynomial optimization problemswith structured sparsity[END_REF] creates numerical instabilities which can be overcome thanks to GMP sparse formulation.

In order to increase the difficulty of problem (28), we defined the following rational optimization problem:

f * = max x 2 i ≤ 1 n-1 i=1 (-1) i 100(x i+1 -x 2 i ) 2 + (x i -1) 2 + 1 . (29)
In the case n = 17, the GMP approach yields a certificate of global optimality at order k = 8 in about 26 seconds on a standard PC. The extracted minimizer is :

x * GM P = (-0.006 0.839 0.703 1.00 1.00 0.667 0.444 0.844 0.711 1.00 1.00 0.667 0.444 0.844 0.711 1.00 1.00 -1.00),

Sum of linear and quadratic ratios

We have compared the performance of GMP and BARON on several instances of problem (1) with a small number of variables, found in the technical literature:

• [31, Example 5.1] is an instance with a sum of N = 16 ratios with linear numerators and denominators in n = 3 variables, on a polytopic set K. Our GMP approach certifies the global solution in approx. 14 seconds, while BARON solves this problem is less than 1 second.

• [31, Example 6.3], also reported in [START_REF] Benson | Using concave envelopes to globally solve the nonlinear sum of ratios problems[END_REF], is an instance with a sum of N = 2 ratios with quadratic numerators and denominators in n = 3 variables, on a polytopic set K. Both our GMP approach and BARON solve this problem is less than 1 second.

• [2, Example 6.2] is an instance with a sum of N = 2 ratios with quadratic numerators and denominators in n = 2 variables, on a polytopic set K. Both our GMP approach and BARON solve this problem is less than 1 second.

• [16, Example 5.1] is an instance with a sum of N = 3 ratios with linear numerators and denominators in n = 3 variables, on a polytopic set K. Our GMP approach solves the problem is approx. 2 seconds, whereas BARON solves this problem is less than 1 second.

• [16, Example 5.2] is an instance with a sum of N = 4 ratios with linear numerators and denominators in n = 3 variables, on a polytopic set K. Our GMP approach solves the problem is approx. 3 seconds, whereas BARON solves this problem is less than 1 second.

• [30, Example 5.1] is an instance with a sum of N = 2 ratios with quadratic numerators and denominators in n = 3 variables, on a quartic set K. Both our GMP approach and BARON solve this problem is less than 1 second.

• [START_REF] Wang | Global optimization for sum of geometric fractional functions[END_REF]Example 5.3] is an instance with a sum of N = 2 ratios with quadratic numerators and denominators in n = 2 variables, on a polytopic set K. Both our GMP approach and BARON solve this problem is less than 1 second.

Conclusion

The problem of minimizing a sum of many low-degree (typically non-convex) rational fractions on a (typically non-convex) semi-algebraic set arises in several important applications, and notably in computer vision (triangulation, estimation of the fundamental matrix in epipolar geometry) and in systems control (H 2 optimal control with a fixedorder controller of a linear system subject to parametric uncertainty). These engineering problems motivated our work, but the application of our techniques to computer vision and systems control will be described elsewhere. These fractional programming problems being non convex, local optimization approaches yield only upper bounds on the optimum.

In this paper we were interested in computing the global minimum (and possibly global minimizers) or at least, computing valid lower bounds on the global minimum, for fractional programs involving a sum with many terms. We have used a moment-SOS approach with semidefinite relaxations by formulating the rational optimization problem as an instance of the generalized moment problem (GMP). In addition, when the number of variables is large, some structured sparsity pattern in problem data can sometimes be exploited. In numerical experiments, our public-domain software GloptiPoly interfaced with off-the-shelf semidefinite programming solvers indicate that the approach can solve problems that can be challenging for state-of-the-art global optimization algorithms. This is consistent with the experiments made in [START_REF] Kahl | Globally optimal estimates for geometric reconstruction problems[END_REF] where the (dense) SDP relaxation approach was first applied to (polynomial) optimization problems of computer vision.

For larger and/or ill-conditioned problems, it can happen that GloptiPolyextracts from the moment matrix a minimizer which is not very accurate. It can also happen that GloptiPoly is not able to extract a minimizer, but when the global minimizer is unique (which is generically true) the vector of first-order moments (of an optimal solution of the relaxation) provides an approximation that converges to the global minimizer. And so this resulting approximation may be used as initial guess for any local optimization algorithm.

In this Matlab script, the instructions mpol, meas, mass, mom, mmon, msdp, max and msol are GloptiPoly 3 commands, see the user's guide [START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF] for more information. Variable f is the objective function to be maximized. Since p i = 1 for all i = 1, . . . , N, it is the sum of masses of measures µ i . Vector e stores the linear moment constraints and the instruction mmon(x,k) generates all monomials of variable x up to degree k. Finally, instruction msdp generates the SDP relaxation of the GMP, and msol solves the SDP problem with the default conic solver (SeDuMi 1.3 in our case).

r 2 ,

 2 . . . , (N -1)l + 1, . . . , Nl r N , Nl + 1, . . . , Nl + n x } be the set of indices which correspond to the variables {r 1 , . . . , r N , x 1 , . . . , x n }. Then, I 0 := N i=1 I i with I i = {(i -1)l + 1, . . . , il, Nl + 1, . . . , Nl + n} and, because I i ∩ I j = {Nl + 1, . . . , Nl + n} ∀i = j, the sparsity pattern (I i ) i=1,...,N satisfies the running intersection property (14).

Theorem 3 . 1

 31 Let K ⊂ R n in (2) be compact. If the sparsity pattern (I i ) N i=1 satisfies the running intersection property (14) then f = f * .

Figure 1 :

 1 Figure 1: Lower bounds for SDP relaxations of problem (18) on bounded sets K = [-R, R] for R=2 (top curve), 3, 4, 5, 6, 7, 8, 9 and 10 (bottom curve).

  times (s) order k GMP 0.192 0.190 0.123 0.135 3.10×10 -4 10 3 Epigraph 0.194 0.188 0.129 0.132 3.12×10 -4 208 3

7. 2

 2 Subsection 4.1.2 function script mpol x1 x2 f1 = 1+x1+x1^2; g1 = 1+x1^2; f2 = 1+x2^2; g2 = 1+2*x2^2; mu1 = meas(x1); mu2 = meas(x2); bounds = []; for k = 1:6 P = msdp(min(mom(f1)+mom(f2)), ... mom(mmon(x1,2*(k-1))*g1) == mom(mmon(x2,2*(k-1))*g2), mom(g1) == 1); [stat, obj] = msol(P); bounds = [bounds; obj]; end bounds 7.3 Subsection 4.2 function scripts 7.3.1 Script 1 mpol x1 x2 x3 x4 Pdense = msdp(min(x1*x2+x1*x3+x1*x4), ... x1^2+x2^2<=1,x1^2+x3^2<=2,x1^2+x4^2<=3,2); [stat,obj] = msol(Pdense); 7.3.2 Script 2 mpol x1 3 mpol x2 x3 x4 mu(1) = meas([x1(1) x2]); % first measure on x1 and x2 mu(2) = meas([x1(2) x3]); % second measure on x1 and x3 mu(3) = meas([x1(3) x4]); % third measure on x1 and x4 f = mom(x1(1)*x2)+mom(x1(2)*x3)+mom(x1(3)*x4); % objective function m1 = mom(mmon(x1(1),3)); % moments of first measure m2 = mom(mmon(x1(2),3)); % moments of second measure m3 = mom(mmon(x1(3),3)); % moments of third measure K = [x1(1)^2+x2^2<=1, x1(2)^2+x3^2<=2, x1(3)^2+x4^2<=3]; % supports Psparse = msdp(min(f),m1-m2==0,m2-m3==0,K,mass(mu)==1); [stat,obj] = msol(Psparse);

Table 1 :

 1 Lower bounds for SDP relaxations of problem[START_REF] Lasserre | A semidefinite programming approach to the generalized problem of moments[END_REF].

	1.0958

At SDP relaxation k = 9, GloptiPoly certifies global optimality and extracts the global minimizer. Table

Table 4 :

 4 Approximation, orders and computational times given by the epigraph approach for problem[START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF].

	x * 1	x * 2	f *	order k times (s)
	9 -0.3484 -0.2417 -2.527	3	5.8s
	12 -0.0272 -0.2887 -2.739	2	3.2s
	15 -0.0323 -0.5588 -3.115	2	4.9s

Table 17

 17

	], the GMP

Table 5 :

 5 Values of n for which BARON finds a solution far from the global maximum of problem[START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF], and the corresponding optimal values f * BAR .We revisit the Kowalik problem of Example 4.3.2. As reported in Table 4.4.3, BARON finds a good approximate solution in less than 2 seconds, whereas the GMP approaches certifies globally optimality of a solution which is slightly closer to the theoretical optimum in approx. 10 seconds.

	n	f *	f * BAR
	260 259 243.474
	280 279 252.753
	340 339 336.403
	420 419 414.606

Acknowledgments

We are grateful to Michel Devy, Jean-José Orteu, Tomáš Pajdla, Thierry Sentenac and Rekha Thomas for insightful discussions on applications of real algebraic geometry and SDP in computer vision, and to Josh Taylor for his feedback on the example of section 4.2.

* The first author acknowledges support by the French National Research Agency (ANR) through COSINUS program (project ID4CS ANR-09-COSI-005). The second author acknowledges support by Research Program MSM6840770038 of the Czech Ministry of Education and Project 103/10/0628 of the Grant Agency of the Czech Republic.

A comparison of our approach with other global optimization techniques (e.g., reported in Hans Mittelmann's or Arnold Neumaier's webpages) is out of the scope of this paper. We believe however that such a comparison would be fair only if no expert tuning is required for alternative algorithms. Indeed, when using GloptiPoly the only assumption we make is that we know a ball containing the global optimizer. Besides this, our results are fully reproducible (Matlab files reproducing our examples are available upon request) and the SDP relaxations are solved with (black box) general-purpose semidefinite programming solvers.

Appendix on determinacy of measures on compact sets

Let K ⊂ R n be a compact set and let C(K) be the Banach space of continuous functions on K, equipped with the sup-norm. By Stone-Weierstrass, the polynomials are dense in C(K). So let µ and ν be two finite Borel measures on K and assume that µ and ν have all same moment y = (y α ), α ∈ N n , i.e.,

Let f ∈ C(K) be fixed arbitrary. As the polynomials are dense in C(K) then K f dµ = K f dν. And as f was arbitrary one concludes that this holds for every f ∈ C(K).

But this clearly implies that µ = ν. Hence every finite Borel measure on K is moment determinate.

7 Appendix on GloptiPoly scripts


Eric Serris

Omar Al Haj

Jean Kittel

Véronique Peres

Francois Grosjean

Francois Ropital

Michel Cournil

Acoustic Emission Analysis Coupled with Thermogravimetric Experiments Dedicated to High Temperature Corrosion Studies on Metallic Alloys

High temperature corrosion of metallic alloys (like iron, nickel, zirconium alloys) can damage equipment of many industrial fields (refinery, petrochemical, nuclear …). Acoustic emission (AE) is an interesting method owing to its sensitivity and its non-destructive aspect to quantify the level of damage in use of these alloys under various environmental conditions. High temperature corrosive phenomena create stresses in the materials; the relaxation by cracks of these stresses can be recorded and analyzed using the AE system. The goal of our study is to establish an acoustic signals database which assigns the acoustic signals to the specific corrosion phenomena. For this purpose, thermogravimetric analysis (TGA) is coupled with acoustic emission (AE) devices.

The oxidation of a zirconium alloy, zircaloy-4, is first studied using thermogravimetric experiment coupled to acoustic emission analysis at 900°C. An inward zirconium oxide scale, preliminary dense, then porous, grow during the isothermal isobaric step. The kinetic rate increases significantly after a kinetic transition (breakaway). This acceleration occurs with an increase of acoustic emission activity. Most of the acoustic emission bursts are recorded after the kinetic transition. Acoustic emission signals are also observed during the cooling of the sample. AE numerical treatments (using wavelet transform) completed by SEM microscopy characterizations allows us to distinguish the different populations of cracks.

Metal dusting represents also a severe form of corrosive degradation of metal alloy. Iron metal dusting corrosion is studied by AE coupled with TGA at 650°C under C 4 H 10 + H 2 + He atmosphere. Acoustic emission signals are detected after a significant increase of the sample mass.

Introduction

Over the last few decades several authors have been studying high temperature corrosion behavior of metals and alloys, steels sulfidation [1], metal dusting inhibition [START_REF] Ferrer | Nace Corrosion Conference[END_REF], and alloys oxidation [START_REF] Tran | [END_REF] using the acoustic emission devices. Since 1977 other authors have coupled acoustic emission with thermogravimetric analysis (TGA) in order to improve the knowledge of different high temperature corrosion phenomena [START_REF] Hochman | Proc. of the symp. On Properties of High Temperatures Alloys with Emphasis on Environnemental Effects[END_REF][START_REF] Bennett | [END_REF][6][7][8]. The sample mass variation and the AE signals were simultaneously recorded over these experiments. In this study, we use an innovative device to perform such experiments that is based on TGA analysis coupled with in situ acoustic emission. The technique is applied to study mass variation and AE signals during the oxidation at high temperature of a zirconium alloy, Zircaloy-4 and also during metal dusting of pure iron.

Experimental

The experiments are performed on Zircaloy-4 platelet specimens (4.8 mm x 4.6 mm x 0.5 mm) and iron platelet (4.4 mm x 4.6 mm x 1 mm). The chemical compositions of these materials are given in Table 1 and2. Samples are polished and cleaned with acetone and ethanol before the oxidation tests. Thermogravimetric analyses are carried out on a symmetric thermobalance (SETARAM TAG 24) with Pt-Rh 6%/ Pt-Rh 30% thermocouples, in order to measure the specimen's mass change during the oxidation tests with a precision of ± 0.001 mg. For Zy-4 oxidation test the temperature is fixed at 900°C ± 0.1°C (this temperature is in the field of accidental conditions in the nuclear power plants); the heating rate is 15°C/min in pure helium. The isothermal dwell time is fixed to 5 hours. Once the desired temperature is reached (T = 900°C), helium is switched to a mixture of (75% He + 21% O 2 + 4% N 2 ) for the first series of oxidation tests. Another oxidant gas mixture (80% He + 20% O 2 ) is used for the second series of oxidation tests. In both series the oxidant gas is introduced by mass flow meters with a total gas flow rate of 50 ml/min. The cooling rate is 15°C/min under the same process gas mixture.

For iron metal dusting tests the temperature is fixed at 650°C ± 0.1°C ; the heating rate is 15°C/min in pure helium. The isothermal dwell time is fixed to 24 hours. Once the desired temperature is reached, helium is switched to a mixture of (90% He + 5 % iC 4 H 10 + 5 % H 2 ). The reactive gases are introduced by mass flow meters with a total gas flow rate of 50 ml/min. The cooling rate is 15°C/min under helium.

AE piezoelectric sensors are linked to the waveguide via a metallic support; sensors and metallic support are placed inside the cold part of the thermobalance where the temperature does not exceed 150°C. The sensors are linked to an acquisition chain controlled by the AEwin™ software and data are analyzed using Noesis™ software provided by the Physical Acoustics Corporation Company. The characteristics of the acquisition chain are given in Table 3. The threshold is very low fixed to 18 dB AE . Discontinuous acoustic emission analysis (AE burst) is used during this study. At ambient temperature, the normalized Hsu-Nielsen test is carried out to verify the AE system.

Blank tests at 900°C under air or oxygen without any specimen are carried out to validate that the waveguide did not significantly react with the gas mixture. During these tests, the stability of the mass signal confirm the chemical inertness of the waveguide.

Results

Blank tests allow us to distinguish the acoustic emission signals which result from the instrumental noise (IN). They are characterized by a very short duration and a low number of counts, 95% of these bursts are characterized by 1 count and a duration of 1 µs. They are also characterized by a high average frequency in the range of 200 kHz to 1000 kHz including the resonance frequency of the sensors (300 kHz). Burst's absolute energy is very low and doesn't exceed 0.1 aJ/burst. These instrumental noise AE bursts are deleted from the acoustic emission analysis for the rest of the study.

Zircaloy-4 corrosion

Oxidation tests under air

Figure 1 shows the bursts amplitude recorded during the oxidation tests in parallel with the kinetic rate variation as function of time. According to the kinetic rate curves, we note that AE bursts have been recorded just after the kinetic transition (breakaway) occurring 2 400 s (40 minutes) after the introduction of the oxidant gas mixture [9][10]. Each time an important AE activity appears just after the breakaway. These bursts are called posttransition bursts. Post-transition bursts recorded during the temperature dwell time are characterized by mean amplitude in the range of 18 to 40 dB AE . AE bursts possess a low average frequency varying between 1 kHz to 200 kHz. Their absolute energy average is about 10 aJ/burst. AE signals are also recorded during the cooling of the sample. AE bursts recorded during the cooling step are more energetic (100 aJ/burst) and characterized by long duration (1000 µs/burst), and high counts number/burst (300 counts/burst as an average). SEM cross section of oxidized sample (Figure 2) obtained with scanning electron microscopy (JEOL 6500 F) indicates that cracks are located inside the inward zirconia layer. Cracks are visible in the external dense zirconia layer (type1), well distributed thin and convoluted cracks are observed parallel to the metal oxide interface (type 2) and big open cracks are periodically observed perpendicular to this interface totally crossing the zirconia layer (type 3). The core of the sample remains partially oxidized forming α-ZrO solid solution of oxygen in zirconium according to the Zirconium-Oxygen binary diagram [START_REF] Abriata | The O-Zr (Oxygen-Zirconium) system[END_REF]. Theses cracks can be associated with the AE signals recorded after the kinetic transition. We can attribute the AE bursts to these post-transition stage cracks. Even the AE threshold is low (18 dB AE ), the type 2 convoluted cracks parallel to the metal/oxide interface probably do not generate AE signals. The number of type 2 cracks surpasses the amount of AE bursts which have been recorded during the oxidation test. These cracks seem not to be emissive events. This hypothesis needs some more investigations to be validated.

Oxidation tests under oxygen

The kinetic transition doesn't appear during the oxygen test without nitrogen (80% He + 20% O 2 ), the kinetic rate decreases or remains constant throughout the experiment (Figure 3). In order to confirm the absence of the kinetic transition under oxygen at 900°C, the dwell time was extended from 5 hours to 10 hours (Figure 3). Results obtained during the extended test (10 hours dwell time) confirm the absence of kinetic transition during the oxidation under oxygen. The kinetic oxidation under oxygen is defined by a sub-parabolic law. The oxidation process is governed by the oxygen vacancy diffusion through a dense zirconia layer. No kinetic transition and no AE signals are observed during the dwell times. AE bursts recorded during short and extended tests under oxygen appear only during the cooling step. The bursts parameters of these tests are similar (amplitude, counts number, duration, average frequency …). The AE bursts recorded during the cooling step are characterized by a high absolute energy (200 aJ/burst as average). Their counts' number is in the order of magnitude of hundreds of counts per burst, and their amplitude varying between 20 dB AE and 60 dB AE .

SEM cross section of oxidized samples under oxygen during 5 hours at 900°C (Figure 4) shows a very dense external zirconia layer. Cracks are only located in the α-Zr(O) scale, which is in white contrast in the metal phase close to the metal/oxide interface. The core of the sample is α-Zr which results from the transformation phase (β-Zr α-Zr) occurring during the cooling step for a temperature lower than 863°C. To study in detail the cooling AE signals, we applied a continuous wavelet analysis of their waveforms. AE bursts recorded during the cooling under air possess a wavelet different from that of AE signals recorded during the cooling under oxygen (Figure 5). AE burst waveform for air test is mainly punctual with one spots line localized between 280 kHz to 420 kHz (Figure 5.a). AE burst waveform for oxygen test is more continuous with two important spots lines; the first one is centred between 120 kHz to 180 kHz, the second one is located between 300 kHz to 450 kHz.

-a--b- For Zircaloy-4 oxidized samples under oxygen at 900°C, differences in thermal expansion coefficients of α-Zr, α-Zr(O) layer and ZrO2 dense scale during the cooling at temperature close to 400°C must be taken into account. Important compressive stresses can created cracks in α-Zr(O) layer (figure 4) which is sandwiched between the metal and the oxide. Considering the micrographs of oxidized samples under oxygen, the AE bursts observed during the last part of the cooling may be generated by the cracks observed in the α-Zr(O) layer.

Metal dusting

The sample mass gain of metal dusting tests on pure iron is shown as function of time in figure 6. The amplitude of acoustic bursts is also plotted in this figure. In the first part of the experiment (up to 40 000 s) the sample mass gain is slowly growing up to 1 mg. Then the sample mass gain accelerates and the curve becomes linear, the total mass gain is nearly 8 mg. Almost all of the mass gain comes from the carbon deposit at the sample surface. At the beginning of this linear part, the acoustic emission occurs until the end of the test. The metal dusting process can be described with several steps [12]. The first one is carbon dissolution inside the iron matrix. When the activity of carbon inside the iron reaches the activity of formation of cementite (Fe 3 C), this phase can form according to this chemical reaction: 3 Fe+C = Fe 3 C . When the surface is covered by cementite, a large amount of graphite and coke can deposit on the sample surface. Then the metastable cementite disintegrates by giving iron free particle and pits inside the iron matrix. We can consider that the first step of the carbon dissolution is the slow part of mass gain curve and when the process of carbon and coke deposit (with cementite formation and disintegration) occurs, this corresponds to the linear part of the curve. SEM cross section of the iron samples after 24 hours of metal dusting (Figure 7) shows the small carbons pits at iron surface. The darker zone of the sample surface is carbon enrichment inside the iron matrix. This hypothesis is confirmed by EDX plots throughout the surface. To study in detail the AE signals, we apply a continuous wavelet analysis of their waveforms. We found that there is only one kind of wavelet for all bursts (figure 8). The acoustic emission begins with the acceleration of sample mass gain (linear part of the curve after 50000 s of experiment). We consider that the most probable step that may lead to a significant energetic release is the decomposition of cementite and more precisely the incorporation of carbon inside the iron matrix. This non reversible step may lead to the acoustic emission recorded in our study.

Conclusions

Thermogravimetric experiments coupled with acoustic emission analysis are an interesting way to improve knowledge on the corrosion of metallic materials at high temperature. AE technique allows us to study in details the oxidation behaviour of zircaloy-4 at high temperature. The kinetic transition is detected under air tests at 900°C by a change in the rate of mass gain during the isothermal dwell time. This breakaway is also immediately detected by the AE activity. AE analysis is complementary of post-mortem oxidized samples characterizations. It allows us to distinguish the cracks which occur during the zircaloy-4 oxidation from the cracks which arise during the cooling of the samples. During the oxidation, the first cracks which appear after the breakaway are located in the external ZrO 2 layer perpendicular to the metal oxide interface. The AE signals correspond to these cracks. The numerous small convoluted thin pores observed deeper in the zirconia scale are not detected by the AE technique. Cracks due to cooling of oxidized samples under oxygen at 900°C are located in the α-Zr(O) phase. They possess a typical AE signature. From these studies we can conclude that mechanisms as diffusion of atoms (oxygen vacancies in case of zirconium inward oxidation in pure oxygen at 900°C) are not emissive. Irreversible mechanisms, as cracks initiation and propagation, generate AE signals.

We also successfully use this innovative device for petrochemical applications for which metal dusting represents a severe form of corrosion. Metal dusting of iron samples is studied by AE coupled with TGA at 650°C under isobutane and hydrogen. Acoustic emission signals are detected after a significant increase of the sample mass corresponding to carbon penetration in iron.

Fig. 1 .

 1 Fig. 1. Rate of mass gain and burst amplitude as a function of time during Zircaloy-4 oxidation tests under 75% He + 21% O2 + 4% N2

Fig. 2 .

 2 Fig. 2. SEM cross section of Zircaloy-4 oxidized under air at 900°C

Fig. 3 .

 3 Fig.3. Rate of mass gain as a function of time and bursts amplitude variation during Zircaloy-4 oxidation tests under oxygen (▲) [5 hours] -( ♦ ) [10 hours]

Fig. 4 .

 4 Fig. 4. SEM cross section of Zircaloy-4 oxidized 5 hours under oxygen at 900°C (cracks indicated by "1" indicators)

Fig. 5 .

 5 Fig. 5. Typical AE burst waveform continuous wavelets recorded during the cooling of oxidation tests

Fig. 6 .

 6 Fig. 6. Typical AE burst waveform continuous wavelets recorded during the cooling of oxidation tests

Fig. 7 .

 7 Fig. 7. SEM cross section of pure iron after 24 hours of metal dusting at 900°C

Fig. 8 .

 8 Fig. 8. Typical AE burst waveform continuous wavelets recorded during the metal dusting

Table 1 :

 1 Chemical composition of Zircaloy-4 in weight% or ppm

Table 2 :

 2 Chemical composition of pure iron in ppm

Table 3 :

 3 Main characteristics of the AE

acquisition chain Sn (wt%) Fe (wt%) O (wt%) Cr (wt%) C (wt ppm) Nb (wt ppm) H (wt ppm) Zr 1.32 - 1.35 0.21 0.123 -0.129 0.11 125 -140 < 40 < 3 Bal . Fe C Cr Si Al Ti Mo +99,8% 2 ppm 0,94 ppm 0,18 ppm 0,19 ppm 0,05 ppm 0,03 ppm Instrumentation Sensors Threshold (dB AE ) System filter (KHz) Model of the amplifier Sampling rate PDT -HDT -HLT Characteristics PICO 30 18 10 -1200 2/4/6 gain : 60 dB AE

	0.25 µs	100 -200
	(4MHz)	-400 (µs)

Acknowledgment

This work is a part of the French FUI program: IREINE (Innovation for REliability of INdustrial Equipments) dedicated to the development of devices and monitoring services to follow the corrosion of industrial process equipment. This program is founded by the French Rhone Alpes Region.