Splitting Algorithms for the Sum of Two Nonlinear Operators

1979/12/01 by P. L. Lions, Pierre‐Louis Lions, B. Mercier +1 · 187 citations
Computer Science · Mathematics · Engineering · #Optimization and Variational Analysis #Advanced Optimization Algorithms Research #Aerospace Engineering and Control Systems

paper · doi:10.1137/0716071

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\n 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\n ADMM
• Duality methods for solving variational inequalities
• Dynamical systems and forward-backward algorithms associated with the\n sum of a convex subdifferential and a monotone cocoercive operator
• Online Distributed ADMM on Networks
• Fast convergence of generalized forward-backward algorithms for\n 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\n 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\n 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\n 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\n 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\n 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\n 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\n 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\n Multiple Regularizers
• A Nonlinear Bregman Primal-Dual Framework for Optimizing Nonconvex\n 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\n 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,\n forward-backward and Tseng's modified forward-backward methods with inertial\n 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\n Level Problems
• An Incremental Path-Following Splitting Method for Linearly Constrained Nonconvex Nonsmooth Programs
• An O(n\log(n)) Algorithm for Projecting Onto the Ordered Weighted\n \ℓ₁ 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\n scheme
• Douglas-Rachford Splitting: Complexity Estimates and Accelerated\n Variants
• A new splitting method for solving composite monotone inclusions involving parallel-sum operators
• Sparse Learning with Semi-Proximal-Based Strictly Contractive\n 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\n 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
• 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
• 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\n 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
• A Constant Step Stochastic Douglas-Rachford Algorithm with Application\n to Non Separable Regularizations
• Graph splitting methods: Fixed points and strong convergence for linear subspaces
• A Decomposition Method for Solving Multicommodity Network Equilibrium

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