On the convergence rate of the Douglas-Rachford splitting algorithm

Hadi Abbaszadehpeivasti, Moslem Zamani · 2025

Read On the convergence rate of the Douglas-Rachford splitting algorithm by Hadi Abbaszadehpeivasti, Moslem Zamani (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-06676.txt.

Introduction

How fast a widely used optimization method settles down is pinned down exactly by Hadi Abbaszadehpeivasti and one co-author in a 2025 optimization paper. The Douglas-Rachford splitting algorithm finds a point where two maximally monotone operators sum to zero, a task behind many feasibility and optimization problems. Precise rates, rather than rough bounds, were missing.

The authors obtain an exact convergence rate for the method and show it cannot be improved, at least for convex feasibility problems. They also give conditions that are both necessary and sufficient for the faster linear form of convergence. Composite optimization problems, where a cost splits into simpler pieces, get their own analysis of the method's behavior. The paper ends with several conjectures about that setting, marking where the theory of this workhorse algorithm remains unfinished.

Catalog record

CREATORHadi Abbaszadehpeivasti, Moslem Zamani
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-06676

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the convergence rate of the Douglas-Rachford splitting algorithm Hadi Abbaszadehpeivasti, Moslem Zamani Abstract This work is concerned with the convergence rate analysis of the Dou- glas–Rachford splitting (DRS) method for finding a zero of the sum of two maximally monotone operators. We obtain an exact rate of convergence for the DRS algorithm and demonstrate its sharpness in the setting of convex feasibility problems. Further- more, we investigate the linear convergence of the DRS algorithm, providing both necessary and sufficient conditions that characterize this behavior. We further examine the performance of the DRS method when applied to convex composite optimization problems. The paper concludes with several conjectures on the convergence behavior of the DRS algorithm for this class of problems. keywords Douglas-Rachford splitting method, Convergence rate, Performance estimation † † manuscriptno: IJOC-0001-2024.00 † † runningauthor: A. Peivasti and Zamani † † runningtitle: Convergence rate of the DRS algorithm † † authors: Department of Econometrics and Operations Research, Tilburg University, Tilburg, The Netherlands, [email protected] Department of Industrial Engineering and Innovation Sciences, Eindhoven University of Technology, Eindhoven, The Netherlands, [email protected] † † affiliation: † † affiliation: † † affiliation: † † affiliation: 1 Introduction We consider the following monotone inclusion problem \displaystyle\underset{x\in\mathbb{R}^{n}}{\text{find}}\quad 0\in Ax+Bx, (1) where A,B:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n} are maximally monotone operators. The monotone inclusion problem provides a unifying framework that captures numerous fundamental problems in convex optimization, variational inequalities, and equilibrium models [ 5 , 7 , 24 ] . Among the iterative schemes devised for solving monotone inclusions, the Douglas–Rachford splitting (DRS) algorithm [ 7 ] has emerged as one of the most effective and versatile methods. Its popularity stems from its ability to decompose complex problems into simpler subproblems. Furthermore, several important algorithms, including the alternating direction method of multipliers (ADMM), can be analyzed through the lens of the DRS algorithm; see [ 24 , Chapter 3] for further details. Indeed, the close connection of the DRS method to other fundamental operator-splitting techniques, notably ADMM, further highlights its central role in modern optimization [ 24 ] . The DRS method is originally introduced for solving linear systems that appeared in the numerical treatment of partial differential equations (heat equation) [ 8 ] . Lions and Mercier [ 18 ] established that the method is also convergent for a general maximal monotone inclusion problem in the form of ( 1 ). Eckstein and Bertsekas [ 10 ] showed that the DRS method can be interpreted as a proximal point method. We refer the interested reader to [ 13 ] for a historical review of the DRS. The method is given in Algorithm 1 ; see Section 2 for the notations used in Algorithm 1 . Algorithm 1 The Douglas-Rachford splitting method Parameters: number of iterations N , positive stepsize \gamma>0 and relaxation factor \lambda\in(0,2) . Inputs: maximally monotone operators A and B , initial iterate w^{1}\in\mathbb{R}^{n} . For k=1,2,\ldots,N perform the following steps: i) x^{k}=J_{\gamma B}(w^{k}) . ii) y^{k}=J_{\gamma A}(2x^{k}-w^{k}) . iii) w^{k+1}=w^{k}+\lambda(y^{k}-x^{k}) . Algorithm 1 can be written as a fixed point iteration w^{k+1}=Tw^{k} , where \displaystyle T=(1-\tfrac{\lambda}{2})I+\tfrac{\lambda}{2}R_{\gamma A}R_{\gamma B}. (2) and R denotes the reflected resolvent transformation. We call T the Douglas-Rachford (DR) operator throughout the text. It is worth noting that x^{\star} is a solution of problem ( 1 ) if and only if there exists w^{\star} such that x^{\star}=J_{\gamma B}w^{\star} and w^{\star} is a fixed point of the DR operator. We denote the fixed points of operator T by W^{\star} . We adopt the following assumptions to establish convergence rate results. {assumption} Operators A and B are maximally monotone operators and the DR operator ( 2 ) for the given parameters admits a fixed point w^{*} . Note that under these assumptions, w^{k}\to w^{\star} for some w^{\star}\in W^{\star} ; see [ 5 , Theorem 26.11] . In this manuscript, we employ the performance estimation framework to establish our main results. Performance estimation provides a strong and unifying approach for the analysis and design of first-order methods. The framework is introduced in the seminal work of Drori and Teboulle [ 9 ] , and has since attracted significant attention in the optimization community. For a comprehensive review of the performance estimation, we refer the interested reader to [ 1 , 25 , 26 ] . This paper is structured as follows. Section 2 introduces the definitions and fundamental concepts that will be used throughout the subsequent sections. In Section 3 , we analyze the sublinear convergence of the DRS method. Section 4 is dedicated to the study of its linear convergence. Finally, in Section 5 , we investigate the behavior of the DRS method in the context of convex composite optimization problems, and we conclude the paper with some conjectures on the convergence rate of the DRS algorithm for this class of problems. 2 Terminology and notation We briefly recall the key definitions employed in this paper. For further details, the reader is referred to standard references [ 5 , 24 ] . We denote the Euclidean inner product and norm by \langle\cdot,\cdot\rangle and \|\cdot\| , respectively. We use I to denote the identity operator. For a (set-valued) operator A:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n} , we define its graph by \operatorname{gra}A=\{(x,u):u\in Ax\} and we denote its inverse by A^{-1} . An operator A:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n} is called monotone if \langle u-v,x-y\rangle\geq 0\quad\forall(x,u),(y,v)\in\operatorname{gra}A, and it is called maximally monotone if its graph is not properly contained in that of any other monotone operator. The operator A is \beta -cocoercive if for some \beta>0 , we have \langle u-v,x-y\rangle\geq\beta\|u-v\|^{2}\quad\forall(x,u),(y,v)\in\operatorname{gra}A. It is seen that cocoercivity implies Lipschitz continuity but its converse does not necessarily hold. Consequently, a cocoercive operator is single-valued. The operator A is called nonexpansive if it is Lipschitz continuous with modulus one. An operator A is called \mu -strongly monotone if its inverse is \mu -cocoercive. The resolvent of operator A is denoted and defined as J_{A}=(I+A)^{-1} . In addition, we use R_{A}=2J_{A}-I to denote the reflected resolvent of A . Let f:\mathbb{R}^{n}\to(-\infty,\infty] be an extended convex function. The function f is called closed if its epigraph is closed, i.e. \{(x,r):f(x)\leq r\} is a closed subset of \mathbb{R}^{n+1} . The function f is said to be proper if there exists x\in\mathbb{R}^{n} with f(x)<\infty . The subgradients of f at x are denoted and defined as \partial f(x)=\{u:f(y)\geq f(x)+\langle u,y-x\rangle,\forall y\in\mathbb{R}^{n}\}. When f is a closed proper convex function, \partial f is a maximally monotone operator. The convex function f is called L -smooth if \partial f is \tfrac{1}{L} -cocoercive. The function f is said to be \mu -strongly convex if \partial f is \mu -strongly monotone. The proximal operator of a closed proper convex function f is defined and denoted as \operatorname{prox}_{f}=(I+\partial f)^{-1} . Given closed convex set C , the normal cone operator N_{C} of C is defined by N_{C}(x)=\{u\in\mathbb{R}^{n}:\langle u,y-x\rangle\leq 0,\ \forall y\in C\},\quad x\in C, with N_{C}(x)=\emptyset otherwise. The projection onto C is written as \Pi_{C} . The corresponding distance function to C is denoted by \dist_{C} . 3 Sublinear convergence of the DRS method In this section, we study the convergence of the DRS algorithm for a general monotone inclusion problem. Regarding the DRS algorithm, we have \displaystyle\left\|Tw^{N}-w^{N}\right\|^{2}\leq\tfrac{\lambda(N-1)^{(N-1)}}{(2-\lambda)N^{N}}\left\|w^{1}-w^{\star}\right\|^{2}, (3) when \gamma>0 and \lambda\in[1,1+\sqrt{\tfrac{k-1}{k}}) in Algorithm 1 ; see [ 17

Read the complete text