Fast convergence of generalized forward-backward algorithms for structured monotone inclusions

MaRDI QIDQ5091986zbMATH OpenFDO

Authors Paul-Emile Maingé

Publication date 27 July 2022

Full work available at URL https://arxiv.org/abs/2107.10107, https://www.heldermann.de/JCA/JCA29/JCA293/jca29051.htm#jca293

zbMATH Keywords

global rate of convergencefixed point problemcorrection terminertial-type algorithmaccelerated proximal algorithmfast first-order methodNesterov-type algorithmrelaxation factors

Mathematics Subject Classification ID

Convex programming (90C25) Analysis of algorithms and problem complexity (68Q25) Nonlinear programming (90C30) Abstract computational complexity for mathematical programming problems (90C60) Discrete approximations in optimal control (49M25)

Abstract: In this paper, 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 (closed 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)$, with worst-case rates of $o(n^{-2})$ in terms of both the discrete velocity and the fixed point residual, instead of the classical rates of $calO(n^{-1})$ 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.

Recommendations

• Convergence of a relaxed inertial forward-backward algorithm for structured monotone inclusions
• Strong convergence of inertial forward–backward methods for solving monotone inclusions
• Generalized forward-backward splitting with penalization for monotone inclusion problems
• Backward-forward algorithms for structured monotone inclusions in Hilbert spaces
• ACCELERATED PROJECTION-BASED FORWARD-BACKWARD SPLITTING ALGORITHMS FOR MONOTONE INCLUSION PROBLEMS
• A strong convergence result involving an inertial forward-backward algorithm for monotone inclusions
• scientific article; zbMATH DE number 7574089
• A fast-convergent method for solving strongly monotone variational inequality problems
• An inertial forward-backward algorithm for monotone inclusions
• Forward-Backward-Half Forward Algorithm for Solving Monotone Inclusions

Cites work

• scientific article; zbMATH DE number 4133840 (Why is no real title available?)
• scientific article; zbMATH DE number 3850830 (Why is no real title available?)
• scientific article; zbMATH DE number 3309655 (Why is no real title available?)
• scientific article; zbMATH DE number 3341597 (Why is no real title available?)
• scientific article; zbMATH DE number 3376275 (Why is no real title available?)
• scientific article; zbMATH DE number 3398324 (Why is no real title available?)
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• A Modified Forward-Backward Splitting Method for Maximal Monotone Mappings
• A generalized forward-backward splitting
• A generalized proximal point algorithm and its convergence rate
• A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
• A reflected forward-backward splitting method for monotone inclusions involving Lipschitzian operators
• A splitting algorithm for dual monotone inclusions involving cocoercive operators
• Accelerated and inexact forward-backward algorithms
• Accelerated proximal algorithms with a correction term for monotone inclusions
• Accelerated proximal point method for maximally monotone operators
• An inertial forward-backward algorithm for monotone inclusions
• An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
• Augmented Lagrangian and proximal alternating direction methods of multipliers in Hilbert spaces. Applications to games, PDE's and control
• Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
• Bregmanized nonlocal regularization for deconvolution and sparse reconstruction
• Catalyst acceleration for first-order convex optimization: from theory to practice
• Convergence of a relaxed inertial forward-backward algorithm for structured monotone inclusions
• Convergence of a splitting inertial proximal method for monotone operators
• Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators
• Convex analysis and monotone operator theory in Hilbert spaces
• Efficient online and batch learning using forward backward splitting
• Ergodic convergence to a zero of the sum of monotone operators in Hilbert space
• Gradient methods for minimizing composite functions
• Monotone Operators and the Proximal Point Algorithm
• Monotone operator theory in convex optimization
• New Proximal Point Algorithms for Convex Minimization
• Newton-like inertial dynamics and proximal algorithms governed by maximally monotone operators
• Nonlinear functional analysis. Fixed point theory and its applications
• On the Convergence of the Proximal Point Algorithm for Convex Minimization
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
• On the square root of a positive selfadjoint operator
• Performance of first-order methods for smooth convex minimization: a novel approach
• Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators
• Produits infinis de resolvantes
• Signal Recovery by Proximal Forward-Backward Splitting
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• The Numerical Solution of Parabolic and Elliptic Differential Equations
• The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than \(1/k^2\)
• Variable metric forward-backward splitting with applications to monotone inclusions in duality
• Variational Analysis

Cited in

(13)

• Multidomain optimal control of variational subpotential mixed evolution inclusions
• Convergence analysis of the stochastic reflected forward-backward splitting algorithm
• Convergence rates of inertial forward-backward algorithms
• Accelerated forward–backward algorithms for structured monotone inclusions
• Fast continuous dynamics inside the graph of maximally monotone operators
• Nonlinear forward-backward splitting with momentum correction
• Stochastic relaxed inertial forward-backward-forward splitting for monotone inclusions in Hilbert spaces
• From Halpern's fixed-point iterations to Nesterov's accelerated interpretations for root-finding problems
• A strong convergence result involving an inertial forward-backward algorithm for monotone inclusions
• Convergence rate of a relaxed inertial proximal algorithm for convex minimization
• Backward-forward algorithms for structured monotone inclusions in Hilbert spaces
• An inertial forward-backward algorithm for monotone inclusions
• Convergence of a relaxed inertial forward-backward algorithm for structured monotone inclusions

This page was built for publication: Fast convergence of generalized forward-backward algorithms for structured monotone inclusions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091986)