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 x (t) +btẋ (t) + F (x (t) ) in a finite-dimensional Hilbert space R^d, 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 03 this order is of o (t^{-2}) 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.