Graph and Distributed Extensions of the Douglas–Rachford Method
Kristian Bredies, Enis Chenchene, Emanuele Naldi · SIAM Journal on Optimization · 2024
Abstract. 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 [Formula: see text] 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.