Extending Douglas–Rachford Splitting for Convex Optimization
Max Nilsson, Anton Åkerman, Pontus Giselsson[0.5ex] Department of Automatic Control, Lund University, Lund, Sweden{ max.nilsson , anton.akerman , pontus.giselsson }@control.lth.se, [1ex] These authors contributed equally to this work. · 2025
Read Extending Douglas–Rachford Splitting for Convex Optimization by Max Nilsson, Anton Åkerman, Pontus Giselsson[0.5ex] Department of Automatic Control, Lund University, Lund, Sweden{ max.nilsson , anton.akerman , pontus.giselsson }@control.lth.se, [1ex] These authors contributed equally to this work. (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-2511-19637.txt.
Introduction
Max Nilsson, Anton Åkerman, and Pontus Giselsson extend a classical algorithm family for convex optimization. Douglas-Rachford splitting solves problems built from two monotone operators, and it was recently shown to be the only frugal splitting of its kind that always converges in general. The authors ask whether convex problems allow more.
When the operators come from convex functions, a strictly larger class of such methods converges unconditionally. The paper characterizes every member of that class and proves the boundary is sharp: convergence holds exactly on the identified parameter regions. New ADMM-type and Chambolle-Pock-type methods fall out through known reformulations.
Catalog record
| CREATOR | Max Nilsson, Anton Åkerman, Pontus Giselsson[0.5ex] Department of Automatic Control, Lund University, Lund, Sweden{ max.nilsson , anton.akerman , pontus.giselsson }@control.lth.se, [1ex] These authors contributed equally to this work. |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 109 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-19637
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Extending Douglas–Rachford Splitting for Convex Optimization Max Nilsson, Anton Åkerman, Pontus Giselsson[0.5ex] Department of Automatic Control, Lund University, Lund, Sweden{ max.nilsson , anton.akerman , pontus.giselsson }@control.lth.se, [1ex] These authors contributed equally to this work. Abstract The Douglas–Rachford splitting method is a classical and widely used algorithm for solving monotone inclusions involving the sum of two maximally monotone operators. It was recently shown to be the unique frugal, no-lifting resolvent-splitting method that is unconditionally convergent in the general two-operator setting. In this work, we show that this uniqueness does not hold in the convex optimization case: when the operators are subdifferentials of proper, closed, convex functions, a strictly larger class of frugal, no-lifting resolvent-splitting methods is unconditionally convergent. We provide a complete characterization of all such methods in the convex optimization setting and prove that this characterization is sharp: unconditional convergence holds exactly on the identified parameter regions. These results immediately yield new families of convergent ADMM-type and Chambolle–Pock-type methods obtained through their Douglas–Rachford reformulations. 1 Introduction \alpha/\beta \theta 2 1 Figure 1: Parameter region of unconditional convergence for the algorithm in ( 4 ). The region of unconditional convergence for the general monotone inclusion setting (i.e., for the algorithm in ( 3 )) is the line segment \alpha/\beta=1 and \theta\in(0,2) . The Douglas–Rachford splitting method is a celebrated algorithm for solving monotone inclusion problems of the form \text{find }x\in\mathcal{H}\text{ such that }0\in A(x)+B(x), (1) where A,B:\mathcal{H}\rightrightarrows\mathcal{H} are maximally monotone operators and \mathcal{H} is a real Hilbert space. While originally developed for solving heat conduction problems [ 16 ] , it has since Lions and Mercier in [ 30 ] proved its applicability to maximal monotone inclusion problems been extensively used and analyzed. A particularly important case of study is the convex optimization setting with problems of the form \minimize_{x\in\mathcal{H}}f(x)+g(x), (2) where f,g:\mathcal{H}\to\mathbb{R}\cup\{+\infty\} are proper, closed, and convex functions. Under mild assumptions (see e.g., [ 5 ] ), the problem ( 2 ) is a specialization of ( 1 ) by letting A=\partial f and B=\partial g . An early interpretation of the Douglas–Rachford method was provided in [ 18 , 17 ] , where it was shown to be an instance of the proximal point algorithm [ 33 , 39 ] , offering a powerful framework for its analysis. Many subsequent works have provided (local) linear convergence for the Douglas–Rachford splitting method under various assumptions. For instance: [ 8 , 26 , 6 , 25 ] for convex and nonconvex feasibility problems, [ 7 , 15 , 29 ] for convex optimization problems under more or less general partial smoothness assumptions, [ 30 , 21 , 22 , 35 , 42 ] under different combinations of strong monotonicity and smoothness assumptions in monotone inclusion and convex optimization settings, and [ 27 , 44 ] for nonconvex optimization. Many of these analyses are tight in the sense that they are not improvable without changing the assumptions. The remarkable success of the Douglas–Rachford splitting method can perhaps in part be explained by the result of [ 43 ] , which shows that it is the unique “simple” resolvent splitting method for problems of the form ( 1 ) that both possesses the fixed-point encoding property and is unconditionally convergent . Here, “simple” refers to methods that use minimal lifting and are frugal . Loosely speaking, a resolvent splitting method is an algorithm that accesses the operators A and B only through their resolvents (denoted J_{\alpha A} and J_{\beta B} respectively, where \alpha,\beta\in\mathbb{R}_{++} are step sizes) and forms iterates from pre-defined linear combinations of their inputs and outputs. Such a method is frugal if it evaluates each resolvent only once per iteration, has minimal lifting if the dimension d (the lifting number) of the product space vector in \mathcal{H}^{d} that carries information between algorithm iterations is as small as possible (in the Douglas–Rachford case, we have no lifting, i.e., d=1 ), is a fixed-point encoding if the fixed-point set of the algorithm and the solution set of the problem are simultaneously nonempty, and is unconditionally convergent if there exist parameter choices guaranteeing convergence for every problem in the problem class and every algorithm starting point. The uniqueness of the Douglas–Rachford method under these conditions for problems of the form ( 1 ) is established in [ 43 ] through two results: one parameterizing the class of frugal, no-lifting resolvent methods with the fixed-point encoding property, and one characterizing its subset of methods with unconditional convergence. It was shown that each frugal, no-lifting resolvent method for solving ( 1 )—up to equivalence—satisfies the fixed-point encoding property if and only if it has the form \left\lfloor\begin{aligned} x_{1}&=J_{\alpha A}(z)\\ x_{2}&=J_{\beta B}\left(\left(1+\frac{\beta}{\alpha}\right)x_{1}-\frac{\beta}{\alpha}z\right)\\ z^{+}&=z+\theta(x_{2}-x_{1})\end{aligned}\right., (3) with parameters \alpha,\beta\in\mathbb{R}_{++} and \theta\in\mathbb{R}\setminus\{0\} . The second result in [ 43 ] establishes that, among algorithms of the form ( 3 ), the restrictions \alpha=\beta and \theta\in(0,2) are necessary and sufficient for unconditional convergence whenever \dim(\mathcal{H})\geq 2 . The results in [ 43 ] have sparked much research on minimal lifting methods, see, e.g., [ 32 , 2 , 34 , 1 ] , which address monotone inclusions involving sums of arbitrarily many operators. In this work, we address the following question in the two-operator setting: Can we characterize all frugal, no-lifting, unconditionally convergent resolvent splitting methods with fixed-point encoding for solving ( 1 ) in the convex optimization setting A=\partial f , B=\partial g ? We show that the answer is yes . Moreover, the restriction to the optimization setting leads to a significantly larger class of admissible algorithms than in the general monotone inclusion setting of [ 43 ] . In particular, we show that the convex-optimization specialization of ( 3 ) \left\lfloor\begin{aligned} x_{1}&={\rm{prox}}_{\alpha f}(z)\\ x_{2}&={\rm{prox}}_{\beta g}\left(\left(1+\frac{\beta}{\alpha}\right)x_{1}-\frac{\beta}{\alpha}z\right)\\ z^{+}&=z+\theta(x_{2}-x_{1})\end{aligned}\right., (4) completely characterizes all frugal, no-lifting, unconditionally convergent resolvent splittings with fixed-point encoding in the convex optimization setting ( 2 ), when the parameters (\alpha,\beta,\theta) satisfy \displaystyle(\alpha,\beta,\theta)\in\left\{(\alpha,\beta,\theta)\in\mathbb{R}_{++}^{3}\mid\theta<\min\{2,2\alpha/\beta\}\right\}. (5) Figure 1 illustrates how the unconditional-convergence region expands in the convex optimization setting, shown in terms of the ratio \alpha/\beta , which in the monotone-inclusion setting is constrained to satisfy \alpha/\beta=1 . Unlike the Douglas–Rachford case, our sufficiency analysis does not rely on the conceptually simple proximal point algorithm or nonexpansive operators. Instead, we partition the region of unconditionally convergent parameters in ( 5 ) as (\alpha,\beta,\theta)\in S^{(1)}\cup S^{(2)} , where \displaystyle S^{(1)} \displaystyle\coloneqq\left\{(\alpha,\beta,\theta)\in\mathbb{R}_{++}^{3}\mid\alpha/\beta\in(0,1],\ \theta\in(0,2\alpha/\beta)\right\}, \displaystyle S^{(2)} \displaystyle\coloneqq\left\{(\alpha,\beta,\theta)\in\mathbb{R}_{++}^{3}\mid\alpha/\beta\in[1,\infty),\ \theta\in(0,2)\right\}, and develop Lyapunov analyses for these newly identified parameter regions whose intersection \left(S^{(1)}\cap S^{(2)}=\mathbb{R}_{++}\{(1,1)\}\times(0,2)\right) represents the unconditional-convergence region for monotone inclusions established in [ 43 ] . The discovery of the Lyapunov inequalities has been assisted by the automatic Lyapunov methodologies and tools of [ 45 , 46 ] . Necessity is demonstrated using simple one-dimensional counterexamples involving the zero function and the indicator function of \{0\} . While we primarily characterize the entire class of frugal, minimal lifting, unconditionally convergent resolvent splittings with fixed-point encoding in the optimization setting, we emphasize that all our convergence guarantees for methods with \alpha/\beta\neq 1 appear to be new. Because the alternating direction method of multipliers (ADMM) [ 23 , 19 , 9 ] arises as a special case of Douglas–Rachford splitting [ 20 , 17 ] , our results yield a family of completely new convergent ADMM-type