E Bergou

Y Diouane

S Gratton
email: serge.gratton@enseeiht.fr

A Line-Search Algorithm Inspired by the Adaptive Cubic Regularization Framework and Complexity Analysis

Keywords: Nonlinear optimization, unconstrained optimization, line-search methods, adaptive regularized framework using cubics, trust-region methods, worst-case complexity

Adaptive regularized framework using cubics has emerged as an alternative to line-search and trust-region algorithms for smooth nonconvex optimization, with an optimal complexity amongst second-order methods. In this paper, we propose and analyze the use of an iteration dependent scaled norm in the adaptive regularized framework using cubics. Within such scaled norm, the obtained method behaves as a line-search algorithm along the quasi-Newton direction with a special backtracking strategy. Under appropriate assumptions, the new algorithm enjoys the same convergence and complexity properties as adaptive regularized algorithm using cubics. The complexity for finding an approximate first-order stationary point can be improved to be optimal whenever a second order version of the proposed algorithm is regarded. In a similar way, using the same scaled norm to define the trust-region neighborhood, we show that the trust-region algorithm behaves as a line-search algorithm. The good potential of the obtained algorithms is shown on a set of large scale optimization problems.

Introduction

An unconstrained nonlinear optimization problem considers the minimization of a scalar function known as the objective function. Classical iterative methods for solving the previous problem are trust-region (TR) [START_REF] Conn | Trust-Region Methods[END_REF][START_REF] Yuan | Recent advances in trust region algorithms[END_REF], line-search (LS) [START_REF] Dennis | Numerical methods for unconstrained optimization and nonlinear equations[END_REF] and algorithms using cubic regularization. The latter class of algorithms has been first investigated by Griewank [START_REF] Griewank | The modification of Newton's method for unconstrained optimization by bounding cubic terms[END_REF] and then by Nesterov and Polyak [START_REF] Nesterov | Cubic regularization of Newton's method and its global performance[END_REF]. Recently, Cartis et al [START_REF] Cartis | Adaptive cubic regularisation methods for unconstrained optimization. Part I: Motivation, convergence and numerical results[END_REF] proposed a generalization to an adaptive regularized framework using cubics (ARC).

The worst-case evaluation complexity of finding an ǫ-approximate first-order critical point using TR or LS methods is shown to be computed in at most O(ǫ -2 ) objective function or gradient evaluations, where ǫ ∈]0, 1[ is a user-defined accuracy threshold on the gradient norm 1 [START_REF] Nesterov | Introductory Lectures on Convex Optimization[END_REF][START_REF] Gratton | Recursive trust-region methods for multiscale nonlinear optimization[END_REF][START_REF] Cartis | Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained optimization[END_REF]. Under appropriate assumptions, ARC takes at most O(ǫ -3/2 ) objective function or gradient evaluations to reduce the gradient of the objective function norm below ǫ, and thus it is improving substantially the worst-case complexity over the classical TR/LS methods [START_REF] Cartis | Adaptive cubic overestimation methods for unconstrained optimization. Part II: worst-case function-and derivative-evaluation complexity[END_REF]. Such complexity bound can be improved using higher order regularized models, we refer the reader for instance to the references [START_REF] Birgin | Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models[END_REF][START_REF] Cartis | Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization[END_REF].

More recently, a non-standard TR method [START_REF] Curtis | A trust region algorithm with a worst-case iteration complexity of O(ǫ -3/2 ) for nonconvex optimization[END_REF] is proposed with the same worst-case complexity bound as ARC. It is proved also that the same worst-case complexity O(ǫ -3/2 ) can be achieved by mean of a specific variable-norm in a TR method [START_REF] Martínez | Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization[END_REF] or using quadratic regularization [START_REF] Birgin | The use of quadratic regularization with a cubic descent condition for unconstrained optimization[END_REF]. All previous approaches use a cubic sufficient descent condition instead of the more usual predicted-reduction based descent. Generally, they need to solve more than one linear system in sequence at each outer iteration (by outer iteration, we mean the sequence of the iterates generated by the algorithm), this makes the computational cost per iteration expensive.

In [START_REF] Bergou | On the use of the energy norm in trust-region and adaptive cubic regularization subproblems[END_REF], it has been shown how to use the so-called energy norm in the ARC/TR framework when a symmetric positive definite (SPD) approximation of the objective function Hessian is available. Within the energy norm, ARC/TR methods behave as LS algorithms along the Newton direction, with a special backtracking strategy and an acceptability condition in the spirit of ARC/TR methods. As far as the model of the objective function is convex, in [START_REF] Bergou | On the use of the energy norm in trust-region and adaptive cubic regularization subproblems[END_REF] the proposed LS algorithm derived from ARC enjoys the same convergence and complexity analysis properties as ARC, in particular the first-order complexity bound of O(ǫ -3/2 ). In the complexity analysis of ARC method [START_REF] Cartis | Adaptive cubic overestimation methods for unconstrained optimization. Part II: worst-case function-and derivative-evaluation complexity[END_REF], it is required that the Hessian approximation has to approximate accurately enough the true Hessian [4, Assumption AM.4], obtaining such convex approximation may be out of reach when handling nonconvex optimization. This paper generalizes the proposed methodology in [START_REF] Bergou | On the use of the energy norm in trust-region and adaptive cubic regularization subproblems[END_REF] to handle nonconvex models. We propose to use, in the regularization term of the ARC cubic model, an iteration dependent scaled norm. In this case, ARC behaves as an LS algorithm with a worst-case evaluation complexity of finding an ǫ-approximate first-order critical point of O(ǫ -2 ) function or gradient evaluations. Moreover, under appropriate assumptions, a second order version of the obtained LS algorithm is shown to have a worst-case complexity of O(ǫ -3/2 ).

The use of a scaled norm was first introduced in [8, Section 7.7.1] for TR methods where it was suggested to use the absolute-value of the Hessian matrix in the scaled norm, such choice was described as "the ideal trust region" that reflects the proper scaling of the underlying problem. For a large scale indefinite Hessian matrix, computing its absolute-value is certainly a computationally expensive task as it requires a spectral decomposition. This means that for large scale optimization problems the use of the absolute-value based norm can be seen as out of reach. Our approach in this paper is different as it allows the use of subspace methods.

In fact, as far as the quasi-Newton direction is not orthogonal with the gradient of the objective function at the current iterate, the specific choice of the scaled norm renders the ARC subproblem solution collinear with the quasi-Newton direction. Using subspace methods, we also consider the large-scale setting when the matrix factorizations are not affordable, implying that only iterative methods for computing a trial step can be used. Compared to the classical ARC, when using the Euclidean norm, the dominant computational cost regardless the function evaluation cost of the resulting algorithm is mainly the cost of solving a linear system for successful iterations. Moreover, the cost of the subproblem solution for unsuccessful iterations is getting inexpensive and requires only an update of a scalar. Hence, ARC behaves as an LS algorithm along the quasi-Newton direction, with a special backtracking strategy and an acceptance criteria in the sprite of ARC algorithm.

In this context, the obtained LS algorithm is globally convergent and requires a number of iterations of order ǫ -2 to produce an ǫ-approximate first-order critical point. A second order version of the algorithm is also proposed, by making use of the exact Hessian or at least of a good approximation of the exact Hessian, to ensure an optimal worst-case complexity bound of order ǫ -3/2 . In this case, we investigate how the complexity bound depends on the quality of the chosen quasi-Newton direction in terms of being a sufficient descent direction. In fact, the obtained complexity bound can be worse than it seems to be whenever the quasi-Newton direction is approximately orthogonal with the gradient of the objective function. Similarly to ARC, we show that the TR method behaves also as an LS algorithm using the same scaled norm as in ARC. Numerical illustrations over a test set of large scale optimization problems are given in order to assess the efficiency of the obtained LS algorithms.

The proposed analysis in this paper assumes that the quasi-Newton direction is not orthogonal with the gradient of the objective function during the minimization process. When such assumption is violated, one can either modify the Hessian approximation using regularization techniques or, when a second order version of the LS algorithm is regarded, switch to the classical ARC algorithm using the Euclidean norm until this assumption holds. In the latter scenario, we propose to check first if there exists an approximate quasi-Newton direction, among all the iterates generated using a subspace method, which is not orthogonal with the gradient and that satisfies the desired properties. If not, one minimizes the model using the Euclidean norm until a new successful outer iteration is found.

We organize this paper as follows. In Section 2, we introduce the ARC method using a general scaled norm and derive the obtained LS algorithm on the base of ARC when a specific scaled norm is used. Section 3 analyses the minimization of the cubic model and discusses the choice of the scaled norm that simplifies solving the ARC subproblem. Section 4 discusses first how the iteration dependent can be chosen uniformly equivalent to the Euclidean norm, and then we propose a second order LS algorithm that enjoys the optimal complexity bound. The section ends with a detailed complexity analysis of the obtained algorithm. Similarly to ARC and using the same scaled norm, an LS algorithm in the spirit of TR algorithm is proposed in Section 5. Numerical tests are illustrated and discussed in Section 6. Conclusions and future improvements are given in Section 7.

2 ARC Framework Using a Specific M k -Norm

ARC Framework

We consider a problem of unconstrained minimization of the form

min x∈R n f (x), (1)
where the objective function f : R n → R is assumed to be continuously differentiable. The ARC framework [START_REF] Cartis | Adaptive cubic regularisation methods for unconstrained optimization. Part I: Motivation, convergence and numerical results[END_REF] can be described as follows: at a given iterate x k , we define m Q k : R n → R as an approximate second-order Taylor approximation of the objective function f around x k , i.e.,

m Q k (s) = f (x k ) + s ⊤ g k + 1 2 s ⊤ B k s, (2)
where g k = ∇f (x k ) is the gradient of f at the current iterate x k , and B k is a symmetric local approximation (uniformly bounded from above) of the Hessian of f at x k . The trial step s k approximates the global minimizer of the cubic model

m k (s) = m Q k (s) + 1 3 σ k s 3 M k , i.e., s k ≈ arg min s∈R n m k (s), (3)
where . M k denotes an iteration dependent scaled norm of the form x M k = x ⊤ M k x for all x ∈ R n and M k is a given SPD matrix. σ k > 0 is a dynamic positive parameter that might be regarded as the reciprocal of the TR radius in TR algorithms (see [START_REF] Cartis | Adaptive cubic regularisation methods for unconstrained optimization. Part I: Motivation, convergence and numerical results[END_REF]). The parameter σ k is taking into account the agreement between the objective function f and the model m k .

To decide whether the trial step is acceptable or not a ratio between the actual reduction and the predicted reduction is computed, as follows:

ρ k = f (x k ) -f (x k + s k ) f (x k ) -m Q k (s k ) . ( 4
)
For a given scalar 0 < η < 1, the k th outer iteration will be said successful if ρ k ≥ η, and unsuccessful otherwise. For all successful iterations we set x k+1 = x k + s k ; otherwise the current iterate is kept unchanged x k+1 = x k . We note that, unlike the original ARC [START_REF] Cartis | Adaptive cubic regularisation methods for unconstrained optimization. Part I: Motivation, convergence and numerical results[END_REF][START_REF] Cartis | Adaptive cubic overestimation methods for unconstrained optimization. Part II: worst-case function-and derivative-evaluation complexity[END_REF] where the cubic model is used to evaluate the denominator in (4), in the nowadays works related to ARC, only the quadratic approximation m Q k (s k ) is used in the comparison with the actual value of f without the regularization parameter (see [START_REF] Birgin | Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models[END_REF] for instance). Algorithm 1 gives a detailed description of ARC.

Algorithm 1: ARC algorithm.

Data: select an initial point x 0 and the constant 0 < η < 1. Set the initial regularization σ 0 > 0 and σ min ∈]0, σ 0 ], set also the constants 0 < ν 1 ≤ 1 < ν 2 . for k = 1, 2, . . . do Compute the step s k as an approximate solution of (3) such that

m k (s k ) ≤ m k (s c k ) (5)
where

s c k = -δ c k g k and δ c k = arg min t>0 m k (-tg k ) ; if ρ k ≥ η then Set x k+1 = x k + s k and σ k+1 = max{ν 1 σ k , σ min }; else Set x k+1 = x k and σ k+1 = ν 2 σ k ; end end
The Cauchy step s c k , defined in Algorithm 1, is computationally inexpensive compared to the computational cost of the global minimizer of m k . The condition (5) on s k is sufficient for ensuring global convergence of ARC to first-order critical points.

From now on, we will assume that first-order stationarity is not reached yet, meaning that the gradient of the objective function is non null at the current iteration k (i.e., g k = 0). Also,

• will denote the vector or matrix ℓ 2 -norm, sgn(α) the sign of a real α, and I n the identity matrix of size n.

An LS Algorithm Inspired by the ARC Framework

Using a specific M k -norm in the definition of the cubic model m k , we will show that ARC framework (Algorithm 1) behaves as an LS algorithm along the quasi-Newton direction. In a previous work [START_REF] Bergou | On the use of the energy norm in trust-region and adaptive cubic regularization subproblems[END_REF], when the matrix B k is assumed to be positive definite, we showed that the minimizer s k of the cubic model defined in (3) is getting collinear with the quasi-Newton direction when the matrix M k is set to be equal to B k . In this section we generalize our proposed approach to cover the case where the linear system B k s = -g k admits an approximate solution and B k is not necessarily SPD.

Let s Q k be an approximate solution of the linear system B k s = -g k and assume that such step s Q k is not orthogonal with the gradient of the objective function at x k , i.e., there exists an

ǫ d > 0 such that |g ⊤ k s Q k | ≥ ǫ d g k s Q k .
Suppose that there exists an SPD matrix

M k such that M k s Q k = β k s Q k 2 g ⊤ k s Q k g k where β k ∈]β min ,
s k = δ k s Q k , where δ k = 2 1 -sgn(g ⊤ k s Q k ) 1 + 4 σ k s Q k 3 M k |g ⊤ k s Q k | . (6)
For unsuccessful iterations in Algorithm 1, since the step direction s Q k does not change, the approximate solution of the subproblem, given by [START_REF] Cartis | Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization[END_REF], can be obtained only by updating the step-size δ k . This means that the subproblem computational cost of unsuccessful iterations is getting straightforward compared to solving the subproblem as required by ARC when the Euclidean norm is used (see e.g., [START_REF] Cartis | Adaptive cubic regularisation methods for unconstrained optimization. Part I: Motivation, convergence and numerical results[END_REF]). As a consequence, the use of the proposed M k -norm in Algorithm 1 will lead to a new formulation of ARC algorithm where the dominant computational cost, regardless the objective function evaluation cost, is the cost of solving a linear system for successful iterations. In other words, with the proposed M k -norm, the ARC algorithm behaves as an LS method with a specific backtracking strategy and an acceptance criteria in the sprite of ARC algorithm, i.e., the step is of the form s k = δ k s Q k where the step length δ k > 0 is chosen such as

ρ k = f (x k ) -f (x k + s k ) f (x k ) -m Q k (s k ) ≥ η and m k (s k ) ≤ m k (-δ c k g k ). (7)
The step lengths δ k and δ c k are computed respectively as follows:

δ k = 2 1 -sgn(g ⊤ k s Q k ) 1 + 4 σ k β 3/2 k s Q k 3 |g ⊤ k s Q k | , (8)
and

δ c k = 2 g ⊤ k B k g k g k 2 + g ⊤ k B k g k g k 2 2 + 4σ k χ 3/2 k g k (9)
where

χ k = β k 5 2 -3 2 cos(̟ k ) 2 + 2 1-cos(̟ k ) 2 cos(̟ k ) 2 and cos(̟ k ) = g ⊤ k s Q k g k s Q k . The M k -norms of
the vectors s Q k and g k in the computation of δ k and δ c k have been substituted using the expressions given in Theorem 4.1. The value of σ k is set equal to the current value of the regularization parameter as in the original ARC algorithm. For large values of δ k the decrease condition [START_REF] Cartis | Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained optimization[END_REF] may not be satisfied. In this case, the value of σ k is enlarged using an expansion factor ν 2 > 1. Iteratively, the value of δ k is updated and the acceptance condition [START_REF] Cartis | Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained optimization[END_REF] is checked again, until its satisfaction.

We referred the ARC algorithm, when the proposed scaled M k -norm is used, by LS-ARC as it behaves as an LS type method in this case. Algorithm 2 details the final algorithm. We recall again that this algorithm is nothing but ARC algorithm using a specific M k -norm.

Algorithm 2: LS-ARC algorithm.

Data: select an initial point x 0 and the constants 0

< η < 1, 0 < ǫ d < 1, 0 < ν 1 ≤ 1 < ν 2 and 0 < β min < β max . Set σ 0 > 0 and σ min ∈]0, σ 0 ]. for k = 1, 2, . . . do Choose a parameter β k ∈]β min , β max [; Let s Q k be an approximate solution of B k s = -g k such as |g ⊤ k s Q k | ≥ ǫ d g k s Q k ; Set δ k and δ c
k respectively using ( 8) and ( 9); while condition [START_REF] Cartis | Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained optimization[END_REF] is not satisfied do Set σ k ← ν 2 σ k and update δ k and δ c k respectively using ( 8) and ( 9);

end Set s k = δ k s Q k , x k+1 = x k + s k and σ k+1 = max{ν 1 σ k , σ min }; end
Note that in Algorithm 2 the step s Q k may not exist or be approximately orthogonal with the gradient g k . A possible way to overcome this issue can be ensured by modifying the matrix B k using regularization techniques. In fact, as far as the Hessian approximation is still uniformly bounded from above, the global convergence will still hold as well as a complexity bound of order ǫ -2 to drive the norm of the gradient below ǫ ∈]0, 1[ (see [START_REF] Cartis | Adaptive cubic regularisation methods for unconstrained optimization. Part I: Motivation, convergence and numerical results[END_REF] for instance).

The complexity bound can be improved to be of the order of ǫ -3/2 if a second order version of the algorithm LS-ARC is used, by making B k equals to the exact Hessian or at least being a good approximation of the exact Hessian (as in Assumption 4.2 of Section 4). In this case, modify the matrix B k using regularization techniques such that the step s Q k approximates the linear system

B k s = -g k and |g ⊤ k s Q k | ≥ ǫ d g k s Q k is not trivial anymore.
This second order version of the algorithm LS-ARC will be discussed in details in Section 4 where convergence and complexity analysis, when the proposed M k -norm is used, will be outlined.

On the Cubic Model Minimization

In this section, we assume that the linear system B k s = -g k has a solution. We will mostly focus on the solution of the subproblem (3) for a given outer iteration k. In particular, we will explicit the condition to impose on the matrix M k in order to get the solution of the ARC subproblem collinear with the step s Q k . Hence, in such case, one can get the solution of the ARC subproblem at a modest computational cost.

The step s Q k can be obtained exactly using a direct method if the matrix B k is not too large. Typically, one can use the LDL T factorization to solve this linear system. For large scale optimization problems, computing s Q k can be prohibitively computationally expensive. We will show that it will be possible to relax this requirement by letting the step s Q k be only an approximation of the exact solution using subspace methods.

In fact, when an approximate solution is used and as far as the global convergence of Algorithm 1 is concerned, all what is needed is that the solution of the subproblem (3) yields a decrease in the cubic model which is as good as the Cauchy decrease (as emphasized in condition ( 5)). In practice, a version of Algorithm 2 solely based on the Cauchy step would suffer from the same drawbacks as the steepest descent algorithm on ill-conditioned problems and faster convergence can be expected if the matrix B k influences also the minimization direction. The main idea consists of achieving a further decrease on the cubic model, better than the Cauchy decrease, by projection onto a sequence of embedded Krylov subspaces. We now show how to use a similar idea to compute a solution of the subproblem that is computationally cheap and yields the global convergence of Algorithm 2.

A classical way to approximate the exact solution s Q k is by using subspace methods, typically a Krylov subspace method. For that, let L k be a subspace of R n and l its dimension. Let Q k denotes an n × l matrix whose columns form a basis of L k . Thus for all s ∈ L k , we have

s k = Q k z k , for some z k ∈ R l .
In this case, s Q k denotes the exact stationary point of the model function m Q over the subspace L k when it exists.

For both cases, exact and inexact, we will assume that the step s Q k is not orthogonal with the gradient g k . In what comes next, we state our assumption on s Q k formally as follows:

Assumption 3.1 The model m Q k admits a stationary point s Q k such as |g ⊤ k s Q k | ≥ ǫ d g k s Q k where ǫ d > 0 is a pre-defined positive constant.
We define also a Newton-like step s N k associated with the minimization of the cubic model m k over the subspace L k on the following way, when s Q k corresponds to the exact solution of

B k s = -g k by s N k = δ N k s Q k , where δ N k = arg min δ∈I k m k (δs Q k ), (10)
where

I k = R + if g ⊤ k s Q k < 0 and I k = R -otherwise. If s Q k is computed using an iterative subspace method, then s N k = Q k z N k ,
where z N k is the Newton-like step , as in [START_REF] Dennis | Numerical methods for unconstrained optimization and nonlinear equations[END_REF], associated to the following reduced subproblem:

min z∈R l f (x k ) + z ⊤ Q ⊤ k g k + 1 2 z ⊤ Q ⊤ k B k Q k z + 1 3 σ k z 3 Q ⊤ k M k Q k . ( 11
) Theorem 3.1 Let Assumption 3.1 hold. The Newton-like step s N k is of the form s N k = δ N k s Q k , where δ N k = 2 1 -sgn(g ⊤ k s Q k ) 1 + 4 σ k s Q k 3 M k |g ⊤ k s Q k | . ( 12
)
Proof. Consider first the case where the step

s Q k is computed exactly (i.e., B k s Q k = -g k ).
In this case, for all δ ∈ I k , one has

m k (δs Q k ) -m k (0) = δg ⊤ k s Q k + δ 2 2 [s Q k ] ⊤ B k [s Q k ] + σ|δ| 3 3 s Q k 3 M k = (g ⊤ k s Q k )δ -(g ⊤ k s Q k ) δ 2 2 + (σ k s Q k 3 M k ) |δ| 3 3 . ( 13
) If g ⊤ k s Q k < 0 (hence, I k = R + )
, we compute the value of the parameter δ N k at which the unique minimizer of the above function is attained. Taking the derivative of ( 13) with respect to δ and equating the result to zero, one gets

0 = g ⊤ k s Q k -(g ⊤ k s Q k )δ N k + σ k s Q k 3 M k δ N k 2 , (14)
and thus, since

δ N k > 0, δ N k = g ⊤ k s Q k + g ⊤ k s Q k 2 -4σ k (g ⊤ k s Q k ) s Q k 3 M k 2σ k s Q k 3 M k = 2 1 + 1 -4 σ k s Q k 3 M k g ⊤ k s Q k . If g ⊤ k s Q k > 0 (hence, I k = R -)
,and again by taking the derivative of ( 13) with respect to δ and equating the result to zero, one gets

0 = g ⊤ k s Q k -(g ⊤ k s Q k )δ N k -σ k s Q k 3 M k δ N k 2 , (15)
and thus, since δ N k < 0 in this case,

δ N k = g ⊤ k s Q k + g ⊤ k s Q k 2 + 4σ k (g ⊤ k s Q k ) s Q k 3 M k 2σ k s Q k 3 M k = 2 1 -1 + 4 σ k s Q k 3 M k g ⊤ k s Q k .
From both cases, one deduces that

δ N k = 2 1-sgn(g ⊤ k s Q k ) 1+4 σ k s Q k 3 M k |g ⊤ k s Q k |
.

Consider now the case where s Q k is computed using an iterative subspace method. In this cas, one has

s N k = Q k z N k ,
where z N k is the Newton-like step associated to the reduced subproblem [START_REF] Dolan | Benchmarking optimization software with performance profiles[END_REF]. Hence by applying the first part of the proof (the exact case) to the reduced subproblem [START_REF] Dolan | Benchmarking optimization software with performance profiles[END_REF], it follows that

z N k = δN k z Q k where δN k = 2 1 -sgn((Q ⊤ k g k ) ⊤ z Q k ) 1 + 4 σ k z Q k 3 Q ⊤ k M k Q k |(Q ⊤ k g k ) ⊤ z Q k |
, where z Q k is a stationary point of the quadratic part of the minimized model in [START_REF] Dolan | Benchmarking optimization software with performance profiles[END_REF]. Thus, by

substituting z N k in the formula s N k = Q k z N k , one gets s N k = Q k       2 1 -sgn((Q ⊤ k g k ) ⊤ z Q k ) 1 + 4 σ k z Q k 3 Q ⊤ k M k Q k |Q ⊤ k g k ) ⊤ z Q k | z Q k       = 2 1 -sgn(g ⊤ k Q k z Q k ) 1 + 4 σ k Q k z Q k 3 M k |g ⊤ k Q k z Q k | Q k z Q k = 2 1 -sgn(g ⊤ k s Q k ) 1 + 4 σ k s Q k 3 M k |g ⊤ k s Q k | s Q k .
In general, for ARC algorithm, the matrix M k can be any arbitrary SPD matrix. Our goal, in this section, is to determine how one can choose the matrix M k so that the Newton-like step s N k becomes a stationary point of the subproblem (3). The following theorem gives explicitly the necessary and sufficient condition on the matrix M k to reach this aim.

θ k > 0 such that M k s Q k = θ k g ⊤ k s Q k g k . Note that θ k = s Q k 2 M k .
Proof. Indeed, in the exact case, if we suppose that the step s N k is a stationary point of the subproblem (3), this means that

∇m k (s N k ) = g k + B k s N k + σ k s N k M k M k s N k = 0, (16)
In another hand,

s N k = δ N k s Q k where δ N k is solution of g ⊤ k s Q k -(g ⊤ k s Q k )δ N k + σ k s Q k 3 M k |δ N k |δ N k = 0 (such
equation can be deduced from ( 14) and ( 15)). Hence, we obtain that

0 = ∇m k (s N k ) = g k -δ N k g k + σ k |δ N k |δ N k s Q k M k M k s Q k = 1 -δ N k g k + σ k s Q k 3 M k g ⊤ k s Q k |δ N k |δ N k g ⊤ k s Q k s Q 2 M k M k s Q k = σ k s Q k 3 M k g ⊤ k s Q k |δ N k |δ N k g k - g ⊤ k s Q k s Q k 2 M k M k s Q k . Equivalently, we conclude that M k s Q k = θ k g ⊤ k s Q k g k where θ k = s Q k 2 M k > 0.
A similar proof applies when a subspace method is used to compute s Q k . The key condition to ensure that the ARC subproblem stationary point is equal to the Newton-like step s N k , is the choice of the matrix M k which satisfies the following secant-like equation

M k s Q k = θ k g ⊤ k s Q k g k for a given θ k > 0.
The existence of such matrix M k is not problematic as far as Assumption 3.1 holds. In fact, Theorem 4.1 will explicit a range of θ k > 0 for which the matrix M k exists. Note that in the formula of s N k , such matrix is used only through the computation of the M k -norm of s Q k . Therefore an explicit formula of the matrix M k is not needed, and only the value of

θ k = s Q k 2
M k suffices for the computations. When the matrix M k satisfies the desired properties (as in Theorem 3.2), one is ensured that s N k is a stationary point for the model m k . However, ARC algorithm imposes on the approximate step to satisfy the Cauchy decrease given by ( 5), and such condition is not guaranteed by s N k as the model m k may be non-convex. In the next theorem, we show that for a sufficiently large σ k , s N k is getting the global minimizer of m k and thus satisfying the Cauchy decrease is not an issue anymore.

Theorem 3.3 Let Assumption 3.1 hold. Let M k be an SPD matrix which satisfies M k s Q k = θ k g ⊤ k s Q k g k for a fixed θ k > 0. If the matrix Q ⊤ k (B k + σ k s N k M k M k )Q k is positive definite, then the step s N
k is the unique minimizer of the subproblem (3) over the subspace L k .

Proof. Indeed, when s Q is computed exactly (i.e.,

Q k = I n and L k = R n ),
(B k + λ * k M k )s * k = -g k where B k + λ * k M k is positive semi-definite matrix and λ * k = σ k s * k M k . Moreover, if B k + λ * k M k is positive definite, s * k is unique. Since M k s Q k = θ k g ⊤ k s Q k g k , by applying Theorem 3.2, we see that (B k + λ N k M k )s N k = -g k with λ N k = σ k s N k M k . Thus, if we assume that B k + λ N k M k is positive definite matrix, then s N k
is the unique global minimizer of the subproblem (3). Consider now, the case where s Q k is computed using a subspace method, since

M k s Q k = θ k g ⊤ k s Q k g k one has that Q ⊤ k M k Q k z Q k = θ k (Q ⊤ k g k ) ⊤ z Q k Q ⊤ k g k .
Hence, if we suppose that the matrix

Q ⊤ k (B k + λ N k M k )Q k is
positive definite, by applying the same proof of the exact case to the reduced subproblem [START_REF] Dolan | Benchmarking optimization software with performance profiles[END_REF], we see that the step z N k is the unique global minimizer of the subproblem [START_REF] Dolan | Benchmarking optimization software with performance profiles[END_REF]. We conclude that s N k = Q k z N k is the global minimizer of the subproblem (3) over the subspace L k . Theorem 3.3 states that the step s N k is the global minimizer of the cubic model m k over the subspace L k as far as the matrix

Q ⊤ k (B k + σ k s N k M k M k )Q k is positive definite, where λ N k = σ k s N k M k . Note that λ N k = σ k s N k M k = 2σ k s Q k M k 1 -sgn(g ⊤ k s Q k ) 1 + 4 σ k s Q k 3 M k |g ⊤ k s Q k | → +∞ as σ k → ∞.
Thus, since M k is an SPD matrix and the regularization parameter σ k is increased for unsuccessful iterations in Algorithm 1, the positive definiteness of matrix

Q ⊤ k (B k +σ k s N k M k M k )Q k is
guaranteed after finitely many unsuccessful iterations. In other words, one would have insurance that s N k will satisfy the Cauchy decrease after a certain number of unsuccessful iterations.

Complexity Analysis of the LS-ARC Algorithm

For the well definiteness of the algorithm LS-ARC, one needs first to show that the proposed M knorm is uniformly equivalent to the Euclidean norm. The next theorem gives a range of choices for the parameter θ k to ensure the existence of an SPD matrix M k such as

M k s Q k = θ k g ⊤ k s Q k g k and
the M k -norm is uniformly equivalent to the ℓ 2 -norm.

θ k = β k s Q k 2 where β k ∈]β min , β max [ and β max > β min > 0, ( 17
)
then there exists an SPD matrix M k such as

i) M k s Q k = θ k g ⊤ k s Q k g k ,
ii) the M k -norm is uniformly equivalent to the ℓ 2 -norm on R n and for all x ∈ R n , one has

√ β min √ 2 x ≤ x M k ≤ √ 2β max ǫ d x . (18)
iii) Moreover, one has s Q k 2

M k = β k s Q k 2 and g k 2 M k = χ k g k 2 where χ k = β k 5 2 -3 2 cos(̟ k ) 2 + 2 1-cos(̟ cos(̟ and cos(̟ k ) = g ⊤ k s Q k g k s Q k Proof. Let sQ k = s Q k s Q k
and ḡk be an orthonormal vector to sQ k (i.e., ḡk = 1 and ḡ⊤

k sQ k = 0) such that g k g k = cos(̟ k )s Q k + sin(̟ k ) ḡk . ( 19
)
For a given

θ k = β k s Q k 2 where β k ∈]β min , β max [ and β max > β min > 0, one would like to construct an SPD matrix M k such as M k s Q k = θ k g k g ⊤ k s Q k , hence M k sQ k = θ k g k g ⊤ k s Q k s Q k = θ k g k g ⊤ k s Q k s Q k cos(̟ k )s Q k + sin(̟ k )ḡ k = β k sQ k + β k tan(̟ k )ḡ k .
Using the symmetric structure of the matrix M k , let γ k be a positive parameter such as

M k = sQ k , ḡk N k sQ k , ḡk ⊤ where N k = β k β k tan(̟ k ) β k tan(̟ k ) γ k .
The eigenvalues λ min k and λ max k of the matrix N k are the roots of

λ 2 -(β k + γ k ) λ + β k γ k -(β k tan(̟ k )) 2 = 0, hence λ min k = (β k + γ k ) - √ ϑ k 2 and λ max k = (β k + γ k ) + √ ϑ k 2 ,
where

ϑ k = (β k -γ k ) 2 + 4 (β k tan(̟ k )) 2 .
Note that both eigenvalues are monotonically increasing as functions of γ k . One may choose λ min k to be equal to

1 2 β k = 1 2 θ k s Q k 2 , therefore λ min k > 1 2
β min is uniformly bounded away from zero. In this case, from the expression of λ min k , we deduce that

γ k = 2β k tan(̟ k ) 2 + β k /2 and λ max k = 3 4 β k + β k tan(̟ k ) 2 + 1 16 β 2 k + 1 2 β 2 k tan(̟ k ) 2 + β 2 k tan(̟ k ) 4 = β k 3 4 + tan(̟ k ) 2 + 1 16 + 1 2 tan(̟ k ) 2 + tan(̟ k ) 4 = β k 1 + 2 tan(̟ k ) 2 . From Assumption 3.1, i.e., |g ⊤ k s Q k | ≥ ǫ d g k s Q k where ǫ d > 0, one has tan(̟ k ) 2 ≤ 1-ǫ 2 d ǫ 2 d
. Hence,

λ max k ≤ β max 1 + 2 1 -ǫ 2 d ǫ 2 d ≤ 2β max ǫ 2 d
A possible choice for the matrix M k can be obtained by completing the vectors family {s Q k , ḡk } to an orthonormal basis {s Q k , ḡk , q 3 , q 4 , . . . , q n } of R n as follows: 2) with positive diagonal entrees independent from k . One concludes that for all θ k = β k s Q k 2 where β k ∈]β min , β max [ and β max > β min > 0, the eigenvalue of the constructed M k are uniformly bounded away from zero and from above, hence the scaled M k -norm is uniformly equivalent to the ℓ 2 -norm on R n and for all x ∈ R n , one has

M k = [s Q k , ḡk , q 3 , . . . , q n ] N k 0 0 D [s Q k , ḡk , q 3 , . . . , q n ] ⊤ , where D = diag(d 3 , . . . , d n ) ∈ R (n-2)×(n-
√ β min √ 2 x ≤ λ min k x ≤ x M k ≤ λ max k x ≤ √ 2β max ǫ d x .
By multiplying

M k s Q k = θ k g ⊤ k s Q k g k from both sides by s Q k , one gets s Q k 2 M k = θ k = β k s Q k 2 .
Moreover, using ( 19) and ( 20), one has

g k 2 M k = g k 2 cos(̟ k )s Q k + sin(̟ k ) ḡk ⊤ cos(̟ k )M k sQ k + sin(̟ k )M k ḡk = g k 2 θ k cos(̟ k ) 2 s Q k 2 + γ k sin(̟ k ) 2 + 2 sin(̟ k ) cos(̟ k ) θ k tan(̟ k ) 2 s Q k 2 = β k g k 2 cos(̟ k ) 2 + 5 2 sin(̟ k ) 2 + 2 sin(̟ k ) 2 tan(̟ k ) 2 = β k g k 2 5 2 - 3 2 cos(̟ k ) 2 + 2 1 -cos(̟ k ) 2 cos(̟ k ) 2 .
A direct consequence of Theorem 4.1 is that, by choosing θ k > 0 of the form β k s Q k 2 where β k ∈]β min , β max [ and β max > β min > 0 during the application of LS-ARC algorithm, the global convergence and complexity bounds of LS-ARC algorithm can be derived straightforwardly from the classical ARC analysis [START_REF] Cartis | Adaptive cubic overestimation methods for unconstrained optimization. Part II: worst-case function-and derivative-evaluation complexity[END_REF]. In fact, as far as the objective function f is continuously differentiable, its gradient is Lipschitz continuous, and its approximated Hessian B k is bounded for all iterations (see [4, Assumptions AF1, AF4, and AM1]), the LS-ARC algorithm is globally convergent and will required at most a number of iterations of order ǫ -2 to produce a point x ǫ with ∇f (x ǫ ) ≤ ǫ [4, Corollary 3.4].

In what comes next, we assume the following on the objective function f : Assumption 4.1 Assume that f is twice continuously differentiable with Lipschitz continuous Hessian, i.e., there exists a constant L ≥ 0 such that for all x, y ∈ R n one has

∇ 2 f (x) -∇ 2 f (y) ≤ L x -y .
When the matrix B k is set to be equal to the exact Hessian of the problem and under Assumption 4.1, one can improve the function-evaluation complexity to be O(ǫ -3/2 ) for ARC algorithm by imposing, in addition to the Cauchy decrease, another termination condition during the computation of the trial step s k (see [START_REF] Cartis | Adaptive cubic overestimation methods for unconstrained optimization. Part II: worst-case function-and derivative-evaluation complexity[END_REF][START_REF] Birgin | Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models[END_REF]). Such condition is of the form

∇m k (s k ) ≤ ζ s k 2 , (20)
where ζ > 0 is a given constant chosen at the start of the algorithm.

When only an approximation of the Hessian is available during the application Algorithm 1, an additional condition has to be imposed on the Hessian approximation B k in order to ensure an optimal complexity of order ǫ -3/2 . Such condition is often considered as (see [4,

(∇ 2 f (x k ) -B k )s k ≤ C s k 2 (21)
for all k ≥ 0 and for some constant C > 0.

Similarly, for LS-ARC algorithm, the complexity bound can be improved to be of the order of ǫ -3/2 if one includes the two following requirements (a) the s k satisfies the criterion condition [START_REF] Yuan | Recent advances in trust region algorithms[END_REF] and (b) the Hessian approximation matrix B k has to satisfy Assumption 4.2. When our proposed M k -norm is used, the termination condition [START_REF] Yuan | Recent advances in trust region algorithms[END_REF] imposed on the cubic model m k can be expressed only in terms of s Q k and ∇m Q k . The latter condition will be required in the LS-ARC algorithm at each iteration to ensure that it takes at most O(ǫ -3/2 ) iterations to reduce the gradient norm below ǫ. Such result is given in the following proposition

∇m Q k (s Q k ) ≤ 2 sgn(g ⊤ k s Q k )ζ -1 + sgn(g ⊤ k s Q k ) 1 + 4 σ k θ 3/2 k |g ⊤ k s Q k | s Q k 2 . ( 22
)
Proof. Since Assumption 3.1 holds and

θ k = β k s Q k 2 as in (17), Theorem 4.1 implies the existence of an SPD matrix M k such that M k s Q k = θ k g ⊤ k s Q k g k . Using such M k -norm, an approximate solution of the cubic model m k is of the form s k = δ k s Q k where δ k is solution of g ⊤ k s Q k -(g ⊤ k s Q k )δ k + σ k s Q k 3 M k |δ k |δ k = 0. Hence, ∇m k (s k ) = g k + B k s k + σ k s k M k M k s k = g k + δ k B k s Q k + σ k |δ k |δ k s Q k M k M k s Q k . Since M k s Q k = θ k g ⊤ k s Q k g k with θ k = s Q k 2 M k , one has ∇m k (s k ) = g k + δ k B k s Q k + σ k |δ k |δ k s Q k 3 M k g ⊤ k s Q k g k = 1 + σ k |δ k |δ k s k 3 M k g ⊤ k s Q k g k + δ k B k s Q k .
From the fact that g

⊤ k s Q k -(g ⊤ k s Q k )δ k + σ k s Q k 3 M k |δ k |δ k = 0, one deduces ∇m k (s k ) = δ k g k + B k s Q k = δ k ∇m Q k (s Q k ).
Hence, the condition ( 20) is being equivalent to

∇m Q k (s Q k ) ≤ ζ δ k s k 2 = ζ|δ k | s Q k 2 .
We note that the use of an exact solver to compute s Q k implies that the condition (22) will be automatically satisfied for a such iteration. Moreover, when a subspace method is used to approximate the step s Q k , we note the important freedom to add an additional preconditioner to the problem. In this case, one would solve the quadratic problem with preconditioning until the criterion (22) is met. This is expected to happen early along the Krylov iterations when the preconditioner for the linear system B k s = -g k is good enough.

Algorithm 3 summarized a second-order variant of LS-ARC, referred here as LS-ARC (s) , which is guaranteed to have an improved iteration worst-case complexity of order ǫ -3/2 (see Theorem 4.2). The Hessian approximation B k (as required by Assumption 4.2) involves s k , hence finding a new matrix B k so that the new s Q k satisfies Assumption 3.1 using regularization techniques is not trivial as s k is unknown at this stage. A possible way to satisfy Assumption 4.2 without modifying B k is by choosing s Q k as the first iterate to satisfy (22) when using a subspace method to solve the linear system B k s = -g k . Then, one checks if s Q k satisfies Assumption 3.1 or not. If s Q k violates the latter assumption, one runs further iterations of the subspace method until Assumption 3.1 will be satisfied. If the subspace method ends and Assumption 3.1 is still violated, one would restore such assumption by minimizing the cubic model using the ℓ 2 -norm until a successful outer iteration is found.

For the sake of illustration, consider the minimization of the objective function f (x, y) = x 2 -y 2 for all (x, y) ∈ R 2 , starting from x 0 = (1, 1), with σ 0 = 1, and B k being the exact Hessian Algorithm 3: LS-ARC (s) Algorithm.

In each iteration k of Algorithm 2:

Let s Q k be an approximate solution of B k s = -g k such as |g ⊤ k s Q k | ≥ ǫ d g k s Q k and the termination condition ∇m Q k (s Q k ) ≤ 2 sgn(g ⊤ k s Q k )ζ -1 + sgn(g ⊤ k s Q k ) 1 + 4 σ k β 3/2 k s Q k 3 |g ⊤ k s Q k | s Q k 2
is satisfied for a given constant ζ > 0 chosen at the beginning of the algorithm.

of the problem during the application of the algorithm. One starts by checking if s Q 0 = (-1, -1) (i.e., the exact solution of the linear system B 0 s = -g 0 ) is a sufficient descent direction or not. Since the slop g ⊤ 0 s Q 0 is equal to zero for this example, the algorithm has to switch to the ℓ 2 -norm and thus s 0 will be set as a minimizer of the cubic model with the ℓ 2 -norm to define the cubic regularization term. Using a subproblem solver (in our case the GLRT solver from GALAHAD [START_REF] Gould | GALAHAD, a library of thread-safe fortran 90 packages for large-scale nonlinear optimization[END_REF], more details are given in Section 6), one finds the step s 0 = (-0.4220, 2.7063) and the point x 1 = x 0 + s 0 is accepted (with f (x 1 ) = -13.4027). Computing the new gradient g 1 = (1.1559, -7.4126) and the quasi-Newton direction s

Q 1 = (-0.5780, -3.7063), one has |g ⊤ 1 s Q 1 | = 20.5485 ≥ ǫ d g 1 s Q 1 = 0.
0205 where ǫ d = 10 -3 (hence Assumption 3.1 holds). We perform then our proposed LS strategy along the direction s Q 1 to obtain the step s 1 . For this example, except the first one, all the remaining iterations k satisfy the condition

|g ⊤ k s Q k | ≥ ǫ d g k s Q k .
We note that the regarded minimization problem is unbounded from below, hence f decreases to -∞ during the application of the algorithm.

LS strategies require in general to have a sufficient descent direction for each iteration, it seems then natural that one may need to choose ǫ d to be large (close to 1) to target good performance. However, during the application of LS-ARC (s) and to satisfy Assumption 3.1 (without modifying the matrix B k ), one may be encouraged to use an ǫ d small. In what comes next, we will give a detailed complexity analysis of the LS-ARC (s) algorithm in this case. In particular, we will explicit how the complexity bound will depend on the choice of the constant ǫ d . The following results are obtained from [2, Lemma 2.1] and [2, Lemma 2.2]: Lemma 4.1 Let Assumptions 4.1 and 3.1 hold and consider Algorithm 3. Then for all k ≥ 0, one has

f (x k ) -m Q k (s k ) ≥ σ k 3 s k 3 M k , (23)
and

σ k ≤ σ max := max σ 0 , 3ν 2 L 2(1 -η) . ( 24
)
The next lemma is an adaptation of [2, Lemma 2.3] when the proposed M k -norm is used in the ARC framework.

s k ≥ g k+1 L + C + 2 √ 2σ max β 3/2 max ǫ -3 d + ζ 1 2
.

Proof. Indeed, using Assumptions 4.1 and 4.2 within Taylor expansion, one has

g k+1 ≤ g k+1 -∇m k (s k ) + ∇m k (s k ) ≤ g k+1 -g k -B k s k -σ k s k M k M k s k + ζ s k 2 ≤ g k+1 -g k -∇ 2 f (x k )s k + (∇ 2 f (x k ) -B k )s k + σ k M k 3/2 s k 2 + ζ s k 2 ≤ L s k 2 + C s k 2 + (σ k M k 3/2 + ζ) s k 2 .
Using (24), one has

g k+1 ≤ (L + C + σ max M k 3/2 + ζ) s k 2 .
Since Assumption 4.2 holds and

θ k = β k s Q k 2
where β k ∈]β min , β max [, then using Theorem 4.1, the matrix M k norm is bounded from above by 2β max ǫ -2 d . Hence,

g k+1 ≤ L + C + 2 √ 2σ max β 3/2 max ǫ -3 d + ζ s k 2 .
Theorem 4.2 Let Assumptions 4.1, 4.2 and 3.1 hold. Consider Algorithm 3 with

θ k = β k s Q k 2
where β k ∈]β min , β max [ and β max > β min > 0. Then, given an ǫ > 0, Algorithm 3 needs at most

κ s (ǫ d ) f (x 0 ) -f low ǫ 3/2
iterations to produce an iterate x ǫ such that ∇f (x ǫ ) ≤ ǫ where f low is a lower bound on f and κ s (ǫ d ) is given by

κ s (ǫ d ) = 6 √ 2 L + C + 2 √ 2σ max β 3/2 max ǫ -3 d + ζ 3/2 ησ min β 3/2 min .
Proof. Indeed, at each iteration of Algorithm 3, one has

f (x k ) -f (x k + s k ) ≥ η(f (x k ) -m Q k (s k )) ≥ ησ k 3 s k 3 M k ≥ ησ min β 3/2 min 6 √ 2 s k 3 ≥ ησ min β 3/2 min 6 √ 2 L + C + 2 √ 2σ max β 3/2 max ǫ -3 d + ζ 3/2 g k+1 3/2 ≥ ησ min β 3/2 min 6 √ 2 L + C + 2 √ 2σ max β 3/2 max ǫ -3 d + ζ 3/2 ǫ 3/2 ,
by using ( 7), ( 23), ( 18), (25), and the fact that g k+1 ≥ ǫ before termination. Thus we deduce for all iterations as long as the stopping criterion does not occur

f (x 0 ) -f (x k+1 ) = k j=0 f (x j ) -f (x j+1 ) ≥ (k + 1) ησ min √ β min 3 √ 2 L + C + 2 √ 2σ max β 3/2 max ǫ -3 d + ζ 3/2 ǫ 3/2 .
Hence, the required number of iterations to produce an iterate x ǫ such that ∇f (x ǫ ) ≤ ǫ is given as follow

k + 1 ≤ 6 √ 2 L + C + 2 √ 2σ max β 3/2 max ǫ -3 d + ζ 3/2 ησ min β 3/2 min f (x 0 ) -f low ǫ 3/2
where f low is a lower bound on f . Thus the proof is completed. We note that κ s (ǫ d ) can be large for small values of ǫ d . Hence, although the displayed worst-case complexity bound is of order ǫ -3/2 , the latter can be worse than it appears to be if the value of ǫ d is very small (i.e., the chosen direction is almost orthogonal with the gradient). Such result seems coherent regarding the LS algorithm strategy where it is required to have a sufficient descent direction (i.e., an ǫ d sufficiently large).

TR Algorithm Using a Specific M k -Norm

Similarly to ARC algorithm, it is possible to render TR algorithm behaves as an LS algorithm using the same scaled norm to define the trust-region neighborhood. As a reminder in a basic TR algorithm [START_REF] Conn | Trust-Region Methods[END_REF], one computes a trial step p k by approximately solving

min p∈R n m Q k (p) s. t. p M k ≤ ∆ k , (25)
where ∆ k > 0 is known as the TR radius. As in ARC algorithms, the scaled norm . M k may vary along the iterations and M k is an SPD matrix.

Once the trial step p k is determined, the objective function is computed at x k + p k and compared with the value predicted by the model at this point. If the model value predicts sufficiently well the objective function (i.e., the iteration is successful), the trial point x k + p k will be accepted and the TR radius is eventually expanded (i.e., ∆ k+1 = τ 2 ∆ k with τ 2 ≥ 1). If the model turns out to predict poorly the objective function (i.e., the iteration is unsuccessful), the trial point is rejected and the TR radius is contracted (i.e., ∆ k+1 = τ 1 ∆ k with τ 1 < 1). The ratio between the actual reduction and the predicted reduction for the TR algorithms is defined as in ARC (see ( 4)). For a given scalar 0 < η < 1, the iteration will be said successful if ρ k ≥ η, and unsuccessful otherwise. Algorithm 4 gives a detailed description of a basic TR algorithm.

Note that for the TR subproblem, the solution we are looking for lies either interior to the trust region, that is p k M k < ∆ k , or on the boundary, p k M k = ∆ k . If the solution is interior, the solution p k is the unconstrained minimizer of the quadratic model m Q k . Such scenario can only happen if m Q k is convex. In the non convex case a solution lies on the boundary of the trust Algorithm 4: TR algorithm. Data: select an initial point x 0 and 0 < η < 1. Set the initial TR radius ∆ 0 > 0, the constants 0 ≤ τ 1 < 1 ≤ τ 2 , and ∆ max > ∆ 0 . for k = 1, 2, . . . do Compute the step p k as an approximate solution of (25) such that

m Q k (p k ) ≤ m k (p c k ) (26)
where

p c k = -α c k g k and α c k = arg min 0<t≤ ∆ k g k M k m Q k (-tg k ); if ρ k ≥ η then Set x k+1 = x k + p k and ∆ k+1 = min{τ 2 ∆ k , ∆ max }; else Set x k+1 = x k and ∆ k+1 = τ 1 ∆ k ; end end
region, while in the convex case a solution may or may not do so. Consequently in practice, the TR algorithm finds first the unconstrained minimizer of the model m Q k . If the model is unbounded from below, or if the unconstrained minimizer lies outside the trust region, the minimizer then occurs on the boundary of the trust region.

In this section, we will assume that the approximated solution s Q k of the linear system B k s = -g k is computed exactly. Using similar arguments as for ARC algorithm, one can extend the obtained results when a truncated step is used in the TR algorithm. Under Assumption 3.1, we will call the Newton-like step associated with the TR subproblem the vector of the following form

p N k = α N k s Q k , where α N k = arg min α∈R k m Q k (αs Q k ), (27)
where

R k =]0, ∆ k s Q k M k ] if g ⊤ k s Q k < 0 and R k = [-∆ k s Q k M k , 0[ otherwise.
Similarly to ARC algorithm, one has the following results:

Theorem 5.1 Let Assumption 3.1 hold.

1. The Newton-like step (27) is of the following form:

p N k = α N k s Q k , where α N k = min 1, -sgn(g ⊤ k s Q k ) ∆ s Q k M k . ( 28
)
2. When it lies on the border of the trust region p N k is a stationary point of the subproblem (25) if and only if

M k s Q k = θ g ⊤ k s Q k g k where θ k = s Q k 2 M k . 3. Let λ N k = g ⊤ k s Q k θ k 1 + sgn(g ⊤ k s Q k ) s Q k M k ∆ k
and assume that p N k lies on the border of the trustregion. Then, if the matrix B k + λ N k M k is positive definite, the step p N k will be the unique minimizer of the subproblem (25) over the subspace L k .

Proof. 1. To calculate the Newton-like step p N k , we first note, for all α ∈ R k

m Q k (αs Q k ) -m Q k (0) = αg ⊤ k s Q k + α 2 2 [s Q k ] ⊤ B k [s Q k ] = (g ⊤ k s Q k )α -(g ⊤ k s Q k ) α 2 2 . ( 29
)
Consider the case where the curvature model along the Newton direction is positive, that is when

g ⊤ k s Q k < 0, (i.e., R k =]0, ∆ k s Q k M k
]) and compute the value of the parameter α at which the unique minimizer of (29) is attained. Let α * k denotes this optimal parameter. Taking the derivative of (29) with respect to α and equating the result to zero, one has α * k = 1. Two sub-cases may then occur. The first is when this minimizer lies within the trust region (i.e.,

α * k s Q k M k ≤ ∆ k ), then α N k = 1. If α * k s Q k M k > ∆ k ,
then the line minimizer is outside the trust region and we have that

α N k = ∆ k s Q k M k .
Finally, we consider the case where the curvature of the model along the Newton-like step is negative, that is, when g ⊤ k s Q k > 0. In that case, the minimizer lies on the boundary of the trust region, and thus

α N k = - ∆ k s Q k M k .
By combining all cases, one concludes that

p N k = α N k s Q k , where α N k = min 1, -sgn(g ⊤ k s Q k ) ∆ k s Q k M k .
2. Suppose that the Newton-like step lies on the border of the trust region, i.e., p

N k = α N k s Q k = -sgn(g ⊤ k s Q k ) ∆ k s Q k M k s Q k .
The latter step is a stationary point of the subproblem (25) if and only if there exists a Lagrange multiplier λ N k ≥ 0 such that

(B k + λ N k M k )p N k = -g k . Substituting p N k = α N k s Q k in the latter equation, one has λ N k M k s Q k = 1 - 1 α N k g k . ( 30
)
By multiplying it from left by (s Q ) ⊤ , we deduce that

λ N k = 1 - 1 α N k g ⊤ k s Q k s Q k 2 M k = g ⊤ k s Q k θ 1 + sgn(g ⊤ k s Q k ) s Q k M k ∆ k .
By replacing the value of λ N k in (30), we obtain that

M k s Q k = θ k g ⊤ k s Q k g k where θ k = s Q k 2
M k > 0. 3. Indeed, when the step p N k lies on the boundary of the trust-region and

M k s Q k = θ k g ⊤ k s Q k g.
Then applying item (1) of Theorem 5.1, we see that

(B k + λ N k M k )p N k = -g k with λ N k = g ⊤ k s Q k θ k 1 + sgn(g ⊤ k s Q k ) s Q k M k ∆ k > 0.
Applying [START_REF] Conn | Trust-Region Methods[END_REF]Theorem 7.4.1], we see that if we assume that the matrix B k + λ N k M k is positive definite, then p N k is the unique minimizer of the subproblem (25).

Given an SPD matrix M k that satisfies the secant equation

M k s Q k = θ k g ⊤ k s Q k g k , item (3)
of Theorem 5.1 states that the step p N k is the global minimizer of the associated subproblems over the subspace L k as far as the matrix B k + λ N k M k is SPD. We note that λ N k goes to infinity as the trust region radius ∆ k goes to zero, meaning that the matrix B k + λ N k M k will be SPD as far as ∆ k is chosen to be sufficiently small. Since the TR update mechanism allows to shrink the value of ∆ k (when the iteration is declared as unsuccessful), satisfying the targeted condition will be geared automatically by the TR algorithm.

Again, when Assumption 3.1 holds, we note that unsuccessful iterations in the TR Algorithm require only updating the value of the TR radius ∆ k and the current step direction is kept unchanged. For such iterations, as far as there exists a matrix M k such as

M k s Q k = β k s Q k 2 g ⊤ k s Q k g k
where β k ∈]β min , β max [ and β max > β min > 0, the approximate solution of the TR subproblem is obtained only by updating the step-size α N k . This means that the computational cost of unsuccessful iterations do not requires solving any extra subproblem. We note that during the application of the algorithm, we will take θ k of the form

β k s Q k 2 2
, where β k ∈]β min , β max [ and 0 < β min < β max . Such choice of the parameter θ k ensures that the proposed M k -norm uniformly equivalent to the l 2 one along the iterations (see Theorem 4.1).

In this setting, TR algorithms behaves as an LS method with a specific backtracking strategy. In fact, at the k th iteration, the step is of the form p k = α k s Q k where s Q k is the (approximate) solution of the linear system B k s = -g k . The step length α k > 0 is chosen such as

f (x k ) -f (x k + p k ) f (x k ) -m Q k (p k ) ≥ η and m Q k (p k ) ≤ m Q k (-α c k g k ). (31)
The values of α k and α c k are computed respectively as follows:

α k = min 1, -sgn(g ⊤ k s Q k ) ∆ k β 1/2 k s Q k ( 32
)
and

α c k =        ∆ k χ 1/2 k g k if g ⊤ k B k g k ≤ 0 or g ⊤ k B k g k g k ≥ ∆ k χ 1/2 k , g ⊤ k B k g k g k 2
else.

(33)

20

where

χ k = β k 5 2 -3 2 cos(̟ k ) 2 + 2 1-cos(̟ k ) 2 cos(̟ k ) 2 and cos(̟ k ) = g ⊤ k s Q k g k s Q k . ∆ k is initially
equals to the current value of the TR radius (as in the original TR algorithm). For large values of α k the sufficient decrease condition (31) may not be satisfied, in this case, the value of ∆ k is contracted using the factor τ 1 . Iteratively, the value of α k is updated and the acceptance condition (31) is checked again until its satisfaction. Algorithm 5 details the adaptation of the classical TR algorithm when our proposed M k -norm is used. We denote the final algorithm by LS-TR as it behaves as an LS algorithm.

Algorithm 5: LS-TR algorithm. Data: select an initial point x 0 and the constants 0

< η < 1, 0 < ǫ d ≤ 1, 0 ≤ τ 1 < 1 ≤ τ 2 ,
= α k s Q k , x k+1 = x k + p k and ∆ k+1 = min{τ 2 ∆ k , ∆ max }; end
As far as the objective function f is continuously differentiable, its gradient is Lipschitz continuous, and its approximated Hessian B k is bounded for all iterations, the TR algorithm is globally convergent and will required a number of iterations of order ǫ -2 to produce a point x ǫ with ∇f (x ǫ ) ≤ ǫ [START_REF] Gratton | Recursive trust-region methods for multiscale nonlinear optimization[END_REF].

We note that the satisfaction of Assumption 3.1 is not problematic. As suggested for LS-ARC algorithm, one can modify the matrix B k using regularization techniques (as far as the Hessian approximation is kept uniformly bounded from above all over the iterations, the global convergence and the complexity bounds will still hold [START_REF] Conn | Trust-Region Methods[END_REF]).

Numerical Experiments

In this section we report the results of experiments performed in order to assess the efficiency and the robustness of the proposed algorithms (LS-ARC and LS-TR) compared with the classical LS algorithm using the standard Armijo rule. In the latter approach, the trial step is of the form

s k = δ k d k where d k = s Q k if -g ⊤ k s Q k ≥ ǫ d g k s Q k (s Q k is being an approximate stationary point of m Q k ) otherwise d k = -g k , and the step length δ k > 0 is chosen such as f (x k + s k ) ≤ f (x k ) + ηs ⊤ k g k , (34)
where η ∈]0, 1[. The appropriate value of δ k is estimated using a backtracking approach with a contraction factor set to τ ∈]0, 1[ and where the step length is initially chosen to be 1. This LS method will be called LS-ARMIJO. We implement all the the algorithms as Matlab m-files and for all the tested algorithms B k is set to the true Hessian ∇ 2 f (x k ), and ǫ d = 10 -3 for both LS-ARC and LS-ARMIJO. Other numerical experiments (not reported here) with different values of ǫ d (for instance ǫ d = 10 -1 , 10 -6 , and 10 -12 ) lead to almost the same results. By way of comparison, we have also implemented the standard ARC/TR algorithms (see Algorithms 1 and 4) using the Lanczos-based solver GLTR/GLRT implemented in GALAHAD [START_REF] Gould | GALAHAD, a library of thread-safe fortran 90 packages for large-scale nonlinear optimization[END_REF].The two subproblem solvers, GLTR/GLRT are implemented in Fortran and interfaced with Matlab using the default parameters. For the subproblem formulation we used the ℓ 2 -norm (i.e., for all iterations the matrix M k is set to identity). We shall refer to the ARC/TR methods based on GLRT/GLTR as GLRT-ARC/GLTR-TR.

The other parameters defining the implemented algorithms are set as follows, for GLRT-ARC and LS-ARC η = 0.1, ν 1 = 0.5, ν 2 = 2, σ 0 = 1, and σ min = 10 -16 ;

for GLTR-TR and LS-TR η = 0.1, τ 1 = 0.5, τ 2 = 2, ∆ 0 = 1, and ∆ max = 10 16 ;

and last for LS-ARMIJO η = 0.1, and τ = 0.5.

In all algorithms the maximum number of iterations is set to 10000 and the algorithms stop when g k ≤ 10 -5 .

A crucial ingredient in LS-ARC and LS-TR is the management of the parameter

β k . A possible choice for β k is |g ⊤ k s Q k |/ s Q k 2 .
This choice is inspired from the fact that, when the Hessian matrix B k is SPD, this update corresponds to use the energy norm, meaning that the matrix M k is set equals to B k (see [START_REF] Bergou | On the use of the energy norm in trust-region and adaptive cubic regularization subproblems[END_REF] for more details). However, this choice did not lead to good performance of the algorithms LS-ARC and LS-TR. In our implementation, for the LS-ARC algorithm, we set the value of β k as follows:

β k = 10 -4 σ -2/3 k if g ⊤ k s Q k < 0
and 2 otherwise. By this choice, we are willing to allow LS-ARC, at the start of the backtracking procedure, to take approximately the Newton step. Similarly, for the LS-TR method, we set β k = 1 and this allows LS-TR to use the Newton step at the start of the backtracking strategy (as in LS-ARMIJO method).

All the Algorithms are evaluated on a set of unconstrained optimization problems from the CUTEst collection [START_REF] Gould | CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization[END_REF]. The test set contains 62 large-scale (1000 ≤ n ≤ 10000) CUTest problems with their default parameters. Regarding the algorithms LS-TR, LS-ARC, and LS-ARMIJO, we approximate the solution of the linear system B k s = -g k using the MINRES Matlab solver. The latter method is a Krylov subspace method designed to solve symmetric linear systems [START_REF] Paige | Solution of sparse indefinite systems of linear equations[END_REF]. We run the algorithms with the MINRES default parameters except the relative tolerance error which is set to 10 -4 . We note that on the tested problems, for LS-ARC/LS-TR , Assumption 3.1 was not violated frequently. The restoration of this assumption was ensured by performing iterations of GLRT-ARC/GLTR-TR (with the ℓ 2 -norm) until a new successful iteration is found.

To compare the performance of the algorithms we use performance profiles proposed by Dolan and Moré [START_REF] Dolan | Benchmarking optimization software with performance profiles[END_REF] over a variety of problems. Given a set of problems P (of cardinality |P|) and a set of solvers S, the performance profile ρ s (τ ) of a solver s is defined as the fraction of problems where the performance ratio r p,s is at most τ ρ s (τ ) = 1 |P| size{p ∈ P : r p,s ≤ τ }.

The performance ratio r p,s is in turn defined by r p,s = t p,s min{t p,s : s ∈ S} , where t p,s > 0 measures the performance of the solver s when solving problem p (seen here as the function evaluation, the gradient evaluation, and the CPU time). Better performance of the solver s, relatively to the other solvers on the set of problems, is indicated by higher values of ρ s (τ ). In particular, efficiency is measured by ρ s (1) (the fraction of problems for which solver s performs the best) and robustness is measured by ρ s (τ ) for τ sufficiently large (the fraction of problems solved by s). Following what is suggested in [START_REF] Dolan | Benchmarking optimization software with performance profiles[END_REF] for a better visualization, we will plot the performance profiles in a log 2 -scale (for which τ = 1 will correspond to τ = 0). We present the obtained performance profiles in Figure 1. Regarding the gradient evaluation (i.e., outer iteration) performance profile, see Figure 1(a), LS approaches are the most efficient among all the tested solvers (in more 60% of the tested problems LS methods perform the best, while GLRT-ARC and GLTR-TR are performing better only in less than 15%). When it comes to robustness, all the tested approaches exhibit good performance, GLRT-ARC and GLTR-TR are slightly better.

For function evaluation performance profile given by Figure 1(b), GLRT-ARC and GLTR-TR show a better efficiency but not as good as LS methods. In fact, in more than 50% of the tested problems LS methods perform the best while GLRT-ARC and GLTR-TR are better only in less than 35%. The robustness of the tested algorithms is the same as in the gradient evaluation performance profile.

In terms of the demanded computing time, see Figure 1(c), as one can expect, GLRT-ARC and GLTR-TR are turned to be very consuming compared to the LS approaches. In fact, unlike the LS methods where only an approximate solution of one linear system is needed, the GLRT/GLTR approaches may require (approximately) solving multiple linear systems in sequence.

For the LS approaches, one can see that LS-TR displays better performance compared to LS-ARMIJO on the tested problems. The main difference between the two LS algorithms is the strategy of choosing the search direction whenever g ⊤ k s Q k > 0. In our tested problems, the obtained performance using LS-TR suggests that going exactly in the opposite direction -s Q k , whenever s Q k is not a descent direction, can be seen as a good strategy compared to LS-ARMIJO.

Conclusions

In this paper, we have proposed the use of a specific norm in ARC/TR. With this norm choice, we have shown that the trial step of ARC/TR is getting collinear to the quasi-Newton direction. The obtained ARC/TR algorithm behaves as LS algorithms with a specific backtracking strategy. Under mild assumptions, the proposed scaled norm was shown to be uniformly equivalent to the Euclidean norm. In this case, the obtained LS algorithms enjoy the same convergence and complexity properties as ARC/TR. We have also proposed a second order version of the LS algorithm derived from ARC with an optimal worst-case complexity bound of order ǫ -3/2 . Our numerical experiments showed encouraging performance of the proposed LS algorithms.

A number of issues need further investigation, in particular the best choice and the impact of the parameter β k on the performance of the proposed LS approaches. Also, the analysis of the second order version of ARC suggests that taking the Newton direction is suitable for defining a line-search method with an optimal worst-case complexity bound of order ǫ -3/2 . It would be interesting to confirm the potential of the proposed line search strategy compared to the classical LS approaches using extensive numerical tests.

Theorem 3 . 2

 32 Let Assumption 3.1 hold. The step s N k is a stationary point for the subproblem (3) if and only if there exists

Theorem 4 . 1

 41 Let Assumption 3.1 hold. If

Assumption 4 . 2

 42 The matrix B k approximate the Hessian ∇ 2 f (x k ) in the sense that

Proposition 4 . 1

 41 Let Assumption 3.1 hold. Let θ k = β k s Q k 2 where β k ∈]β min , β max [ and β max > β min > 0.Then imposing the condition (20) in Algorithm 2 is equivalent to the following condition

Lemma 4 . 2

 42 Let Assumptions 4.1, 4.2 and 3.1 hold. Consider Algorithm 3 with θ k = β k s Q k 2 where β k ∈]β min , β max [ and β max > β min > 0. Then for all k ≥ 0

Figure 1 :

 1 Figure 1: Performance profiles for 62 large scale optimization problems (i.e., 1000 ≤ n ≤ 10000).

  β max [ and β max > β min > 0, in Theorem 4.1 we will show that such matrix M k exists. By using the associated M k -norm in the definition of the cubic model m k , one can show (see Theorem 3.3) that an approximate stationary point of the subproblem (3) is of the form

  then using [8, Theorem 3.1] one has that, for a given vector s * k , it is a global minimizer of m k if and only if it satisfies

  and 0 < β min < β max . Set the initial TR radius ∆ 0 > 0 and∆ max > ∆ 0 . for k = 1, 2, . . . do Choose a parameter β k ∈]β min , β max [; Let s Q k be an approximate stationary point of m Q k satisfying |g ⊤ k s Q k | ≥ ǫ d g k s Q k ; Set α k andα c k using (32) and (33); while condition (31) is not satisfied do Set ∆ k ← τ 1 ∆ k , and update α k and α c k using (32) and (33); end Set p k


Anaïs Ferris

Benjamin Reig

Asma Eddarir

Jean-François Pierson

Sébastien Garbarino

Daniel Guay

David Pech

Atypical Properties of FIB-Patterned RuOx Nanosupercapacitors

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

While the demand for ever-smaller electronic devices has pushed to the miniaturization of a variety of technologies, energy-storage units have lagged behind in this downsizing tendency. [START_REF] Oudenhoven | All-Solid-State Lithium-Ion Microbatteries: A Review of Various Three-Dimensional Concepts[END_REF] Developing energy-storage elements for self-powered nanosystems, such as nanoelectromechanical systems (NEMS) [START_REF] Craighead | Nanoelectromechanical Systems[END_REF] or wireless nanosensor networks, [START_REF] Wang | Self-Powered Nanosensors and Nanosystems[END_REF] is of critical importance in many areas of applications, ranging from home automation and industrial tracking to healthcare and environmental monitoring. As the size of power source should be commensurate with the device it powers, great efforts have been recently devoted to integrating energy harvesting [START_REF] Hu | Recent Advancements in Nanogenerators for Energy Harvesting[END_REF] and storage [START_REF] Lowy | Nanobatteries: Decreasing Size Power Sources for Growing Technologies[END_REF] nanodevices with the objective to build densely integrated electronic systems having total energy autonomy.

Electrochemical capacitors, also called supercapacitors, are reversible energy-storage devices with a high power density, fast charge and discharge rates, and long service life compared to batteries. [START_REF] Salunkhe | Large-Scale Synthesis of Coaxial Carbon Nanotube/Ni(OH)2 Composites for Asymmetric Supercapacitor Application[END_REF][START_REF] Salunkhe | Asymmetric Supercapacitors Using 3D Nanoporous Carbon and Cobalt Oxide Electrodes Synthesized from a Single Metal-Organic Framework[END_REF][START_REF] Salanne | Efficient Storage Mechanisms for Building Better Supercapacitors[END_REF] Nanoscale supercapacitors are consequently of great interest in the development of nanoscale sensor systems requiring the delivery of peak power and long operating lifetime. For nanoscale supercapacitors, it is imperative to consider all reported properties (capacitance, energy, power…) normalized to the footprint area on the chip. However, fabrication of miniaturized planar electrodes at very small scale is a challenge on its own. Optical lithographic efforts have led to the development of microscopic thin-film supercapacitors, 9,10 however the resolution of conventional photolithography techniques is limited by the diffraction of light, which makes it difficult for them to meet the demand of fabricating ultra-high density integrated devices. Actually, most of the "microsupercapacitorsˮ reported in the literature have photolithographic feature size well above 10 µm and typical footprint occupancy of ca. 1 cm 2 . [START_REF] Dinh | High-Resolution On-Chip Supercapacitors with Ultra-High Scan Rate Ability[END_REF] To overcome size limitation, an interesting approach is to combine optical lithography with the use of focused ion beam (FIB) technology to directly scribe a high-resolution pattern onto a deposited thin film electrode. [START_REF] Lobo | Miniaturized Supercapacitors: Focused Ion Beam Reduced Graphene Oxide Supercapacitors with Enhanced Performance Metrics[END_REF] Several carbonaceous [START_REF] Chaikittisilp | Nanoporous Carbons through Direct Carbonization of a Zeolitic Imidazolate Framework for Supercapacitor Electrodes[END_REF][START_REF] Salunkhe | Fabrication of Symmetric Supercapacitors Based on MOF-Derived Nanoporous Carbons[END_REF][START_REF] Zhuang | Silicon-Compatible Carbon-Based Micro-Supercapacitors[END_REF][START_REF] Huang | On-Chip and Freestanding Elastic Carbon Films for Micro-Supercapacitors[END_REF] and pseudocapacitive materials [START_REF] Eustache | MnO2 Thin Films on 3D Scaffold: Microsupercapacitor Electrodes Competing with "Bulkˮ Carbon Electrodes[END_REF][START_REF] Ferris | 3D RuO2 Microsupercapacitors with Remarkable Areal Energy[END_REF] have been evaluated for miniaturized supercapacitors, considering the choice of materials is one of the factors that ensure high performance. Among them, ruthenium oxide, RuOx, appears to be the most promising material owing to its high specific capacitance, highly reversible redox reactions and long cycling life. Even if its high cost has limited its development for large-size supercapacitors, the use of this material becomes relevant for miniaturized supercapacitors where only tiny amount of active material is required.

Here we describe the FIB-fabrication of a nanosupercapacitor based on ruthenium oxide that exhibits singular properties. The manufacturing approach allows the diminution of the cell dimension by six orders of magnitude (from square centimeters to few tens of square micrometers) and the reduction of the inter-electrode spacing by two orders of magnitude (from tens of micrometers to hundreds of nanometers). We show that this scaling down reduces the ohmic losses and improves the energy storage efficiency of the electrochemical devices. We also focus on the anomalous extension of cell voltage observed at very high charge/discharge rate.

A Cr/Pt (40/200 nm) thin film was deposited by evaporation on an oxidized silicon substrate

Si/SiO2 (500 nm), followed by the deposition of a 100 nm-thick metallic Ru by magnetron sputtering under a total pressure of 1 Pa without additional heating. [START_REF] Bouhtiyya | Application of Sputtered Ruthenium Nitride Thin Films as Electrode Material for Energy-Storage Devices[END_REF] The electrical resistivity of Ru was measured to be ca. 40 µΩ.cm. Using a suitable lithographic process and an optimized ion beam (Supporting Figure S1 and S2), a narrow gap of 50 nm was created by FIB sputter etching in the thin film of Pt/Ru material with a well-defined pattern, as illustrated in Figure 1. The Ru was then electrochemically oxidized into hydrous ruthenium oxide RuOx (Supporting Figure S3) before being heat-treated at 150°C for 1 h. A protective insulating SU-8 masking layer was subsequently deposited to define an electrochemically active surface exposed to the electrolyte, delimiting a final device area of 25 µm 2 (i.e. potentially enabling 4 million units per cm 2 ).

Figure 2a shows the Nyquist plot of the FIB nanosupercapacitor, with an exceptionally low equivalent series resistance (ESR, Figure 2a inset) of 821 Ω.µm 2 (i.e. 8.2 µΩ.cm 2 ) and a perfect vertical increase of the impedance in the low-frequency region. The corresponding specific power density is 304 µW/µm 2 (i.e. 30.4 kW/cm 2 ) for a cell voltage of 1 V, which is the highest value ever reported for miniaturized on-chip supercapacitors and more than four orders of magnitude higher than state-of-the-art microsupercapacitors. [START_REF] Dinh | High-Resolution On-Chip Supercapacitors with Ultra-High Scan Rate Ability[END_REF][START_REF] Pech | Ultrahigh-Power Micrometre-Sized Supercapacitors Based on Onion-Like Carbon[END_REF][START_REF] Liu | Superior Micro-Supercapacitors Based on Graphene Quantum Dots[END_REF][START_REF] Thissandier | Are Tomorrow's Micro-Supercapacitors Hidden in a Forest of Silicon Nanotrees ?[END_REF][START_REF] Shen | Engineering the Electrochemical Capacitive Properties of Microsupercapacitors Based on Graphene Quantum Dots/MnO2 Using Ionic Liquid Gel Electrolytes[END_REF] This prodigious power ability of nanosupercapacitors is explained by the ultra-small physical separation isolating the positive and the negative electrode, which leads to a dramatic reduction of the cell constant and the ESR, as demonstrated in our previous works. [START_REF] Pech | Influence of the Configuration in Planar Interdigitated Electrochemical Micro-Capacitors[END_REF] However, ultra-high power values should always be treated with caution. There is a trade-off between power and capacitance, and the ultimate performance improvement is to increase the areal power density without sacrificing the areal energy of the device. [START_REF] Kyeremateng | Microsupercapacitors as Miniaturized Energy-Storage Components for On-Chip Electronics[END_REF] In the low frequency region, an increase of the imaginary portion of the impedance is observed with a slope close to 90°, as it is expected for capacitive behavior with no leakage current. At such high impedance, the contribution of the dielectric capacitance of the underlying SiO2 layer, Cd, cannot be neglected. The measured capacitance, C, is therefore the sum of two capacitances in parallel, the dielectric capacitance and the pseudocapacitance of the nanosupercapacitor, Csc, so that C = Cd + Csc. Taking into account Cd, the cell capacitance deduced from the impedance spectrum at 100 mHz is 180 pF/µm 2 (i.e. 18 mF/cm 2 ), which is an excellent value compared to those reported for thin-film microsupercapacitors. [START_REF] Kyeremateng | Microsupercapacitors as Miniaturized Energy-Storage Components for On-Chip Electronics[END_REF][START_REF] Beidaghi | Capacitive Energy Storage in Micro-Scale Devices: Recent Advances in Design and Fabrication of Micro-Supercapacitors[END_REF] The high specific power of the nanosupercapacitor is thus concomitant with a high specific capacitance with a very low time constant  = ESR.C of 148 ns. The aptitude to combine high areal energy and high areal power density is also illustrated by the ability of the nanosupercapacitor to maintain a capacitive behavior at both low (Figure 2b) and ultra-high scan rates (Figure 2c). At low scan rates, the cyclic voltammograms (CVs) display the quasi-perfect rectangular shape of an ideal capacitor with no ESR. The cell capacitance, estimated from the CV, achieves a reproducible value of 40 pF/µm 2 (i.e. 4 mF/cm 2 ) when cycled at 5 mV/s, and an excellent areal energy density of 20 pJ/µm 2 (i.e. 2 mJ/cm 2 ) for a 1 V cell voltage. The volumetric capacitance is estimated to be around 222 pF/µm 3 (i.e. 222 F/cm 3 ) which is slightly lower to the theoretic value of hydrated ruthenium oxide. [START_REF] Hu | How to Achieve Maximum Utilization of Hydrous Ruthenium Oxide for Supercapacitors[END_REF] The capacitive behavior was also maintained at ultra-high voltage scan rates exceeding 20 V/s with good reversibility, as reported for high-power microsupercapacitors designed to meet the specifications of ac line-filtering applications. [START_REF] Miller | Graphene Double-Layer Capacitor with AC Line-Filtering Performance[END_REF][START_REF] Sheng | Ultrahigh-Rate Supercapacitors Based on Electrochemically Reduced Graphene Oxide for AC Line-Filtering[END_REF][START_REF] Wu | Alternating Current Line-Filter Based on Electrochemical Capacitors Utilizing Template-Patterned Graphene[END_REF][START_REF] Wu | Ultrathin Printable Graphene Supercapacitors with AC Line-Filtering Performance[END_REF] Another unexpected consequence of using nanopatterned supercapacitor is the extent of the cell voltage. We evaluated the electrochemical behavior of the RuOx based nanosupercapacitor at 10 V/s with increasing voltage window (Figure 3a). Surprisingly, the nanodevice was able to cycle up to 1.7 V in aqueous sulfuric acid electrolyte with no visible sign of degradation due to water electrolysis. This result challenges the long-held axiom that supercapacitors based on aqueous electrolyte have a restricted operating voltage range of ca. 1 V because of the electrochemical decomposition of water at higher potentials. [START_REF] Zheng | Electrochemical Behavior of Amorphous and Crystalline Ruthenium Oxide Electrodes[END_REF][START_REF] Dai | Cell Voltage Versus Electrode Potential Range in Aqueous Supercapacitors[END_REF] Moreover, an intriguing phenomenon is that the abrupt current increase related to water splitting appears to move towards higher voltage values with increasing scan rates, from ca. 1 V at 100 mV/s up to ca. 1.9 V at 50 V/s (Figure 3b). Since the stored energy E increases with the square of the voltage (E = ½C.V0 2 ), this extension of the nanosupercapacitor voltage leads to a 261 % increase in energy. As a result, the nanosupercapacitor has far more energy when high power delivery is required in very short times. This behavior is in total disagreement with conventional supercapacitors and microsupercapacitors where the specific energy decreases with increase in specific power because of kinetic and resistance issues. [START_REF] Simon | Materials for Electrochemical Capacitors[END_REF] To understand and analyze this unusual behavior, we have considered the sweep rate dependence of the recorded current at different cell voltages (from 1 to 1.9 V) as shown in Figure 4. A linear dependency between log(current i) and log(scan rate v) is observed for a cell voltage of 1 V in aqueous sulfuric acid electrolyte. The slope of the log(i) vs. log(v) plot is 0.96 on the whole sweep-rate range (from 50 mV/s to 20 V/s), indicating that the overall response tends to be capacitive as expected for a pseudocapacitive material tested within the domain of thermodynamic stability of water. When the nanosupercapacitor is tested at much higher voltages, i.e. well above the upper limit for water decomposition (H2O) into oxygen (O2) and hydrogen (H2) gas, an additional faradaic current contribution appears. In Figure 4, this is evidenced by a region at low scan rates where log(i) is independent of scan rate. The faradaic current if increases steadily with the cell voltage (from 1.5 to 1.9 V), suggesting the reaction is under kinetic control. [START_REF] Bard | Electrochemical Method: Fundamentals and Applications[END_REF] Accordingly, for a fixed cell voltage V0 ≥ 1.5 V, the current response is the sum of two contributions, a pseudocapacitive current (ic) originating from ruthenium oxide and a faradaic current (if) resulting from water electrolysis. For V0 ≥ 1.5 V, we can therefore observe two distinct behaviors according to the sweep-rate: at low and medium scan rates, the faradaic current of water electrolysis prevails on the capacitive current. However, the capacitive current ic = f(v) gets more and more important with increasing scan rates v and becomes larger than the faradaic contribution at high scan rates (i.e. when v > if / C). Having a sub microsecond time constant  of 148 ns, the nanosupercapacitors are moreover able to maintain capacitive behaviors at ultra-high voltage scan rates v. [START_REF] Kyeremateng | Microsupercapacitors as Miniaturized Energy-Storage Components for On-Chip Electronics[END_REF] This phenomenon explains the atypical extension of the nanosupercapacitor voltage above 1.5 V.

Furthermore, the ability to operate at such high voltage is illustrated by the remarkable lifetime of the device in harsh conditionsusing galvanostatic charge/discharge cycles at 8 nA/µm 2 (i.e. 0.8 A/cm 2 ) up to 1.5 V. Figure 5 reveals the incredible stability of the device, with no capacitance loss even after ten thousands cycles of charge/discharge. Regarding the galvanostatic cycles, they all exhibit a symmetrical triangular curve with a nearly linear variation of voltage as a function of time at very high current densities, from 2 to 64 nA/µm 2 (i.e. 0.2 to 6.4 A/cm 2 ) with a high specific energy reaching 130 pJ/µm 2 (i.e. 13 mJ/cm 2 ) for the cell. The potential IR-drop at the current switching point is also negligible, confirming the extremely small ESR of the cell, as aforementioned.

In summary, we have demonstrated that supercapacitors undergo remarkable enhancement in their electrochemical performances when passing from micro to nanodimensions, with unusual and unique properties in terms of specific energy, power, lifetime and cell voltage. Our FIBpatterned nanosupercapacitor displays a cell capacitance of 180 pF/µm 2 (i.e. 18 mF/cm 2 ) and can deliver an outstanding specific energy per surface area of 325 pJ/µm 2 (32.5 mJ/cm 2 ) thanks to a full utilization of the active material involved in the charge storage. The nanosupercapacitor exhibits also an ultralow ESR leading to a maximum power density of 304 µW/µm 2 (i.e.

30.4 kW/cm 2 ), which is orders of magnitude higher than any result reported with alternative devices. Electrochemical investigations carried out in 0.5 M H2SO4 solution also confirmed the possibility to extend, under certain conditions, the operating voltage of up to 1.9 V in aqueous solution without any capacitance fade. Although these phenomena arising from nanoengineered supercapacitors have been validated with a RuOx pseudocapacitive material in aqueous sulfuric acid, the extension of the upper voltage limit could also be obtained with carbonaceous electrode materials and organic electrolytes working well above 2.

FIGURESFigure 1 .

 1 FIGURES

Figure 2 .

 2 Figure 2. Electrochemical characterization of the nanosupercapacitor soaked in one drop of

Figure 3 .Figure 4 .

 34 Figure 3. Anomalous extension of the nanosupercapacitor voltage in aqueous H2SO4 electrolyte.

Figure 5 .

 5 Figure 5. Galvanostatic charge/discharge measurements within a cell voltage of 1.5 V. (a) Even

ACKNOWLEDGMENT

This work was partly supported by the French RENATECH network and the Canada Research Chair Program.

ASSOCIATED CONTENT

Supporting Information.

Experimental methods, sweep-rate dependence of voltammetric currents, additional figures, and supporting references.