GRAPH AND DISTRIBUTED EXTENSIONS OF THE DOUGLAS RACHFORD METHOD.

In this paper, we propose several graph-based extensions of the Douglas-Rachford splitting (DRS) method to solve monotone inclusion problems involving the sum of N maximal monotone operators. Our construction is based on the choice of two nested graphs, to which we associate a generalization of the DRS algorithm that presents a prescribed structure. The resulting schemes can be understood as unconditionally stable frugal resolvent splitting methods with minimal lifting in the sense of Ryu [Math. Program., 182 (2020), pp. 233-273] as well as instances of the (degenerate) preconditioned proximal point method, which provides robust convergence guarantees. We further describe how the graph-based extensions of the DRS method can be leveraged to design new fully distributed protocols. Applications to a congested optimal transport problem and to distributed support vector machines show interesting connections with the underlying graph topology and highly competitive performances with state-of-the-art distributed optimization approaches. [ABSTRACT FROM AUTHOR]