Resolvent splitting for sums of monotone operators with minimal lifting

DOI10.1007/S10107-022-01906-4zbMATH Open1522.47107arXiv2108.02897OpenAlexW4312202117MaRDI QIDQ6165585FDOQ6165585

Authors: Yura Malitsky, Matthew K. Tam 

Publication date: 1 August 2023

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

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.

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

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

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)

Cites Work

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

Cited In (12)

• Regularity of sets under a reformulation in a product space with reduced dimension
• Distributed forward-backward methods for ring networks
• The geometry of monotone operator splitting methods
• Resolvents of minus \(M\)-matrices and splittings of \(M\)-matrices
• 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
• Title not available (Why is that?)
• 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)