Fast Convergence of Generalized Forward-Backward Algorithms for Structured Monotone Inclusions
Open Access
- 1 January 2022
- journal article
- Published by Banach Press LLC in Journal of Convex Analysis
- Vol. 29 (3) , 893-920
Abstract
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 (x_n) ( x n ) , 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.Keywords
This publication has 40 references indexed in Scilit:
- Accelerated Proximal Algorithms with a Correction Term for Monotone InclusionsApplied Mathematics & Optimization, 2021
- Convergence of a Relaxed Inertial Forward–Backward Algorithm for Structured Monotone InclusionsApplied Mathematics & Optimization, 2019
- Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operatorsMathematical Programming, 2018
- Convex Analysis and Monotone Operator Theory in Hilbert Spaces2017
- Performance of first-order methods for smooth convex minimization: a novel approachMathematical Programming, 2013
- Gradient methods for minimizing composite functionsMathematical Programming, 2012
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraintCommunications on Pure and Applied Mathematics, 2004
- Variational Analysis1998
- On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operatorsMathematical Programming, 1992
- Produits infinis de resolvantesIsrael Journal of Mathematics, 1978