Convergence of inertial dynamics and proximal algorithms governed by maximal monotone operators

Hedy Attouch, Juan Peypouquet

Published 2017-05-10Version 1

Let $\mathcal H$ be a real Hilbert space endowed with the scalar product $\langle \cdot,\cdot\rangle$ and norm $\|\cdot\|$. Given a maximal monotone operator $A: \mathcal H \rightarrow 2^{\mathcal H}$, we study the asymptotic behavior, as time goes to $+\infty$, of the trajectories of the second-order differential equation $$ \ddot{x}(t) + \frac{\alpha}{t} \dot{x}(t) +A_{\lambda(t)}(x(t)) = 0, \qquad t>t_0>0, $$ where $A_\lambda$ stands for the Yosida regularization of $A$ of index $\lambda>0$, along with a new {\em Regularized Inertial Proximal Algorithm} obtained by means of a convenient finite-difference discretization. These systems are the counterpart to accelerated forward-backward algorithms in the context of maximal monotone operators. A proper tuning of the parameters allows us to prove the weak convergence of the trajectories to solutions of the inclusion $0\in Ax$, as we let time $-$or the number of iterations$-$ tend to $+\infty$. Moreover, it is possible to estimate the rate at which the speed and acceleration vanish. We also study the effect of perturbations or computational errors that leave the convergence properties unchanged. We also analyze a growth condition under which strong convergence can be guaranteed. A simple example shows the criticality of the assumptions on the Yosida approximation parameter, and allows us to illustrate the behavior of these systems compared with some of their close relatives.