The Differential Inclusion Modeling FISTA Algorithm and Optimality of Convergence Rate in the Case b ≤3

In this paper we are interested in the differential inclusion 0∈ ẍ(t)+b/tẋ(t)+∂ F(x(t)) in a finite-dimensional Hilbert space Rᵈ, where F is a proper, convex, lower semicontinuous function. The motivation of this study is that the differential inclusion models the FISTA algorithm as considered in [A. Chambolle and C. Dossal, J. Optim. Theory Appl., 166 (2015), pp. 968--982]. In particular, we investigate the different asymptotic properties of solutions for this inclusion for $b>0$. We show that the convergence rate of $F(x(t))$ towards the minimum of F is of order of O(t-2b/3) when $0<b<3$, while for $b>3$ this order is of o(t⁻²) and the solution-trajectory converges to a minimizer of F. These results generalize the ones obtained in the differential setting (where F is differentiable) in [H. Attouch, Z. Chbani, J. Peypouquet, and P. Redont, Math. Program., 2016, pp. 1--53], [H. Attouch, Z. Chbani, and H. Riahi, arXiv:1706.05671, 2017], [J. Aujol and C. Dossal, Optimal Rate of Convergence of an ODE Associated to the Fast Gradient Descent Schemes for $b> 0$, 2017], and [W. Su, S. Boyd, and E. J. Candes, J. Mach. Learn. Res., 17 (2016), pp. 1--43]. In addition, we show that the order of the convergence rate O(t-2b/3) of $F(x(t))$ towards the minimum is optimal, in the case of low friction $b<3$, by making a particular choice of F.