Splitting Algorithms for the Sum of Two Nonlinear Operators

1979/12/01 by P. L. Lions, Pierre‐Louis Lions, B. Mercier +1 · 2,023 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Aerospace Engineering and Control Systems #Algorithm #Applied mathematics #Computation #Convergence (economics) #Linear operators #Mathematical analysis #Mathematical optimization #Mathematics #Minification #Monotone polygon #Nonlinear system #Operator splitting #Optimization and Variational Analysis

paper · doi:10.1137/0716071

published in SIAM Journal on Numerical Analysis 16(6), 964-979 (Society for Industrial and Applied Mathematics)

openalex publication_date 1979/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Splitting algorithms for the sum of two monotone operators. We study two splitting algorithms for (stationary and evolution) problems involving the sum of two monotone operators. These algorithms are well known in the linear case and are here extended to the case of multivalued monotone operators. We prove the convergence of these algorithms, we give some applications to the obstacle problem and to minimization problems; and finally we present numerical computations comparing these algorithms to some other classical methods.

Cited by

• Homogeneous Self-Dual Embedding via Perspective Functions
• Finite Element Approximation of the Cahn--Hilliard Equation with Degenerate Mobility
• Forward-Reflected-Backward algorithm with Linesearch
• A frugal primal-dual splitting with minimal lifting over arbitrary rooted trees
• A primal-dual splitting algorithm for monotone inclusions with applications
• Majorization-Minimization Bregman Proximal Gradient Algorithms for NMF with the Kullback–Leibler Divergence
• An Efficient Primal-Dual Prox Method for Non-Smooth Optimization
• Clustering with feature selection using alternating minimization, Application to computational biology
• An adaptive splitting algorithm for the sum of three operators
• A simplified proof of weak convergence in Douglas-Rachford method to a solution of the unnderlying inclusion problem
• Convergence of the Chambolle-Pock Algorithm in the Absence of Monotonicity
• Convergence of the Preconditioned Proximal Point Method and Douglas-Rachford Splitting in the Absence of Monotonicity
• Projection and contraction methods with double inertial steps for variational inclusion problems on Hilbert spaces
• Curvature Recycling Douglas-Rachford Splitting: Transported Quasi-Newton Models for Expensive Smooth Proximal Subproblems
• Regularization methods for solving hierarchical variational inequalities with complexity guarantees
• Shadow splitting methods for nonconvex optimisation: epi-approximation, convergence and saddle point avoidance
• A perturbed preconditioned gradient descent method for the unconstrained minimization of composite objectives
• Linear convergence of relocated fixed-point iterations
• A Direct Second-Order Method for Solving Two-Player Zero-Sum Games
• Primal-dual splitting for structured composite monotone inclusions with or without cocoercivity
• A nonmonotone extrapolated proximal gradient-subgradient algorithm beyond global Lipschitz gradient continuity
• Uniqueness of DRS as the 2 Operator Resolvent-Splitting and\n Impossibility of 3 Operator Resolvent-Splitting
• Parabolic hysteresis problems revisited: Finite element error analysis and convergent Newton-type solvers
• Robust supervised classification and feature selection using a primal-dual method
• Peaceman-Rachford splitting for a class of nonconvex optimization problems
• Extending Douglas-Rachford Splitting for Convex Optimization
• Perturbing the Derivative: Doubly Wild Refitting for Model-Free Evaluation of Opaque Machine Learning Predictors
• Tight Linear Convergence Rate Bounds for Douglas-Rachford Splitting and ADMM
• Duality methods for solving variational inequalities
• Dynamical systems and forward-backward algorithms associated with the sum of a convex subdifferential and a monotone cocoercive operator
• Online Distributed ADMM on Networks
• Fast convergence of generalized forward-backward algorithms for structured monotone inclusions
• Stochastic Smoothing for Nonsmooth Minimizations: Accelerating SGD by Exploiting Structure
• Parallel Multi-Block ADMM with o(1/k) Convergence
• Systems of Structured Monotone Inclusions: Duality, Algorithms, and Applications
• Linear Convergence and Error Bounds for Optimization Without Strong Convexity
• Proximal Point Algorithms for Nonsmooth Convex Optimization with Fixed Point Constraints
• Alternating Direction Method of Multipliers for Linear Inverse Problems
• A two-level distributed algorithm for nonconvex constrained optimization
• Proximal Gradient Descent-Ascent: Variable Convergence under KŁ Geometry
• Geometry of First-Order Methods and Adaptive Acceleration
• Resolvent Splitting for Sums of Monotone Operators with Minimal Lifting
• Towards stability and optimality in stochastic gradient descent
• Nuclear Norm based Matrix Regression with Applications to Face Recognition with Occlusion and Illumination Changes
• Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusions
• On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers
• Augmented Lagrangian-Based Decomposition Methods with Non-Ergodic Optimal Rates
• On the computation of equilibria in monotone and potential stochastic hierarchical games
• Nonnegative Low-Rank Matrix Correction under an Orthogonality Constraint in Conservative Vlasov Simulations
• Efficient Optimization Algorithms for Robust Principal Component Analysis and Its Variants
• Proximal-Like Incremental Aggregated Gradient Method with Linear Convergence under Bregman Distance Growth Conditions
• Phase Retrieval with Application to Optical Imaging: A contemporary overview
• Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
• A Monotone+Skew Splitting Model for Composite Monotone Inclusions in Duality
• An alternating direction method with increasing penalty for stable principal component pursuit
• Modified Fejér sequences and applications
• Convergence rate analysis of primal-dual splitting schemes
• Online and stochastic Douglas-Rachford splitting method for large scale machine learning
• Generalized Kalman Smoothing: Modeling and Algorithms
• The Douglas-Rachford Algorithm for Weakly Convex Penalties
• Proximal Splitting Methods in Signal Processing
• Local Convergence Properties of Douglas--Rachford and ADMM
• Nonlinear forward-backward-half forward splitting with momentum for monotone inclusions
• Activity Identification and Local Linear Convergence of Douglas--Rachford/ADMM under Partial Smoothness
• Scenarios and Policy Aggregation in Optimization Under Uncertainty
• Efficient optimization-based invariant-domain-preserving limiters in solving gas dynamics equations
• Solving Mixed Integer Programs Using Neural Networks
• Quadratic Convergence of a Projection Method for a Plane Curve Feasibility Problem
• Communication-Efficient Algorithms For Distributed Optimization
• Linear convergence of the Douglas-Rachford algorithm via a generic error bound condition
• Approximate Bregman proximal gradient algorithm with variable metric Armijo--Wolfe line search
• An Extragradient-Based Alternating Direction Method for Convex Minimization
• A primal-dual splitting algorithm with convex combination and larger step sizes for composite monotone inclusion problems
• Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions
• On the Relationships among GPU-Accelerated First-Order Methods for Solving Linear Programming
• A note on the Davis-Yin three-operator splitting method
• A regret minimization approach to fixed-point iterations
• A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functions
• Forward-backward approximation of evolution equations in finite and infinite horizon
• Exact Total Variation Minimizers as Non-Oscillatory Limiters in High-Order Methods for Conservation Laws
• On the Optimal Linear Convergence Rate of a Generalized Proximal Point Algorithm
• On the Asymptotic Linear Convergence Speed of Anderson Acceleration Applied to ADMM
• Nonconvex Regularization for Feature Selection in Reinforcement Learning
• Simple linesearch-free first-order methods for nonconvex optimization
• On the order of the operators in the Douglas-Rachford algorithm
• Optimal rates of convergence of matrices with applications
• Random Nonlinear Fusion Frames from Averaged Operator Iterations
• Bregman Douglas-Rachford Splitting Method
• A Monte Carlo Approach for Nonsmooth Convex Optimization via Proximal Splitting Algorithms
• OSQP: An Operator Splitting Solver for Quadratic Programs
• On the convergence rate of the Douglas-Rachford splitting algorithm
• On the Schur Stability of Some Image Reconstruction Operators
• Auxiliary Image Regularization for Deep CNNs with Noisy Labels
• ADMM for Multiaffine Constrained Optimization
• Solving Imaging Inverse Problems Using Plug-and-Play Denoisers: Regularization and Optimization Perspectives
• Asynchronous Variance-reduced Block Schemes for Composite Nonconvex Stochastic Optimization: Block-specific Steplengths and Adapted Batch-sizes
• Asymptotic behavior of a nonautonomous evolution equation governed by a quasi-nonexpansive operator
• On Generalized Forward-Reflected-Backward Method for Monotone Inclusion Problems
• Forward-Douglas-Rachford splitting and forward-partial inverse method for solving monotone inclusions
• Designing across domains with declarative thinking: Insights from the 96-Eyes ptychographic imager project
• Weak convergence on Douglas-Rachford method
• A Generic online acceleration scheme for Optimization algorithms via Relaxation and Inertia
• Phase Retrieval with Application to Optical Imaging
• Linear Convergence of Proximal Gradient Algorithm with Extrapolation for a Class of Nonconvex Nonsmooth Minimization Problems
• Incremental Aggregated Proximal and Augmented Lagrangian Algorithms
• Stadium norm and Douglas-Rachford splitting: a new approach to road design optimization
• On the Sublinear Convergence Rate of Multi-Block ADMM
• Mean Field Type Control with Congestion (II): An Augmented Lagrangian Method
• Constraint reduction reformulations for projection algorithms with applications to wavelet construction
• From Noisy Fixed-Point Iterations to Private ADMM for Centralized and Federated Learning
• A New Use of Douglas-Rachford Splitting and ADMM for Identifying Infeasible, Unbounded, and Pathological Conic Programs
• An outer reflected forward-backward splitting algorithm for solving monotone inclusions
• On the Global Linear Convergence of the ADMM with Multi-Block Variables
• The Baillon-Haddad Theorem Revisited
• On Douglas-Rachford operators that fail to be proximal mappings
• On the Linear Convergence of the Alternating Direction Method of Multipliers
• Alternating Linearization for Structured Regularization Problems
• A three-operator splitting perspective of a three-block ADMM for convex quadratic semidefinite programming and extensions
• An approximation scheme for semilinear parabolic PDEs with convex and coercive Hamiltonians
• A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity
• Asymptotics of Proximity Operator for Squared Loss and Performance Prediction of Nonconvex Sparse Signal Recovery
• Relaxed and inertial nonlinear Forward-Backward algorithm
• Fast First-Order Methods for Stable Principal Component Pursuit
• Distributed Algorithms for Computing a Common Fixed Point of a Group of Nonexpansive Operators
• The splitting algorithms by Ryu and by Malitsky-Tam applied to normal cones of linear subspaces converge strongly to the projection onto the intersection
• Level-set Subdifferential Error Bounds and Linear Convergence of Variable Bregman Proximal Gradient Method
• Optimal Nonergodic Sublinear Convergence Rate of Proximal Point Algorithm for Maximal Monotone Inclusion Problems
• A Variational Approach on Level sets and Linear Convergence of Variable Bregman Proximal Gradient Method for Nonconvex Optimization Problems
• Stochastic Projective Splitting: Solving Saddle-Point Problems with Multiple Regularizers
• A Nonlinear Bregman Primal-Dual Framework for Optimizing Nonconvex Infimal Convolutions
• Inertial Douglas-Rachford splitting for monotone inclusion problems
• A Proximal Stochastic Gradient Method with Progressive Variance Reduction
• Solution to a Monotone Inclusion Problem using the Relaxed Peaceman-Rachford Splitting Method: Convergence and its Rates
• Set intersection problems: Integrating projection and quadratic programming algorithms
• Accelerated Symmetric ADMM and Its Applications in Signal Processing
• On inexact relative-error hybrid proximal extragradient, forward-backward and Tseng's modified forward-backward methods with inertial effects
• An ADMM-Based Interior-Point Method for Large-Scale Linear Programming
• Proximal Gradient Algorithms: Applications in Signal Processing
• Techniques for Gradient Based Bilevel Optimization with Nonsmooth Lower Level Problems
• An Incremental Path-Following Splitting Method for Linearly Constrained Nonconvex Nonsmooth Programs
• An O(nlog(n)) Algorithm for Projecting Onto the Ordered Weighted ℓ₁ Norm Ball
• Fixed Point Analysis of Douglas-Rachford Splitting for Ptychography and Phase Retrieval
• Local Linear Convergence Analysis of Primal-Dual Splitting Methods
• On Biased Stochastic Gradient Estimation
• Estimation of low-rank tensors via convex optimization
• Dissipativity-based time domain decomposition for optimal control of hyperbolic PDEs
• Relocated Fixed-Point Iterations with Applications to Variable Stepsize Resolvent Splitting
• Randomized First-Order Methods for Saddle Point Optimization
• An inexact inertial projective splitting algorithm with strong convergence
• Convergence rate analysis of the forward-Douglas-Rachford splitting scheme
• Douglas-Rachford Splitting: Complexity Estimates and Accelerated Variants
• A new splitting method for solving composite monotone inclusions involving parallel-sum operators
• Sparse Learning with Semi-Proximal-Based Strictly Contractive Peaceman-Rachford Splitting Method
• HPR-QP: A dual Halpern Peaceman-Rachford method for solving large-scale convex composite quadratic programming
• Alternating Direction Method of Multipliers for Sparse Principal Component Analysis
• On fully practical finite element approximations of degenerate Cahn-Hilliard systems
• Algorithms for Overcoming the Curse of Dimensionality for Certain Hamilton-Jacobi Equations Arising in Control Theory and Elsewhere
• Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Quadratic and Semi-Definite Programming
• AutoLyap: A Python package for computer-assisted Lyapunov analyses for first-order methods
• Exact worst-case convergence rates for Douglas--Rachford and Davis--Yin splitting methods
• Solving Composite Monotone Inclusions in Reflexive Banach Spaces by Constructing Best Bregman Approximations from Their Kuhn-Tucker Set
• Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions
• Decomposition in conic optimization with partially separable structure
• Splitting with Near-Circulant Linear Systems: Applications to Total Variation CT and PET
• Linear Convergence of the Douglas-Rachford Method for Two Closed Sets
• On the Convergence Analysis of Asynchronous Distributed Quadratic\n Programming via Dual Decomposition
• Norm Convergence of Realistic Projection and Reflection Methods
• Block based refitting in ℓ₁₂ sparse regularisation
• A projection-based framework for gradient-free and parallel learning
• A Douglas-Rachford construction of non-separable continuous compactly supported multidimensional wavelets
• TFPnP: Tuning-free Plug-and-Play Proximal Algorithm with Applications to Inverse Imaging Problems
• Distributed Deblurring of Large Images of Wide Field-Of-View
• Proximal Gradient Method for Nonsmooth Optimization over the Stiefel Manifold
• Projective Splitting with Forward Steps: Asynchronous and Block-Iterative Operator Splitting
• On the convergence rate improvement of a splitting method for finding the resolvent of the sum of maximal monotone operators
• Exploring the Subgraph Density-Size Trade-off via the Lovász Extension
• Linear convergence of the generalized PPA and several splitting methods for the composite inclusion problem
• Dynamical behavior of a stochastic forward-backward algorithm using random monotone operators
• A Relaxed-Projection Splitting Algorithm for Variational Inequalities in Hilbert Spaces
• Screening for Sparse Online Learning
• Stabilized Sparse Online Learning for Sparse Data
• Iteration-Complexity of a Generalized Forward Backward Splitting Algorithm
• An Operator Splitting View of Federated Learning
• A New Primal-Dual Algorithm for a Class of Nonlinear Compositional Convex Optimization Problems
• Fourier Phase Retrieval with a Single Mask by Douglas-Rachford Algorithm
• Activity Identification and Local Linear Convergence of Forward--Backward-type methods
• Alternating direction method of multipliers with variable step sizes
• A Constant Step Stochastic Douglas-Rachford Algorithm with Application to Non Separable Regularizations
• Graph splitting methods: Fixed points and strong convergence for linear subspaces
• A Decomposition Method for Solving Multicommodity Network Equilibrium
• Resolvent splitting with minimal lifting for composite monotone inclusions
• An accelerated proximal iterative hard thresholding method for ℓ₀ minimization
• A Learning-Based Inexact ADMM for Solving Quadratic Programs
• Douglas-Rachford splitting for a Lipschitz continuous and a strongly\n monotone operator
• Projection methods in quantum information science
• Random Function Iterations for Stochastic Fixed Point Problems
• Multi-scale Mining of fMRI data with Hierarchical Structured Sparsity
• A Stochastic forward-backward splitting method for solving monotone inclusions in Hilbert spaces
• Blind Ptychography by Douglas-Rachford Splitting
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• Asymptotic Linear Convergence of ADMM for Isotropic TV Norm Compressed Sensing
• A Double Inertial Forward-Backward Splitting Algorithm With Applications to Regression and Classification Problems
• An Envelope for Davis-Yin Splitting and Strict Saddle Point Avoidance
• Efficient and robust high-dimensional sparse logistic regression via nonlinear primal-dual hybrid gradient algorithms
• A path-following framework on fiber bundle for variational inequalities
• Machine Discovery of Partial Differential Equations from Spatiotemporal Data
• Finding best approximation pairs for two intersections of closed convex sets
• Solving monotone inclusions via compositions of nonexpansive averaged operators
• The charge-flipping algorithm in crystallography
• Shadow-point Enhanced Inexact Accelerated Proximal Gradient Method with Preserved Convergence Guarantees
• Monotone Operator Theory in Convex Optimization
• Split-Douglas-Rachford algorithm for composite monotone inclusions and Split-ADMM
• Sparse approximate solution of fitting surface to scattered points by MLASSO model
• Convergence Rate Analysis for Averaged Fixed Point Iterations in Common Fixed Point Problems
• Semi-implicit relaxed Douglas-Rachford algorithm (sDR) for ptychography
• An inertial three-operator splitting algorithm with applications to image inpainting
• A Fast Stochastic Plug-and-Play ADMM for Imaging Inverse Problems
• New Primal-Dual Algorithm for Convex Problems
• On the complexity of proximal gradient and proximal gradient-Newton-CG methods for \(ℓ₁\)-regularized Optimization
• Non-Stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
• A general approach to distributed operator splitting
• Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization without Strong Convexity
• Recent Results on Douglas–Rachford Methods for Combinatorial Optimization Problems
• Inducing strong convergence of trajectories in dynamical systems associated to monotone inclusions with composite structure
• Optimal Convergence Rates for Generalized Alternating Projections
• Splitting the Forward-Backward Algorithm: A Full Characterization
• A relaxed version of Ryu's three-operator splitting method for structured nonconvex optimization
• Hierarchical Convex Optimization by the Hybrid Steepest Descent Method with Proximal Splitting Operators—Enhancements of SVM and Lasso
• A Geometric Framework for Stochastic Iterations
• On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operators
• A General Framework for a Class of First Order Primal-Dual Algorithms for Convex Optimization in Imaging Science
• Hybrid algorithm for common solution of monotone inclusion problem and fixed point problem and applications to variational inequalities. [europepmc]
• Iterative Potts and Blake-Zisserman minimization for the recovery of functions with discontinuities from indirect measurements. [europepmc]
• Sparse Parallel MRI Based on Accelerated Operator Splitting Schemes. [europepmc]
• Accurate and efficient numerical solutions for elliptic obstacle problems. [europepmc]
• Learning partial differential equations via data discovery and sparse optimization. [europepmc]
• Strong convergence theorems by hybrid and shrinking projection methods for sums of two monotone operators. [europepmc]
• A symmetric version of the generalized alternating direction method of multipliers for two-block separable convex programming. [europepmc]
• The symmetric ADMM with indefinite proximal regularization and its application. [europepmc]
• Modified forward-backward splitting midpoint method with superposition perturbations for the sum of two kinds of infinite accretive mappings and its applications. [europepmc]
• Proximal extrapolated gradient methods for variational inequalities. [europepmc]
• Strong convergence and bounded perturbation resilience of a modified proximal gradient algorithm. [europepmc]
• FitEllipsoid: a fast supervised ellipsoid segmentation plugin. [europepmc]
• Flow of a new class of non-Newtonian fluids in tubes of non-circular cross-sections. [europepmc]
• On the Performance of Efficient Channel Estimation Strategies for Hybrid Millimeter Wave MIMO System. [europepmc]
• On the asymptotic behavior of the Douglas-Rachford and proximal-point algorithms for convex optimization. [europepmc]
• An Optimization-Based Meta-Learning Model for MRI Reconstruction with Diverse Dataset. [europepmc]
• Sparse and risk diversification portfolio selection. [europepmc]
• A primal-dual splitting algorithm for composite monotone inclusions with minimal lifting. [europepmc]
• Graph regularized non-negative matrix factorization with L 2 , 1 norm regularization terms for drug-target interactions prediction. [europepmc]
• In Vivo Myelin Water Quantification Using Diffusion-Relaxation Correlation MRI: A Comparison of 1D and 2D Methods. [europepmc]
• A modified Tseng algorithm approach to restoring thoracic diseases' computerized tomography images. [europepmc]
• Efficient First-Order Algorithms for Large-Scale, Non-Smooth Maximum Entropy Models with Application to Wildfire Science. [europepmc]
• Automated tight Lyapunov analysis for first-order methods. [europepmc]
• In-vivo myelin water quantification using diffusion-relaxation correlation MRI: a comparison of 1D and 2D methods [europepmc]

Related

• An adaptive splitting algorithm for the sum of three operators
• On the convergence rate improvement of a splitting method for finding the resolvent of the sum of maximal monotone operators
• Nonlinear three-operator splitting algorithms with momentum for monotone inclusions
• Four-operator splitting algorithms for solving monotone inclusions
• Backward-Forward-Reflected-Backward Splitting for Three Operator Monotone Inclusions