Fast Convergence of Generalized Forward-Backward Algorithms for Structured Monotone Inclusions

We develop rapidly convergent forward-backward algorithms for computing zeroes of the sum of finitely many maximally monotone operators. A modification of the classical forward-backward method for two general operators is first considered, by incorporating an inertial term (close to the acceleration techniques introduced by Nesterov), a constant relaxation factor and a correction term. In a Hilbert space setting, we prove the weak convergence to equilibria of the iterates

, with worst-case rates of

o(n^{-1}) o ( n − 1 )

in terms of both the discrete velocity and the fixed point residual, instead of the classical rates of

{\cal O}(n^{-1/2}) O ( n − 1 / 2 )

established so far for related algorithms. Our procedure is then adapted to more general monotone inclusions and a fast primal-dual algorithm is proposed for solving convex-concave saddle point problems.