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

zbMATH Open1496.90058arXiv2107.10107MaRDI QIDQ5091986FDOQ5091986

Authors: Paul-Emile Maingé 

Publication date: 27 July 2022

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.

Full work available at URL: https://arxiv.org/abs/2107.10107

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

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)

Cites Work

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

Cited In (13)

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

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)