Convergence rate of inertial proximal algorithms with general extrapolation and proximal coefficients (Q2189628)

The authors study the convergence properties of the inertial proximal algorithm: \[ \text{(IP)}_{\alpha_k,\beta_k}: \qquad \left \{ \begin{array}{lll} y_k & = & x_k + \alpha_k(x_k-x_{k-1}), \\ x_{k+1} & = & \text{prox}_{\beta_k} \phi (y_k). \end{array} \right . \] Here the sequences \(\alpha_k\) and \(\beta_k\) play the role of parameters. Proximal methods can be derived by implicit discretization of gradient-type continuous evolution systems. The authors study the convergence properties when \(\phi\) is continuously differentiable, using the relationship between the proximal algorithm \(\text{(IP)}_{\alpha_k,\beta_k}\) and the continuous second-order evolution equation \[ \text{(IGS)}_{\alpha_k,\beta_k}: \qquad \ddot{x}(t) \gamma(t) + \dot{x}(t) + \beta(t) \nabla \phi(x(t)) = 0. \] Here \(\gamma (t)\) is a positive damping coefficient, and \(\beta(t)\) is a time scale coefficient. Depending on the behavior of the sequences \(\alpha_k\), and \(\beta_k\), the convergence rates are given for the values of the sequences \(x_k\) generated by the algorithm \(\text{(IP)}_{\alpha_k,\beta_k}\). Furthermore the convergence rate of the velocities is analyzed. General conditions on the sequences \(\alpha_k\) and \(\beta_k\) which guarantee the weak convergence of the iterates are given. The authors study also compare their results with the accelerated proximal algorithm in [\textit{O. Güler}, SIAM J. Control Optimization 29, No. 2, 403--419 (1991; Zbl 0737.90047)] and provide a dynamical interpretation of this algorithm.