A Goldsztejn

C Michel

M Rueher
email: rueher@essi.fr

An Efficient Algorithm for a Sharp Approximation of Universally Quantified Inequalities

Keywords: G.1 [Numerical Analysis]: Miscellaneous Theory, Algorithms Quantified constraints, continuous domains, interval arithmetic

This paper introduces a new algorithm for solving a subclass of quantified constraint satisfaction problems (QCSP) where existential quantifiers precede universally quantified inequalities on continuous domains. This class of QCSPs has numerous applications in engineering and design. We propose here a new generic branch and prune algorithm for solving such continuous QCSPs. Standard pruning operators and solution identification operators are specialized for universally quantified inequalities. Special rules are also proposed for handling the parameters of the constraints. First experimentation show that our algorithm outperforms the state of the art methods.

INTRODUCTION

Many applications in engineering require verifying safety or performance conditions on a given system. For instance verifying for all electrical current in the interval [imin, imax] and all possible resistor values in the interval r0±5% that the voltage across the resistor remains lower than a safety bound umax. In other words, we have to check the satisfiability of (∀i ∈ [imin, imax]) (∀r ∈ [0.95 r0, 1.05 r0]) (ri ≤ umax). [START_REF] Benhamou | Universally quantified interval constraints[END_REF] Examples can be found in [START_REF] Benhamou | Interval Constraint Solving for Camera Control and Motion Planning[END_REF] where the safety condition to be verified is a minimal mutual distance between some satellites during a complete revolution.

In design problems, requirements are a bit more general. Instead of verifying theses conditions, we have to determine values of design variables that satisfy safety and performance conditions for all values of uncertain physical data. All these problems can be modeled in the framework of quantified constraint satisfaction problems (QCSPs). QCSPs arise naturally in numerous other applications (cf. [START_REF] Jaulin | Guaranteed tuning, with application to robust control and motion planning[END_REF][START_REF] Jirstand | Nonlinear control system design by quantifier elimination[END_REF][START_REF] Benhamou | Interval Constraint Solving for Camera Control and Motion Planning[END_REF][START_REF] Goldsztejn | A Branch and Prune Algorithm for the Approximation of Non-Linear AE-Solution Sets[END_REF][START_REF] Goldsztejn | Inner and Outer Approximations of Existentially Quantified Equality Constraints[END_REF][START_REF] Ratschan | Applications of Quantified Constraint Solving over the Reals Bibliography[END_REF]).

In this paper, we are interested in a restricted form of QCSPs where existential quantifiers precede universal quantifiers, i.e. ∃x ∈ x, ∀y ∈ y, c1(x, y)

∧ • • • ∧ cp(x, y), (2)
where x = (x1, . . . , xn) and y = (y1, . . . , ym) are vectors of variables, x = (x1, . . . , xn) and y = (y1, . . . , ym) are vectors of intervals over continuous domains, and constraints ci are inequalities of the form fi(x, y) ≤ 0. In addition to the problems introduced in [START_REF] Benhamou | Interval Constraint Solving for Camera Control and Motion Planning[END_REF], this class of QCSPs can tackle the design of robust controllers, which has been addressed in numerous works [START_REF] Fiorio | Robust performance design of fixed structure controllers for systems with uncertain parameters[END_REF][START_REF] Jaulin | Guaranteed tuning, with application to robust control and motion planning[END_REF][START_REF] Dorato | Robust multi-objective feedback design by quanti er elimination[END_REF][START_REF] Malan | Robust analysis and design of control systems using interval arithmetic[END_REF][START_REF] Zettler | Robustness analysis of polynomials with polynomial parameterdependency using bernstein expansion[END_REF][START_REF] Dorato | Quantified multivariate polynomial inequalities[END_REF].

In general, we are not only interested in the decision problem [START_REF] Benhamou | Interval Constraint Solving for Camera Control and Motion Planning[END_REF] but also in finding assignments of the existential variables which satisfy the constraints.

In other words, we consider x as a search space where we try to find values x ∈ x such that the relation ∀y ∈ y, c1(x, y) ∧ • • • ∧ cp(x, y) holds. Such a value x is called a solution of (2) and we define the solution set of (2) in the following way:

Sol := {x ∈ x : ∀y ∈ y , i∈{1,...,p} ci(x, y)}. (3)
An essential observation is that in all mentioned applications, solution sets are continuums of solutions and that users are not really interested by isolated solutions but by continuous subsets of x where all points are solutions. Indeed, in design problems determining the real value of a physical value without any tolerance information does not really make sense. That's why we compute two sets I and B (called respectively the inner approximation and the boundary approximation) which satisfy the following relation:

I ⊆ Sol ⊆ I ∪ B. (4)
Set I contains only solutions whereas set B contains the boundary of the solution set. Thus B contains indifferently solutions and non-solutions. I ∪ B contains the whole solution set and is called the outer approximation. Actually, due to computational limitations, I and B are unions of boxes (cf. Figure 1). In this paper, we propose a new algorithm for computing the sets of boxes I and B. In contrast with other methods dedicated to the resolution of QCSPs, we handle the QCSP (2) as a non quantified CSP with quantified constraints: we introduce a CSP equivalent to (2) formed of constraints c y (x) on the variables x (the domain parameter y is explicitly given in exponent for clarity). These constraints are quantified inequalities: c y (x) ≡ ∀y ∈ y, f (x, y) ≤ 0; y are called the parameters and y their domains. We propose here a generic branch and prune algorithm dedicated to continuous CSP with parametric constraints. This algorithm is based on a specific implementation for universally quantified inequalities of the following techniques:

-Pruning the non solution set; -Identifying the solution set; -Handling of parameter domains. Other methods [START_REF] Benhamou | Universally quantified interval constraints[END_REF][START_REF] Ratschan | Approximate quantified constraint solving by cylindrical box decomposition[END_REF][START_REF] Benhamou | Interval Constraint Solving for Camera Control and Motion Planning[END_REF][START_REF] Ratschan | Efficient solving of quantified inequality constraints over the real numbers[END_REF] have been proposed to compute approximations of the solution set of (2). The new algorithm we propose here is both much simpler than the previously proposed algorithms, and also much more efficient. First experimentation show that our algorithm outperforms the methods introduced in [1, [START_REF] Ratschan | Approximate quantified constraint solving by cylindrical box decomposition[END_REF][START_REF] Benhamou | Interval Constraint Solving for Camera Control and Motion Planning[END_REF][START_REF] Ratschan | Efficient solving of quantified inequality constraints over the real numbers[END_REF].

Notations. Boldface symbols denotes intervals, e.g. x = [x, x] = {x ∈ R : x ≤ x ≤ x} where x and x belong to a finite subset of R (usually the floating point numbers, cf. [START_REF] Goldberg | What every computer scientist should know about floating-point arithmetic[END_REF]). The set of these intervals is denoted by IR and the set of n dimensional interval vectors (also called boxes) by IR n . The width of an interval vector x = (x1, . . . , xn) is wid(x) = maxi |x i -xi| and its midpoint is mid(x). x denotes a value of x. For two boxes x and y, the interval hull is denoted by x ∨ y and is the smallest box which contains both x and y (note the difference between the union

[-1, 1] ∪ [2, 3] = {x ∈ R : -1 ≤ x ≤ 1 ∨ 2 ≤ x ≤ 3} which is disconnected, and the interval hull [-1, 1] ∪ [2, 3] = [-1, 3]). Also, their set difference is denoted by x\y = {x ∈ x : x / ∈ y}.
Outline of the paper. Section 2 recalls some basics on CSP with continuous domains. Section 3 describes the key features of the algorithm we propose. First experimental results are given in Section 4.

BASICS ON CSP WITH CONTINUOUS DOMAINS

To tackle CSP with continuous domains, a key issue is to be able to prove properties on continuums of real numbers. Interval analysis handles this problem in an efficient way using only computations on floating point numbers.

We recall here some basics which are required to understand the paper. More details can be found in [START_REF] Neumaier | Interval Methods for Systems of Equations[END_REF][START_REF] Kearfott | Interval Computations: Introduction, Uses, and Resources[END_REF].

An interval contractor for a constraint c with n variables is a function

Contractc : IR n -→ IR n , (5)
that satisfies the following properties: (1) Contractc(x) ⊆ x;

(2) ∀x x ∈ x ∧ c(x) =⇒ x ∈ Contractc(x). Such contractors can be implemented using various techniques [START_REF] Neumaier | Interval Methods for Systems of Equations[END_REF][START_REF] Lhomme | Consistency Techniques for Numeric CSPs[END_REF][START_REF] Benhamou | CLP(Intervals) Revisited[END_REF][START_REF] Collavizza | Comparing Partial Consistencies[END_REF] for standard inequality constraints. Examples and experimentation presented in this paper use contractors based on the 2B-consistency. 2B-consistency [START_REF] Cleary | Logical arithmetic[END_REF][START_REF] Lhomme | Consistency Techniques for Numeric CSPs[END_REF] (also known as hull consistency) states a local property on the bounds of the domain of a variable at a single constraint level. A constraint c is 2Bconsistent if, for any variable xi, there exist values in the domains of all other variables that satisfy c when xi is fixed to x i and xi.

The filtering by 2B-consistency of P = (x, C) is the CSP P ′ = (x ′ , C) such that • P and P ′ have the same solutions;

• P ′ is 2B-consistent;
• x ′ ⊆ x and the domains in x ′ are the largest ones for which P ′ is 2B-consistent.

Filtering by 2B-consistency of P always exists and is unique [START_REF] Lhomme | Consistency Techniques for Numeric CSPs[END_REF], that is to say, it is a closure.

DESCRIPTION OF THE ALGORITHM

The key idea of our algorithm is to reformulate a QCSP as a CSP with parametric constraints. More precisely, we reformulate a QCSP with constraints of type (2) as a CSP V, C, D where:

-V = (x1, . . . , xn); -C = {c y 1 , . . . , c y p } with c y i (x) ≡ ∀y ∈ y, fi(x, y) ≤ 0; -D = (x1, . . . , xn). The parameter domains are considered at the level of each constraint, so we can process them differently for each constraint; they are initialized with y. Standard techniques have to be adapted for this class of constraints. For example, we show in Subsection 3.2 that Contract ∀y∈y,f (x,y)≤0 (x) can be achieved with Contract f (x, ỹ)≤0 (x) for any ỹ ∈ y, the latter being implemented using standard interval contractors.

Outline of the Algorithm

The branch and prune algorithm we propose alternates pruning and branching steps in a standard way to reject parts of the search space that do not contain any solution. This process is interleaved with the identification of inner boxes that contain only solutions.

We also introduce new parameter instantiations and parameter reduction techniques which play a key role during the pruning of the search space and the identification of the solution sets. These key points are detailed in subsections 3.2, 3.3 and 3.4. They are implemented within a branching process (see Algorithm 1) using the following functions: Function ParameterInstantiation() returns a set of constraints C ′ which is equivalent to C on the domain x, but Function SolutionIndentification() contracts x ′ to x ′′ and returns a list of inner boxes I ′ (see Subsection 3.3). The domains of the parameters are also updated in C ′′ (see Subsubsection 3.4.1).

Function ParameterDomainBisection() bisects the parameter domains of the constraints and thus increases the number of constraints in C ′′ (see Subsubsection 3.4.2).

Function Branching() achieves a standard bisection of the domains x ′′ .

Pruning

Local Pruning. Given a constraint ∀y ∈ y i , ci(x, y) and a box x, we want to contract x rejecting only parts which do not contain any solution of this constraint. To achieve this task, Benhamou et al. and Ratschan [START_REF] Benhamou | Interval Constraint Solving for Camera Control and Motion Planning[END_REF][START_REF] Ratschan | Efficient solving of quantified inequality constraints over the real numbers[END_REF] apply Contract c i (x,y i ) (x), where y is handled as an existentially quantified variable in the domain y i . However, this strategy lacks efficiency. That's why we propose a better contractor by instantiating the parameter to an arbitrary value ỹ ∈ y i (see Example 1). More formally, the box x is contracted using Contract c i (x, ỹ) (x) which rejects only parts of x that do not satisfy ci(x, ỹ), and thus, do not satisfy ∀y ∈ y i , ci(x, y).

Many strategies can be used to choose ỹ. We chose ỹ = mid(y i ). Experimentation have shown that searching for a better value of ỹ is not worthwhile. This is due to the fact that the parameter handling techniques reduce the impact of this choice (see examples 4 and 5 in Subsection 3.4).

Example 1. Let us consider the constraint c(x) defined by ∀y ∈ y, f (x, y) ≤ 0 with f (x, y) = 10yxy 2 , y = [0, 1], and x = [0, 15]. The solution set of this simple CSP is the interval [START_REF] Dorato | Robust multi-objective feedback design by quanti er elimination[END_REF][START_REF] Jaulin | Guaranteed tuning, with application to robust control and motion planning[END_REF]. To reject values of x that do not satisfy c(x), we apply Contract f (x,0.5)≤0 (x), which reduces x to x ′ = [4.75, 15]. The method proposed in [START_REF] Benhamou | Interval Constraint Solving for Camera Control and Motion Planning[END_REF][START_REF] Ratschan | Efficient solving of quantified inequality constraints over the real numbers[END_REF] computes Contract f (x,y)≤0 (x) but cannot achieve any contraction.

Global Pruning. The contraction of x using one constraint removes solutions of this constraint, and therefore solutions of the global CSP. This is illustrated in the first row of Figure 2 where diagrams (a) and (b) show two local contractions leading to x 1′ and x 2′ . The global contraction depicted in Diagram (c) is obtained by computing x 1′ ∩ x 2′ . Of course, in practice we compute this intersection in an incremental way.

Identification of Sets of Solutions

As in [START_REF] Collavizza | Extending Consistent Domains of Numeric CSP[END_REF][START_REF] Ratschan | Approximate quantified constraint solving by cylindrical box decomposition[END_REF][START_REF] Vu | Approximation techniques for non-linear problems with continuum of solutions[END_REF][START_REF] Benhamou | Interval Constraint Solving for Camera Control and Motion Planning[END_REF][START_REF] Ratschan | Efficient solving of quantified inequality constraints over the real numbers[END_REF][START_REF] Vu | Branch-and-prune search strategies for numerical constraint solving[END_REF], the identification of sets of solutions is implemented by applying interval contractors to the negation of the constraints. Again, this process is achieved for each constraint separately. However, now only areas that are proved to be local solutions for all constraints are solutions of the whole CSP.

Identification of Solutions for a Single Constraint. In order to identify parts of a box x which contains only solutions of the constraint ∀y ∈ y i , fi(x, y) ≤ 0, we compute

x i′ , y i′ = Contract f i (x,y)≥0 ( x, y i ), (6)
where x, y stands for the vector (x1, . . . , xn, y1, . . . , ym). Thus, every value of x\x i′ satisfies fi(x, y) < 0 for all values of y in y i . Indeed, the part of x, y i which has been pruned does not contain any solution:

∀x ∈ x ∀y ∈ y i , (x / ∈ x i′ ∨y / ∈ y i′ ) =⇒ ¬(fi(x, y) ≥ 0). (7)
From [START_REF] Collavizza | Comparing Partial Consistencies[END_REF] we have trivially

∀x ∈ x ∀y ∈ y i , x / ∈ x i′ =⇒ fi(x, y) < 0. ( 8
)
This process is illustrated on the following example.

Identification of Solutions of the whole CSP. The x i′

for i ∈ {1, . . . , p} have been computed in such a way that all values of x\x i′ verify ci(x) (cf. the diagrams (d) and (e) of the second row of Figure 2). Thus, the values of x that are outside all x i′ satisfy all the constraints. Formally,

x\(x 1′ ∪ • • • ∪ x p′ ) (9)
contains only solutions of the CSP. This inner approximation ( 9) is the dashed area of Diagram (f) of the second row of Figure 2. Its description becomes very complicated for higher dimensions and when numerous constraints are involved. As in [START_REF] Ratschan | Efficient solving of quantified inequality constraints over the real numbers[END_REF], we use instead the weaker inner approximation

x\(x 1′ ∨ • • • ∨ x p′ ). ( 10
)
This inner approximation is represented on Diagram (g) of the second row of Figure 2. Let us define

x ′ = x 1′ ∨ • • • ∨ x p′ .
The closure1 of x\x ′ is added to the set of inner boxes while x ′ has to be further explored.

Handling Parameter Domains

As said before, the size of the domains of the parameters is a critical issue for an efficient application of interval contractors. This section details the three methods implemented in our algorithm to overcome this problem. The goal of these methods is to only apply interval contractors to parts of the initial parameter domains while keeping the CSP solution set unchanged.

Parameter Domain Pruning

During the identification of solutions ( 6) the domains of the parameters y i are reduced to y i′ . In [START_REF] Benhamou | Interval Constraint Solving for Camera Control and Motion Planning[END_REF][START_REF] Ratschan | Efficient solving of quantified inequality constraints over the real numbers[END_REF], the initial parameter domain is restored, so this contraction of the parameter domains is not propagated. However, this reduced domain can be used while keeping the solution set of the constraint unchanged. Indeed, (7) trivially entails ∀x ∈ x ∀y ∈ (y i \y i′ ) fi(x, y) < 0, [START_REF] Goldberg | What every computer scientist should know about floating-point arithmetic[END_REF] As a consequence, for every fixed x in x, ∀y ∈ y i′ , c(x, y) implies ∀y ∈ y i , c(x, y). Finally, we can replace the latter by the former keeping the solution set unchanged during the solution identification step of the algorithm. This is a significant improvement that is implemented without any overhead since the parameter domains have to be contracted anyway during the solution identification step.

Example 3. In Example 2, the identification of solutions step has contracted the parameter domain from y = [0, 1] to y ′ = [0.475, 1]. This latter domain can be used in future processing while keeping unchanged the CSP solution set.

Parameter Domain Bisection

Bisecting parameter domains is the most obvious way to reduce them. This is a critical issue to improve the convergence of the algorithm. Bisection is also used in [START_REF] Ratschan | Efficient solving of quantified inequality constraints over the real numbers[END_REF] but implemented in a different way. Here, we change the constraint ∀y ∈ y, c(x, y) to the conjunction of the two constraints ∀y ∈ y 1 , c(x, y) and ∀y ∈ y 2 , c(x, y), where y 1 and y 2 are obtained by bisecting y. The following example illustrates how the parameter domain bisection is performed, then it is also non positive in its closure cl(x\x ′ ), e.g. if f (x) ≤ 0 in [-10, -1[∪]1, 10] then f (x) ≤ 0 also holds in [-10, -1] ∪ [START_REF] Benhamou | Universally quantified interval constraints[END_REF][START_REF] Fiorio | Robust performance design of fixed structure controllers for systems with uncertain parameters[END_REF]. Thus, cl(x\x ′ ), which can be described by a simple union of boxes, is recorded instead of x\x ′ . and how it improves the pruning process as well as the identification of solutions. The pruning operator is now applied to each constraint of the store, thus the two contractions Contract f (x,0.25)≤0 (x) and Contract f (x,0.75)≤0 (x) are computed. This leads to x ′ = [6.9375, 15]. The pruning achieved here is sharper than the one computed without bisecting the parameter domains (cf. Example 1).

To identify solutions of this new CSP, we compute (x i′ , y i′ ) = Contract f (x,y)≥0 (x ′ , y i ) for i ∈ {1, 2}. We obtain x 1′ = ∅, y 1′ = ∅, x 2′ = [6.9375, 9.75] and y 2′ = [0.71875, 1]. Finally, x ′ is contracted to x 1′ ∨ x 2′ = [6.9375, 9.75] while cl([6.9375, 15]\[6.9375, 9.75]) = [9.75, 15] is proved to be an inner box. The solution identification is also more efficient thanks to the bisection of the parameter domain (cf. Example 2).

Parameter Instantiation

The constraint ∀y ∈ y, f (x, y) ≤ 0, where y = [y, y], can be simplified if the function f is proved to be monotonic w.r.t. the parameter. Indeed, if f is increasing (resp. decreasing) w.r.t. y, then the quantified constraint is obviously equivalent to the non-quantified constraint f (x, y) ≤ 0 (resp. f (x, y) ≤ 0). The variation of the function can be checked by evaluating its derivative w.r.t. the parameter on the intervals x and y. The same property holds if there are several parameters, using a derivative w.r.t. each parameter.

we prove that f is increasing w.r.t. y. Therefore, the constraint ∀y ∈ y, f (x, y) ≤ 0 is equivalent to f (x, 1) ≤ 0. Then, the pruning contracts x = [0, 15] to [START_REF] Dorato | Robust multi-objective feedback design by quanti er elimination[END_REF][START_REF] Jaulin | Guaranteed tuning, with application to robust control and motion planning[END_REF] and the solution identification proves that [START_REF] Dorato | Robust multi-objective feedback design by quanti er elimination[END_REF][START_REF] Jaulin | Guaranteed tuning, with application to robust control and motion planning[END_REF] contains only solutions. On this simple example, we obtain an exact description of the solution set. This set is much sharper than The parameter instantiation can drastically improve the efficiency of the pruning and the solution identification steps. However, evaluating derivatives can be expensive, in particular when they involve trigonometric function. Experimentation presented in the next section illustrate well this trade-off.

EXPERIMENTATION

This section compares the results of the IPA system described in [START_REF] Benhamou | Interval Constraint Solving for Camera Control and Motion Planning[END_REF], Rsolver [START_REF] Ratschan | Efficient solving of quantified inequality constraints over the real numbers[END_REF] from S. Ratschan with our system, called "Qine", on a set of 9 benches.

The 9 benches come from the literature. The Circle, Path-Point, Parabola, Robot and Satellite QCSPs are taken from [START_REF] Benhamou | Interval Constraint Solving for Camera Control and Motion Planning[END_REF]. A description of Robust1 (respectively, Robust4, Ro-bust5 and Robust6) can be found in [START_REF] Dorato | Quantified multivariate polynomial inequalities[END_REF] (respectively, [START_REF] Malan | Robust analysis and design of control systems using interval arithmetic[END_REF], [START_REF] Jaulin | Guaranteed tuning, with application to robust control and motion planning[END_REF] and [START_REF] Jaulin | Interval methods for nonlinear identification and robust control[END_REF]).

The Rsolver and Qine benches have been run on an Intel Core Duo 2 at 2.4Ghz with a time out of 600s. To limit the effect of the high memory consumption of these algorithms, the available memory has been restricted to 1Gb. Thus, a bench could either succeed to run within these two limits, end with a time out ("-"), or reach the memory limit ("- * ").

Table 1 reports the results obtained with Rsolver and Qine. It gives Rsolver timing, as well as the time required to solve the benches for the different Qine running options :

• "2B" uses the contractor based on 2b-consistency techniques. More precisely, its implementation relies on a forward-backward evaluation of the direct acyclic graph which represents the constraint.

where Vinner is the total volume of the inner boxes, Vouter is the total volume of the outer boxes and V initial is the volume given by the initial domains of the variables. Though all the benches have been run for ratios going from 0.5 to 0.99999, the table gives only the most significant results for the sake of space.

As shown in table 1, in average, Qine outperforms Rsolver by one order of magnitude. For instance, Qine handles the Robust benches immediately while Rsolver needs much for time to do so. A comparison of the different available combinations shows that the "2B+" combination has a more robust behavior. It takes advantage of all the available information and offers a good trade-off between the computation time and the domain reductions. However, on the Satellite bench, 2B performs better than 2B+. This illustrates the trade-off between the cost of derivative computation and the benefit of parameter instantiations.

Tables 2 compares IPA with Qine. IPA system has been run on a Pentium M at 2Ghz running Linux. To allow a fair comparison, we have computed a timing correction : the same system, Rsolver, has been run on both systems in order to determine this correction. Therefore, the initial timing obtained for IPA (column 3) has been multiplied by 0.58 (column 4) to allow a fair comparison between the two systems.

Here again, Qine outperforms IPA. Indeed, IPA was not able to solve the PathPoint bench within the timeout for only one of the tested ratios. However, IPA is faster than Qine on the Satellite bench for the lower ratio values. This behavior is probably due to the limit of the 2B based contractor whose domain reduction capabilities decrease when a variable has multiple occurrences within one constraint. IPA is based on a Box contractor which does not suffer from the same behavior (see [START_REF] Collavizza | Comparing Partial Consistencies[END_REF] for a detailed comparison of 2B and Box). However, when the ratio value increases, Qine becomes faster than IPA. For instance, IPA needs more than 876s (corrected time) to solve the Satellite bench for a ratio of 0.6276 whereas Qine achieves this task with 2B within 401.44s.

Note that the class of QCSPs handled by IPA is limited to one parameter. Thus, IPA is not able to solve the Robust benches.

CONCLUSION

In this paper, we have introduced a new, simple and efficient algorithm to handle a significant class of QCSPs. Examples coming from the literature reveal that this class covers most of the practical applications.

Our algorithm is based on new techniques for handling parameters. It also takes advantage of information provided by the derivatives to improve the contraction of the domains involved in constraints with parameters, a key issue in the efficient solving of QCSPs.

Experimentation underline the efficiency of our algorithm which outperforms two of the available state of the art implementations able to handle such QCSPs. In average, our implementation is by one order of magnitude quicker than the two other systems.

Further work concerns the improvement of the implementation of the contractor by using the best filtering techniques for each type of constraints and the generalization of the use of available information to still enhance the speed of the solving process.

Figure 1 :

 1 Figure 1: On the left hand side, the solution set Sol; on the right hand side, the inner approximation I in light gray and the boundary approximation B in dark gray.

Algorithm 1 : 4 C 5 x 6 ( 7 I 8 C 9 U 14 return

 145678914 Generic Branch and Prune Algorithm Input: C, x, ǫ Output: (I, B) U ← {(C, x)}; B ← {}; I ← {}; 1 while ¬empty(U) do 2 (C, x) ← extract(U); 3 if wid(x) > ǫ then ′ ← ParameterInstantiation(C, x); ′ ← Pruning(C ′ , x); C ′′ , x ′′ , I ′ ) ← SolutionIndentification(C ′ , x ′ ); ← I ∪ I ′ ; ′′′ ← ParameterDomainBisection(C ′′ , x ′′ ); ← U ∪ Branching(C ′′′ , x ′′ ); (I, B); 15 where some parameters have been instantiated (see Subsubsection 3.4.3). Function Pruning() contracts the domain x without loosing any solution of C ′ (see Subsection 3.2).

Example 2 .

 2 Continuing Example 1, let us consider c(x) and x = [4.75, 15]. In order to identify values of x that satisfy c(x), we apply Contract f (x,y)≥0 (x, y) and obtain x ′ = [4.75, 10] and y ′ = [0.475, 1]. Therefore, x\x ′ =]10, 15] contains only solutions of the constraint.

Figure 2 :

 2 Figure 2: Upper row: pruning computed from local contractions. Lower row: identification of solutions using local contractions of the negation of the constraints.

Example 4 .

 4 Let us come back to Example 1 where the constraint store contains only one constraint C = {(∀y ∈ y, f (x, y) ≤ 0)}. Bisecting parameter domains, we obtain the new constraint store C ′ = {(∀y ∈ y 1 , f (x, y) ≤ 0), (∀y ∈ y 2 , f (x, y) ≤ 0)} with y 1 = [0, 0.5] and y 2 = [0.5, 1]. The latter constraint store is equivalent to the original one, but contains more constraints with smaller parameter domains.

Example 5 .

 5 Let us come back to Example 1. Evaluating (∂f /∂y)(x, y) = 10 -2y = [8, 10],

Table 1 :

 1 Timing (in seconds) for Rsolve vs Qine the contractions obtained without this instantiation of the parameter (cf. examples 1 and 2).

				Qine
	problem	ratio	Rsolver	2B	2B+
		0.98	55.67	0.90	1.03
	Circle	0.99	169.51	2.32	2.22
		0.999	-	69.18	31.55
		0.6	122.72	0.01	0.01
	PathPoint	0.65	334.34	0.01	0.02
		0.7	-	0.02	0.03
		0.96	48.33	1.47	1.36
	Parabola	0.97	130.30	2.74	1.92
		0.98	-	8.77	6.59
		0.98	10.34	0.06	0.08
	Robot	0.99	26.74	0.14	0.18
		0.999	-	5.37	4.08
		0.5	303.30	71.36 114.33
	Satellite	0.55	-	168.32 268.36
		0.6	-	227.09 368.90
		0.999	1.10	0.01	0.00
	Robust1	0.9999	7.16	0.04	0.00
		0.99999	76.25	0.10	0.00
		0.5	-	- *	0.00
	Robust4	0.55	-	-	0.01
		0.6	-	-	0.01
		0.7	75.35	0.00	0.00
	Robust5	0.75	80.62	0.00	0.00
		0.8	-	0.01	0.00
		0.7	59.98	0.02	0.00
	Robust6	0.75	224.33	0.05	0.00
		0.8	-	0.09	0.00

The set difference x\x ′ is not closed in general, e.g. [-10, 10]\[-1, 1] = [-10, -1[∪]1, 10]. Nevertheless, we can observe that if f is continuous and non positive in x\x ′ ,

Acknowledgments

We are grateful to Marc Christie for his valuable help in the experimentation.


Jacob Olchowka

Ronan Invernizzi

Alexia Lemoine

Joachim Allouche

Isabelle Baraille

Delphine Flahaut

Liliane Guerlou-Demourgues

Stabilization and Improvement of Energy Storage Performance of High Mass Loading Cobalt Hydroxide Electrode by Surface Functionalization

Keywords: Supercapacitors, Electrochemical energy storage, Surface modification, Cobalt hydroxide, Ionic Liquids

Nano oxides and hydroxides generate great interest as promising positive electrode materials for the development of high energy density supercapacitors. However, their usually limited ionic and electronic conductivities significantly decrease their energy storage performances when increasing the electrode's mass loading. Here, we report on a sonochemical approach to functionalize the surface of Co(OH)2 nanomaterials by EmimBF4 ionic liquid that greatly improves the stability and the electrochemical performances of high mass loading electrodes (13 mg/cm²). This surface functionalization boosts the transport properties and strongly enhances the capacity as well as the capacity retention at higher current densities compared to basic Co(OH)2 (e.g. 113.5 C/g vs. 59.2 C/g at 1 A/g). Additionally, the protective layer formed by the ionic liquid stabilizes the electrode material upon cycling in KOH aqueous electrolyte and protects the material from oxidation upon open-air storage.

One of the biggest challenge in supercapacitor research area consists in increasing their energy density, which is, in the current supercapacitors, still limited for several applications into renewable energy storage or transport sector. A possible way to face this challenge is to develop high capacitance electrodes based on nanostructured pseudocapacitive or battery-like materials. 1 Indeed, the latter materials have the ability to achieve rapid redox reactions that can deliver a higher energy density than adsorption/desorption mechanisms currently observed for carbon-based electrodes used in the commercial EDLC. 2 These last years, different oxides/hydroxides such as RuO2, MnO2, Co3O4, Ni(OH)2, Co(OH)2, NiCo2O4, have been studied for that purpose. 2,3 Among these materials, cobalt hydroxide has attracted attention due to its layered structure that allows a good ionic mobility, its high theoretical capacity (2076 C/g considering 2 electrons exchange) and relatively low cost. Additionally, Deng et al. determined recently that the oxidation/reduction processes generate only minor structural changes enabling excellent rate performances and high cycling life. 4 Cobalt hydroxide can be synthesized in two different phases: the α-form is described as positively charged Co(OH)2-x sheets separated by interlayered anions (NO3 -, Cl -…) to compensate the charge and the brucite-like ß-form of Co(OH)2, which is reported as a hexagonal close-packed structure of hydroxyl ions with Co(II) occupying octahedral interstices one plane out of two. 5,6 In the α-form, the presence of anionic species together with water molecules generates bigger interlayered spacing compared to those in ß-Co(OH)2, however the α-Co(OH)2 is metastable and quickly evolve to ß-form in alkaline solution. 7 Various synthesis approaches such as sol-gel, hydrothermal, precipitation or electrodeposition leading to different original morphologies of nanostructured Co(OH)2 or hybrid carbon-Co(OH)2 materials are reported in the literature. For instance, Ranganatha et al. reported a sol-gel synthesis of mesoporous α-Co(OH)2, 8 Wang et al. synthesized flower-like α-Co(OH)2 by precipitation method, 9 Fu et al grown pine needle ß-Co(OH)2 on nickel foam, 10 and Darbandi et al. communicated on the preparation of ß-Co(OH)2 nanorings by chemical precipitation. 11 Although these electrode materials reported in the literature present most of the time good electrochemical performances and high specific capacities, the active material mass loading used in these studies is usually very low and not adapted for real devices (see Table 1).

In fact, electrode mass loading should be above 10 mg.cm -² in hybrid supercapacitors in order to validate the gravimetric capacity of full devices and the absence of study with adequate mass loading does not allow to evaluate the real potentiality of Co(OH)2 electrode material. 12,13 It is well known that increasing mass loading leads usually to increase the charge transfer resistance and to slow down ionic diffusion, that finally lowers the specific capacity. 14,15 For instance Jagadale et al. reported for α-Co(OH)2 a drastic drop in capacitance from 386.4 F.g -1 (193 C.g - 1 ) to 150 F.g -1 (75 C.g -1 ) for a slight increase in electrode active mass loading (from 2.5 to 3.1 mg.cm -²). 16 Similarly, Ranganatha et al. have shown that the specific capacitance is consequently lowered when increasing mass loading levels (mass loading of 0.5-0.6 mg.cm -², 2.4-2.5 mg.cm -² and 4.7-4.8 mg.cm -² lead to a capacitance of ~ 450 F.g -1 , ~ 270 F.g -1 and ~ 150 F.g -1 respectively). 17 To face this problem and optimize the transport properties, the surface modification of the active material could be an ideal issue. For instance, a surface modification by ionic liquids (IL) "functionalization" can reshape the surface properties or bring new ones (e.g. hydrophobicity), alter the interface reactivity or reduce the surface defects. [18][19][20] Concerning the conduction properties, the group of Tarascon found that LiZnSO4F-IL, synthesized by ionothermal approach, exhibits a RT ionic conductivity four orders of magnitude higher than the basic LiZnSO4F. 21 Interestingly, Choi et al. have also demonstrated by DFT calculations that the functionalization of Co(OH)2 surface by the BmimBF4 ionic liquid permits faster ion diffusion and easier hydrogen adsorption/desorption processes on Co(OH)2. 22 However, in their work, the synthesized nanohybrid material, Co(OH)2-IL, has a different size/morphology and a 6 time higher specific surface area than their benchmark Co(OH)2, which makes impossible to evaluate experimentally the sole influence of the surface modification on the ionic diffusion and energy storage performances. 22 Additionally, the mass loading of their electrode was not high enough for practical application. In this work, we develop a sonochemical assisted method to synthesize Co(OH)2-IL nanohybrids and investigate the influence of the surface functionalization on the energy storage performances of high mass loading electrodes (13 mg.cm -²), by comparing Co(OH)2-IL with the benchmark Co(OH)2 material of similar size/morphology. EmimBF4 (1-ethyl-3-methylimidazolium tetrafluoroborate) was chosen for this study due to its higher conductivity compared to BmimBF4 (1-butyl-3-methylimidazolium tetrafluoroborate) and other imidazolium based ionic liquids with longer alkyl chains. 23 Synthesis: Co(OH)2-IL was prepared by ionic liquid assisted sonochemical method. In a first step, 3.18 g of Co(NO3)2.6H2O were dissolved in a mixture of 5 mL of H2O, 5 mL of ethanol and 2 mL of EmimBF4 (1-ethyl-3-methylimidazolium tetrafluoroborate), then 10 mL of 3M NaOH was added to the cobalt solution. Immediately after the addition, the solution was sonicated during 30 min (with pulses of 7 s "on" and 3 s "off"). The pink powder was then collected by centrifugation, washed several times in ethanol and dried at 60°C overnight. The same procedure was done without IL to obtain the benchmark Co(OH)2.

XRD analyses: A Philips Panalytical X'Pert Pro diffractometer was used to record X-ray powder diffraction patterns. A Co Kα radiation was used in order to avoid fluorescence problematic with traditional Copper sources and to generate high quality patterns. The powder diffraction patterns were recorded for about 4 h in the 10°-110° (2θ) angular range, with a 0.0167° (2θ) step size and a 2.122° (2θ) active width in the detector.

Scanning electron microscopy (SEM) images were taken on the metallized samples (Pddeposited) by a Hitachi Model S-4500 microscope.

Fourier transform infrared (FT-IR) spectra were recorded by using a Bruker Equinox 55 spectrometer in the wavenumber range of 400-4000 cm -1 (mid-IR) with a resolution of 4 cm -1 .

The samples were finely ground in a mortar with dried KBr in an approximate ratio of 1: 40 (by wt.%).

XPS experiment: The X-ray photoelectron spectroscopy analyses (XPS) were performed with the Thermo K-alpha spectrometer with a hemispherical analyzer and a microfocussed monochromatized radiation Al Kα line (1486.6 eV) operating at 75 W under a residual pressure of 1 x 10 -7 mBar. The analysis area was ca. 200 μm 2 and a pass energy of 20 eV was used for core peak records. The use of neutralizer gun, which sprays the low energy electrons and Ar + ions over the sample surface, to minimize the surface charging was necessary. All the binding energies were referenced to the C 1s peak at 285.0 eV originating from the adventitious carbon (always detected at surface of materials). Core peaks were analysed using a nonlinear Shirleytype background and peak positions and areas were obtained by a weighted least-squares fitting of model curves (70% Gaussian, 30% Lorentzian) to the experimental date. Quantification of surface composition was based on Scofield's relative sensitivity factors. 24 The Auger Electron Spectroscopy (AES) analyses were carried out with a JEOL JAMP 9500F Auger spectrometer (JEOL Ltd, Tokyo, Japan) working under UHV conditions (pressure < 2.10 -7 Pa). The UHV equipment was a Schottky field emission Auger electron spectrometer (FE-AES) allowing a high lateral resolution (∼ 10 nm) analysis and a high brightness.

AES spectra (kinetic energy from 0 to 1000 eV) were carried out at a constant retarding ratio Results: Both syntheses (with and without ionic liquid) lead to pure and well crystallized ß-Co(OH)2 as it is confirmed by X-ray diffraction (see Figure 1a) and deduced from the pink color of the polycrystalline powders. The presence of the ionic liquid during the sonochemical synthesis does not influence the nature of the polymorph as in the hydrothermal synthesis reported by Jana et al. 25 and has no influence on the morphology as in the synthesis approach reported by Choi et al. 22 Indeed, figure 2 shows that both Co(OH)2 and Co(OH)2-IL are characterized by polydispersed platelets with a width ranging from about 50 to 300 nm. During the synthesis, the ionic liquid does not hinder the platelets growing and/or Ostwald ripening that should be induced by the heating of the synthesis media and particle's collision generated by ultrasound radiations. 26 In fact, the precipitation of Co(OH)2 happens directly after introducing the sodium hydroxide in the cobalt solution (see Figure S1) and the IL is rather used as reactant to generate the surface modification. Additional experiments reveal that the αpolymorph can also be formed with this synthesis method by replacing Co(NO)3.6H2O by CoCl2 (see Figure S2).

Figure 1b shows the infrared spectra of Co(OH)2 and Co(OH)2-IL. For both materials, the sharp band at ~3629 cm -1 (νOH: stretching of the free hydroxyl groups) and the broad signal peaking at 530 cm -1 attributed to Co-O stretching perfectly fit with to the spectrum of ß-Co(OH)2. 27 For Co(OH)2-IL, the additional signals corresponding to νB-F (~1084 cm -1 ), νC-N (~1569 cm -1 ) and νC-H (between 2900 and 3200 cm -1 ) confirm the presence of EmimBF4 even after several washing steps, 18,28 whereas the low intensity peak at 2425 cm -1 could be attributed to boron-oxygen bonds. These latter might be formed by the reaction between the decomposition products of BF4 -and the solvent, indeed BF4 -can be partially decomposed under ultrasonic radiation and generate F -ions. 18,29 The band around 1384 cm -1 belongs to N-O stretching vibrations of nitrates that are adsorbed on the particle surface of Co(OH)2 during the synthesis. 4 XPS survey has been first recorded, and the orbitals of the elements coming from the Co(OH)2 materials and from the ionic liquid have been detected (see Figure 3). High-resolution spectra have also been obtained for all the orbitals of the elements detected. The corresponding binding energies (B.E.) and atomic percentages are reported in Table 2.

Co 2p spectrum exhibits two main components due the spin-orbit coupling located, respectively, at 780.5 eV for the Co 2p3/2 and 797.0 eV for the Co2p1/2. Two large peaks, assigned to shake-up satellites, located at 5.7 eV toward the higher binding energies can also been detected. Lower satellites are also observed at 790.6 eV and 806.5 eV. The energy position, the FWHM and the area ratio between the satellites and the main component (ICo2psat/ICo2pmain) ~ 0.8) indicates that the cobalt is in the +2 oxidation state in a hydroxyl environment. 30 The O1s spectrum is decomposed in three components: the hydroxyl groups of the bulk materials is assigned to the major component at 531. The N 1s, F 1s and B 1s core peaks are directly associated to the presence of the ionic liquid on the Co(OH)2 surface. The BF4 -environment is assigned, from the literature, 31 to the component located at 194.6 eV. The second component at 192.0 eV should be due to the boron atom in an oxygenated environment. This latter supports the partial decomposition of the BF4 -upon sonification as deduced from IR spectrum (see Figure 1b). Two components are also detected in the F 1s core peaks one at 686.5 eV for the fluorine in the BF4 -anions, and the other at 684.3 eV due to chemisorbed fluorine on the material surface. 32 The ratio between the fluorine and the boron assigned to the "BF4 -" environment reaches 3.2. The imidazolium N 1s signal of the cation is well detected at 401.9 eV in accordance with the literature. 33 The C 1s spectrum (not shown here) exhibits three components attributed to the hydrocarbonated species (285 eV), the C-O and C-N environments (286.5eV) and the adsorbed species (289.2 eV).

Finally, in addition to the Infrared data, the XPS analyses confirm the grafting of the ionic liquid on the Co(OH)2 materials surface with a I(N 1s401.9) / I(Co 2p) ratio of 0.08. These results are also supported by Auger analyses revealing on several single Co(OH)2 particles nitrogen and boron signals corresponding to the ionic liquid fingerprint (see Figure S3).

In order to investigate the effect of the surface modification on the energy storage performances, galvanostatic charge/discharge (GCD), cyclic voltammetry (CV) as well as electrochemical impedance spectroscopy (EIS) measurements were performed on both Co(OH)2 and Co(OH)2-IL electrode materials. The influence of the nickel foam on the capacity was investigated and can be considered as negligible (see Figure S4). The CV curves (see Figure 4a) show that the two materials present two highly reversible oxidation peaks that might be assigned, according to the literature, to the oxidation of Co and leading to HxCoO2 phases. 34,35 The functionalization of Co(OH)2 surface by EmimBF4 triggers higher intensity oxidation and reduction peaks, leading to a higher capacity. Additionally, it seems to induce a slight shift of the redox peaks that lowers the polarization upon cycling (especially for P2/P'2: 0.12 V and 0.085 V for Co(OH)2 and Co(OH)2-IL respectively), suggesting a higher reversibility and better kinetics. The GCD curves (see Figure 4b) confirm the battery-like signature and the increased specific capacity for the hybrid material. This latter, evaluated from the discharge curve, is 113.5 C/g at 1 A/g for Co(OH)2-IL against 59.2 C/g at 1 A/g for Co(OH)2. Besides the capacity is nearly doubled for the functionalized material, the capacity retention when increasing the current density is also improved (see Figure 4c-d). For instance at 5 A/g, the capacity is maintained at 96.8 C/g (85.7% of capacity retention compared to the capacity at 1 A/g) whereas it is only at 39 C/g (67% of capacity retention) for the bare Co(OH)2.

In order to deeper investigate the effect of the ionic liquid, CV measurements at various scan rate were performed (see Figure S5). The evolution of the intensity versus the scan rate was further analyzed using the power-law relation (equation ( 1)):

𝑖(𝑉) = 𝛼ν 𝑏 ( 1
)
Here i is the intensity at a defined potential V, Indeed, a synergic effect happens between the Co(OH)2 and the EmimBF4 which has a high intrinsic conductivity (15 mS.cm -²) that optimizes the transport properties of the hybrid material. 39 These obtained results fit well to the theoretical calculations, which conclude that the adsorption/desorption of the proton is facilitated by the ionic liquid. 22 For a better comprehension of the interfacial processes, EIS measurements were performed at open-circuit potential. Nyquist plots of Co(OH)2 and Co(OH)2-IL, represented figure 5c, are characterized by a semi-circle at high frequencies corresponding to the charge transfer resistance (RCT) at the interfaces and a slope at low frequencies assigned to Warburg impedance (ZW). The trend of the RCT value, obtained using the equivalent circuit represented in the inset, suggests that the ionic liquid optimizes the interfacial exchanges (RCT = 1.35 Ω and 1.9 Ω for Co(OH)2-IL and Co(OH)2 respectively) (See Table S1 for data refinement). Although the particle's size and morphology as well as the cationic part of the ionic liquid differ, these values are close to the ones reported by Choi et al. (1.53 Ω and 2.59 Ω for the nanohybrids and the bare material respectively). The hydrid material electrode presents also better diffusion properties that are characterized by a more vertical Warburg slope at low frequencies (Figure 5c). Finally, the surface modification induces a better stability of the electrode material upon long-term cycling and thus, a better capacity retention. Indeed, for Co(OH)2-IL the charge transfer resistance does not evolve after 5000 cycles at 2 A/g whereas it strongly increases for Co(OH)2 (Figure 5c and Table S1). Similarly, the impact of long-term cycling on the ionic diffusion is detrimental for Co(OH)2 whereas it is nearly negligible for Co(OH)2-IL. Figure 5d shows the capacity evolution for both electrode materials upon long-term cycling performed at 2 A/g in 5M-KOH. For Co(OH)2-IL, the slight increase of capacity (from 105 to 110 C/g) that happens during the first 500 cycles can be attributed to an activation process. Then, the capacity remains nearly constant during 5000 cycles, which, together with the excellent coulombic efficiency, attest the great electrode material stability already observed by EIS. On the other hand, the capacity of Co(OH)2 progressively decreases upon cycling to reach a capacity retention of 73% after 5000 cycles. Thus, it can be reasonably supposed that the electrode material directly starts to degrade upon cycling. From the EIS and long-term cycling analyses, it can be assumed that the better transport properties for Co(OH)2-IL prevent from mechanical constraints that induce a degradation of the material upon cycling It is very important to highlight that the surface functionalization of Co(OH)2 nanomaterials not only improves the stability upon long-term cycling and the energy storage performance, but it also protects the material against moisture and oxidation under air. Figure 1a phase becomes black (see Figure S6) and is completely oxidized in a mixture of HCoO2 and spinel Co3O4 whereas Co(OH)2-IL is perfectly stable. 40 This induces that the IL acts as a protective layer against oxidation and it seems to cover homogeneously the material since no structural evolution could be detected after 8-month air exposure.

α
To summarize, the XPS, Auger and infrared analyses confirmed that we were able to functionalize the surface of Co(OH)2 with EMIMBF4 ionic liquid. The comparison of energy storage performances with the not functionalized material shows that this surface modification produces a synergetic effect between the highly conductive ionic liquid and the Co(OH)2 extremely beneficial for the electrode material. As demonstrated by the electrochemical measurements, it enhances the transport properties leading to a better ionic diffusion within the high mass loading electrode. This optimization leads to nearly double the specific capacity at 1 A/g and strongly improves the capacity retention at higher current densities. Moreover, the full capacity retention after 5000 cycles and the comparison of EIS data before and after the longterm cycling have shown that the protective ionic liquid layer stabilizes the material upon cycling. Additionally, the XRD measurements exhibit that this latter protects the material against oxidation/decomposition during the open-air storage. Finally, this work supports the fact that surface modifications have great influence on the energy storage properties and represent a promising strategy to optimize and control the electrochemical performances of electrode materials.

Notes

The authors declare no competing financial interest.

Figures and Tables

(

  CRR) mode with dE/E = 0.5% (high sensibility) at an acceleration voltage of 15 keV and a probe current of 5 nA (working distance = 23 mm and sample tilt angle = 30°). Scanning Auger Maps (SAM) were recorded at constant retarding ratio (CAE) operating conditions and an acceleration voltage of 15 keV with a probe current of 5 nA (working distance = 23 mm and sample tilt angle = 30°). Electrochemical measurements were performed in aqueous 5M-KOH electrolytes in a three electrode mode at room temperature. Platinum wire was used as counter electrode whereas Hg/HgO was used as reference electrode in the basic electrolyte. The working electrodes were prepared with a mixture of active material / carbon black / polytetrafluoroethylene in a weight ratio of 80/15/5. A disk of about 7 mm diameter of the electrode material, with a weight of ~8 mg, was pressed during 30 s at 5 bars on a nickel foam (current collector). It results in a 8 mm disk and hence an active material loading of ~13 mg/cm 2 . The three electrodes (working electrode, reference electrode and counter electrode) were placed in the electrolyte in order to form an equilateral triangle and each electrode was separated from the two others by ≈ 16 mm. Electrochemical impedance measurements were performed under open-circuit condition. A small AC perturbation amplitude of 10 mV versus the open-circuit potential was applied in a frequency range from 50 kHz down to 0.1 Hz. Cyclic Voltammetry (CV), Constant Current Charge/Discharge (CCCD) and Electrochemical Impedance Spectroscopy (EIS) were performed using a EC-lab potentiostat.

  1 eV. Two other minor components are attributed to oxide (B.E. O 1s = 529.1 eV) and oxygen from adsorbed species (B.E. O 1s = 532.5 eV).

  Figure5a), which corresponds mainly to a faradaic region, the b-value of 0.5 for Co(OH)2 traduces a purely semi-infinite diffusion mechanism whereas the surface functionalization of Co(OH)2 by EmimBF4 leads to a b-value of 0.72. This higher b-value suggests a more surface limited charge storage mechanism and/or limited diffusion mechanism. At E = 0.33 V (see Figure5b), which should rather correspond to (pseudo)capacitive region, the b-value of 1 for Co(OH)2-IL confirms a surface limited process whereas the lower b-value (0.68) is rather characteristic of a finite diffusion process. Although the high mass loading electrodes (13 mg.cm 2 ) may influence the b-value, in both regions Co(OH)2-IL presents better kinetics.

  shows the XRD patterns of both Co(OH)2 and Co(OH)2-IL after 8-month open air storage. The bare Co(OH)2

  Figure 1. a) XRD pattern of Co(OH)2-IL (red) and Co(OH)2 (black), and the materials after 8-month air exposure b) Infrared spectra of Co(OH)2-IL (red) and Co(OH)2 (black).

Figure 2 .

 2 Figure 2. SEM images of a) Co(OH)2-IL and b) Co(OH)2, the tick corresponds to 300 nm.

Figure 4 .

 4 Figure 4. a) Cyclic voltammetry curves measured in 5M-KOH at 5 mV/s for Co(OH)2 and Co(OH)2-IL b) Galvanostatic charge and discharge curves of Co(OH)2 and Co(OH)2-IL at 1 A/g in 5M-KOH c) Capacity retention versus current density. 5 cycles at each current density were performed and the 4 last cycles are plotted d) Galvanostatic charge and discharge curves of Co(OH)2-IL at different current density.

Figure 5 .

 5 Figure 5. Evolution of the intensity versus the scan rate for Co(OH)2 and Co(OH)2-IL a) at the cathodic voltage of 0.15 V and b) at the cathodic voltage of 0.33 V c) Nyquist plots of Co(OH)2 and Co(OH)2-IL performed before and after 5000 GCD cycles at 2 A/g d) Evolution of the capacity and the coulombic efficiency for Co(OH)2 and Co(OH)2-IL upon 5000 cycles performed at 2 A/g in 5M-KOH.

Table 1 :

 1 Comparison of the performances of different Co(OH)2 extracted from the literature. For a better comparison, all the capacity values are reported here in Coulomb per gram.

	Phase	Electrolyte Capacity	Scan rate Loading mass Ref
	α-Co(OH)2	6M KOH	430 C/g	1 A/g	0.8-1 mg/cm² 8
	ß-Co(OH)2	6M KOH	426 C/g (1066 F/g)*0.4	2 A/g	2 mg/cm²	25
	α-Co(OH)2	6M KOH	245 C/g (613 F/g)*0.4	2 A/g	2 mg/cm²	25
	Co(OH)2	1M KOH	225 C/g (562 F/g)*0.4	0.1 mA/g 0.14 mg/cm²	41
	α-Co(OH)2	2M KOH	343 C/g (429 F/g)*0.8	1 A/g	5 mg/cm²	9
	ß-Co(OH)2	1M KOH	250 C/g (416 F/g)*0.6	1 A/g	Not mentioned 42
	α-Co(OH)2	1M LiOH	193 C/g (386 F/g)*0.5	0.4 A/g	2.5 mg/cm²	16
	ß-Co(OH)2	6M KOH	108.5 C/g (217 F/g)*0.5	0.1 A/g	Not mentioned 43
	ß-Co(OH)2	6M KOH	38 C/g (94 F/g)*0.4	1 A/g	2 mg/cm²	44
	ß-Co(OH)2	6M KOH	192 C/g (480 F/g)*0.4	1 A/g	2 mg/cm²	44
	/graphene
	ß-Co(OH)2	6M KOH	216.5 C/g (433 F/g)*0.5	0.1 A/g	Not mentioned 43
	/graphene
	ß-Co(OH)2	1M KOH	412 C/g (1030 F/g)*0.4	9.09 A/g	0.92 mg/cm²	45
	/graphene
	Co(OH)2/grap	2M KOH	257 C/g (367 F/g)*0.7	1 A/g	2.6 mg/cm²	46
	hene/chitosan
	ß-Co(OH)2	2M KOH	303 C/g	1 A/g	1 mg/cm²	47
	/CMC
	ß-Co(OH)2	6M KOH	175.5 C/g (351 F/g)*0.5	1 A/g	1.8 mg/cm²	48
	ß-Co(OH)2	1M KOH	75 C/g (166.7 F/g)*0.45	1 A/g	1.65 mg/cm²	49
	ß-Co(OH)2	2M KOH	534 C/g (1186 F/g)*0.45	1 A/g	4 mg/cm²	50
	/CNF
	ß-Co(OH)2	2M KOH	228.5 C/g	1 A/g	1.86 mg/cm²	51
	/CNT
	α-Co(OH)2	1M KOH	260 C/g (473 F/g)*0.55	2 A/g	0.74 mg/cm²	52
	α-Co(OH)2	0.5M KOH 218.4 C/g (273 F/g)*0.8	0.75 A/g	1.33 mg/cm²	53
	ß-Co(OH)2	1M KOH	534.7 C/g (891.2 F/g)*0.6 1 A/g	5.42 mg/cm²	54
	Co2(OH)3Cl	3M KOH	292.5 C/g (450 F/g)*0.65 2 A/g	~0.5 g/cm²	17
	ß-Co(OH)2-IL 5M KOH	113.5 C/g	1 A/g	13 mg/cm²	This work

Table 2 :

 2 Binding Energies (eV) and atomic percentages (at. %) of Co(OH)2-IL.

	Orbitals	B.E. (eV)	at. %	Assignments
	C 1s	285.0	25.3	C-C, C-H
		286.6	8.3	C-O, C-N
		289.1	2.2	CO2
			34.0
	O 1s	529.1	0.5	oxide O 2-
		531.1	33.9	Co(OH)2
		532.5	5.4	Adsorbed species
			37.3
	N 1s	398.8	0.4	C=N=C
		400.0	0.5	N-C
		401.9	1.1	imidazolium
			1.8
	F 1s	684.3	1.0	Chemisorbed F-Co
		686.5	3.5	BF4-
			4.2
	B 1s	192.0	0.5	BOx
		194.6	1.1	BF4-
			1.6
	Na 1s	1071.9	2.0
	Co 2p3/2-1/2	780.5-797.0	14.4	Co +2 (OH)2

Acknowledgements:

The authors thank the financial support of Région Nouvelle Aquitaine and of the French National Research Agency (STORE-EX Labex Project ANR-10-LABX-76-01). The authors also want to thank Cathy DENAGE, Emmanuel Petit and Eric LEBRAUD (ICMCB) for her help with SEM, ICP-OES and XRD respectively.