Douglas–Rachford for multioperator comonotone inclusions with applications to multiblock optimization

Jan Harold Alcantara Minh N. Dao Akiko Takeda · 2025

Read Douglas–Rachford for multioperator comonotone inclusions with applications to multiblock optimization by Jan Harold Alcantara Minh N. Dao Akiko Takeda (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-2506-22928.txt.

Introduction

Jan Harold Alcantara and co-authors studied a splitting method for hard maths problems in a 2025 paper. Their problem joins several operators that may not behave in the usual smooth way. Such problems sit behind many tasks with several blocks of variables.

The team used a product space form to handle the awkward cases, then proved the relaxed method settles under stated limits. Their proof works through a paired dual problem. As a use case, they built a multi-block method for both smooth and rough optimisation tasks. Proof of settling covers the fully smooth case and a mixed strong and weak case.

Catalog record

CREATORJan Harold Alcantara Minh N. Dao Akiko Takeda
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE112 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-22928

Browse the full library · About the Tower of Babel

Full text

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

Douglas–Rachford for multioperator comonotone inclusions with applications to multiblock optimization Jan Harold Alcantara Minh N. Dao Akiko Takeda Abstract We study the convergence of the adaptive Douglas–Rachford (aDR) algorithm for solving a multioperator inclusion problem involving the sum of maximally comonotone operators. To address such problems, we adopt a product space reformulation that accommodates nonconvex-valued operators, which is essential when dealing with comonotone mappings. We establish convergence of the aDR method under comonotonicity assumptions, subject to suitable conditions on the algorithm parameters and comonotonicity moduli of the operators. Our analysis leverages the Attouch–Théra duality framework, which allows us to study the convergence of the aDR algorithm via its application to the dual inclusion problem. As an application, we derive a multiblock ADMM-type algorithm for structured convex and nonconvex optimization problems by applying the aDR algorithm to the operator inclusion formulation of the KKT system. The resulting method extends to multiblock and nonconvex settings the classical duality between the Douglas–Rachford algorithm and the alternating direction method of multipliers in the convex two-block case. Moreover, we establish convergence guarantees for both the fully convex and strongly convex-weakly convex regimes. Keywords. adaptive Douglas–Rachford; multioperator inclusion; comonotone operator; product space reformulation; Attouch–Théra dual; multiblock optimization; ADMM 1 Introduction Consider the multioperator inclusion problem \text{Find~}x\in\mathcal{H}~\text{such that }0\in A_{1}(x)+A_{2}(x)+\cdots+A_{m}(x) (1.1) where A_{1},A_{2},\dots,A_{m}:\mathcal{H}\rightrightarrows\mathcal{H} are set-valued operators on a real Hilbert space \mathcal{H} . In this paper, we study the convergence of the Douglas–Rachford algorithm based on the product space reformulation proposed in [ 1 ] for solving ( 1.1 ) when the operators A_{1},A_{2},\dots,A_{m} are maximal comonotone (see Definition 2.2 ). 1.1 Motivation The Douglas–Rachford algorithm for comonotone operators is of particular interest because such operators naturally arise in the convergence analysis of the alternating direction method of multipliers (ADMM) for linearly constrained multiblock problems of the form \min_{u_{i}\in\mathcal{H}_{i}}\,f_{1}(u_{1})+\cdots+f_{m}(u_{m})\quad\text{s.t.}\quad\sum_{i=1}^{m}L_{i}u_{i}=b, (1.2) where b\in\mathcal{H} , each f_{i}:\mathcal{H}_{i}\to(-\infty,+\infty] is a proper closed function, and L_{i}:\mathcal{H}_{i}\to\mathcal{H} is a bounded linear operator. This connection becomes especially relevant when the functions f_{i} exhibit a mix of strong and weak convexity, as will be elaborated in detail in Section 5 . This correspondence was observed by Bartz, Campoy, and Phan [ 4 ] in the two-block case: \min_{u_{i}\in\mathcal{H}_{i}}\,f_{1}(u_{1})+f_{2}(u_{2})\quad\text{s.t.}\quad L_{1}u_{1}-u_{2}=0, (1.3) where f_{1} is strongly convex and f_{2} is weakly convex. Under suitable assumptions, critical points of the Lagrangian associated with ( 1.3 ) are indeed solutions of the original problem and correspond to solutions of the inclusion problem [ 4 , Lemma 4.3 and Proposition 4.1] \text{Find }x\in\mathcal{H}\text{ such that }0\in A_{1}(x)+A_{2}(x), (1.4) where the operators A_{1} and A_{2} are defined by A_{1}\coloneqq-L_{1}\circ(\partial f_{1})^{-1}\circ(-L_{1}^{\top}),\quad A_{2}\coloneqq(\widehat{\partial}f_{2})^{-1}, (1.5) with the subdifferential and inverse mappings defined as in Section 2.1 . It is shown in [ 4 , Lemmas 4.6 and 4.7] that A_{1} and A_{2} are strongly and weakly comonotone, respectively. Moreover, the Douglas–Rachford (DR) algorithm applied to the inclusion ( 1.4 ) with operators A_{1} and A_{2} defined in ( 1.5 ) is equivalent to the ADMM iteration for ( 1.3 ) under suitable conditions [ 4 , Lemmas 4.6 and 4.8] . Leveraging this equivalence, the convergence of ADMM for ( 1.3 ) with strongly convex f_{1} and weakly convex f_{2} was established via the DR framework, using the properties of strongly and weakly comonotone operators A_{1} and A_{2} . This extends the classical duality between ADMM and DR in fully convex settings [ 15 ] to broader problems involving both strongly and weakly convex functions. However, extending this framework to the multiblock setting remains an open question, as the Douglas–Rachford algorithm for multioperator inclusion problems involving comonotone operators is itself not yet explored. 1.2 Two-operator reformulations A standard strategy for addressing ( 1.1 ) involves reformulating it as a two-operator inclusion over a lifted space. A traditional two-operator reformulation is the Pierra’s product space reformulation [ 20 , 21 ] : \text{Find}~\mathbf{x}\in\mathcal{H}^{m}~\text{such that }0\in\mathbf{F}_{\rm Pierra}(\mathbf{x})+\mathbf{G}_{\rm Pierra}(\mathbf{x}), (1.6) where \mathbf{x}=(x_{1},\dots,x_{m})\in\mathcal{H}^{m} , \mathbf{F}_{\rm Pierra}(\mathbf{x})\coloneqq A_{1}(x_{1})\times\cdots\times A_{m}(x_{m}) and \mathbf{G}_{\rm Pierra}\coloneqq N_{\mathbf{D}_{m}} , the normal cone 1 1 1 That is, N_{\mathbf{D}_{m}}(\mathbf{x})=\mathbf{D}_{m}^{\perp}=\{\mathbf{w}=(w_{1},\dots,w_{m})\in\mathcal{H}^{m}:\sum_{i=1}^{m}w_{i}=0\} for \mathbf{x}\in\mathbf{D}_{m} and N_{\mathbf{D}_{m}}(\mathbf{x})=\emptyset if \mathbf{x}\notin\mathbf{D}_{m} . operator to \mathbf{D}_{m}\coloneqq\{(x_{1},\dots,x_{m})\in\mathcal{H}^{m}:x_{1}=\cdots=x_{m}\} . However, in this reformulation, the second operator \mathbf{G}_{\rm Pierra} is fixed as a maximal monotone operator. As a result, any nonmonotonicity present in the original operators A_{1},\dots,A_{m} is entirely absorbed into the first operator \mathbf{F}_{\rm Pierra} , which may be undesirable for convergence analysis. To the best of our knowledge, there are currently no results on applying the Douglas–Rachford algorithm to ( 1.6 ) in the nonmonotone setting. Based on [ 17 ] , another product space reformulation was proposed by [ 9 ] : \text{Find}~\mathbf{x}\in\mathcal{H}^{m-1}~\text{such that }0\in\mathbf{F}_{\rm Campoy}(\mathbf{x})+\mathbf{G}_{\rm Campoy}(\mathbf{x}), (1.7) where \displaystyle\mathbf{F}_{\rm Campoy}(\mathbf{x}) \displaystyle\coloneqq A_{1}(x_{1})\times\cdots\times A_{m-1}(x_{m-1}), \displaystyle\mathbf{G}_{\rm Campoy}(\mathbf{x}) \displaystyle\coloneqq\frac{1}{m-1}A_{m}(x_{1})\times\cdots\times\frac{1}{m-1}A_{m}(x_{m-1})+N_{\mathbf{D}_{m-1}}(\mathbf{x}). This reformulation reduces the ambient space dimension by one compared to ( 1.6 ), which could be more desirable in practice [ 18 ] . Moreover, since A_{m} is embedded in the second operator, the reformulation permits some nonmonotonicity in the second operator \mathbf{G}_{\rm Campoy} , in contrast to the formulation in ( 1.6 ). However, as noted in [ 1 ] , this reformulation is not suitable when the operator A_{m} is not convex-valued. This last point is quite important and relevant, since weakly comonotone operators are not necessarily convex-valued in general; see Example 2.7 . 1.3 Our approach and contributions In this work, we use the product space reformulation proposed in [ 1 ] , which introduces a slight but crucial modification of Campoy’s formulation ( 1.7 ) to accommodate nonconvex-valued operators, such as comonotone ones. In particular, the flexible reformulation is given by \text{Find}~\mathbf{x}\in\mathcal{H}^{m-1}~\text{such that }0\in\mathbf{F}(\mathbf{x})+\mathbf{G}(\mathbf{x}), (1.8) where \displaystyle\mathbf{F}(\mathbf{x}) \displaystyle\coloneqq\mathbf{F}_{\rm Campoy}(\mathbf{x})=A_{1}(x_{1})\times\cdots\times A_{m-1}(x_{m-1}), (1.9) \displaystyle\mathbf{G}(\mathbf{x}) \displaystyle\coloneqq\mathbf{K}(\mathbf{x})+N_{\mathbf{D}_{m-1}}(\mathbf{x}), (1.10) with \mathbf{K}(\mathbf{x})\coloneqq\begin{cases}\{\frac{1}{m-1}(v,\ldots,v):v\in A_{m}(x_{1})\}&\text{if}~\mathbf{x}=(x_{1},\dots,x_{m-1})\in\mathbf{D}_{m-1}\\ \emptyset&\text{otherwise}.\end{cases} Indeed, 0\in\mathbf{F}(\mathbf{x})+\mathbf{G}(\mathbf{x})\quad\Longleftrightarrow\quad\exists x\in\mathcal{H}~\text{s.t.}~\mathbf{x}=(x,\dots,x)~\text{and}~0\in A_{1}(x)+\cdots+A_{m}(x). (1.11) With this product space reformulation, we are able to apply the adaptive Douglas–Rachford (aDR) algorithm for two-operator inclusion problems proposed in [ 13 ] to the reformulated problem ( 1.8 ). The resulting algorithm is detailed in Algorithm 1 in Section 4 . Our main contributions are twofold: 1. We establish the convergence of the adaptive Douglas–Rachford algorithm for multioperator inclusion problems where each A_{i} is maximally \sigma_{i} -comonotone, with \sigma_{i}\geq 0 for i=1,\dots,m{-}1 and \sigma_{m}\leq 0 . Convergence is guaranteed under suitable assumptions on the monotonicity moduli and algorithm parameters; see Theorem 4.12 . Our analysis relies on the Attouch–Théra duality framework [ 2 ] , which facilitates the analysis of the aDR algorithm on the dual inclusion problem. As a by-product, our results resolve (in the negative) an open question posed in [ 3 , Remark 4.2] regarding the strong convergence of the shadow sequence in the case m=2 and \sigma_{1}+\sigma_{2}>0 . We also improve the result in [ 3 , Theorem 4.2] by establishing the weak convergence of the shadow sequence under less restrictive assumptions. 2. We derive a multiblock ADMM algorithm with convergence guarantees for solving problem ( 1.2 ). (a) This result generalizes to the multiblock case the well-known duality between the Douglas–Rachford and ADMM algorithms for two-block problems in the convex setting, as well as its extension to the strongly convex-weakly convex setting in [ 4 ] . Notably, the derived multiblock ADMM algorithm preserves this duality structure even when the involved functions are not convex. In particular, the algorithm

Read the complete text