Resolvent splitting for sums of monotone operators with minimal lifting

DOI10.1007/S10107-022-01906-4MaRDI QIDQ6165585zbMATH OpenOpenAlexFDO

Authors Yura Malitsky, Matthew K. Tam

Publication date 1 August 2023

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

ADMMsplitting algorithmmonotone operatordecentralised optimisation

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Nonlinear programming (90C30) Monotone operators and generalizations (47H05) Fixed-point iterations (47J26)

Abstract: In this work, we study fixed point algorithms for finding a zero in the sum of $ngeq2$ maximally monotone operators by using their resolvents. More precisely, we consider the class of such algorithms where each resolvent is evaluated only once per iteration. For any algorithm from this class, we show that the underlying fixed point operator is necessarily defined on a $d$-fold Cartesian product space with $dgeqn-1$. Further, we show that this bound is unimprovable by providing a family of examples for which $d=n-1$ is attained. This family includes the Douglas-Rachford algorithm as the special case when $n=2$. Applications of the new family of algorithms in distributed decentralised optimisation and multi-block extensions of the alternation direction method of multipliers (ADMM) are discussed.

Recommendations

• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• Iterative construction of the resolvent of a sum of maximal monotone operators
• Adaptive Douglas-Rachford splitting algorithm for the sum of two operators
• Inertial Douglas-Rachford splitting for monotone inclusion problems
• Uniqueness of DRS as the 2 operator resolvent-splitting and impossibility of 3 operator resolvent-splitting

Cites work

• A first-order primal-dual algorithm for convex problems with applications to imaging
• A primal-dual splitting algorithm for composite monotone inclusions with minimal lifting
• A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
• A product space reformulation with reduced dimension for splitting algorithms
• Asymptotic behavior of contractions in Hilbert space
• Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective
• Convex analysis and monotone operator theory in Hilbert spaces
• Convex optimization algorithms
• Douglas-Rachford splitting and ADMM for pathological convex optimization
• Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers
• Monotone (nonlinear) operators in Hilbert space
• Monotone Operators and the Proximal Point Algorithm
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
• Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twists
• Proximal splitting methods in signal processing
• Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Strengthened splitting methods for computing resolvents
• The Numerical Solution of Parabolic and Elliptic Differential Equations
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
• Uniqueness of DRS as the 2 operator resolvent-splitting and impossibility of 3 operator resolvent-splitting

Cited in

(12)

• Regularity of sets under a reformulation in a product space with reduced dimension
• Distributed forward-backward methods for ring networks
• Resolvents of minus \(M\)-matrices and splittings of \(M\)-matrices
• The geometry of monotone operator splitting methods
• Frugal Splitting Operators: Representation, Minimal Lifting, and Convergence
• Adaptive Douglas-Rachford splitting algorithm for the sum of two operators
• Iterative construction of the resolvent of a sum of maximal monotone operators
• Strengthened splitting methods for computing resolvents
• Computing the resolvent of the sum of maximally monotone operators with the averaged alternating modified reflections algorithm
• scientific article; zbMATH DE number 3869827 (Why is no real title available?)
• Uniqueness of DRS as the 2 operator resolvent-splitting and impossibility of 3 operator resolvent-splitting
• On a new simple algorithm to compute the resolvents

This page was built for publication: Resolvent splitting for sums of monotone operators with minimal lifting

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