Hedy Attouch

Alexandre Cabot
email: alexandre.cabot@u-bourgogne.fr

CONVERGENCE RATE OF A RELAXED INERTIAL PROXIMAL ALGORITHM FOR CONVEX MINIMIZATION

Keywords: May 24, 2018. 1991 Mathematics Subject Classification. 49M37, 65K05, 65K10, 90C25 Inertial proximal method, Lyapunov analysis, maximally monotone operators, nonsmooth convex minimization, relaxation, subdifferential of convex functions

In a Hilbert space setting, the authors recently introduced a general class of relaxed inertial proximal algorithms that aim at solving monotone inclusions. In this paper, we specialize this study in the case of non-smooth convex minimization problems. We obtain convergence rates for the values which have similarities with the results based on the Nesterov accelerated gradient method. The joint adjustment of inertia, relaxation and proximal terms plays a central role. In doing so, we put to the fore inertial proximal algorithms that converge for general monotone inclusions, and which, in the case of convex minimization, give fast convergence rates of the values in the worst case.

Introduction

Throughout the paper, H is a real Hilbert space equipped with the scalar product ., . and the corresponding norm . . The Relaxed Inertial Proximal Algorithm (RIPA) was introduced by the authors in [START_REF] Attouch | Convergence of a relaxed inertial proximal algorithm for maximally monotone operators[END_REF]. It aims at solving by fast methods the inclusion A(x) 0, where A : H → 2 H is a general maximally monotone operator. (RIPA) is a proximal-based algorithm involving both inertia and relaxation aspects. In [START_REF] Attouch | Convergence of a relaxed inertial proximal algorithm for maximally monotone operators[END_REF], it is shown the weak convergence of the iterates to equilibria under general conditions on the inertia, relaxation, and proximal coefficients of the algorithm. It extends the work of Attouch-Peypouquet [START_REF] Attouch | Convergence of inertial dynamics and proximal algorithms governed by maximal monotone operators[END_REF] which concerns the particular case where the inertial coefficient is of the form 1 -α k , an important issue because of its connection with the accelerated method of Nesterov, see [START_REF] Attouch | Convergence rates of inertial forward-backward algorithms[END_REF], [START_REF] Attouch | Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity[END_REF], [START_REF] Chambolle | On the convergence of the iterates of the Fast Iterative Shrinkage/Thresholding Algorithm[END_REF], [START_REF] Su | A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights[END_REF].

In this paper, we specialize the study of (RIPA) in the case of (nonsmooth) convex minimization problems. This corresponds to taking A = ∂Φ where Φ : H → R ∪ {+∞} is a convex lower semicontinuous proper function. The algorithm is then written [START_REF] Álvarez | On the minimizing property of a second-order dissipative system in Hilbert spaces[END_REF] (RIPA)

y k = x k + α k (x k -x k-1 ) x k+1 = (1 -ρ k )y k + ρ k prox µ k Φ (y k ),
where the proximal mapping prox µΦ : H → H is defined, for every x ∈ H, and every µ > 0 by the formula prox µΦ (x) = argmin ξ∈H µΦ(ξ) + 1 2

x -ξ 2 .

The sequence (α k ) of nonnegative numbers reflects the inertial aspects, while (ρ k ) is the sequence of positive relaxation parameters. The sequence (µ k ) of positive numbers makes it possible to consider the proximal operator with a varying parameter, which is an important issue in this context, see [START_REF] Attouch | Convergence of inertial dynamics and proximal algorithms governed by maximal monotone operators[END_REF]. By using variational methods and well-chosen Lyapunov functions, we obtain convergence rates for the values. In doing so, we put to the fore inertial algorithms whose iterates converge in the case of general monotone inclusions, and which, in the case of convex minimization, give fast convergence rates of the values (in the worst case). Let's first recall the main results concerning (RIPA) in the general maximally monotone framework.

1.1. (RIPA) for general monotone inclusions. Given A : H → 2 H a maximally monotone operator, the Relaxed Inertial Proximal Algorithm, (RIPA) for short, is defined by, for k ≥ 1 (RIPA)

y k = x k + α k (x k -x k-1 )
x k+1 = (1 -ρ k )y k + ρ k J µ k A (y k ).

In the above formula, J µA = (I + µA) -1 is the resolvent of A with index µ > 0. It plays a central role in the analysis of (RIPA), along with the Yosida regularization of A with parameter µ > 0, which is defined by A µ = 1 µ (I -J µA ). We denote by zerA the set of zeros of A, and we assume that zerA = ∅. The weak convergence of the sequences (x k ) generated by the algorithm (RIPA) is based on a joint tuning of the sequences (α k ), (µ k ), (ρ k ). As a crucial ingredient, the analysis of the convergence properties of (RIPA) involves the sequence (t k ) defined by [START_REF] Álvarez | Weak Convergence of a Relaxed and Inertial Hybrid Projection-Proximal Point Algorithm for Maximal Monotone Operators in Hilbert Space[END_REF] t

k := 1 + +∞ l=k   l j=k α j   .
The sequence (t k ) is well defined under the following standing assumption

(K 0 ) +∞ l=k   l j=k α j   < +∞ for every k ≥ 1.
The formula (2) that allows to pass from (α k ) to (t k ) may seem complicated. By contrast, one can simply retrieve (α k ) from (t k ) thanks to the following formula that will prove very useful.

Lemma 1.1. Assume that the nonnegative sequence (α k ) satisfies (K 0 ). Then the sequence (t k ) satisfies

(3) 1 + α k t k+1 = t k for every k ≥ 1.
Let us first formulate the convergence properties of (RIPA) in the case (ρ k ) bounded away from zero.

Theorem 1.2. ([6, Theorem 2.6]) Let A : H → 2 H be a maximally monotone operator such that zerA = ∅. Suppose that α k ∈ [0, 1], ρ k ∈]0, 2] and µ k > 0 for every k ≥ 1. Under (K 0 ), let (t k ) be the sequence defined by [START_REF] Álvarez | Weak Convergence of a Relaxed and Inertial Hybrid Projection-Proximal Point Algorithm for Maximal Monotone Operators in Hilbert Space[END_REF]. Assume that there exists ε ∈]0, 1[ such that for k large enough,

(L) (1 -ε) 2 -ρ k-1 ρ k-1 (1 -α k-1 ) ≥ α k t k+1 1 + α k + 2 -ρ k ρ k (1 -α k ) - 2 -ρ k-1 ρ k-1 (1 -α k-1 ) + .
Then for any sequence (x k ) generated by (RIPA), we have

(i) +∞ k=1 2 -ρ k-1 ρ k-1 (1 -α k-1 ) x k -x k-1 2 < +∞, and hence +∞ k=1 α k t k+1 x k -x k-1 2 < +∞. (ii) +∞ k=1 ρ k (2 -ρ k ) t k+1 µ k A µ k (x k ) 2 < +∞.
(iii) For any z ∈ zerA, lim k→+∞ x k -z exists, and hence (x k ) is bounded. Assume moreover that lim sup k→+∞ ρ k < 2, and lim inf k→+∞ ρ k > 0. Then the following holds

(iv) lim k→+∞ µ k A µ k (x k ) = 0. (v) If lim inf k→+∞ µ k > 0, then there exists x ∞ ∈ zerA such that x k x ∞ weakly in H as k → +∞.
Let us now state the convergence results in the case of a possibly vanishing sequence (ρ k ).

Theorem 1.3. ([6, Theorem 2.14]) Let A : H → 2 H be a maximally monotone operator such that zerA = ∅. Suppose that α k ∈ [0, 1], ρ k ∈]0, 2] and µ k > 0 for every k ≥ 1. Assume moreover that conditions (K 0 ) and (L) hold true. Then for any sequence (x k ) generated by (RIPA), (i) There exists C ≥ 0 such that for every k ≥ 1,

x k+1 -x k ≤ C k i=1 k j=i+1 α j ρ i .
Assume morover that lim sup k→+∞ ρ k < 2, together with

• k i=1 k j=i+1 α j ρ i = O(ρ k t k+1 ), |µ k+1 -µ k | µ k+1 = O(ρ k t k+1 ), ρ k-1 t k = O(ρ k t k+1 ) as k → +∞; • +∞ k=1 ρ k t k+1 = +∞. Then the following holds (ii) lim k→+∞ µ k A µ k (x k ) = 0. If lim inf k→+∞ µ k > 0, then there exists x ∞ ∈ zerA such that x k x ∞ weakly in H as k → +∞.
In particular, the above results provide estimates concerning the rate of convergence to zero of the discrete velocities. When A is the subdifferential of a convex lower semicontinuous proper function, we will complete these results by estimating the rate of convergence of the values. 1.2. (RIPA) for convex minimization. Let us now suppose that A is the subdifferential of a convex lower semicontinuous proper function Φ : H → R ∪ {+∞}, let A = ∂Φ. Then, as a classical result, A : H → 2 H is a maximally monotone operator, and the minimizers of Φ are exactly the zeros of A. Let us specialize (RIPA) in this framework. We have J µ∂Φ = prox µΦ , hence the formulation (1) of (RIPA). Let's give another useful formulation of (RIPA). By definition of the Yosida approximation

(1 -ρ k )y k + ρ k J µ k A (y k ) = y k -ρ k µ k A µ k (y k ).
We have A µ = ∇Φ µ , where Φ µ is the Moreau envelope of Φ with index µ > 0. Recall that, for all

x ∈ H Φ µ (x) = inf ξ∈H Φ(ξ) + 1 2µ x -ξ 2 ,
see Appendix A for its classical properties. It follows that (RIPA) can be rewritten in an equivalent way (4) (RIPA)

y k = x k + α k (x k -x k-1 ) x k+1 = y k -ρ k µ k ∇Φ µ k (y k ).
As a distinctive property, Φ µ : H → R is a convex differentiable function, whose gradient is Lipschitz continuous. Thus, when A is the subdifferential of a convex lower semicontinuous proper function, this property naturally links (RIPA) to the inertial gradient methods, see [START_REF] Álvarez | On the minimizing property of a second-order dissipative system in Hilbert spaces[END_REF], [START_REF] Attouch | Convergence rates of inertial forward-backward algorithms[END_REF], [START_REF] Attouch | The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1 k 2[END_REF], [START_REF] Aujol | Stability of over-relaxations for the Forward-Backward algorithm, application to FISTA[END_REF] [13], [START_REF] Chambolle | On the convergence of the iterates of the Fast Iterative Shrinkage/Thresholding Algorithm[END_REF], [START_REF] Drori | Performance of first-order methods for smooth convex minimization: a novel approach[END_REF], [START_REF] Kim | Optimized first-order methods for smooth convex minimization[END_REF], [START_REF] Liang | Local linear convergence of forward-backward under partial smoothness[END_REF], [START_REF] Nesterov | Introductory lectures on convex optimization: A basic course[END_REF], [START_REF] Su | A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights[END_REF], [START_REF] Villa | Accelerated and inexact forward-backward[END_REF] for some of the rich literature that has been devoted to this class of algorithms in recent years. The new aspects of the algorithm (RIPA) are the general inertial coefficients (α k ), the fact that the potential Φ µ k varies at each iteration, as well as the step size ρ k µ k . A helpful study is [START_REF] Attouch | Convergence rates of inertial forward-backward algorithms[END_REF], where the authors considered inertial forward-backward algorithms for structured convex minimization problems, and with general inertial coefficients.

1.3. Links with continuous dynamics. Linking (RIPA) to continuous inertial dynamical systems provides a physical intuition, and enlights the role of parameters entering the algorithm. Following [START_REF] Attouch | Convergence of damped inertial dynamics governed by regularized maximally monotone operators[END_REF] and [START_REF] Attouch | Convergence of inertial dynamics and proximal algorithms governed by maximal monotone operators[END_REF], let us consider the continuous dynamics

(5) ẍ(t) + γ(t) ẋ(t) + ∇Φ µ(t) (x(t)) = 0,
where γ(•) is a positive viscous damping parameter, which is time-dependent. It is governed by the Yosida regularization of the maximally monotone operator ∂Φ, with a time-dependent regularization parameter µ(t). Thanks to the Lipschitz continuity property of the Yosida approximation, this dynamics is relevant owing to the Cauchy-Lipschitz theorem, and the corresponding Cauchy problem is well-posed. Let us describe successively explicit and implicit discretization of [START_REF] Attouch | Convergence of damped inertial dynamics governed by regularized maximally monotone operators[END_REF].

Take a time step h k > 0, and set

t k = k i=1 h i , x k = x(t k ), µ k = µ(t k ), γ k = γ(t k ). 1.3.1.
Explicit discretization. A finite-difference scheme for [START_REF] Attouch | Convergence of damped inertial dynamics governed by regularized maximally monotone operators[END_REF] with centered second-order variation gives

(6) 1 h 2 k (x k+1 -2x k + x k-1 ) + γ k h k (x k -x k-1 ) + ∇Φ µ k (y k ) = 0,
where y k is an extrapolated point from x k and x k-1 that will be chosen later (because ∇Φ µ k is Lipschitz continuous, there is some flexibility in this choice). After developing (6), we obtain

x k+1 = x k + (1 -γ k h k )(x k -x k-1 ) -h 2 k ∇Φ µ k (y k ). Take y k = x k + (1 -γ k h k )(x k -x k-1
), which is the Nesterov choice for the extrapolation term. We obtain

y k = x k + (1 -γ k h k )(x k -x k-1 ) x k+1 = y k -h 2 k ∇Φ µ k (y k ). That's algorithm (RIPA), as formulated in (4) with α k = 1 -γ k h k and ρ k = h 2 k µ k . Thus ρ k µ k
has the dimension of the square of a length, and the vanishing viscosity property γ k → 0 is related to α k → 1.

1.3.2. Implicit discretization. Implicit discretization of (5) gives 1 h 2 k (x k+1 -2x k + x k-1 ) + γ k h k (x k -x k-1 ) + ∇Φ µ k (x k+1 ) = 0. Equivalently, x k+1 + h 2 k ∇Φ µ k (x k+1 ) = x k + (1 -γ k h k ) (x k -x k-1
), which gives

x k+1 = I + h 2 k ∇Φ µ k -1 (x k + (1 -γ k h k ) (x k -x k-1 )) .
Using the resolvent equation (see [START_REF] Attouch | Convergence of a relaxed inertial proximal algorithm for maximally monotone operators[END_REF] for more details) we obtain   

y k = x k + (1 -γ k h k ) (x k -x k-1 ) x k+1 = µ k µ k + h 2 k y k + h 2 k µ k + h 2 k prox (µ k +h 2 k )Φ (y k ).
That's algorithm (RIPA) with

α k = 1 -γ k h k , ρ k = h 2 k µ k +h 2 k
, and proximal parameter µ k + h 2 k .

1.4. Inertia and relaxation. In his pioneering work [START_REF] Polyak | Some methods of speeding up the convergence of iteration methods[END_REF], Polyak introduced the Heavy Ball method in order to speed up the classical gradient algorithm. Later Alvarez [START_REF] Álvarez | On the minimizing property of a second-order dissipative system in Hilbert spaces[END_REF] studied the Inertial Proximal algorithm, which can be viewed as an implicit version of the Heavy Ball method. The extension from the subgradient case to the maximally monotone case was first considered by Alvarez-Attouch [START_REF] Álvarez | An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping[END_REF]. Recently, an extensive literature has been devoted to inertial methods, in relation with their acceleration properties.

Relaxation has proven to be an essential ingredient in the resolution of monotone inclusions, see Bauschke-Combettes [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert spaces[END_REF], Eckstein-Bertsekas [START_REF] Eckstein | On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators[END_REF]. After having reformulated the problem in the form of a fixed point, it makes it possible to use Krasnoselskii-Mann theorem. Without using inertia, over-relaxation provides a natural way to speed up the algorithm. By contrast, for the resolution of monotone inclusions by inertial methods, we will see that under-relaxation allows to balance the inertial extrapolation effect. This makes it play a crucial role in the convergence of inertial proximal methods for general monotone inclusions. Let us mention some related contributions: Alvarez [START_REF] Álvarez | Weak Convergence of a Relaxed and Inertial Hybrid Projection-Proximal Point Algorithm for Maximal Monotone Operators in Hilbert Space[END_REF], Attouch-Cabot [START_REF] Attouch | Convergence of a relaxed inertial proximal algorithm for maximally monotone operators[END_REF], Attouch-Peypouquet [START_REF] Attouch | Convergence of inertial dynamics and proximal algorithms governed by maximal monotone operators[END_REF], Bot-Csetnek [START_REF] Bot | Second order forward-backward dynamical systems for monotone inclusion problems[END_REF], Maingé [START_REF] Maingé | Convergence theorems for inertial KM-type algorithms[END_REF]. In [START_REF] Iutzeler | Generic online acceleration scheme for optimization algorithms via relaxation and inertia[END_REF], Iutzeler-Hendrickx compare the numerical performances of inertia and relaxation techniques.

2. Convergence rate of the values for (RIPA) Throughout this section, we assume that A = ∂Φ, and make the following assumptions on the function Φ and the sequences (α k ), (ρ k ), (µ k ):

(H)                • Φ : H → R ∪ {+∞} is a convex lower semicontinuous proper function; • S := argminΦ = ∅; • (α k ) is a nonnegative sequence; • 0 < ρ k ≤ 1 for all k ≥ 1;
• (µ k ) and (ρ k µ k ) are nondecreasing sequences of positive numbers.

For each k ≥ 1, we write briefly Φ k for Φ µ k , and set s k = ρ k µ k . Therefore, (RIPA) is written in an equivalent way [START_REF] Attouch | Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity[END_REF]

y k = x k + α k (x k -x k-1 ) x k+1 = y k -s k ∇Φ k (y k ).
A key point of our study will be to control the variations of Φ k with respect to k. To do this, we will use the fact that the application µ → Φ µ is nonincreasing (a direct consequence of its definition), and assume that k → µ k is nondecreasing (assumption (H)).

2.1. Preliminary results. Let us establish some lemmas concerning the energy sequence (W k ) and the sequence of anchor terms (h k ). They will play a central role in the Lyapunov analysis of (RIPA).

2.1.1. Descent rule. As a key classical ingredient, we use the descent rule for the gradient method, that we recall below, see

[13, Lemma 2.3], [17, Lemma 1]. Lemma 2.1. (descent rule) Suppose that Θ : H → R is a convex, differentiable function, whose gradient is L-Lipschitz continuous. Then for any 0 < s ≤ 1 L , for all x, y ∈ H, we have Θ(y -s∇Θ(y)) ≤ Θ(x) + ∇Θ(y), y -x - s 2 ∇Θ(y) 2 .
Note that ∇Φ k is Lipschitz continuous with the Lipschitz constant 1 µ k . We have s k = ρ k µ k ≤ µ k , therefore the descent rule applies for Φ k with the step size s k . So, the following inequality is true for all x, y ∈ H, and all k ≥ 1

(8) Φ k (y -s k ∇Φ k (y)) ≤ Φ k (x) + ∇Φ k (y), y -x - s k 2 ∇Φ k (y) 2 .
2.1.2. Energy sequence (W k ). Let us introduce the sequence (W k )

W k := Φ k (x k ) -min Φ + 1 2s k x k -x k-1 2 .
The term W k is naturally interpreted as the global mechanical energy (potential + kinetic) at the stage k. Since inf Φ k = inf Φ, we have Φ k (x k ) -min Φ ≥ 0. Therefore, W k is nonnegative, as the sum of two nonnegative terms. Let us evaluate the energy decay. The following result is consistent with the fact that the friction effect, and hence the dissipation of mechanical energy, is related to α k ≤ 1.

Proposition 2.2. Let us make assumption (H). Let (x k ) be a sequence generated by the algorithm (RIPA). Then, the energy sequence

(W k ) satisfies for every k ≥ 1, (9) W k+1 -W k ≤ - 1 -α 2 k 2s k x k -x k-1 2 .
As a consequence, the sequence

(W k ) is nonincreasing if α k ∈ [0, 1] for every k ≥ 1.
Proof. By applying formula [START_REF] Attouch | The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1 k 2[END_REF] with y = y k and x = x k , we obtain

Φ k (x k+1 ) = Φ k (y k -s k ∇Φ k (y k )) ≤ Φ k (x k ) + ∇Φ k (y k ), y k -x k - s k 2 ∇Φ k (y k ) 2 = Φ k (x k ) - 1 2s k y k -s k ∇Φ k (y k ) -x k 2 + 1 2s k y k -x k 2 . Since x k+1 = y k -s k ∇Φ k (y k ) and y k -x k = α k (x k -x k-1 ), this implies that Φ k (x k+1 ) ≤ Φ k (x k ) - 1 2s k x k+1 -x k 2 + α 2 k 2s k x k -x k-1 2 . Equivalently Φ k (x k+1 ) + 1 2s k x k+1 -x k 2 ≤ Φ k (x k ) + 1 2s k x k -x k-1 2 + α 2 k 2s k - 1 2s k x k -x k-1 2 .
By assumption (H), the sequences (s k ) = (ρ k µ k ) and (µ k ) are nondecreasing. These properties respectively imply that

1 2s k+1 ≤ 1 2s k and Φ k+1 ≤ Φ k . It follows that Φ k+1 (x k+1 ) + 1 2s k+1 x k+1 -x k 2 ≤ Φ k (x k ) + 1 2s k x k -x k-1 2 + α 2 k 2s k - 1 2s k x k -x k-1 2 .
This can be equivalently rewritten as

W k+1 ≤ W k - 1 -α 2 k 2s k x k -x k-1 2 .
The last assertion is immediate.

Anchor sequence (h k ).

Let us now fix x * ∈ H, and consider the anchor sequence (h k ) which is defined by

h k = 1 2 x k -x * 2 .
Proposition 2.3. Let us make assumption (H). Let (x k ) be a sequence generated by the algorithm (RIPA). We have for every k ≥ 1

(10) h k+1 -h k -α k (h k -h k-1 ) = 1 2 (α 2 k +α k ) x k -x k-1 2 -s k ∇Φ µ k (y k ), y k -x * + s 2 k 2 ∇Φ µ k (y k ) 2 .
If moreover x * ∈ argmin Φ, then

h k+1 -h k -α k (h k -h k-1 ) ≤ 1 2 (α 2 k + α k ) x k -x k-1 2 -s k (Φ µ k (x k+1 ) -min Φ).
Proof. Observe that

y k -x * 2 = x k + α k (x k -x k-1 ) -x * 2 = x k -x * 2 + α 2 k x k -x k-1 2 + 2α k x k -x * , x k -x k-1 = x k -x * 2 + α 2 k x k -x k-1 2 + α k x k -x * 2 + α k x k -x k-1 2 -α k x k-1 -x * 2 = x k -x * 2 + α k ( x k -x * 2 -x k-1 -x * 2 ) + (α 2 k + α k ) x k -x k-1 2 = 2[h k + α k (h k -h k-1 )] + (α 2 k + α k ) x k -x k-1 2 .
Setting briefly

A k = h k+1 -h k -α k (h k -h k-1 ) = 1 2 x k+1 -x * 2 -[h k + α k (h k -h k-1
)], we deduce that

A k = 1 2 x k+1 -x * 2 - 1 2 y k -x * 2 + 1 2 (α 2 k + α k ) x k -x k-1 2 = x k+1 -y k , 1 2 (x k+1 + y k ) -x * + 1 2 (α 2 k + α k ) x k -x k-1 2 = x k+1 -y k , y k -x * + 1 2 x k+1 -y k 2 + 1 2 (α 2 k + α k ) x k -x k-1 2 .
Using the equality x k+1 = y k -s k ∇Φ µ k (y k ), we obtain [START_REF] Aujol | Stability of over-relaxations for the Forward-Backward algorithm, application to FISTA[END_REF].

Let us now assume that x * ∈ argmin Φ. From inequality (8) applied with y = y k and x = x * (recall the simplified notation

Φ k = Φ µ k ) Φ k (x k+1 ) = Φ k (y k -s k ∇Φ k (y k )) ≤ Φ k (x * ) + ∇Φ k (y k ), y k -x * - s k 2 ∇Φ k (y k ) 2 .
Since Φ k (x * ) = min Φ, we infer that

-s k ∇Φ k (y k ), y k -x * + s 2 k 2 ∇Φ k (y k ) 2 ≤ -s k (Φ k (x k+1 ) -min Φ),
which completes the proof of Proposition 2.3.

2.2.

Convergence rates for the values. Given x * ∈ argmin Φ, let us define (E k ) by, for each k ≥ 1 ( 11)

E k = t 2 k (Φ µ k (x k ) -min Φ) + 1 2ρ k µ k x k-1 + t k (x k -x k-1 ) -x * 2 .
With our simplified notations Φ k = Φ µ k , and

s k = ρ k µ k , the energy E k writes E k = t 2 k (Φ k (x k ) -min Φ) + 1 2s k x k-1 + t k (x k -x k-1 ) -x * 2 .
The next result shows that the sequence (E k ) is nonincreasing, under some suitable condition (K 1 ).

The following statement is an adaptation of [13, Lemma 4.1] to our setting.

Proposition 2.4. Let us make assumptions (H) and (K 0 ). Let (x k ) be a sequence generated by the algorithm (RIPA), and let (E k ) be the sequence defined by [START_REF] Aujol | Optimal convergence rates for Nesterov acceleration[END_REF]. Then we have

(12) E k+1 -E k ≤ (t 2 k+1 -t 2 k -t k+1 )(Φ µ k (x k ) -min Φ). Under the assumption (K 1 ) t 2 k+1 -t 2 k ≤ t k+1 for every k ≥ 1, then the sequence (E k ) is nonincreasing.
Proof. Let us write successively formula (8) at y = y k and x = x k , then at y = y k and x = x * . Recalling that x k+1 = y k -s k ∇Φ k (y k ), we obtain the two inequalities

Φ k (x k+1 ) ≤ Φ k (x k ) + ∇Φ k (y k ), y k -x k - s k 2 ∇Φ k (y k ) 2 , ( 13
) Φ k (x k+1 ) ≤ min Φ + ∇Φ k (y k ), y k -x * - s k 2 ∇Φ k (y k ) 2 . ( 14
)
Multiplying ( 13) by t k+1 -1 ≥ 0, then adding ( 14), we derive that

t k+1 Φ k (x k+1 ) ≤ (t k+1 -1)Φ k (x k ) + min Φ (15) + ∇Φ k (y k ), (t k+1 -1)(y k -x k ) + y k -x * - s k 2 t k+1 ∇Φ k (y k ) 2 .
Observe that

(t k+1 -1)(y k -x k ) + y k = t k+1 y k -(t k+1 -1)x k = x k + t k+1 α k (x k -x k-1 ) = x k-1 + (1 + t k+1 α k )(x k -x k-1 ) = x k-1 + t k (x k -x k-1
) in view of (3).

Setting

z k = x k-1 + t k (x k -x k-1
), we then deduce from ( 15) that [START_REF] Brézis | Opérateurs maximaux monotones dans les espaces de Hilbert et équations d'évolution[END_REF]

t k+1 (Φ k (x k+1 )-min Φ) ≤ (t k+1 -1)(Φ k (x k )-min Φ)+ ∇Φ k (y k ), z k -x * - s k 2 t k+1 ∇Φ k (y k ) 2 .
On the other hand, observe that

z k+1 -z k = x k + t k+1 (x k+1 -x k ) -x k-1 -t k (x k -x k-1 ) = t k+1 (x k+1 -x k ) -(t k -1)(x k -x k-1 ) = t k+1 (x k+1 -x k -α k (x k -x k-1 )) in view of (3) = t k+1 (x k+1 -y k ) = -s k t k+1 ∇Φ k (y k ). It ensues that z k+1 -x * = z k -x * -s k t k+1 ∇Φ k (y k ), which gives z k+1 -x * 2 = z k -x * 2 -2s k t k+1 ∇Φ k (y k ), z k -x * + s 2 k t 2 k+1 ∇Φ k (y k ) 2
. By using this equality in [START_REF] Brézis | Opérateurs maximaux monotones dans les espaces de Hilbert et équations d'évolution[END_REF], we find

t k+1 (Φ k (x k+1 ) -min Φ) ≤ (t k+1 -1)(Φ k (x k ) -min Φ) + 1 2s k t k+1 ( z k -x * 2 -z k+1 -x * 2 ),
which is equivalent to

(17) t 2 k+1 (Φ k (x k+1 ) -min Φ) + 1 2s k z k+1 -x * 2 ≤ (t 2 k+1 -t k+1 )(Φ k (x k ) -min Φ) + 1 2s k z k -x * 2 .
By assumption (H), the sequences (s k ) = (ρ k µ k ) and (µ k ) are nondecreasing. These properties respectively imply that 1 s k+1 ≤ 1 s k and Φ k+1 ≤ Φ k . Therefore, we deduce from (17) that

t 2 k+1 (Φ k+1 (x k+1 ) -min Φ) + 1 2s k+1 z k+1 -x * 2 ≤ (t 2 k+1 -t k+1 )(Φ k (x k ) -min Φ) + 1 2s k z k -x * 2 .
Using the expression of the sequence (E k ), we obtain

E k+1 ≤ E k + (t 2 k+1 -t 2 k -t k+1 )(Φ k (x k ) -min Φ)
. The last assertion is immediate.

We can now state our main result concerning the rate of convergence of the values for (RIPA).

Theorem 2.5. Under (H), assume that the nonnegative sequence (α k ) satisfies (K 0 )-(K 1 ). Let (x k ) be a sequence generated by the algorithm (RIPA). Then we have

(i) For every k ≥ 1, Φ µ k (x k ) -min Φ ≤ C t 2 k , with C = t 2 1 (Φ µ1 (x 1 ) -min Φ) + 1 ρ1µ1 (d(x 0 , S) 2 + t 2 1 x 1 -x 0 2 ).
As a consequence, setting p k = prox µ k Φ (x k ), we have

Φ(p k ) -min Φ = O 1 t 2 k and x k -p k 2 = O µ k t 2 k as k → +∞.
(ii) Assume moreover that there exists 0 ≤ m < 1 such that

(K + 1 ) t 2 k+1 -t 2 k ≤ m t k+1 for every k ≥ 1. Then we have +∞ k=1 t k+1 (Φ µ k (x k ) -min Φ) < +∞.
Proof. (i) By Proposition 2.4, the sequence (E k ) is nonincreasing. It ensues that E k ≤ E 1 for every k ≥ 1. Recalling the expression of E k , we deduce that

t 2 k (Φ µ k (x k ) -min Φ) ≤ E 1 = t 2 1 (Φ µ1 (x 1 ) -min Φ) + 1 2ρ 1 µ 1 x 0 + t 1 (x 1 -x 0 ) -x * 2 ≤ t 2 1 (Φ µ1 (x 1 ) -min Φ) + 1 ρ 1 µ 1 ( x 0 -x * 2 + t 2 1 x 1 -x 0 2 ).
Since x * can be taken arbitrarily in S = argminΦ, we obtain

t 2 k (Φ µ k (x k ) -min Φ) ≤ C, with C = t 2 1 (Φ µ1 (x 1 ) -min Φ) + 1 ρ 1 µ 1 d(x 0 , S) 2 + t 2 1 x 1 -x 0 2 .
(ii) By summing inequality ( 12) from k = 1 to n, we find

E n+1 + n k=1 (t k+1 -t 2 k+1 + t 2 k )(Φ µ k (x k ) -min Φ) ≤ E 1 . Since E n+1 ≥ 0 and since t 2 k+1 -t 2 k ≤ m t k+1 , this implies that (1 -m) n k=1 t k+1 (Φ µ k (x k ) -min Φ) ≤ E 1 .
The expected estimate is obtained by letting n tend to infinity.

Remark 2.6. By contrast with the classical inertial gradient methods, the rate of convergence of the values for (RIPA) is expressed in terms of the proximal sequence (p k ), with p k = prox µ k Φ (x k ), and not directly in terms of (x k ). This has some analogy with the convergence properties of the shadow sequence in the Douglas-Rachford algorithm.

Remark 2.7. Let us assume that x 1 belongs to the domain of Φ, that is Φ(x 1 ) < +∞. Then Φ µ1 (x 1 ) ≤ Φ(x 1 ) < +∞, and Theorem 2.5 gives, for every k ≥ 1

Φ µ k (x k ) -min Φ ≤ E 1 (x 0 , x 1 ) t 2 k where E 1 (x 0 , x 1 ) = t 2 1 [Φ(x 1 ) -min Φ] + 1 ρ 1 µ 1 x 0 -x * + t 1 (x 1 -x 0 ) 2 .
As a function of (x 0 , x 1 ), E 1 achieves its minimum when x 1 ∈ argmin Φ and x 1 -x 0 = 1 t1 (x * -x 0 ). Of course, taking x 1 ∈ argmin Φ is not realistic, since this would mean that the problem is already solved. But this suggests taking the initial direction x 1 -x 0 as a multiple of an approximation of x * -x 0 , such as the opposite of the gradient ∇Φ µ0 (x 0 ). This amounts to take a gradient step at the first stage.

2.3.

Convergence rate of the velocities to zero. Let us first show estimates in a summation form.

Proposition 2.8. Under (H), assume that the sequence (α k ) satisfies (K 0 )-(K + 1 ). Let (x k ) be a sequence generated by the algorithm (RIPA). Then we have

(18) +∞ k=1 t k s k x k -x k-1 2 < +∞. Moreover +∞ k=1 t k+1 s k x k -x k-1 2 < +∞,
and hence

+∞ k=1 t k+1 W k < +∞.
Proof. Let us recall the inequality (9) from Proposition 2.2

W k+1 -W k ≤ - 1 -α 2 k 2s k x k -x k-1 2 .
Multiplying this inequality by t 2 k+1 and summing from k = 1 to n, we obtain

n k=1 t 2 k+1 (W k+1 -W k ) + n k=1 1 2s k t 2 k+1 (1 -α 2 k ) x k -x k-1 2 ≤ 0.
By rearranging the terms (we perform a discrete form of the integration by parts formula), we find

t 2 n+1 W n+1 + k=1 (t 2 k -t 2 k+1 )W k + n k=1 1 2s k t 2 k+1 (1 -α 2 k ) x k -x k-1 2 ≤ t 2 1 W 1 .
Recalling the expression of W k , we deduce that

n k=1 1 2s k [t 2 k -t 2 k+1 + t 2 k+1 (1 -α 2 k )] x k -x k-1 2 ≤ t 2 1 W 1 + n k=1 (t 2 k+1 -t 2 k )(Φ k (x k ) -min Φ).
Since t k+1 α k = t k -1 and t 2 k+1 -t 2 k ≤ t k+1 by assumption (K 1 ), this implies

n k=1 1 2s k [t 2 k -(t k -1) 2 ] x k -x k-1 2 ≤ t 2 1 W 1 + n k=1 t k+1 (Φ k (x k ) -min Φ).
Observing that t k ≥ 1, we have

t 2 k -(t k -1) 2 = 2t k -1 ≥ t k . Hence, n k=1 1 2s k t k x k -x k-1 2 ≤ t 2 1 W 1 + n k=1 t k+1 (Φ k (x k ) -min Φ).
By letting n tend to infinity in the above inequality we obtain

+∞ k=1 t k s k x k -x k-1 2 ≤ 2t 2 1 W 1 + 2 +∞ k=1 t k+1 (Φ k (x k ) -min Φ) < +∞,
which gives the conclusion [START_REF] Drori | Performance of first-order methods for smooth convex minimization: a novel approach[END_REF]. Let us complete this result by observing that assumption (K 1 ) implies

t k+1 -t k ≤ t k+1 t k+1 + t k ≤ 1.
Since t k ≥ 1, we deduce that t k+1 ≤ 2t k for every k ≥ 1. The estimate (18) then yields

+∞ k=1 t k+1 s k x k -x k-1 2 < +∞.
Recalling from Theorem 2.5 that

+∞ k=1 t k+1 (Φ k (x k )-min Φ) < +∞, we obtain +∞ k=1 t k+1 W k < +∞.
Let us now establish pointwise estimates for the rate of convergence of the velocities.

Theorem 2.9. Under (H), assume that the sequence (α k ) satisfies (K 0 )-(K + 1 ), and α k ∈ [0, 1] for every k ≥ 1. Then for any sequence (x k ) generated by the algorithm (RIPA), the following holds true

(19) Φ µ k (x k ) -min Φ = o 1 k i=1 t i and x k -x k-1 = o s k k i=1 t i 1 2
as k → +∞, thus implying

(20) Φ(p k ) -min Φ = o 1 k i=1 t i and x k -p k = o µ k k i=1 t i 1 2
as k → +∞.

As a consequence, we have

Φ(p k ) -min Φ = o 1 t 2 k , x k -p k = o √ µ k t k and x k -x k-1 = o √ s k t k as k → +∞.
Proof. According to Proposition 2.2 and α k ∈ [0, 1] for all k ≥ 1, we deduce that the energy sequence (W k ) is nonincreasing. By Proposition 2.8, we have that

+∞ k=1 t k+1 W k < +∞. Since (W k ) is nonincreasing, this implies that +∞ k=1 t k+1 W k+1 < +∞, hence +∞ k=1 t k W k < +∞.
Let us apply Lemma B.2 in the Appendix, with the sequences (t k ) and (W k ), respectively in place of (τ k ) and (ε k ). We obtain that

W k = o 1 k i=1 t i as k → +∞.
The estimates [START_REF] Eckstein | On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators[END_REF] follow immediately. From the definition of Φ µ k , we clearly deduce [START_REF] Iutzeler | Generic online acceleration scheme for optimization algorithms via relaxation and inertia[END_REF]. In view of assumption (K 1 ), we have t 2 i+1 -t 2 i ≤ t i+1 for every i ≥ 1, hence by summing from i = 1 to k -1

t 2 k ≤ t 2 1 + k-1 i=1 t i+1 = t 2 1 -t 1 + k i=1 t i .
We easily deduce the last estimates.

Convergence of the sequence of iterates (x k ).

Theorem 2.10. Under (H), assume that the sequence

(α k ) satisfies (K 0 )-(K + 1 ), together with α k ∈ [0, 1] for every k ≥ 1. Assume moreover that sup k µ k k i=1 t i < +∞ and sup k ρ k µ k < +∞.
Then, for any sequence (x k ) generated by algorithm (RIPA), the following holds (i) lim k→+∞ x k -p k = 0, where p k = prox µ k Φ (x k );

(ii) (x k ) converges weakly, as k → +∞, to some x * ∈ argmin Φ.

Proof. (i) By the second estimate of (20) we have

x k -p k = o µ k k i=1 t i 1 2 -→ 0 as k → +∞, because sup k µ k k i=1
ti < +∞ by assumption. (ii) Let us verify successively the items (i) and (ii) of the Opial lemma, see Lemma B.1 in the Appendix. Take S = argmin Φ. From the first estimate of (20), the sequence (p k ) is minimizing, which implies that any weak cluster point of (p k ) belongs to S. Since lim x k -p k = 0, the same property holds true for the sequence (x k ), which completes item (i) of Opial's lemma. Let us fix x * ∈ S, and show that lim k→+∞ x k -x * exists. For that purpose, let us set h k = 1 2 x k -x * 2 . By Proposition 2.3, the sequence (h k ) satisfies the following inequalities

h k+1 -h k -α k (h k -h k-1 ) ≤ 1 2 (α 2 k + α k ) x k -x k-1 2 -s k (Φ µ k (x k+1 ) -min Φ) ≤ 1 2 (α 2 k + α k ) x k -x k-1 2 ≤ x k -x k-1 2 since α k ∈ [0, 1].
Taking the positive part, we find

(h k+1 -h k ) + ≤ α k (h k -h k-1 ) + + x k -x k-1 2 .
By Proposition 2.8 we have

+∞ k=1 t k+1 s k x k -x k-1 2 < +∞.
Since (s k ) has been supposed to be bounded from above, this implies

+∞ k=1 t k+1 x k -x k-1 2 < +∞. By applying Lemma B.3 (given in the Appendix) with a k = (h k -h k-1 ) + and ω k = x k -x k-1 2 , we obtain +∞ k=1 (h k -h k-1 ) + < +∞.
Since (h k ) is nonnegative, this classically implies that lim k→+∞ h k exists. The second point of the Opial lemma is shown, which ends the proof.

2.5. Geometrical aspects. The results obtained in the previous section deal with general convex lower semicontinuous proper functions Φ : H → R ∪ {+∞}. They give convergence rates for values in the worst case. It is a well-documented fact that under additional geometric properties on Φ, one can expect better convergence rates. Let us mention [START_REF] Attouch | Convergence rates of inertial forward-backward algorithms[END_REF], [START_REF] Attouch | Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity[END_REF], [START_REF] Su | A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights[END_REF] for results based on strong convexity, [START_REF] Liang | Local linear convergence of forward-backward under partial smoothness[END_REF] for results based on partial smoothness, and [START_REF] Bégout | On damped second-order gradient systems[END_REF][START_REF] Iutzeler | On the Proximal Gradient Algorithm with Alternated Inertia[END_REF] for results based on the Kurdyka-Lojasiewicz property. For the Nesterov acceleration (vanishing damping coefficient of the form α t ), [START_REF] Aujol | Optimal convergence rates for Nesterov acceleration[END_REF] gives a recent account on these issues with optimal convergence rates.

Since (RIPA) is governed by ∇Φ µ k at iteration k, a natural question is to ask whether such geometric assumptions about Φ, are preserved by taking the Moreau envelopes. We will examine several cases for which we will answer this question affirmatively. This suggests that in these cases, it is likely that one can improve the rate of convergence that we obtained for (RIPA) in the worst case. This is an interesting question for future studies. [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert spaces[END_REF]Section 10.2] for classical results concerning strong convexity. First, as a direct consequence of Theorems 2.9 and 2.10, we obtain the strong convergence of the iterates in this case.

Strong convexity. We recall that Φ :

H → R ∪ {+∞} is strongly convex with constant β > 0 if Φ -β 2 • 2 is convex. One can consult
Proposition 2.11. Let's make the hypotheses of Theorem 2.10, and suppose that Φ : H → R∪{+∞} is a convex lower semicontinuous proper function that is strongly convex. Then, for any sequence (x k ) generated by (RIPA), (x k ) and (p k ) converge strongly, as k → +∞, to the unique minimizer x * of Φ.

Proof. By Theorem 2.9, we have Φ(p k ) -min Φ = o 1 t 2 k . Since t k ≥ 1, this implies Φ(p k ) → min Φ. Hence, (p k ) is a minimizing sequence of the strongly convex function Φ. This classically implies that (p k ) converges strongly to the unique minimizer x * of Φ. By Theorem 2.10, we have lim k→+∞ x k -p k = 0, which implies that, likewise, (x k ) converges strongly, as k → +∞, to the unique minimizer x * of Φ. Proposition 2.12. Suppose that Φ : H → R ∪ {+∞} is a convex lower semicontinuous proper function. Then, the following implications hold: for any β, γ > 0 and µ > 0 (i) Φ strongly convex with constant β =⇒ Φ µ strongly convex with constant β 1 + βµ .

(ii) Φ µ strongly convex with constant γ < 1 µ =⇒ Φ strongly convex with constant γ 1 -γµ .

Proof. (i) If Φ is strongly convex with constant β > 0, we have Φ = Ψ + β 2 • 2 for some convex function Ψ. Elementary calculus (see [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert spaces[END_REF]Exercise 12.6] for example) gives, with θ = µ 1+βµ ,

Φ µ (x) = Ψ θ 1 1 + µβ x + β 2(1 + βµ) x 2 . Since x → Ψ θ 1 1+µβ
x is a convex function, the above formula shows that Φ µ is strongly convex

with constant γ = β 1+βµ . Note that γµ = βµ 1+βµ < 1, which gives γ < 1 µ . (ii) Conversely, suppose that Φ µ = G + γ 2 • 2 for some convex function G and some γ > 0 such that γµ < 1. Since the Moreau envelope Φ µ is of class C 1 , the function G is also of class C 1 . Taking the Legendre-Fenchel conjugate, we obtain (Φ µ ) * = G + γ 2 • 2 * .
Using classical calculus rules, we have

(Φ µ ) * = Φ # 1 2µ • 2 * = Φ * + µ 2 • 2 , and G + γ 2 • 2 * = G * # 1 2γ • 2 = (G * ) γ ,
where # denotes the infimal convolution (also called epi-addition). It ensues that Φ * = (G * ) γ -µ 2 • 2 . Since Φ is convex lower semicontinuous and proper, we have Φ = Φ * * = (G * ) γ -µ 2 • 2 * . By definition of the Legendre-Fenchel conjugate and the infimal convolution, this gives

Φ(x) = sup ξ sup u x, ξ -G * (u) - 1 2γ ξ -u 2 + µ 2 ξ 2 .
Elementary calculus (switch order of supremum in the above expression) gives Φ = J + γ 2(1-γµ) • 2 , where J is convex lower semicontinuous and proper. Hence Φ is strongly convex with constant γ 1-γµ . 2.5.2. Growth condition. Let us consider Φ : H → R ∪ {+∞} a convex lower semicontinuous proper function that satisfies the growth condition: there exists some positive constant β such that for all

x ∈ H Φ(x) ≥ min Φ + β 2 d(x, S) 2 ,
where S = argminΦ. When Φ is convex, which is our case, it is equivalent to a Kurdyka-Lojasiewicz inequality. This makes it play an important role in the mathematical analysis of continuous and discrete dynamical systems. It is also called conditioning or Hölderian error bounds. Note that 1 2 d(x, S) 2 = (δ S ) 1 where δ S is the indicator function of the set S. The resolvent equality (semi-group property) gives

1 2 d(•, S) 2 µ = ((δ S ) 1 ) µ = (δ S ) 1+µ = 1 2(1 + µ) d(•, S) 2 .
From this, it is an easy exercise to verify that for such a function Φ, the Moreau envelope Φ µ satisfies

Φ µ (x) ≥ min Φ + β 2(1 + βµ) d(x, S) 2 .
Since min Φ = min Φ µ , we deduce that Φ µ satisfies a similar growth condition (with another constant).

2.6. Related algorithms. The analysis of (RIPA) performed in the previous sections is based on its formulation as an inertial gradient algorithm ( 21)

y k = x k + α k (x k -x k-1 ) x k+1 = y k -s k ∇Φ k (y k ),
where, as a distinctive feature, the potential function Φ k varies at each iteration. A careful inspection at the proofs shows that the results listed in section 2 up to the first part of Theorem 2.9 are valid in a more general context than that of Moreau-Yosida regularization. As part of the algorithm ( 21), these results remain true for sequences (Φ k ) and (s k ) that meet the following conditions:

           • (Φ k ) is a nonincreasing sequence of differentiable convex functions; • ∇Φ k is L k -Lipschitzian; • argminΦ k is not empty and min Φ k ≡ m for all k ≥ 1; • s k is a nondecreasing sequence such that s k ≤ 1 L k for all k ≥ 1.
This suggests a natural extension, which consists of replacing the quadratic regularization term of the Moreau envelopes with a general Bregman distance. This is another direction for future research.

3. Application to particular classes of parameters α k , µ k and ρ k

We will now specialize the parameters α k , µ k and ρ k in order to obtain inertial proximal-based algorithms whose iterations converge in the case of general monotone inclusions, and which, in the case of convex minimization, give fast convergence rates of values (in the worst case).

Theorem 1.3 provides convergence of the iterates for general maximally monotone operators, and Theorem 2.5 gives fast convergence of the values for convex minimization. So, each of them meets one of the two above objectives, and we just need to synthesize them. This amounts to finding assumptions about the data (α k ), (ρ k ), (µ k ) for which both results are valid. Note that apart from the (K 0 ) assumption common to both, and which is basic to define the sequence (t k ), each of these results is based on a specific set of assumptions. For general monotone inclusions, we use Theorem 1.3, which concerns the case ρ k → 0. Indeed, when α k → 1, which is the situation for which one can expect rapid convergence results of the values for convex minimization, a direct inspection of the condition (L) shows that we must have ρ k → 0. The assumptions of Theorem 1.3 and Theorem 2.5 are expressed in terms of the sequences (α k ), (ρ k ), (µ k ), and (t k ). Only the sequence (t k ) is not given explicitly from the data. The following proposition provides a criterion for simply obtaining an asymptotic equivalent of (t k ), see [START_REF] Attouch | Convergence rates of inertial forward-backward algorithms[END_REF]Propositions 14 and 15]. It also guarantees that the property (K 0 ) is satisfied.

Proposition 3.1. Let (α k ) be a sequence such that α k ∈ [0, 1[ for every k ≥ 1. Assume that (22) lim k→+∞ 1 1 -α k+1 - 1 1 -α k = c,
for some c ∈ [0, 1[. Then the property (K 0 ) is satisfied, and

t k+1 ∼ 1 (1 -c)(1 -α k )
as k → +∞.

The following result gives a practical form of Theorem 1.3 that relies on Proposition 3.1. The conditions are now expressed simply and directly in terms of the sequences (α k ), (ρ k ), (µ k ). Theorem 3.2. [6, Theorem 3.6] Let A : H → 2 H be a maximally monotone operator such that zerA = ∅. Suppose that the sequences (α k ) and

(ρ k ) satisfy α k ∈ [0, 1[ and ρ k ∈]0, 2[ for every k ≥ 1. Let us assume that there exist α ∈ [0, 1], ρ ∈ [0, 2[, c ∈ [0, 1[ and c ∈ R, with -(1 -ρ/2) < c ≤ -(1 -ρ/2)c such that lim k→+∞ α k = α and lim k→+∞ ρ k = ρ; (23) lim k→+∞ 1 1 -α k+1 - 1 1 -α k = c; (24) lim k→+∞ ρ k+1 -ρ k ρ k+1 (1 -α k ) = c ; (25) lim inf k→+∞ (1 -α k ) 2 ρ k > α(1 + α) 2 -ρ + 2c . ( 26
)
Then for any sequence (x k ) generated by (RIPA), we have

(i) x k+1 -x k = O ρ k 1 -α k as k → +∞.
Assume additionally that

|µ k+1 -µ k | µ k+1 = O ρ k 1 -α k as k → +∞, together with +∞ k=1 ρ k 1 -α k = +∞.
Then the following holds

(ii) lim k→+∞ µ k A µ k (x k ) = 0. If lim inf k→+∞ µ k > 0, then there exists x ∞ ∈ zerA such that x k x ∞ weakly in H as k → +∞. 3.1. The case α k = 1 - α k .
In a seminal paper [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate O(1/k 2 )[END_REF], Nesterov considered the accelerated gradient method

y k = x k + α k (x k -x k-1 ) x k+1 = y k -λ k ∇Φ(y k ),
which aims at minimizing a differentiable convex function Φ : H → R. It is assumed that Φ has a L-Lipschitz gradient, and that the parameters satisfy λ k ≡ 1/L, and

α k = t k -1 t k+1 with t 1 = 1 and t k+1 = √ 4t 2 k +1+1 2
(this corresponds to the case of equality in (K 1 )). This choice leads to an increasing sequence of extrapolated coefficients (α k ), that behaves like 1 -3 k as k → +∞. This scheme exhibits the convergence rate for the values Φ(x k ) -min Φ = O( 1 k 2 ) as k → +∞, which, for gradient methods, is known to be optimal among all first-order methods having only information about the gradients and functions at previous iterates [START_REF] Nesterov | Introductory lectures on convex optimization: A basic course[END_REF]. Then, Beck-Teboulle [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF] extended Nesterov's method to inertial proximal-gradient methods for solving structured minimization problems, that's (FISTA). Other choices of the extrapolation factors α k have been recently considered in [START_REF] Attouch | Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity[END_REF][START_REF] Attouch | The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1 k 2[END_REF][START_REF] Aujol | Stability of over-relaxations for the Forward-Backward algorithm, application to FISTA[END_REF][START_REF] Chambolle | On the convergence of the iterates of the Fast Iterative Shrinkage/Thresholding Algorithm[END_REF][START_REF] Su | A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights[END_REF]. Notably, the case α k = 1 -α k , with α > 3 offers many advantages. First, it ensures the convergence of the sequences (x k ), as proved by Chambolle and Dossal [START_REF] Chambolle | On the convergence of the iterates of the Fast Iterative Shrinkage/Thresholding Algorithm[END_REF], see also [START_REF] Attouch | Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity[END_REF]. Let us recall that the convergence of the sequences generated by (FISTA) has not been established so far. Second, as proved by Attouch and Peypouquet in [START_REF] Attouch | The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1 k 2[END_REF], it provides the better rate of convergence Φ(x k ) -min Φ = o 1 k 2 . A unified point of view on these methods has been lately brought to light by Attouch-Cabot [START_REF] Attouch | Convergence rates of inertial forward-backward algorithms[END_REF], where a general extrapolation coefficient α k is considered.

The following result is a direct application of Theorem 3.2 to the case α k = 1 -α k .

Corollary 3.3. [6, Corollary 3.8] Let A : H → 2 H be a maximally monotone operator such that zerA = ∅. Suppose that α k = 1 -α k and ρ k = β k r for k ≥ 1, where the parameters α, β, r are supposed to satisfy: r ≥ 2, α > r and β > 0 is such that β < α(α -2) if r = 2 (no condition on β if r > 2).

Then for any sequence (x k ) generated by (RIPA), we have

(i) x k+1 -x k = O 1 k r-1
as k → +∞.

Assume additionally that r = 2 and that

|µ k+1 -µ k | µ k+1 = O 1 k as k → +∞. Then the following holds (ii) lim k→+∞ µ k A µ k (x k ) = 0. (iii) If lim inf k→+∞ µ k > 0, then there exists x ∞ ∈ zerA such that x k x ∞ weakly in H as k → +∞.
Proof. Let's verify that, with this choice of parameters, the assumptions of Theorem 3.2 are satisfied.

• Assumption ( 23) is clearly satisfied, with α = 1 and ρ = 0 respectively.

• Observe that 1 1-α k+1 -1 1-α k = 1 α (k + 1) -1 α k = 1 α , hence assumption (24) is verified with c = 1 α . • We have ρ k+1 -ρ k ρ k+1 (1-α k ) = 1 (k+1) r -1 k r (k + 1) r k α → -r α
as k → +∞. This shows that assumption ( 25) is fulfilled with c = -r α . The hypothesis

-(1 -ρ/2) < c ≤ -(1 -ρ/2)c amounts to -1 < -r α ≤ -1 α , which is in turn equivalent to 1 ≤ r < α. • Assumption (26) can be rewritten as lim inf k→+∞ (1 -α k ) 2 ρ k > 1 1 -r/α = α α -r .
We have (1

-α k ) 2 /ρ k = (α 2 /k 2 )(k r /β) = α 2 β k r-2 . Therefore lim k→+∞ (1-α k ) 2 ρ k = +∞ if r > 2 α 2 /β if r = 2. Hence, assumption (26) is satisfied if r > 2, while it is equivalent to α(α -2) > β if r = 2. • Condition +∞ k=1 ρ k
1-α k = +∞ amounts to r ≤ 2, which boils down to r = 2.

• |µ k+1 -µ k | µ k+1 = O ρ k 1-α k is equivalent to |µ k+1 -µ k | µ k+1 = O 1 k .
Let's now check the assumptions of Theorem 2.5. Since condition ( 22) is satisfied with c = 1 α , Proposition 3.1 shows that the property (K 0 ) holds true when α > 1, and t k+1 ∼ k α-1 . Indeed one can easily verify that equality holds, that is, t k+1 = k α-1 . We then obtain that condition (K 1 ), namely, t 2 k+1 -t 2 k ≤ t k+1 for every k ≥ 1, is equivalent to α ≥ 3. A similar calculation gives that condition (K + 1 ) is equivalent α > 3. Thus when α ≥ 3, and under assumption (H), we obtain the following convergence rate of the values for (RIPA) Φ(p k ) -min Φ = O 1 k 2 , where p k = prox µ k Φ (x k ). The previous results are summarized in Figure 1. In the general maximally monotone case, weak convergence of the iterates is ensured by the assumptions of the first column. When A = ∂Φ, the convergence rate of the values O 1 k 2 is guaranteed by the hypotheses of the second column. The last column provides assumptions that ensure the weak convergence of the iterates in the case A = ∂Φ. In this case, it is not necessary to assume ρ k → 0 to get convergence of iterates.

(RIPA)

A maximally monotone A = ∂Φ, Φ : H → R ∪ {+∞} convex lsc. α k α k = 1 - α k α > 2 α ≥ 3 α > 3 ρ k ρ k = β k 2 , β < α(α -2) 0 < ρ k ≤ 1 µ k |µ k+1 -µ k | µ k+1 = O 1 k (µ k ) and (ρ k µ k ) nondecreasing lim inf µ k > 0 sup ρ k µ k < +∞ sup µ k k 2 < +∞ weak convergence of iterates Φ(p k ) -min Φ = O 1 k 2 weak convergence of iterates x k+1 -x k = O 1 k with p k = prox µ k Φ (x k )
Figure 1: Summary of the convergence results for (RIPA) with α k = 1 -α k .

We can now easily deduce a set of assumptions for which both types of results are satisfied.

Corollary 3.4. Take the parameters α k , ρ k , µ k of (RIPA) as follows: for each k ≥ 1

• α k = 1 - α k , α ≥ 3; ρ k = β k 2 , β < α(α - 2
); µ k = c k r for some r ≥ 2 and c > 0. Then, we have both a) the weak convergence of the iterates (x k ) generated by (RIPA) when A is a general maximally monotone operator. Moreover,

x k+1 -x k = O 1 k . b) the rate of convergence of the values O 1 k 2 for (RIPA) when A = ∂Φ and Φ : H → R∪{+∞} is convex, lower semicontinuous, proper. Precisely, Φ(p k ) -min Φ = O( 1 k 2 ) where p k = prox µ k Φ (x k ). Proof.
It is an immediate consequence of the results contained in Figure 1. Concerning the choice of µ k just notice that, when taking µ k = ck r for some r ≥ 2, the sequences (µ k ) and (ρ

k µ k ) = cβ k r -2 are nondecreasing. Moreover |µ k+1 -µ k | µ k+1 ∼ r k = O 1 k .
The case r = r = 2 has been studied by Attouch and Peypouquet [START_REF] Attouch | Convergence of inertial dynamics and proximal algorithms governed by maximal monotone operators[END_REF] with α k = 1 -α k , ρ k = s λ k +s and µ k = λ k + s, where α, s > 0 and λ k = (1 + ε) s α 2 k 2 , for some ε > 0. With this choice, the sequence (s k ) with s k = ρ k µ k is constant, equal to s. This particular situation naturally occurs when deriving the algorithm from a dynamical system with constant step size, see section 1.3.2.

The case α

k = 1 - α k q .
The following result is a direct application of Theorem 3.2 to the case α k = 1 -α/k q and ρ k = β/k r , for some α, β > 0, q ∈]0, 1[ and r > 0.

Corollary 3.5. [6, Corollary 3.7] Let A : H → 2 H be a maximally monotone operator such that zerA = ∅. Suppose that α k = 1 -α k q and ρ k = β k r for k ≥ 1, where the parameters α, β, q and r are supposed to satisfy: (q, r) ∈]0, 1[×R * + , r ≥ 2q, and (α,

β) ∈ R * + × R * + satisfies α 2 /β > 1 if r = 2q (no condition if r > 2q
). Then for any sequence (x k ) generated by (RIPA), we have

(i) x k+1 -x k = O 1 k r-q
as k → +∞.

Assume additionally that r ≤ q + 1 and that

|µ k+1 -µ k | µ k+1 = O 1 k r-q
as k → +∞. Then the following holds

(ii) lim k→+∞ µ k A µ k (x k ) = 0. (iii) If lim inf k→+∞ µ k > 0, then there exists x ∞ ∈ zerA such that x k x ∞ weakly in H as k → +∞.
Proof. Let's verify that, with this choice of parameters, the assumptions of Theorem 3.2 are satisfied.

• Assumption ( 23) is clearly satisfied, with α = 1 and ρ = 0.

• Observe that 1 1-α k+1 -1 1-α k = 1 α ((k + 1) q -k q ) ∼ q α k q-1
→ 0 as k → +∞, where we have used q ∈]0, 1[. Hence assumption ( 24) is verified with c = 0.

• We have

ρ k+1 -ρ k ρ k+1 (1-α k ) = 1 (k+1) r -1
k r (k + 1) r k q α ∼ -r α k q-1 → 0 as k → +∞. Therefore, assumption (25) is fulfilled with c = 0.

• Assumption (26) amounts to lim inf k→+∞ 1 k r-q = +∞, that is, r ≤ q + 1.

• |µ k+1 -µ k | µ k+1 = O ρ k 1-α k is equivalent to |µ k+1 -µ k | µ k+1 = O 1 k r-q .
Let's now check the assumptions of Theorem 2.9. We have 1 1-α k+1 -1 1-α k → 0 as k → +∞. Hence, c = 0 in Proposition 3.1, which implies that (K 0 ) is satisfied, and t k+1 ∼ 1 1-α k = 1 α k q . Since c < 1 3 , it follows from [4, Proposition 14] that (K + 1 ) is satisfied. Note that k i=1 t i ∼ 1 α(1+q) k 1+q . According to Theorem 2.9, under (H), the following holds true Φ µ k (x k ) -min Φ = o 1 weak convergence of iterates

α k α k = 1 - α k q , q ∈]0, 1[, α > 0 ρ k = β k r , β > 0 ρ k 0 < ρ k ≤ 1 r = 2q, β < α 2 r ∈]2q, q + 1] µ k |µ k+1 -µ k | µ k+1 = O 1
x k -x k-1 = O 1 k r-q x k -x k-1 = o ρ k µ k k 1+q 1 2
Figure 2: Summary of the convergence results for (RIPA) with α k = 1 -α k q , q ∈]0, 1[.

We can now easily deduce a set of assumptions for which both types of results are satisfied.

Corollary 3.6. Take the parameters α k , ρ k , µ k of (RIPA) as follows: for each k ≥ 1

• α k = 1 -α k q , α > 0, q ∈]0, 1[; • ρ k = β k r , β > 0, r ∈ [2q, q + 1], and β < α 2 if r = 2q (no condition if r > 2q); • µ k = c k r for some r ≥ r and some positive constant c. Then, we have both a) the weak convergence of the iterates (x k ) generated by (RIPA) when A is a general maximally monotone operator. Moreover, Proof. It is an immediate consequence of the results contained in Figure 2. Concerning the choice of µ k just notice that, when taking µ k = c k r for some r ≥ r, the sequences (µ k ) and (ρ k µ k ) = cβ k r -r are nondecreasing. Moreover |µ k+1 -µ k | µ k+1 ∼ r k = O 1 k r-q , since r ≤ q + 1.

x k -x k-1 = O 1 k r-q . b)
Remark 3.7. As a general rule, we can observe a balance between the inertial effect and the relaxation effect. As α k gets closer to one, the relaxation parameter ρ k gets closer to zero. As well, there is a balance between the relaxation and the regularization parameters. As ρ k tends to zero, the regularization parameter µ k tends to infinity. A typical situation is µ k = C ρ k , for some C > 0.

The following result allows us to establish the summability of a sequence (a k ) satisfying some suitable inequality. Lemma 23]). Given a nonnegative sequence (α k ) satisfying (K 0 ), let (t k ) be the sequence defined by t k = 1 + +∞ i=k i j=k α j . Let (a k ) and (ω k ) be two sequences of nonnegative numbers such that a k+1 ≤ α k a k + ω k , for all k ≥ 0. If +∞ k=0 t k+1 ω k < +∞, then +∞ k=0 a k < +∞.

Lemma B.3 ([4,

( 1 -α k ) 2 ρ k > 1 .

 11 We have(1 -α k ) 2 /ρ k = (α 2 /k 2q )(k r /β) = α 2 β k r-2q , hence lim k→+∞ (1-α k ) 2 ρ k = +∞ if r > 2q α 2 /β if r = 2q. It ensues that assumption (26) is satisfied if r > 2q, while it is equivalent to α 2 > β if r = 2q. • Condition +∞ k=1 ρ k 1-α k = +∞ amounts to +∞ k=1

k 1+q and x k -x k- 1 = o s k k 1+q 1 2.

 11 Therefore, Φ(p k ) -min Φ = o 1 k 1+q , where p k = prox µ k Φ (x k ). Under the additional assumptions sup µ k k 1+q < +∞ and sup ρ k µ k < +∞, Theorem 2.10 shows the weak convergence of the iterates (x k ). The previous results are summarized in the table of

  A = ∂Φ, Φ : H → R ∪ {+∞} convex lsc.

  k r-q (µ k ) and (ρ k µ k ) nondecreasing lim inf µ k > 0 sup ρ k µ k < +∞ sup µ k k 1+q < +∞ weak convergence of iterates Φ(p k ) -min Φ = o 1 k 1+q

  the rate of convergence of the values o 1 k 1+qfor the algorithm (RIPA) when A = ∂Φ andΦ : H → R ∪ {+∞} is convex, lower semicontinuous, proper. Precisely, Φ(p k ) -min Φ = o( 1 k 1+q ) where p k = prox µ k Φ (x k ). Moreover, x k -x k-1 = o k r -r

Appendix A. Moreau envelopes

Recall some basic facts concerning the Moreau envelope. Let Φ : H → R ∪ {+∞} be a convex lower semicontinuous proper function. For any µ > 0, and any x ∈ H,

The infimum in ( 27) is achieved at a unique point prox µΦ (x), which gives

Writing the optimality condition for [START_REF]Weak convergence of the sequence of successive approximations for nonexpansive mappings[END_REF], we get

that is prox µΦ (x) = (I + µ∂Φ) -1 (x). Thus, prox µΦ is the resolvent of index µ > 0 of the maximal monotone operator ∂Φ. Consequently, the mapping prox µΦ : H → H is firmly nonexpansive. For any µ > 0, the function x → Φ µ (x) is continuously differentiable, with

Thus ∇Φ µ = 1 µ I -(I + µ∂Φ) -1 = (∂Φ) µ is the Yosida approximation with index µ of the maximally monotone operator ∂Φ. As such, ∇Φ µ is Lipschitz continuous, with Lipschitz constant 1 µ , and Φ µ ∈ C 1,1 (H). See [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert spaces[END_REF][START_REF] Brézis | Opérateurs maximaux monotones dans les espaces de Hilbert et équations d'évolution[END_REF][START_REF] Parikh | Proximal algorithms[END_REF][START_REF] Peypouquet | Convex optimization in normed spaces: theory, methods and examples[END_REF], for further results.

Appendix B. Auxiliary results

Let us present some auxiliary lemmas that are used throughout the paper. To establish the weak convergence of the iterates of (RIPA), we apply Opial's Lemma [START_REF]Weak convergence of the sequence of successive approximations for nonexpansive mappings[END_REF], that we recall in its discrete form.

Lemma B.1. Let S be a nonempty subset of H, and (x k ) a sequence of elements of H. Assume that (i) every sequential weak cluster point of (x k ), as k → +∞, belongs to S;

(ii) for every z ∈ S, lim k→+∞ x k -z exists. Then (x k ) converges weakly as k → +∞ to a point in S.

The next lemma provides an estimate of the convergence rate of a sequence that is summable with respect to weights.