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

Roxana Hess
email: rhess@laas.fr

Monique Laurent
email: m.laurent@cwi.nl

Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization

Keywords: box-constrained global optimization, polynomial optimization, Jackson kernel, semidefinite programming, generalized eigenvalue problem, sum-of-squares polynomial AMS classification: 90C60, 90C56, 90C26

We consider the problem of minimizing a given n-variate polynomial f over the hypercube [-1, 1] n . An idea introduced by Lasserre, is to find a probability distribution on [-1, 1] n with polynomial density function h (of given degree r) that minimizes the expectation [-1,1] n f (x)h(x)dµ(x), where dµ(x) is a fixed, finite Borel measure supported on [-1, 1] n . It is known that, for the Lebesgue measure dµ(x) = dx, one may show an error bound O(1/ √ r) if h is a sum-of-squares density, and an O(1/r) error bound if h is the density of a beta distribution. In this paper, we show an error bound of

dx (the well-known measure in the study of orthogonal polynomials), and h has a Schmüdgen-type representation with respect to [-1, 1] n , which is a more general condition than a sum of squares. The convergence rate analysis relies on the theory of polynomial kernels, and in particular on Jackson kernels. We also show that the resulting upper bounds may be computed as generalized eigenvalue problems, as is also the case for sum-of-squares densities.

Introduction 1.Background results

We consider the problem of minimizing a given n-variate polynomial f ∈ R[x] over the compact set K = [-1, 1] n , i.e., computing the parameter

f min = min x∈K f (x). (1.1)
This is a hard optimization problem which contains, e.g., the well known NP-hard maximum stable set and maximum cut problems in graphs (see, e.g., [START_REF] Park | Rank of Handelman hierarchy for Max-Cut[END_REF][START_REF] Park | Handelman rank of zero-diagonal quadratic programs over a hypercube and its applications[END_REF]). It falls within box-constrained (aka bound-constrained) optimization which has been widely studied in the literature. In particular iterative methods for boundconstrained optimization are described in the books [START_REF] Bertsekas | Constrained Optimization and Lagrange Multiplier Methods[END_REF][START_REF] Fletcher | Practical Methods of Optimization[END_REF][START_REF] Gill | Practical Optimization[END_REF], including projected gradient and active set methods. The latest algorithmic developments for box-constrained global optimization are surveyed in the recent thesis [START_REF] Pál | Global optimization algorithms for bound constrained problems[END_REF]; see also [START_REF] Hager | A new active set algorithm for box constrained optimization[END_REF] and the references therein for recent work on active set methods, and a list of applications. The box-constrained optimization problem is even of practical interest in the (polynomially solvable) case where f is a convex quadratic problem, and dedicated active set methods have been developed for this case; see [START_REF] Hungerländer | A feasible active set method for strictly convex quadratic problems with simple bounds[END_REF].

In this paper we will focus on the question of finding a sequence of upper bounds converging to the global minimum and allowing a known estimate on the rate of convergence. It should be emphasized that it is in general a difficult challenge in non-convex optimization to obtain such results. Following Lasserre [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF][START_REF] Lasserre | A new look at nonnegativity on closed sets and polynomial optimization[END_REF], our approach will be based on reformulating problem (1.1) as an optimization problem over measures and then restricting to subclasses of measures that we are able to analyze. Sequences of upper bounds have been recently proposed and analyzed in [START_REF] De Klerk | Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization[END_REF][START_REF] De Klerk | Bound-constrained polynomial optimization using only elementary calculations[END_REF], in the present paper we will propose new bounds for which we can prove a sharper rate of convergence. We now introduce our approach.

As observed by Lasserre [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF], problem (1.1) can be reformulated as

f min = min µ∈M(K) K f (x)dµ(x),
where M(K) denotes the set of probability measures supported on K. Hence an upper bound on f min may be obtained by considering a fixed probability measure µ on K. In particular, the optimal value f min is obtained when selecting for µ the Dirac measure at a global minimizer x * of f in K.

Lasserre [START_REF] Lasserre | A new look at nonnegativity on closed sets and polynomial optimization[END_REF] proposed the following strategy to build a hierarchy of upper bounds converging to f min . The idea is to do successive approximations of the Dirac measure at x * by using sum-of-squares (SOS) density functions of growing degrees. More precisely, Lasserre [START_REF] Lasserre | A new look at nonnegativity on closed sets and polynomial optimization[END_REF] considered a set of Borel measures µ r obtained by selecting a fixed, finite Borel measure µ on K (like, e.g., the Lebesgue measure) together with a polynomial density function that is a sum-of-squares (SOS) polynomial of given degree r.

When selecting for µ the Lebesque measure on K this leads to the following hierarchy of upper bounds on f min , indexed by r ∈ N:

f (r) K := inf h∈Σ[x]r K h(x)f (x)dx s.t. K h(x)dx = 1, (1.2)
where Σ[x] r denotes the set of sum-of-squares polynomials of degree at most r.

The convergence to f min of the bounds f (r) K is an immediate consequence of the following theorem, which holds for general compact sets K and continuous functions f . Theorem 1.1 [10, cf. Theorem 3.2] Let K ⊆ R n be compact, let µ be an arbitrary finite Borel measure supported by K, and let f be a continuous function on R n . Then, f is nonnegative on K if and only if

K f g 2 dµ ≥ 0 ∀g ∈ R[x].
Therefore, the minimum of f over K can be expressed as

f min = inf h∈Σ[x] K f hdµ s.t. K hdµ = 1.
(1.3)

In the recent work [START_REF] De Klerk | Bound-constrained polynomial optimization using only elementary calculations[END_REF], it is shown that for a compact set K ⊆ [0, 1] n one may obtain a similar result using density functions arising from (products of univariate) beta distributions. In particular, the following theorem is implicit in [START_REF] De Klerk | Bound-constrained polynomial optimization using only elementary calculations[END_REF].

Theorem 1.2 [3] Let K ⊆ [0, 1
] n be a compact set, let µ be an arbitrary finite Borel measure supported by K, and let f be a continuous function on R n . Then, f is nonnegative on K if and only if

K f hdµ ≥ 0 for all h of the form h(x) = n i=1 x βi i (1 -x i ) ηi K n i=1 x βi i (1 -x i ) ηi , (1.4)
where the β i s and η i s are nonnegative integers. Therefore, the minimum of f over K can be expressed as

f min = inf h K f hdµ s.t. K hdµ = 1, (1.5)
where the infimum is taken over all beta-densities h of the form (1.4).

For the box K = [0, 1] n and selecting for µ the Lebesgue measure, we obtain a hierarchy of upper bounds f H r converging to f min , where f H r is the optimum value of the program (1.5) when the infimum is taken over all beta-densities h of the form (1.4) with degree r.

The rate of convergence of the upper bounds f (r) K and f H r has been investigated recently in [START_REF] De Klerk | Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization[END_REF] and [START_REF] De Klerk | Bound-constrained polynomial optimization using only elementary calculations[END_REF], respectively. It is shown in [START_REF] De Klerk | Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization[END_REF]

that f (r) K -f min = O(1/ √ r)
for a large class of compact sets K (including all convex bodies and thus the box [0, 1] n or [-1, 1] n ) and the stronger rate

f H r -f min = O(1/r) is shown in [3] for the box K = [0, 1] n . While the parameters f (r)
K can be computed using semidefinite optimization (in fact, a generalized eigenvalue computation problem, see [START_REF] Lasserre | A new look at nonnegativity on closed sets and polynomial optimization[END_REF]), an advantage of the parameters f H r is that their computation involves only elementary operations (see [START_REF] De Klerk | Bound-constrained polynomial optimization using only elementary calculations[END_REF]).

Another possibility to get a hierarchy of upper bounds is grid search, where one takes the best function evaluation at all rational points in K = [0, 1] n with given denominator r. It has been shown in [START_REF] De Klerk | Bound-constrained polynomial optimization using only elementary calculations[END_REF] that these bounds have a rate of convergence in O(1/r 2 ). However, the computation of the order r bound needs an exponential number r n of function evaluations.

New contribution

In the present work we continue this line of research. For the box K = [-1, 1] n , our objective is to build a new hierarchy of measure-based upper bounds, for which we will be able to show a sharper rate of convergence in O(1/r 2 ). We obtain these upper bounds by considering a specific Borel measure µ (specified below in (1.7)) and polynomial density functions with a so-called Schmüdgen-type SOS representation (as in (1.6) below).

We first recall the relevant result of Schmüdgen [START_REF] Schmüdgen | The K-moment problem for compact semi-algebraic sets[END_REF], which gives SOS representations for positive polynomials on a basic closed semi-algebraic set (see also, e.g., [START_REF] Prestel | Positive Polynomials -From Hilbert's 17th Problem to Real Algebra[END_REF], [START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF]Theorem 3.16], [START_REF] Marshall | Positive Polynomials and Sums of Squares[END_REF]).

Theorem 1.3 (Schmüdgen [START_REF] Schmüdgen | The K-moment problem for compact semi-algebraic sets[END_REF])

Consider the set K = {x ∈ R n | g 1 (x) ≥ 0, . . . , g m (x) ≥ 0} where g 1 , . . . , g m ∈ R[x],
and assume that K is compact. If p ∈ R[x] is positive on K, then p can be written as p = I⊆[m] σ I i∈I g i , where σ I (I ⊆ [m]) are sum-of-squares polynomials.

For the box K = [-1, 1] n , described by the polynomial inequalities 1-x 2 1 ≥ 0, . . . , 1-x 2 n ≥ 0, we consider polynomial densities that allow a Schmüdgen-type representation of bounded degree r:

h(x) = I⊆[n] σ I (x) i∈I (1 -x 2 i ), (1.6)
where the polynomials σ I are sum-of-squares polynomials with degree at most r -2|I| (to ensure that the degree of h is at most r). We will also fix the following Borel measure µ on [-1, 1] n (which, as will be recalled below, is associated to some orthogonal polynomials):

dµ(x) = n i=1 π 1 -x 2 i -1 dx. (1.7)
This leads to the following new hierarchy of upper bounds f (r) for f min .

Definition 1.4 Let µ be the Borel measure from (1.7). For r ∈ N consider the parameters:

f (r) := inf h [-1,1] n f hdµ s.t. [-1,1] n hdµ = 1, (1.8)
where the infimum is taken over the polynomial densities h that allow a Schmüdgen-type representation (1.6), where each σ I is a sum-of-squares polynomial with degree at most r -2|I|.

The convergence of the parameters f (r) to f min follows as a direct application of Theorem 1.1. A main result in this paper is to show that the bounds f (r) have a rate of convergence in O(1/r 2 ). Moreover we will show that the parameter f (r) can be computed through generalized eigenvalue computations.

Theorem 1.5 Let f ∈ R[x] be a polynomial and f min be its minimum value over the box [-1, 1] n . For any r large enough, the parameters f (r) defined in (1.8) satisfy:

f (r) -f min = O 1 r 2 .
As already observed above this result compares favorably with the estimate: [START_REF] De Klerk | Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization[END_REF] for the bounds f (r) K based on using SOS densities. (Note however that the latter convergence rate holds for a larger class of sets K that includes all convex bodies; see [START_REF] De Klerk | Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization[END_REF] for details.) The new result also improves the estimate: f H r -f min = O 1 r , shown in [START_REF] De Klerk | Bound-constrained polynomial optimization using only elementary calculations[END_REF] for the bounds f H r obtained by using densities arising from beta distributions.

f (r) K -f min = O 1 √ r shown in
We now illustrate the optimal densities appearing in the new bounds f (r) on an example.

Example 1.6 Consider the minimization of the Motzkin polynomial

f (x 1 , x 2 ) = 64(x 4 1 x 2 2 + x 2 1 x 4 2 ) -48x 2 1 x 2 2 + 1
over the hypercube [-1, 1] 2 , which has four global minimizers at the points ± 1 2 , ± 1 2 , and f min = 0. Figure 1 shows the optimal density function h * computed when solving the problem (1.8) for degrees 12 and 16, respectively. Note that the optimal density h * shows four peaks at the four global minimizers of f in [-1, 1] 2 . The corresponding upper bounds from (1.8) are f (12) = 0.8098 and f (16) = 0.6949.

Strategy and outline of the paper

In order to show the convergence rate in O(1/r 2 ) of Theorem 1.5 we need to exhibit a polynomial density function h r of degree at most r which admits a SOS representation of Schmüdgen-type and for which we are able to show that

[-1,1] n f hdµ -f min = O(1/r 2
). The idea is to find such a polynomial density which approximates well the Dirac delta function at a global minimizer x * of f over [-1, 1] n . For this we will use the well established Polynomial Kernel Method (KPM) and more specifically we will use the Jackson kernel, a well known tool in approximation theory to yield best (uniform) polynomial approximations of continuous functions.

The paper is organized as follows. Section 2 contains some background information about the polynomial kernel method needed for our analysis of the new bounds f (r) . Specifically we introduce Chebyshev polynomials in Section 2.1 and Jackson kernels in Section 2.2, and then we use them in Section 2.3 to construct suitable polynomial densities h r giving good approximations of the Dirac delta function at a global minimizer of f in the box. We then carry out the analysis of the upper bounds on f min in Section 3.1 for the univariate case and in Section 3.2 for the general multivariate case, thus proving the result of Theorem 1.5. In Section Notation Throughout, Σ[x] denotes the set of all sum-of-squares (SOS) polynomials (i.e., all polynomials h of the form h = k i=1 p i (x) 2 for some polynomials p 1 , . . . , p k and k ∈ N) and Σ[x] r denotes the set of SOS polynomials of degree at most r (of the form h = k i=1 p i (x) 2 for some polynomials p i of degree at most r/2). For α ∈ N n , Supp(α) = {i ∈ [n] : α i = 0} denotes the support of α and, for α, β ∈ N n , δ α,β ∈ {0, 1} is equal to 1 if and only if α = β.

Background on the polynomial kernel method

Our goal is to approximate the Dirac delta function at a given point x * ∈ R n as well as possible using polynomial density functions of bounded degrees. This is a classical question in approximation theory. In this section we will review how this may be done using the polynomial kernel method and, in particular, using Jackson kernels. This theory is usually developed using the Chebyshev polynomials, and we start by reviewing their properties. We will follow mainly the work [START_REF] Weisse | The kernel polynomial method[END_REF] for our exposition and we refer to the handbook [START_REF]Handbook of Mathematical Functions with formulas, graphs, and mathematical tables[END_REF] for more background information.

Chebyshev polynomials

We will use the univariate polynomials T k (x) and U k (x), respectively known as the Chebyshev polynomials of the first and second kind. They are defined as follows:

T k (x) = cos(k arccos(x)), U k (x) = sin((k + 1) arccos(x)) sin(arccos(x)) for x ∈ [-1, 1], k ∈ N, (2.1)
and they satisfy the following recurrence relationships:

T 0 (x) = 1, T -1 (x) = T 1 (x) = x, T k+1 (x) = 2xT k (x) -T k-1 (x), (2.2)
U 0 (x) = 1, U -1 (x) = 0, U k+1 (x) = 2xU k (x) -U k-1 (x). (2.3)
As a direct application one can verify that

T k (0) =    0 for k odd (-1) k 2 for k even , T k (1) = 1, U k (1) = k + 1, U k (-1) = (-1) k (k + 1) for k ∈ N. (2.4)
The Chebyshev polynomials have the extrema

max x∈[-1,1] |T k (x)| = 1 and max x∈[-1,1] |U k (x)| = k + 1,
attained at x = ±1 (see, e.g., [2, §22.14.4, 22.14.6]).

The Chebyshev polynomials are orthogonal for the following inner product on the space of integrable functions over [-1, 1]:

f, g = 1 -1 f (x)g(x) π √ 1 -x 2 dx, (2.5)
and their orthogonality relationships read:

T k , T m = 0 if k = m, T 0 , T 0 = 1, T k , T k = 1 2 if k ≥ 1. (2.6)
For any r ∈ N the Chebyshev polynomials T k (k ≤ r) form a basis of the space of univariate polynomials with degree at most r. One may write the Chebyshev polynomials in the standard monomial basis using the relations:

T k (x) = k i=0 t (k) i x i = k 2 k 2 m=0 (-1) m (k -m -1)! m!(k -2m)! (2x) k-2m , k > 0 U k-1 (x) = k-1 i=0 u (k) i x i = k-1 2 m=0 (-1) m (k -m -1)! m!(k -1 -2m)! (2x) k-1-2m , k > 1.
See, e.g. [START_REF]Handbook of Mathematical Functions with formulas, graphs, and mathematical tables[END_REF]Chap. 22]. From this, one may derive a bound on the largest coefficient in absolute value appearing in the above expansions of T k (x) and U k-1 (x). A proof for the following result will be given in the Appendix.

Lemma 2.1 For any fixed integer k > 1, one has:

max 0≤i≤k-1 |u (k) i | ≤ max 0≤i≤k |t (k) i | = 2 k-1-2ψ(k) k(k -ψ(k) -1)! ψ(k)!(k -2ψ(k))! (2.7)
where

ψ(k) = 0 for k ≤ 4 and ψ(k) = 1 8 4k -5 - √ 8k 2 -7 for k ≥ 4.
Moreover, the right hand side of (2.7) increases monotonically with increasing k.

In the multivariate case we use the following notation. We let dµ(x) denote the Lebesgue measure on [-1, 1] n with the function

n i=1 π 1 -x 2 i -1
as density function:

dµ(x) = n i=1 π 1 -x 2 i -1 dx (2.8)
and we consider the following inner product for two integrable functions f, g on the box [-1, 1] n :

f, g = [-1,1] n f (x)g(x)dµ(x)
(which coincides with (2.5) in the univariate case n = 1). For α ∈ N n , we define the multivariate Chebyshev polynomial

T α (x) = n i=1 T αi (x i ) for x ∈ R n .
The multivariate Chebyshev polynomials satisfy the following orthogonality relationships:

T α , T β = 1 2 |Supp(α)| δ α,β (2.9)
and, for any r ∈ N, the set of Chebyshev polynomials {T α (x) : |α| ≤ r} is a basis of the space of n-variate polynomials of degree at most r.

Jackson kernels

A classical problem in approximation theory is to find a best (uniform) approximation of a given continuous function f : [-1, 1] → R by a polynomial of given maximum degree r. Following [START_REF] Weisse | The kernel polynomial method[END_REF], a possible approach is to take the convolution f (r) KPM of f with a kernel function of the form

K r (x, y) = 1 π √ 1 -x 2 π 1 -y 2 g r 0 T 0 (x)T 0 (y) + 2 r k=1 g r k T k (x)T k (y) ,
where r ∈ N and the coefficients g r k are selected so that the following properties hold:

(1) The kernel is positive: K r (x, y) > 0 for all x, y ∈ [-1, 1].

(2) The kernel is normalized: g r 0 = 1.

(3) The second coefficients g r 1 tend to 1 as r → ∞.

The function f (r)

KPM is then defined by

f (r) KPM (x) = 1 -1 π 1 -y 2 K r (x, y)f (y)dy. (2.10)
As the first coefficient is g r 0 = 1, the kernel is normalized:

1 -1 K r (x, y)dy = T 0 (x)/π √ 1 -x 2
, and we have:

1 -1 f (r) KPM (x)dx = 1 -1 f (x)dx.
The positivity of the kernel K r implies that the integral operator f → f In what follows we select the following parameters g r k for k = 1, . . . , r, which define the so-called Jackson kernel, again denoted by K r (x, y):

g r k = 1 r+2 ((r + 2 -k) cos(kθ r ) + sin(kθr) sin θr cos θ r ) = 1 r+2 ((r + 2 -k)T k (cos θ r ) + U k-1 (cos θ r ) cos θ r ), (2.11)
where we set θ r := π r + 2 .

This choice of the parameters g r k is the one minimizing the quantity [-1,1] 2 K r (x, y)(x -y) 2 dxdy, which ensures that the corresponding Jackson kernel is maximally peaked at x = y (see [20,

§II.C.3]).

One may show that the Jackson kernel K r (x, y) is indeed positive on [-1, 1] 2 ; see [20, §II.C.2]. Moreover g r 0 = 1 and, for k = 1, we have g r 1 = cos(θ r ) = cos(π/(r + 2)) → 1 if r → ∞ as required. This is in fact true for all k, as will follow from Lemma 2.2 below. Note that one has

|g r k | ≤ 1 for all k, since |T k (cos θ r )| ≤ 1 and |U k-1 (cos θ r )| ≤ k.
For later use, we now give an estimate on the Jackson coefficients g r k , showing that 1 -g r k is in the order O(1/r 2 ).

Lemma 2.2 Let d ≥ 1 and r ≥ d be given integers, and set θ r = π r+2 . There exists a constant C d (depending only on d) such that the following inequalities hold:

|1 -g r k | ≤ C d (1 -cos θ r ) ≤ C d π 2 2(r + 2) 2 for all 0 ≤ k ≤ d.
For the constant C d we may take:

C d = d 2 (1 + 2c d ), where c d = 2 d-1-2ψ(d) d(d -ψ(d) -1)! ψ(d)!(d -2ψ(d))! and ψ(d) =    0 for d ≤ 4 1 8 4d -5 - √ 8d 2 -7 for d ≥ 4.
(2.12)

Proof. Define the polynomial

P k (x) = 1 - r + 2 -k r + 2 T k (x) - 1 r + 2 xU k-1 (x),
with degree k. Then, in view of relation (2.11), we have: 1 -g r k = P k (cos θ r ). Recall from relation (2.4) that T k (1) = 1 and U k-1 (1) = k for any k ∈ N. This implies that P k (1) = 0 and thus we can factor P k (x) as

P k (x) = (1 -x)Q k (x) for some polynomial Q k (x) with degree k -1. If we write P k (x) = k i=0 p i x i , then it follows that Q k (x) = k-1 i=0 q i x i ,
where the scalars q i are given by

q i = i j=0 p j for i = 0, 1, . . . , k -1.
(2.13)

It now suffices to observe that for any 0 ≤ i ≤ k and k ≤ d, the p i 's are bounded by a constant depending only on d, which will imply that the same holds for the scalars q i . For this, set

T k (x) = k i=0 t (k) i x i and U k-1 (x) = k-1 i=0 u (k) i x i .
Then the coefficients p i of P k (x) can be expressed as

p 0 = 1 - r + 2 -k r + 2 t (k) 0 , p i = r + 2 -k r + 2 t (k) i - u (k) i-1 r + 2 (1 ≤ i ≤ k).
-g r k = (1 -cos θ r )Q k (cos θ r ), where Q k (cos θ r ) = k-1 i=0 q i (cos θ r ) i , so that |Q k (cos θ r )| ≤ k-1 i=0 |q i | ≤ d 2 (1 + 2c d ). This implies |1 -g r k | ≤ (1 -cos θ r )C d , after setting C d = d 2 (1 + 2c d ).
Finally, combining with the fact that 1 -cos x ≤ x 2 2 for all x ∈ [0, π], we obtain the desired inequality from the lemma statement. 2

Jackson kernel approximation of the Dirac delta function

If one approximates the Dirac delta function δ x * at a given point x * ∈ [-1, 1] by taking its convolution with the Jackson kernel K r (x, y), then the result is the function:

δ (r) KPM (x -x * ) = 1 π √ 1 -x 2 1 + 2 r k=1 g r k T k (x)T k (x * ) .
See [20, eq. ( 72)]. As mentioned in [20, eq. ( 75)-( 76)], the function δ

(r)
KPM is in fact a good approximation to the Gaussian density: (Recall that the Dirac delta measure may be defined as a limit of the Gaussian measure when σ ↓ 0.) This approximation is illustrated in Figure 2 for several values of r.

δ (r) KPM (x -x * ) ≈ 1 √ 2πσ 2 exp - (x -x * ) 2 2σ 2 with σ 2 ≈ π r + 1 2 1 -x * 2 + 3x * 2 -2 r + 1 . ( 2
By construction, the function δ (r) KPM (x -x * ) is nonnegative over [-1, 1] and we have the normalization:

1 -1 δ (r) KPM (x -x * )dx = 1 -1 δ x * (x)dx = 1.
Hence, it is a probability density function on [-1, 1] for the Lebesgue measure. It is convenient to consider the following univariate polynomial:

h r (x) = 1 + 2 r k=1 g r k T k (x)T k (x * ), (2.15) so that δ (r) KPM (x -x * ) = 1 π √ 1-x 2 h r (x).
The following facts follow directly, which we will use below for the convergence analysis of the new bounds f (r) . Lemma 2.3 For any r ∈ N the polynomial h r from (2.15) is nonnegative over [-1, 1] and

1 -1 h r (x) dx π √ 1-x 2 = 1.
In other words, h r is a probability density function for the measure π

√ 1 -x 2 -1 dx on [-1, 1].

Convergence analysis

In this section we analyze the convergence rate of the new bounds f (r) and we show the result from Theorem 1.5. We will first consider the univariate case in Section 3.1 (see Theorem 3.3) and then the general multivariate case in Section 3.2 (see Theorem 3.6). As we will see, the polynomial h r arising from the Jackson kernel approximation of the Dirac delta function, introduced above in relation (2.15), will play a key role in the convergence analysis.

The univariate case

We consider a univariate polynomial f and let x * be a global minimizer of f in [-1, 1]. As observed in Lemma 2.3 the polynomial h r from (2.15) is a density function for the measure dx π √ 1-x 2 . The key observation now is that the polynomial h r admits a Schmüdgen-type representation, of the form σ(x)+σ 1 (x)(1-x 2 ) with σ 0 , σ 1 sums-of-squares polynomials, since it is non-negative over [-1, 1]. This fact will allow us to use the polynomial h r to get feasible solutions for the program defining the bound f (r) . It follows from the following classical result (see e.g. [11, Thm 3.23 (i)]), that characterizes univariate polynomials that are nonnegative on [-1, 1]. (Note that this is a strengthening of Schmüdgen's theorem (Theorem 1.3) in the univariate case.) Theorem 3.1 (Fekete, Markov-Lukàcz) Let p(x) be a univariate polynomial of degree m. Then p(x) is nonnegative on the interval [-1, 1] if and only if it has the following representation:

p(x) = σ 0 (x) + (1 -x 2 )σ 1 (x)
for some sum-of-squares polynomials σ 0 of degree 2 m/2 and σ 1 of degree 2 m/2 -2.

We start with the following technical lemma. Lemma 3.2 Let f be a polynomial of degree d written in the Chebyshev basis as f = d k=0 f k T k , let x * be a global minimizer of f in [-1, 1] and let h r be the polynomial from (2.15). For any integer r ≥ d we have:

1 -1 f (x)h r (x) dx π √ 1 -x 2 -f (x * ) ≤ C f (r + 2) 2 , where C f = ( d k=1 |f k |) C d π 2 2 and C d is the constant from Lemma 2.2. Proof. As f = d k=0 f k T k and h r = 1 + 2 r k=1 g r k T k (x * )
T k , we use the orthogonality relationships (2.6) to obtain:

1 -1 f (x)h r (x) dx π √ 1 -x 2 = d k=0 f k T i (x * )g r k . (3.1) Combining with f (x * ) = d k=0 f k T k (x * ) gives: 1 -1 f (x)h r (x) dx π √ 1 -x 2 -f (x * ) = d k=1 f k T k (x * )(g r k -1). (3.2)
Now we use the upper bound on g r k -1 from Lemma 2.2 and the bound |T k (x * )| ≤ 1 to conclude the proof. 2

We can now conclude the convergence analysis of the bounds f (r) in the univariate case.

f (r) -f min ≤ C f (r + 1) 2 ,
where

C f = ( d k=1 |f k |) C d π 2 2
and C d is the constant from Lemma 2.2.

Proof. Using the degree bounds in Theorem 3.1 for the sum-of-squares polynomials entering the decomposition of the polynomial h r , we can conclude that for r even, h r is feasible for the program defining the parameter f (r) and for r odd, h r is feasible for the program defining the parameter f (r+1) . Setting

C f = ( d k=1 |f k |) C d π 2 2
and using Lemma 3.2, this implies:

f (r) -f min ≤ C f (r+2) 2 for r even, and f (r) -f min ≤ C f (r+1) 2 for odd r.
The result of the theorem now follows. 2

The multivariate case

We consider now a multivariate polynomial f and we let

x * = (x * 1 , . . . , x * n ) ∈ [-1, 1] n denote a global minimizer of f on [-1, 1] n , i.e. f (x * ) = f min .
In order to obtain a feasible solution to the program defining the parameter f (r) we will consider products of the univariate polynomials h r from (2.15). Namely, given integers r 1 , . . . , r n ∈ N we define the n-tuple r = (r 1 , . . . , r n ) and the n-variate polynomial:

H r (x 1 , . . . , x n ) = n i=1 h ri (x i ). (3.3)
We group in the next lemma some properties of the polynomial H r .

Lemma 3.4

The polynomial H r satisfies the following properties:

(i) H r is non-negative on [-1, 1] n . (ii) [-1,1] n H r (x)dµ(x) = 1
, where dµ is the measure from (1.7).

(iii) H r has a Schmüdgen-type representation of the form:

H r (x) = I⊆[n] σ I (x) i∈I (1 -x 2 i ),
where each σ I is a sum-of-squares polynomial of degree at most 2 n i=1 r i /2 -2|I|.

Proof. (i) and (ii) follow directly from the corresponding properties of the univariate polynomials h ri , and (iii) follows using Theorem 3.1 applied to the polynomials h ri .

2

The next lemma is the analog of Lemma 3.2 for the multivariate case.

Lemma 3.5 Let f be a multivariate polynomial of degree d, written in the basis of multivariate Chebyshev polynomials as f = α∈N n :|α|≤d f α T α , and let x * be a global minimizer of f in [-1, 1] n . Consider r = (r 1 , . . . , r n ), where each r i is an integer satisfying r i ≥ d, and the polynomial H r from (3.3). We have:

[-1,1] n f (x)H r (x)dµ(x) -f (x * ) ≤ C f n i=1 1 (r i + 2) 2 ,
where

C f = ( α:|α|≤d |f α |) C d π 2 2
and C d is the constant from Lemma 2.2.

Proof. As f = α:|α|≤d f α T α and H r = n i=1 h (ri) (x i ) = n i=1 (1 + 2 ri ki=1 g ri ki T ki (x i ))
, we can use the orthogonality relationships (2.9) among the multivariate Chebyshev polynomials to derive:

[-1,1] n f (x)H r (x)dµ(x) = α:|α|≤d f α T α (x * ) n i=1 g ri αi .
Combining with f (x * ) = α:|α|≤d f α T α (x * ) this gives:

[-1,1] n f (x)H r (x)dµ(x) -f (x * ) = α:|α|≤d f α T α (x * )( n i=1
g ri αi -1).

Using the identity: We can now show our main result, which implies Theorem 1.5.

Theorem 3.6 Let f = α:|α|≤d f α T α be a n-variate polynomial of degree d. For any integer r ≥ n(d + 2), we have:

f (r) -f min ≤ C f n 3 (r + 1) 2 , where C f = ( α:|α|≤d |f α |) C d π 2 2
and C d is the constant from Lemma 2.2.

Proof. Write r -n = sn + n 0 , where s, n 0 ∈ N and 0 ≤ n 0 < n, and define the n-tuple r = (r 1 , . . . , r n ), setting r i = s + 1 for 1 ≤ i ≤ n 0 and r i = s for n 0 + 1 ≤ i ≤ n, so that r -n = r 1 + . . . + r n . Note that the condition r ≥ n(d + 2) implies s ≥ d and thus r i ≥ d for all i. Moreover, we have: 2 n i=1 r i /2 = 2n 0 (s + 1)/2 + 2(n -n 0 ) s/2 , which is equal to r -n + n 0 for even s and to r -n 0 for odd s and thus always at most r. Hence the polynomial H r from (3.3) has degree at most r. By Lemma 3.4 (ii),(iii), it follows that the polynomial H r is feasible for the program defining the parameter f (r) . By Lemma 3.5 this implies that

f (r) -f min ≤ [-1,1] n f (x)H r (x)dµ(x) -f (x * ) ≤ C f n i=1 1 (r i + 2) 2 . Finally, n i=1 1 (ri+2) 2 = n0 (s+3) 2 + n-n0 (s+2) 2 ≤ n (s+2) 2 = n 3 (r+n-n0) 2 ≤ n 3 (r+1) 2 , since n 0 ≤ n -1. 2
4 Computing the parameter f (r) as a generalized eigenvalue problem

As the parameter f (r) is defined in terms of sum-of-squares polynomials (cf. Definition 1.4), it can be computed by means of a semidefinite program. As we now observe, as the program (1.8) has only one affine constraint, f (r) can in fact be computed in a cheaper way as a generalized eigenvalue problem.

Using the inner product from (2.5), the parameter f (r) can be rewritten as

f (r) = min h∈R[x] f, h such that h, T 0 = 1, h(x) = I⊆[n] σ I (x) i∈I (1 -x 2 i ), σ I ∈ Σ[x], deg(σ I ) ≤ r -2|I| ∀I ⊆ [n]. (4.1)
For convenience we use below the following notation. For a set I ⊆ [n] and an integer r ∈ N we let Λ I r denote the set of sequences β ∈ N n with |β| ≤ r-2|I|

2

.

As is well known one can express the condition that σ I is a sum-of-squares polynomial, i.e., of the form k p k (x) 2 for some p k ∈ R[x], as a semidefinite program. More precisely, using the Chebyshev basis to express the polynomials p k , we obtain that σ I is a sum-of-squares polynomial if and only if there exists a matrix variable M I indexed by Λ I r , which is positive semidefinite and satisfies:

σ I = β,γ∈Λ I r M I β,γ T β T γ . (4.2)
For each I ⊆ [n], we introduce the following matrices A I and B I , which are also indexed by the set Λ I r and, for β, γ ∈ Λ I r , with entries:

A I β,γ = f, T β T γ i∈I (1 -x 2 i ) , B I β,γ = T 0 , T β T γ i∈I (1 -x 2 i ) . (4.3)
We will indicate in the Appendix how to compute the matrices A I and B I .

We can now reformulate the parameter f (r) as follows.

f (r) = min M I :I⊆[n] I⊆[n] Tr (A I M I ) such that M I 0 ∀I ⊆ [n], I⊆[n]
Tr (B

I M I ) = 1. (4.4)
Proof.

Using relation (4.2) we can express the polynomial variable h in (4.1) in terms of the matrix variables M I and obtain:

h = I⊆[n] β,γ∈Λ I r M I β,γ T β T γ i∈I (1 -x i ) 2 .
First this permits to reformulate the objective function f, h in terms of the matrix variables M I in the following way:

f, h = I β,γ M I β,γ f, T β T γ i∈I (1 -x 2 i ) = I β,γ M I β,γ A I β,γ = I Tr (A I M I ).
Second we can reformulate the constraint T 0 , h = 1 using:

T 0 , h = I β,γ M I β,γ T 0 , T β T γ i∈I (1 -x 2 i ) = I β,γ M I β,γ B I β,γ = I Tr (B I M I ).
From this follows that the program (4.1) is indeed equivalent to the program (4.4). 2

The program (4.4) is a semidefinite program with only one constraint. Hence, as we show next, it is equivalent to a generalized eigenvalue problem. Theorem 4.2 For I ⊆ [n] let A I and B I be the matrices from (4.3) and define the parameter:

λ (I) = max λ | A I -λB I 0 = min λ | A I x = λB I x
for some non-zero vector x .

One then has f

(r) = min I⊆[n] λ (I) .
Proof. The dual semidefinite program of the program (4.4) is given by:

sup λ | A I -λB I 0 ∀I ⊆ [n] . (4.5)
We first show that the primal problem (4.4) is strictly feasible. To see this it suffices to show that Tr (B I ) > 0, since then one may set M I equal to a suitable multiple of the identity matrix and thus one gets a strictly feasible solution to (4.4). Indeed, the matrix B I is positive semidefinite since, for any scalars g β , β,γ

g β g γ B I βγ = [-1,1] n ( β g β x β ) 2 i∈I (1 -x 2 i )dµ(x) ≥ 0.
Thus Tr (B I ) ≥ 0 and moreover Tr (B I ) > 0 since B I is nonzero.

Moreover, the dual problem (4.5) is also feasible, since λ = f min is a feasible solution. This follows from the fact that the polynomial f -f min is nonnegative over [-1, 1] n , which implies that the matrix A I -f min B I is positive semidefinite. Indeed, using the same argument as above for showing that B I 0, we have

β,γ g β g γ (A I -f min B I ) β,γ = [-1,1] n (f (x) -f min )g(x) 2 dµ(x) ≥ 0.
Since the primal problem is strictly feasible and the dual problem is feasible, there is no duality gap and the dual problem attains its supremum. The result follows.

Numerical examples

We examine the polynomial test functions which were also used in [START_REF] De Klerk | Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization[END_REF] and [START_REF] De Klerk | Bound-constrained polynomial optimization using only elementary calculations[END_REF], and are described in the appendix to this paper.

The numerical examples given here only serve to illustrate the observed convergence behavior of the sequence f (r) as compared to the theoretical convergence rate. In particular, the computational demands for computing f (r) for large r are such that it cannot compete in practice with the known iterative methods referenced in the introduction.

For the polynomial test functions we list (Table 1) the values of f (r) for even r up to r = 48, obtained by solving the generalized eigenvalue problem in Theorem 4.2 using the eig function of Matlab. Recall that for step r of the hierarchy the polynomial density function h is of Schmüdgen type and has degree r.

For the examples listed the computational time is negligible, and therefore not listed; recall that the computation of f (r) for even n requires the solution of 2 n generalised eigenvalue problems indexed by subsets I ⊂ [n], where the order of the matrices equals n+ r/2-|I| n ; cf. Theorem 4.2. We note that the observed rate of convergence seems in line with the O(1/r 2 ) error bound.

As a second numerical experiment, we compare (see Table 2) the upper bound f (r) to the upper bound f (r) K defined in (1.2). Recall that the bound f (r) K corresponds to using sum-of-squares density functions of degree at most r and the Lebesgue measure. As shown in [START_REF] De Klerk | Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization[END_REF], the computation of f (r) K may be done by solving a single generalized eigenvalue problem with matrices of order n+ r/2-|I| n . Thus the computation of f (r) K is significantly cheaper than that of f (r) . It is interesting to note that, in almost all cases, f (r) > f (r) K . Thus even though the measure dµ(x) and the Schmüdgen-type densities are useful in getting improved error bounds, they mostly do not lead to improved upper bounds for these examples. This also suggests that it might be possible to improve the error result f

f (r) K f (r) f (r) K f (r) f (r) K f (r) f (r) K f (r) 6
(r) K -f min = O(1/ √ r) in [4], at least for the case K = [-1, 1] n .
Finally, it is shown in [START_REF] De Klerk | Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization[END_REF] that one may obtain feasible points corresponding to bounds like f (r) through sampling from the probability distribution defined by the optimal density function. In particular, one may use the method of conditional distributions (see e.g., [12, Section 8.5.1]). For K = [0, 1] n , the procedure is described in detail in [4, Section 3].

we consider the quotient

|t (k+1) k+1-2m | |t (k) k-2m | = 2 k-2m (k + 1)(k -m)! m! (k -2m)! 2 k-1-2m k(k -m -1)! m! (k + 1 -2m)! = 2 • k + 1 k • k -m k + 1 -2m ,
which is equal to 2 if m = 0, and at least 1 if m > 0 since every factor is at least 1. Thus, for m = ψ(k), we obtain:

|t (k) k-2ψ(k) | ≤ |t (k+1) k+1-2ψ(k) |. (A.2) Consider the map φ : [4, ∞) → R, k → φ(k) = 1 8 4k -5 - √ 8k 2 -7 , so that ψ(k) = φ(k) . The map φ is monotone increasing, since its derivative φ (k) = 1 8 4 -16k 2 √ 8k 2 -7 = √ 8k 2 -7-2k 2 √ 8k 2 -7
is positive for all k ≥ 4. Hence, we have: ψ(k) ≤ ψ(k + 1). Then, in view of (A.1) (and the comment thereafter), we have |t T αi (x i )T βi (x i )T γi (x i )(1 -

x 2 i )dµ(x i ) • i ∈I 1 -1
T αi (x i )T βi (x i )T γi (x i )dµ(x i ).

Thus we can now assume that we are in the univariate case. Suppose we are given integers a, b, c ≥ 0 and the goal is to evaluate the integrals T a (x)T b (x)T c (x)(1 -x 2 )dµ(x).

We use the following identities for the (univariate) Chebyshev polynomials: Moreover, using the fact that 1 -x 2 = (1 -T 2 )/2, we get

T a T b = 1

Figure 1 :

 1 Figure 1: Graphs of h * on [-1, 1] 2 (deg(h * ) = 12, 16) for the Motzkin polynomial.

  (r) KPM is a positive linear operator, i.e., a linear operator that maps the set of nonnegative integrable functions on [-1, 1] into itself. Thus the general (Korovkin) convergence theory of positive linear operators applies and one may conclude the uniform convergence result lim r→∞ f -f (r) KP M ∞ = 0 for any > 0, where f -f (r) KP M ∞ = max -1+ ≤x≤1-|f (x)-f (r) KPM (x)|. (One needs to restrict to subintervals of [-1, 1] because of the denominator in the kernel K r .)

For all 0

 0 ≤ k ≤ d the coefficients of the Chebyshev polynomials T k , U k-1 can be bounded by an absolute constant depending only on d. Namely, by Lemma 2.1, |t (k) i |, |u (k) i | ≤ c d for all 0 ≤ i ≤ k and k ≤ d, where c d is as defined in (2.12). As k ≤ d ≤ r, we have r + 2 -k ≤ r + 2 and thus |p i | ≤ 1 + 2c d for all 0 ≤ i ≤ k ≤ d. Moreover, using (2.13), |q i | ≤ d(c d + 1) for all 0 ≤ i ≤ k -1. Putting things together we can now derive: 1

Figure 2 :

 2 Figure 2: The Jackson kernel approximation δ (r) KPM to the Dirac delta at x * = 0 for r = 8, 16, 32, 64. The corresponding scatterplots show the values of the Gaussian density function in (2.14) with x * = 0.

Theorem 3 . 3

 33 Let f = d k=0 f k T k be a polynomial of degree d. For any integer r ≥ d we have:

  k α k and the fact that |g r k α k | ≤ 1, we get: | n i=1 (g ri αi -1)| ≤ n j=1 |g rj αj -1|. Now use |T α (x * )| ≤ 1 and the bound from Lemma 2.2 for each |1 -g rj αj | to conclude the proof. 2

Lemma 4 . 1

 41 Let A I and B I be the matrices defined as in (4.3) for each I ⊆ [n]. Then the parameter f (r) can be reformulated using the following semidefinite program in the matrix variables M I (I ⊆ [n]):

( 1 -x 2 i ) = i∈I 1 - 1

 111 m+1) | if m ≤ ψ(k + 1), and thus|t (k+1) k+1-2ψ(k) | ≤ |t (k+1) k+1-2ψ(k+1) |. (A.3)Combining (A.2) and (A.3), we obtain the desired inequality: |t(k) k-2ψ(k) | ≤ |t (k+1) k+1-2ψ(k+1) |.2B. Useful identities for the Chebychev polynomialsRecall the notation dµ(x) to denote the Lebesgue measure with the function order to compute the matrices A I and B I we need to evaluate the following integrals:T α , T β T γ i∈I

1 - 1 T

 11 a (x)T b (x)T c (x)dµ(x) and 1 -1

2 (Using the orthogonality relation 1 - 1 T 1 - 1 T

 21111 T a+b + T |a-b| ), T a T b T c = 1 4 (T a+b+c + T |a+b-c| + T |a-b|+c + T ||a-b|-c| ), so that T a T b T c T 2 = 1 8 (T a+b+c+2 + T |a+b+c-2| + T |a+b-c|+2 + T ||a+b-c|-2| +T |a-b|+c+2 + T ||a-b|+c-2| + T ||a-b|-c|+2 + T |||a-b|-c|-2|). a dµ(x) = δ 0,a , we obtain that a T b T c dµ(x) = 1 4 (δ 0,a+b+c + δ 0,a+b-c + δ 0,|a-b|+c + δ 0,|a-b|-c ).

1 - 1 T 1 - 1 T 1 - 1 T 1 - 1 T 1 - 1 Tx 2 2 + x 2 1 x 4 2 ) -48x 2 1 x 2 2 + 1 = 4 ( 4 Rosenbrock

 1111111111222144 a T b T c (1 -x 2 )dµ(x) = 1 2 a T b T c (1 -T 2 )dµ(x) = 1 2 a T b T c dµ(x) -1 2 a T b T c T 2 dµ(x),and thus a T b T c (1 -x 2 )dµ(x) = 1 8 (δ 0,a+b+c + δ 0,a+b-c + δ 0,|a-b|+c + δ 0,|a-b|-c ) a+b+c-2 + δ 0,|a+b-c|-2 + δ 0,|a-b|+c-2 + δ 0,||a-b|-c|-2 ).C. Test functionsBooth Function n = 2, f min = f (0.1, 0.3) = 0, f ([-1, 1] 2 ) ≈ [0, 2 500] f (x) = (10x 1 + 20x 2 -7) 2 + (20x 1 + 10x 2 -5) 2 = 250(T 2 (x 1 ) + T 2 (x 2 )) + 800 T 1 (x 1 )T 1 (x 2 ) -340 T 1 (x 1 ) -380 T 1 (x 2 ) + 574 Matyas Function n = 2, f min = f (0, 0) = 0, f ([-1, 1)] 2 ) ≈ [0, 100] f (x) = 26(x 2 1 + x 2 2 ) -48x 1 x 2 = 13(T 2 (x 1 ) + T 2 (x 2 )) -48T 1 (x 1 )T 1 (x 2 ) + 26 Motzkin Polynomial n = 2, f min = f (± 1 2 , ± 1 2 ) = 0, f ([-1, 1)] 2 ) ≈ [0, 80] f (x) = 64(x 4 1 T 4 (x 1 ) + T 4 (x 1 )T 2 (x 2 ) + T 2 (x 1 )T 4 (x 2 ) + T 4 (x 2 )) + 20 T 2 (x 1 )T 2 (x 2 ) + 16 (T 2 (x 1 ) + T 2 (x 2 )) + 13 Three-Hump Camel Function n = 2, f min = f (0, 0) = 0, f ([-1, 1)] 2 ) ≈ [0,2000] (x 1 ) + 58725 64 T 2 (x 1 ) + 25 T 1 (x 1 )T 1 (x 2 ) + 12.5 T 2 (x 2 ) + 14525 24 Styblinski-Tang Function n = 2, 3, f min = -39.17 • n,f ([-1, 1)] 2 ≈ [-70, 200] Function n = 2, 3, f min = 0, f ([-1, 1)] 2 ) ≈ [0, 4 000] 048 • x j+1 -2.048

Table 1 :

 1 The upper bounds f (r) for the test functions.

	r	Booth	Matyas Motzkin Three-Hump	Styblinski-Tang n = 2 n = 3	Rosenbrock n = 2 n = 3
	6	145.3633	4.1844	1.1002	24.6561	-27.4061	157.7604
	8	118.0554	3.9308	0.8764	15.5022	-34.5465 -40.1625	96.8502	318.0367
	10	91.6631	3.8589	0.8306	9.9919	-40.0362 -47.6759	68.4239	245.9925
	12	71.1906	3.8076	0.8098	6.5364	-47.4208 -55.4061	51.7554	187.2490
	14	57.3843	3.0414	0.7309	4.5538	-51.2011 -64.0426	39.0613	142.8774
	16	47.6354	2.4828	0.6949	3.3453	-56.0904 -70.2894	30.3855	111.0703
	18	40.3097	2.0637	0.5706	2.5814	-58.8010 -76.0311	24.0043	88.3594
	20	34.5306	1.7417	0.5221	2.0755	-61.8751 -80.5870	19.5646	71.5983
	22	28.9754	1.4891	0.4825	1.7242	-63.9161 -85.4149	16.2071	59.0816
	24	24.6380	1.2874	0.4081	1.4716	-65.5717 -88.5665	13.6595	49.5002
	26	21.3151	1.1239	0.3830	1.2830	-67.2790	11.6835
	28	18.7250	0.9896	0.3457	1.1375	-68.2078	10.1194
	30	16.6595	0.8779	0.3016	1.0216	-69.5141	8.8667
	32	14.9582	0.7840	0.2866	0.9263	-70.3399	7.8468
	34	13.5114	0.7044	0.2590	0.8456	-71.0821	7.0070
	36	12.2479	0.6363	0.2306	0.7752	-71.8284	6.3083
	38	11.0441	0.5776	0.2215	0.7129	-72.2581	5.7198
	40	10.0214	0.5266	0.2005	0.6571	-72.8953	5.2215
	42	9.1504	0.4821	0.1815	0.6070	-73.3011	4.7941
	44	8.4017	0.4430	0.1754	0.5622	-73.6811	4.4266
	46	7.7490	0.4084	0.1597	0.5220	-74.0761	4.1070
	48	7.1710	0.3778	0.1462	0.4860	-74.3070	3.8283

Table 2 :

 2 Comparison of the upper bounds f (r) and f (r) K for Booth, Matyas, Three-Hump Camel and Motzkin Functions.

	r	Booth Function	Matyas Function	Three-Hump Camel Function	Motzkin Polynomial

  2 • x 2 j ) 2 + (2.048 • x j -1) 2 • 2.048 4 T 4 (x j ) -100 • 2.048 3 T 2 (x j )T 1 (x j+1 ) + (0.5 + 50 • 2.048 2 )2.048 2 T 2 (x j ) +50 • 2.048 2 T 2 (x j+1 ) -4.096 T 1 (x j ) -100 • 2.048 3 T 1 (x j+1 ) + 1 + 2.048 2 (37.5 • 2.048 2 + 50.5)

	n-1
	=	12.5
	j=1

we show how the new bounds f (r) can be computed as generalized eigenvalue problems and in Section

we conclude with some numerical examples illustrating the behaviour of the bounds f (r) .

Appendix

A. Proof of Lemma 2.1

We give here a proof of lemma 2.1, which we repeat for convenience.

Lemma 2.1 For any fixed integer k > 1, one has:

where

Moreover, the right hand side of the equation increases monotonically with increasing k.

Proof. We recall the representation of the Chebyshev polynomials in the monomial basis:

So, concretely, the coefficients are given by

It follows directly that t

2 and all k > 1 which implies the inequality on the left hand side of (2.7).

Now we show that the value of max

Observe that this quotient is at most 1 if and only if m 1 ≤ m ≤ m 2 , where we set

Observe furthermore that m 1 ≥ 0 if and only if k ≥ 4, and m 2 ≥ k 2 for all k > 1.

Therefore, in the case k ≥ 4, max

Finally we show that the rightmost term of (2.7) increases monotonically with k. We show the inequality: |t


A Akbari

S Desclaux

J C Rouch

J C Remigy
email: remigy@chimie.ups-tlse.fr

Application of nanofiltration hollow fibre membranes, developed by photografting, to treatment of anionic dye solutions

Keywords: Membrane, Hollow fibre, Photografting, Nanofiltration, Textile dyes

New hollow fibre nanofiltration membranes have been developed by UV-photografting using sodium p-styrene sulfonate (NaSS) as a vinyl monomer. The influence of different parameters on the grafting process such as irradiation time, quantity of received UV energy by the membrane and addition of photoinitiator, on the performances and the characteristics of the membranes were examined. The molecular weight cut-off of the grafted hollow fibres was estimated using different PEG solutions. The grafted membranes were also evaluated for the removal of different anionic dyes (Acid, Direct and Reactive dyes) with an aim to reuse the dye and the water in the process house. It is observed that the newly developed hollow-fibre membranes show performances which are close to that of an "ideal" membrane adapted to the treatment of dye effluents. For example, a negatively charged hollow fibre with a 4500 Da cut-off can be used to concentrate a saline direct red 80 solution with a high flux (15 10 -5 l h -1 m -2 Pa -1 (15 l h -1 m -2 bar -1 )), a high dye rejection (R > 97%) and a salt retention lower than 2%.

Introduction

In the textile industry, there are several process operations for finishing of fabric which generate wastewater with various compositions. These operations include desizing, scouring, mercerizing, bleaching, dyeing or printing and finishing. Among all these wastewaters, the dyeing wastewater is more problematic due to the presence of dyes. The textile dyes are organic components which are usually toxic, non-biodegradable and they have ecosystem actions on the rivers [START_REF] O'neil | Colour in textile effluents-sources, measurement, discharge consents and simulation: a review[END_REF]. Consequently, the treatment processes must be able to reduce the colour higher than 90%.

There are three groups of textile dyes depending on their state in solution and on their charge: group N; neutral dyes such as disperse, vat and sulphur dyes which are not soluble in water; group C; cationic dyes like basic dyes and group A; anionic dyes that is to say acid, direct and reactive dyes which are soluble in water. Treatment technologies for removing dye from wastewater are divided into several groups such as: coagulation, biological, adsorption, oxidation, ion-exchange, electrochemical and membrane separation [START_REF] Marrot | Wastewater treatment and reuse in textile industries, a review[END_REF]. There are advantages and disadvantages associated with each of these techniques and not all are suitable for all dye classes.

However, because a membrane can act as a purely physical barrier to specific components without either the degradation of the components or the addition of chemicals, membrane separation, potentially allows the removal and reuse of dyes, chemicals, and process water. In this respect, membrane processes differ from the other generic groups.

Among all types of membrane operations, nanofiltration, due to the different mechanisms of retention allows to concentrate and reject soluble and ionic dyes such as acid, basic, direct and reactive dyes [START_REF] Buckley | Membrane technology for the treatment of dyehouse effluents[END_REF]. Microfiltration and ultrafiltration are suitable for removing of colloidal dyes such as disperse and vat dyes.

However, most of commercial nanofiltration membranes are polyamide based. The polyamide is a textile fibre polymer which can be dyed by the majority of textile dyes. Thus, using this type of nanofiltration membranes for the treatment of dyeing effluents causes membrane fouling and so flux decreases during filtration as it has been shown in a previous paper [START_REF] Akbari | Treatment of textile dye effluents using a polyamide based nanofiltration membrane[END_REF]. B. Van der Bruggen et al. have studied the performance of three nanofiltration membranes (cut-off: 180-250-800 Da) to the treatment of dyehouse effluents [START_REF] Van Der Bruggen | Water reclamation in the textile industry: nanofiltration of dye baths for wool dyeing[END_REF][START_REF] Van Der Bruggen | Mechanisms of retention and flux decline for the nanofiltration of dye baths from the textile industry[END_REF]. The membranes were NF70 (polyamide composite), UTC-20 (piperazineamide composite) and NTR 7450 (polyether sulfone sulfonate) with a molecular weight cut-off (MWCO) of 200, 180 and 600-800 Da, respectively. They have observed that the obtained flux by polyamide membranes (NF70 and UTC-20) has strongly decreased. They have attributed this decline to the osmotic pressure and the dye adsorption by membranes due to the presence of polyamide in the membrane surface.

Van der Bruggen et al. [START_REF] Van Der Bruggen | Mechanisms of retention and flux decline for the nanofiltration of dye baths from the textile industry[END_REF] have also examined the mechanisms of flux decline and dye retention of the same nanofiltration membranes. They have used a synthetic dye solution containing of reactive blue 2 (M.W.: 840 Da, three sulfonate groups), reactive orange 16 (M.W.: 617 Da, two sulfonate groups), Na 2 SO 4 , Na 2 CO 3 , NaOH and a surfactant. They have observed that salt retention was decreasing with a salt concentration increase due to the decrease of the Donnan effect. The flux was also dependent to salt concentration and it decreases rapidly with increasing of salt concentration: due to the important salt retention, the osmotic pressure difference is increased and consequently the flux also decreases.

This brief review of the literature leads us to conclude that:

-NF polyamide-based membranes are not suitable for the treatment of textile dye solutions due to fouling. -NF membranes with a too low MWCO are also not suitable due to a too high salt retention.

An "ideal" membrane for the treatment of textile dye solutions would then have the following characteristics:

-A thin skin with a high density of charges of the same sign that the dyes to be retained (i.e. in order to obtain low fouling and high dye retention). -A small retention of salt in order to avoid a too high osmotic pressure and a decrease of dye retention due to the decrease of the electrostatic part of dye retention.

In a previous paper, an attempt has been successfully made to prepare such an "ideal" flat sheet membrane by UV-photografting an ultrafiltration polysulfone membrane in presence of sodium p-styrene sulfonate (NaSS) and [2-(acryloyloxy)ethyl]trimethyl ammonium chloride (AO) [START_REF] Akbari | New UVphotografted nanofiltration membranes for the treatment of colored textile dye effluents[END_REF]. By UV-photografting technique, chemicals bonds in the polysulfone membrane which is photo-reactive can be cleaved to create radical sites [START_REF] Pieracci | Increasing membrane permeability of UV-modified poly(ether sulfone) ultrafiltration membranes[END_REF]. Free radical polymerisation will occur at these sites in presence of a vinyl monomer, and thus polymer chains are grafted to the membrane surface by covalent bond. In the present study, this method has been adapted for the modification of the external surface of hollow fibres using the photografted process elaborated at our laboratory [START_REF] Bequet | Procédé de photogreffage en continu de membranes fibres creuses[END_REF][START_REF] Goma-Bilongo | Numerical simulation of a UV photografting process for hollow-fibre membranes[END_REF].

The choice of hollow fibre geometry with an outside-in mode of filtration has been made for the following reasons [START_REF] Serra | Dead-end ultrafiltration in hollow fibre modules: module design and process simulation[END_REF]:

-Hollow fibres can be assembled in large modules with large surface areas.

-An outside-in mode of filtration leads to an optimum small diameter hollow fibre giving the possibility to manufacture modules with a larger surface area than with an inside-out mode of filtration. -With an outside-in mode of filtration, fouling is lower and backflushes are more efficient to remove cake layer than with an inside-out mode of filtration.

Materials and methods

Photografting set-up

Fig. 1 represents the UV-photografting set-up. The UF hollow-fibre membrane, initially wet by water, was dipped in the aqueous monomer solution (not degassed). Then the hollow fibre passed through two UV systems (model UVAPRINT LE S/CM, UV polychromatic lamp of F type, 25 cm length, Hoenle UV France, Lyon, France) where the photografting occurs under air. The line rate (U, m min -1 ) of the hollow fibre (production rate) is maintained constant at a value comprises between 2 and 20 m min -1 . After irradiation, the hollow fibre was carefully, washed with reverse osmosis treated water.

The total energy (E, J m -2 ) received by the membrane is equal to the product of the intensity (I UV , W m -2 ) by the residence time or irradiation time (T irr , s) in the reactor. The UV intensity was measured using an UV meter High End (Hoenle UV France, Lyon, France) equipped with UVA, UVB and UVC sensors. Energy given in this article is the total UV energy. A more complete description of these parameters can be found in reference [START_REF] Goma-Bilongo | Numerical simulation of a UV photografting process for hollow-fibre membranes[END_REF].

Filtration system

Fig. 2 shows the tangential NF unit. From the feed tank (volume 5 L), the feed solution is pumped to the hollow-fibre module. The module contains 10 fibres of 20 cm length. The retentate and permeate solutions are recycled to the feed tank so the feed concentration is constant. In the retentate line, a flow meter is placed to regulate the linear feed velocity (u, m s -1 ). The feed flow rate was set between 65 and 260 L h -1 . The desired pressure, adjusted by means of a pressure regulator, was varied in the range of 0.5-4 × 10 5 Pa (0.5-4 bars). The temperature of the feed solution is maintained at 25 • C. Excepted for the long time filtration (see Fig. 14), the flux and retention were measured during 60 min, each 10 min. The values reported here correspond to a stable flux which was achieved after 10 min.

Materials

Support ultrafiltration hollow-fibre membranes

Two hollow-fibre polysulfone membranes called 1A and 2A were home-made by phase inversion [START_REF] Akbari | Elaboration de fibres creuses de nanofiltration par photogreffage: application au traitement de solutions de colorant[END_REF]. The characteristics of these hollow fibre membranes such as water permeability (L p ), intrinsic 10 kDa PEG retention (R int ) [START_REF] Causserand | Improvement of a method for the characterization of ultrafiltration membranes by measurements of tracers retention[END_REF], inner (d in ) and outer (d out ) diameters are presented in Table 1. The active surfaces of the HF modules are also given.

Monomer, crosslinker and photoinitiator

Sodium p-styrene sulfonate, N,N -methylene bis acrylamid (crosslinker, Ret) and 4-hydroxybenzophenone (photoinitiator, PI) were purchased from Aldrich and used as received without further purification. NaSS concentration [NaSS] is given in mass percent. Concentration of Ret [Ret] and PI [PI] are given in mole percent of moles of NaSS.

L p (×10 -5 l h -1 m -2 Pa -1 (l h -1 m -2 bar -1 )) 30 31 R int (%) PEG 10 kDa 65 87
Active surface of module (cm 2 ) 69.1 75.4

Membrane characterizations

The water flux was measured by filtrating reverse osmosis treated water at different applied pressure between 0 and 3 × 10 5 Pa (0 and 3 bars).

The membrane characterization studies were carried out using a polyethylene glycol (PEG) series (600, 2000, 4600, 10,000 Da) (Aldrich, France) for MWCO measurement using the Causserand's protocol [START_REF] Causserand | Improvement of a method for the characterization of ultrafiltration membranes by measurements of tracers retention[END_REF], with dye solution, with single salt solution (NaCl) and mixture of dye and salt solutions. The observed retentions of the dyes and salt were measured under different pressures up to 3 × 10 5 Pa (3 bars) and different feed velocity u (0.1-0.8 m s -1 ).

The concentration of PEG was measured from Total Organic Carbon (TOC) of the single PEG solutions. TOC was measured using a carbon analyzer SHIMADZU model TOC 5050 A. The concentration of dye solutions were analyzed using an UV-vis spectrophotometer ANTHELIE SECOMAN (Domont, France) at the wavelength of the maximum absorption of each dye. Table 2 represents the main characteristics of the used dyes [START_REF]Colour Index International, Society of Dyers and Colourists[END_REF]. A concentration of 100 ppm of dye in water has been used in all experiments. The choice of the concentrations was explained elsewhere [START_REF] Akbari | New UVphotografted nanofiltration membranes for the treatment of colored textile dye effluents[END_REF]. The concentration of salt solutions was determined from the conductivity of solution. The degree of grafting (DG) was determined by an ionexchange capacity method [START_REF] Nasef | Preparation of crosslinked cation exchange membranes by radiation grafting of styrene/divinylbenzene mixtures onto PFA films[END_REF]. After washing with reverse osmosis treated water in order to remove the not grafted monomers, 1 m length of grafted hollow-fibre was placed in 2 M HCl solution for 20 h to obtain the acid form of the sulfonic groups. The hollow fibre in H + form was then equilibrated in 0.05 M NaCl solution for 10 h at 20 • C. The amount of protons released in the solution, was measured using a pH meter. From the pH difference of the NaCl solution after and before equilibration, the degree of grafting was calculated. This analysis was made at least two times in order to have less than 5% of difference between measurements. The degree of grafting is expressed in mmol of monomer per m 2 of membrane.

Results and discussion

Photografting

Irradiation of hollow-fibre membranes in absence of monomer

The hollow fibre membrane (2A) was irradiated in absence of monomer, at received UV energies between 200 and 350 kJ m -2 to investigate the photo degradation of the PSf hollow fibre membrane. Results for the pure water permeability and the observed retention of PEG as a function of the received energy are shown in Fig. 3. One can observe that the water permeability and the PEG retention both decrease when the total received energy increases. This simultaneous decline has already been observed for polyethersulfone membranes and was attributed to competition between two phenomena: crosslinking and chain scission [START_REF] Kaeselev | Influence of the surface structure on the filtration performance of UV-modified PES membranes[END_REF]. The crosslinking of the PSf chains decreases the water permeability (i.e. closing the small pores) while chain scissions are responsible for the loss of membrane selectivity (i.e. opening the big pores).

Effect of received energy 3.1.2.1. Energy monitored by the UV intensity.

Several modified hollow-fibre membranes were prepared from the 1A hollow fibre membrane at the same monomer concentration (15%) and line rate (3 m min -1 ) but at different received energies (i.e. dif- ferent UV intensities). Fig. 4 shows the water permeability and the degree of grafting as a function of the energy. Goma-Bilongo et al. [START_REF] Goma-Bilongo | Numerical simulation of a UV photografting process for hollow-fibre membranes[END_REF] showed that when the line rate is constant, the concentrations of monomer at the membrane and/or in the pore are constant. So the observations only depend of the UV intensity effect. The results show that the degree of grafting increases with the increase of energy, while the water permeability decreases. However, for high energies (larger than 900 kJ m 2 ), the permeability remains constant while the dg still increases. This point is not clearly understood and is probably due to the presence of large pores (i.e. a broad pore size distribution) which are closed with difficulty by the grafted layer. This assumption is partially confirmed by the MWCO measurements of the selected fibre: the retention of 10 kDa PEG is not total (see Fig. 7). energy monitored by variation of the line rate (and consequently by the irradiation time, T irr ). As before, it is observed that the degree of grafting increases with the increase of energy while the water permeability decreases.

Energy monitored by the line rate.

Measurements for an energy of 1000 kJ m -2 (DG = 0.6 mmol m -2 ;

L p = 4 × 10 -5 l h -1 m -2 Pa -1 (4 l h -1 m -2 bar -1
)) correspond to a line rate of 3 m mn -1 and are then directly comparable to the same measurements shown in Fig. 4 (DG = 0.75 mmol m -2 ; L p = 3 × 10 -5 l h -1 m -2 Pa -1 (3 l h -1 m -2 bar -1 )). Discrepancies can be attributed to the different batch of 1AG fibre and to experiments made at several months interval (cumulative small differences on line rate, temperature, monomer concentration and UV lamp power).

On the contrary, the measurements for the other energies were not performed at the same line rate and the results are very different. For example, results for energy of 600 kJ m -2 are DG = 0.25 mmol m -2 (Fig. 4, U = 3 m s -1 ) and DG = 0.55 mmol m -2 (Fig. 5, U = 5 m s -1 ): this means that the line rate increase, tend to increase the grafting ratio (and consequently the permeability decreases). This observation is of a great practical importance since the efficiency of the grafting increases with the increase of the productivity of the spinning/modification line.

Explanation for such remarkable result can be qualitatively explained from the theory of the photo grafting process by dip coating. The observations are the consequence of the variations of UV energy, of the monomer concentration and of the thickness of the deposited liquid film. When U is increased, the reduction in UV energy is composed by the increase of the monomer concentration at the surface and in the pore due to the increase of the film thickness [START_REF] Goma-Bilongo | Numerical simulation of a UV photografting process for hollow-fibre membranes[END_REF]. The data shown in Figs. 4 and5 lead to the conclusion that, in this case, the grafting efficiency is mostly dependent on the amount of monomer presents at the surface (with a thickness of few micrometers).

Photografting in presence of photoinitiator

The addition of a photoinitiator (PI) makes it possible to create radicals in the solution deposited on the membrane and thus to increase the kinetics and the quantity of created polymer chains on the surface. Goma showed that the thickness of the deposited layer is a function of the viscosity and the surface tension of the monomer solution and the line rate through the capillary number [START_REF] Goma-Bilongo | Numerical simulation of a UV photografting process for hollow-fibre membranes[END_REF]. The thickness is thus higher than 10 m and increased with the line rate.

Two sources of radicals will be thus available: on the surface of the membrane due the photoactivity of PSf and inside the entrained solution. The presence of crosslinking agent should make it possible to establish links between the chains of created polymers inside the solution and those created onto the surface of the membrane; interest being to keep chemical bonds between the support membrane and the living polymer.

Fig. 6 represents the variation of the hydraulic permeability and the degree of grafting of modified 2A hollow fibres in presence and absence of photoinitiator according to the received energy by the membrane (monitored by the line rate). Table 3 shows the intrinsic retention of PEG (10 kDa) with and without PI for two line rates (4 and 5 m min -1 or 750 and 600 kJ m -2 ). These results show that:

• In the presence of photoinitiator, the degree of grafting is much more important than in absence of photoinitiator, in particular at the low line rate (i.e. high UV energy, by a factor 5 at 860 kJ m -2 ). • The hydraulic permeability decreases according to the received energy in presence or absence of photoinitiator. The permeability decrease is higher in presence of PI. • The retention of 10 kDa PEG is higher in presence of PI considering the same UV energy (and probably for a same obtained permeability).

The higher degree of grafting obtained in presence of PI is due to the combined effects of a higher kinetic and a photo polymerisation that occurs both in the coated solution and at the surface of the membrane. The thickness of the coated solution is far higher (more than 10 times) than the thickness of the reaction zone at the surface of the membrane [START_REF] Goma-Bilongo | Numerical simulation of a UV photografting process for hollow-fibre membranes[END_REF][START_REF] Akbari | Elaboration de fibres creuses de nanofiltration par photogreffage: application au traitement de solutions de colorant[END_REF]. One can conclude that the thickness of the grafting layer is higher in presence of PI because the grafted polymers are produced at the surface of the membrane and in the coated film (i.e. coated solution).

The efficiency of the grafting layer in term of pore closing is different in presence or in absence of PI. In absence of PI, the growth of the grafted layer starts starting from the surface of the pore in absence of PI (i.e. the initiation of the polymerisation occurs at the surface of the pore). A pore is progressively closed by the increase of the grafting layer at the surface of the pore (i.e. from the surface). In presence of PI, the initiation occurs both at the surface and in the liquid film. A pore is progressively closed by the increase of the grafting layer at the surface and by the synthesis of polymer chains over the pore. [START_REF] Nasef | Preparation of crosslinked cation exchange membranes by radiation grafting of styrene/divinylbenzene mixtures onto PFA films[END_REF] 4

L p (×10 -5 l h -1 m -2 Pa -1 (l h -1 m -2 bar -1 ))
MWCO (Da) 4600 2000

Consequently the permeability decrease is higher and the retention is higher in presence of PI: the efficiency in term of pore closing is higher in presence of PI for a given UV energy. However, with PI, a far higher DG is needed to get the same permeability decrease (2.5 mmol m -2 compared to 0.8 mmol m -2 to get permeability around 3-4 × 10 -5 l h -1 m -2 Pa -1 (3-4 l h -1 m -2 bar -1 )) because the surface porosity is low for this kind of membrane (less 5%): most of the grafted polymer is not used to close the pores but is simply grafted on surface without pore.

Characterisation of the selected hollow fibre membranes

Among all the modified hollow fibres, two were selected for filtration of coloured solutions: the first one is the 1A membrane support which was grafted at a rate of 7.5 m min -1 with an energy of 366 kJ m -2 and without photoinitiator, the second one was prepared from the grafted membrane 2A at the rate of 4 m min -1 , with energy of 755 kJ m -2 and in the presence of photoinitiator (Table 4). These hollow fibres will be called 1AG and 2AG, respectively.

In the range of pressures available on the NF set-up, no compaction is observed. The average permeability of the 1AG and 2AG grafted hollow fibres are, respectively, 15 and 4 × 10 -5 l h -1 m -2 Pa -1 (15 and 4 l h -1 m -2 bar -1 ). The molecular weight cut-off measured by filtration of PEG solutions, are presented in Fig. 7. The MWCO of these membranes (4600 and 2000 Da for 1AG and 2AG membranes, respectively) are higher than the molecular weight of the used dyes (Table 2), the sieving retention mechanism for dyes will be thus limited particularly for the 1AG hollow fibre membrane.

Application to the treatment of dye solutions

Dye retention

The retention of different anionic dyes by the 1AG hollow fibre membrane at feed velocity of 0.8 m s -1 and pressure of 3 × 10 5 Pa (3 bars), are presented in Table 5. The high retention (∼100%) for DR80 can be ascribed to the high molecular weight (1373 Da) and the number of sulfonate groups (six groups). The retention for AO10 and RO16 was lower than that for DR80 because of their lower molecular weight and in particularly, lower charge density (two sulfonate groups). In this case, the sieving mechanism is slightly less important and dye retention takes place by an ionic exclusion mechanism [START_REF] Schäfer | Nanofiltration: Principles and Application[END_REF]. Whereas the dyes DR80, AO10 and RO16 have retention corresponding to their charge or/and their molecular weight, the behaviour of direct yellow 8 (DY8) is remarkable. This dye has a low charge (one sulfonate group) and a molecular weight close to that of dyes AO10 and RO16. The high retention is related to the fact that this dye, used such as in textile industry, is an impure product; the solution of DY8 in distilled water is clear and limpid but addition of salt (NaCl or MgSO 4 ) leads to the formation of flocs (or aggregation). After settling of the flocs, a complete discoloration of the solution is observed while all the coloration is limited to the flocs. The solution of DY8 is thus not that of a pure dye but a mix of a soluble dye and colloidal particles. The strong retention of this dye could thus be explained by the retention of the colloids (aggregated particles) on which would be sorbed most of the soluble dye.

Effect of concentration polarisation

The influence of the concentration polarisation was studied by varying the feed velocity u in the module, at pressure of 3 × 10 5 Pa (3 bars), for four dye solutions using the 1AG membrane (Fig. 8(a andb)) and at two pressures (2 and 3 × 10 5 Pa, 2 and 3 bars) for acid orange 10 using the 2AG membrane (Fig. 9). From these plots, it is observed that the increase of feed velocity increases the flux and the dye retention for the two hollow fibre membranes; this is in particularly true for the low molecular weight dyes such as AO10 and RO16. The increase of feed velocity makes it possible to decrease the concentration at the membrane surface leading to a decrease in permeate concentra- tion (and then an increase in retention). This lower concentration polarisation leads also to an osmotic pressure decrease and consequently an increase in the effective pressure and thus in an increase of the flux. It should be noted that, as the dye concentrations are low (100 ppm), the osmotic pressure is small in comparison with the applied pressure, even at the membrane surface. So the effect of feed velocity (i.e. decrease of the concentration at the membrane surface) on flux is low (i.e. solution flux close to the pure water flux) whereas the dye retention increased significantly. It is to point out that the flux for the dye solutions are quite close to the distilled water flux, especially at high velocity; this means that fouling is negligible. In any case, no adsorption of dye on the membranes surface was observed as previously reported on flat sheet grafted membranes [START_REF] Akbari | New UVphotografted nanofiltration membranes for the treatment of colored textile dye effluents[END_REF]. Concentration polarisation has a remarkable effect on the retention of dyes which are partially retained. The charge effects strongly decrease with the increase in the ion concentration and thus in the concentration polarisation for the aqueous charged solutions. The retention obtained with 1AG membrane for dyes AO10 and RO16 are due to electrostatic repulsion because the molecular weight of the dyes is close to 500-600 Da while the MWCO of 1AG membrane is 4600 Da. The use of this membrane for the filtration of these dyes requires a good control of the concentration polarisation.

Fig. 9 presents the retention of AO10 by the 2AG hollow fibre at two applied pressures for various feed velocities. The effects of the concentration polarisation are qualitatively the same ones as previously reported but quantitatively the retention of AO10 varies only from 3% whereas for the 1AG membrane, the variation is 20% for the same variation in velocity (from 0.2 to 0.7 m s -1 ). Considering that fluxes are measured to more or less 10%, one can say that the flux is relatively constant for the 2AG hollow fibre whereas it increases slightly for 1AG hollow fibre. Theses differences in behaviour are due to:

A low flux for 2AG membrane: thus the retro diffusion is enough to limit the concentration polarisation. On the contrary, the convection flux through the membrane is higher in the case of the 1AG membrane (approximately four times higher at 3 × 10 5 Pa (3 bars)): the concentration polarisation is then more important.

-The MWCO of the 2AG membrane (2000 Da) closer to the size of the dye associated with an important degree of grafting (2.45 mmol m -2 instead of 0.43 mmol m -2 for 1AG): the 2AG membrane is thus higher charged with smaller pores than the 1AG membrane. As a consequence, AO 10 retention is higher with 2AG membrane.

The 1AG hollow fibre thus shows retention lower than that of 2AG hollow fibre for AO10. The retention varies strongly when the concentration polarisation increases owing to the fact that the membrane is less charged and its MWCO is too large. This membrane can be used with high retention and flux in the case of the filtration of dyes when the concentration polarisation is low (high feed velocity; 0.8 m s -1 ). However, the textile effluents are saline solutions, the retention of dye should thus strongly decrease due to the shielding of carried charges by the membrane. 2AG hollow fibre is more powerful in term of retention; fluxes are nevertheless weaker. This membrane which is higher charged and has a lower MWCO should maintain important retention of the dyes for the filtration of saline coloured solutions.

Effect of salt on the flux and dye retention

As already mentioned, the coloured effluents of the textile industry are saline. The quantity of salt used for the dyeing operation depends on the type of dye and the number of sulfonate groups carried by the dye. Mainly sodium chloride is used. The results presented in this paragraph were performed with solu- One can note that, when the salt concentration increases, flux remains constant for a given pressure (points taken vertically) because of the low retention (∼1-3%) of the salt (Fig. 10b). The concentration polarisation for salt is thus non-existent. The osmotic pressure is low and constant (the osmotic pressure due to NaCl varies from 0.25 to 0.33 × 10 5 Pa (0.25 to 0.33 bars) according to the concentration and the retention of salt). The retention of the DR80 decreases with the flux (concentration polarisation) and also decreases with an increase in the salt concentration that this decrease in range of salt concentration from 0 to 510 mM is not very important. This effect is due to the shielding of the fixed charges of the membrane by the cations and the anions present in the solution. However, in the range of the salt concentrations used, which are representative of the concentrations for a real effluent, dye retention remains higher than 97% at concentration of 510 mM NaCl and pressure of 3 × 10 5 Pa (3 bars).

Fig. 11 represents the influence of the NaCl concentration on the retention of AO10 according to flux for the 1AG hollow fibre. The NaCl concentration is equal to 170 mM. AO10 is an anionic dye like DR80 but it has a lower molecular weight and is less charged (only 2 sulfonate groups against six for DR80). Unlike DR80 retention, the AO10 retention decreases strongly in the presence of salt while NaCl retention is still negligible. This decline is worsened by the concentration polarisation due to the increase in flux. The influence of the presence of salt is much more important in the case of AO10 than in that of DR80 because the molecular weight of AO10 is much lower than that of DR80. The sieving retention mechanism is less important and do not allow to compensate for the reduction in the ionic exclusion mechanism.

The use of the 2AG hollow fibre for the filtration of the same solution (AO10 + 170 mM NaCl) makes it possible to obtain retention of AO10 ranging between 85 and 80% (Fig. 12). The retention of AO10 and NaCl decreases according to the NaCl concentration while fluxes remain stables. The fluxes at 2 and 3 × 10 5 Pa (2 and 3 bars) are equals, respectively, to 7.6 and 11.4 l h -1 m -2 . No important decline in the dye retention is observed here because on the one hand, the membrane is more charged than 1AG and on the other hand the MWCO of 2AG is closer to the molecular weight of this dye than the MWCO of 1AG. Then for the 2AG hollow fibre, the sieving mechanism makes it possible to compensate for the loss of ionic exclusion. Nevertheless, it is not possible, with these experiments, to give the relative importance of the two mechanisms. So the different behaviours of the 1AG and 2AG during the filtration of AO10 in presence or in absence of salt are due to the lower MWCO and to the higher DG of the 2AG: the retention of AO10 is higher with the 2AG hollow fibre in presence or in absence of salt.

The results presented in Fig. 13 shows the variation of the retention of AO10 and NaCl as a function of flux for the 2AG membrane and a solution at the concentration of 170 mM in NaCl. Unlike results shown in Fig. 10 and 11, AO10 and NaCl retentions increase with flux. Here, filtration is carried out in osmotic filtration mode (Peclet number below 1) where the mechanisms of transfer inside the pore are dominating relatively those present in the solution: the convection flux of water increases, while the diffusion of the salts remain constant. Thus, 2AG hollow fibre approaches to the "ideal" membrane presented in the introduction: the AO10 dye is retained whereas salts are not it or little. Thus, the fouling for the 1AG hollow fibre is little important, it makes it possible to retain the dye and to let pass salts. It approaches the characteristics of the "ideal" membrane imagined in the introduction for the filtration of DR80 dye in presence of salt. The same "ideal" membrane has been previously produced in a flat sheet shape [START_REF] Akbari | New UVphotografted nanofiltration membranes for the treatment of colored textile dye effluents[END_REF].

Effect of time on the permeability and the retention

Two hollow fibres were used for the filtration of dye solution. The fouling for the two hollow fibres is low 1AG and 2AG and the salt retention is low. The flux is higher for the 1AG HF whereas the MWCO is lower and the retention of dyes is higher for the 2AG HF especially in presence of salt. So the 2AG HF can be used to treat anionic dye solution in presence of salt like AO10 even for low molecular weight dye. The 1AG HF could be used for the high molecular weight dye like DR80 to improve the flux compared to the one obtained using the 2AG HF.

Conclusion

This work showed that it is possible to obtain, by photografting of vinyl monomers on surface of an ultrafiltration hollow fibre membrane, nanofiltration membranes which are capable to be used for the treatment of saline dye solutions.

The influence of different parameters on the grafting process such as quantity of received energy by the membrane and addition of a photoinitiator on the performances and the characteristics of the membrane was examined. One can underline that rate of grafting are about those used for the spinning of hollow fibres. The setting on line, following a chain of spinning, of a system of grafting is thus possible.

The application of these new modified membranes to the treatment of coloured solutions showed that:

-The fouling problem which exists strongly with polyamide membranes is practically limited and the flux of the dye solutions, even after more than 15 h of operating, is almost constant. The presence of identical charge on the surface of the grafted membranes and the dye makes it possible to repulse the molecules of dye, by increasing the retention and limiting fouling. -A MWCO higher than that of the commercial nanofiltration membranes (higher than 1500 Da) can be selected to concentrate the dye solutions while demineralizing the solution. For example, a negatively charged hollow fibre having a MWCO approximately 5000 Da makes it possible to concentrate the direct red 80 (MW 1373 Da) with a retention higher than 87%, a high flux (15 × 10 -5 l h -1 m -2 Pa -1 (15 l h -1 m -2 bar -1 )) and a salt retention lower than 2%. For the dyes of lower molecular weight or less charged, the degree of grafting must be increased in order to decrease the MWCO of the modified membrane. Then an hollow fibre having a MWCO approximately 2000 Da can be used to concentrate the acid orange 10 (MW 452 Da) with a retention higher than 85%, a high flux (15 × 10 -5 l h -1 m -2 Pa -1 (15 l h -1 m -2 bar -1 )) and a salt retention lower than 10%.

Finally, different membranes could be produced using the UV photografting to adapt the MWCO and the charge of the membranes to the dyes (positively or negatively charged, MW, . . .) and to the solution (salt concentration, . . .) in order to obtain a high flux (i.e. low fouling membrane), a high retention of dye and a low retention of salt.

Fig. 1 .

 1 Fig. 1. Schema of the photoreactor set up.

Fig. 2 .

 2 Fig. 2. Schema of the tangential nanofiltration unit and the hollow fibre module.

Fig. 3 .

 3 Fig. 3. Pure water permeability (L p ) and observed retention (R) of PEG 10 kDa (applied pressure: 1 × 10 5 Pa (1 bar) and 25 • C) of 2A hollow fibre membrane irradiated in absence of monomer vs. received UV energy (line rate: 7.5 m min -1 ).

Fig. 4 .

 4 Fig. 4. Degree of grafting (DG) and pure water permeability (L p , 25 • C) of grafted 1A hollow fibre membranes vs. received UV energy (line rate: 3 m min -1 , [NaSS] = 15%, [Ret] = 2%).

  Fig. 5. Degree of grafting (DG) and pure water permeability (L p , 25 • C) grafted 1A hollow fibre membranes as a function of received UV energy, irradiation time and line rate (UV intensity I UV = 100 kW m -2 , [NaSS] = 15%, [Ret] = 2%).

Fig. 6 .

 6 Fig. 6. Degree of grafting (DG) and pure water permeability (L p , 25 • C) grafted 2A hollow fibre membranes vs. received energy in with and without photoinitiator (PI) (UV intensity I UV = 100 kW m -2 , [NaSS] = 15%, [Ret] = 2%, [PI] = 2%).

Fig. 7 .

 7 Fig. 7. PEG retention as a function of molecular weight of PEG of two grafted hollow fibre membranes 1AG and 2AG.

Fig. 8 .

 8 Fig. 8. (a) Observed dye retention (R) and (b) solution flux of dye solutions vs. linear feed velocity (u) for 1AG hollow fibre membrane ([dye] = 100 ppm, applied pressure: 3 × 10 5 Pa (3 bars), Temp.: 25 • C).

Fig. 9 .

 9 Fig. 9. AO10 solution: Observed retention (R) and solution flux vs. linear feed velocity (u) for 2AG hollow fibre membrane ([dye] = 100 ppm, Temp.: 25 • C).

Fig. 10 .

 10 Fig. 10. Observed retention of DR80 (a) and NaCl (b) as a function of flux and NaCl concentration for 1AG hollow fibre membrane ([dye] = 100 ppm, [NaCl] = 170 mM, u = 0.41 m s -1 , Temp.: 25 • C).

Fig. 11 .

 11 Fig. 11. Observed retention of AO10 and of NaCl as a function of flux for 1AG hollow fibre membrane ([dye] = 100 ppm, [NaCl] = 170 mM, u = 0.41 m s -1 , Temp.: 25 • C).

Fig. 12 .

 12 Fig. 12. Observed retention of AO10 and of NaCl as a function of NaCl concentration and applied pressure for 2AG hollow fibre membrane ([dye] = 100 ppm, u = 0.41 m s -1 , Temp.: 25 • C).

Fig. 13 .

 13 Fig. 13. Observed retention of AO10 and of NaCl as a function of flux for 2AG hollow fibre membrane ([dye] = 100 ppm, [NaCl] = 170 mM, u = 0.41 m s -1 , Temp.: 25 • C).

Fig. 14

 14 relates the flux and dye retention to the time of filtration (15 h of filtration) without recycling of the coloured solution with salt (DR80 with NaCl) at the pressure of 2 × 10 5 Pa (2 bars) by 1AG hollow fibre. It is observed that flux decreases slightly during the first 9 h then remains almost constant. In the same time, the retention of the dye remains stable and higher than 97%. The NaCl retention measured is almost null (1-2%).

Fig. 14 .

 14 Fig. 14. Flux and observed retention of direct red 80 (DR80) in presence of NaCl as a function of time for 1AG hollow fibre membrane ([dye] = 100 ppm, [NaCl] = 510 mM, u = 0.41 m s -1 , Temp.: 25 • C, CF (dye)first point = 1, CF (dye)last point = 2.6, CF (NaCl) = 1).

Table 1

 1

	Characteristics of support hollow fibre membranes (i.e. before photografting)
	Support hollow fibre	1A	2A
	d in (mm)	0.60	0.65
	d out (mm)	1.10	1.20

Table 2

 2 Characteristics of the dyes[START_REF]Colour Index International, Society of Dyers and Colourists[END_REF]

	Dye (supplier)	Symbol	M.W.	Charge	[dye]
			(Da)		(mM)
	Acid orange10 (Aldrich)	AO10	452	-2	0.22
	Direct red 80 (Ciba)	DR80	1373	-6	0.07
	Direct yellow 8 (Aldrich)	DY8	518	-1	0.19
	Reactive orange 16 (Aldrich)	RO16	617	-1	0.16

Table 3

 3 Effect of photoinitiator on PEG 10 kDa retention

	Line rate (m min -1 ) UV energy (kJ m -2 ) Without PI (%) With PI (%)
	4	750	76	96
	5	600	72	84

Table 5

 5 Observed retention of different dye solutions for the two grafted hollow fibre membranes (pressure 4 × 10 5 Pa (4 bars), u = 0.8 m s -1 , [dye] = 100 ppm, Temp.: 25 • C)

	Membrane	DR80	DY8	AO10	RO16
	1AG	99.6	99.8	96.4	94.0
	2AG	-	-	98.0	-

Acknowledgements

This study was financially supported by a doctoral grant from the government of Iran, by Société Franc ¸aise d'Exportation des Ressources Educatives (SFERE) and by Région Midi-Pyrénées. For helpful discussions, the authors wish to thank P. Aptel who has initiated this research.

Nomenclature

CF

concentration factor DG degree of grafting (mol monomer m -2 of membrane) L p pure water permeability (×10