论文标题
Douglas-Rachford方法的图形和分布式扩展
Graph and distributed extensions of the Douglas-Rachford method
论文作者
论文摘要
在本文中，我们提出了几种基于图的道格拉斯 - 拉赫福德分裂方法（DRS）方法的扩展，以解决涉及$ n $最大单调运算符的总和的单调包含问题。我们的构造基于我们称为双层图的两层体系结构，我们将其与呈现规定结构的DRS算法的概括相关联。可以将结果的方案理解为无条件稳定的节俭的分解方法，从RYU [数学计划182（1）：233-273，2020]的意义上的提升最少，以及（退化）预先预先近似点方法，可提供强大的融合者保证。我们进一步描述了如何利用基于图的DRS方法的扩展来设计新的完全分布的协议。在拥挤的最佳运输问题和分布式支持向量机器的应用中，与基本的图形拓扑和高度竞争性的表演有关最先进的分布式优化方法，显示出有趣的连接。
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 a two-layer architecture that we refer to as bilevel graphs, to which we associate a generalization of the DRS algorithm that presents the prescribed structure. The resulting schemes can be understood as unconditionally stable frugal resolvent splitting methods with a minimal lifting in the sense of Ryu [Math Program 182(1):233-273, 2020], 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.
