论文标题
线性系统的随机道格拉斯 - 拉赫福德方法：提高精度和效率
Randomized Douglas-Rachford methods for linear systems: Improved accuracy and efficiency
论文作者
论文摘要
道格拉斯 - 拉赫福德（DR）方法是一种广泛使用的方法，用于在两个封闭凸集的交点（可行性问题）中找到一个点。但是，该方法的收敛弱且相关的收敛速率通常很难分析。此外，DR方法的直接扩展是解决比两人组的可行性问题（称为$ r $ -sets-dr方法）的直接扩展，这不一定是收敛的。为了提高优化算法的效率，随机化和动量技术的引入引起了人们越来越多的关注。在本文中，我们提出了随机$ r $ -Sets-DR（RRDR）方法来求解从线性系统得出的可行性问题，显示了随机化的好处，因为它带来了线性收敛的期望，可以与其他不同的$ r $ r $ -sets-sets-dr方法。此外，收敛速率不取决于系数矩阵的尺寸。我们还以沉重的球动量研究RRDR，并建立其加速速率。提供数值实验来确认我们的结果，并证明由随机化和动量技术带来的DR方法的准确性和效率显着提高。
The Douglas-Rachford (DR) method is a widely used method for finding a point in the intersection of two closed convex sets (feasibility problem). However, the method converges weakly and the associated rate of convergence is hard to analyze in general. In addition, the direct extension of the DR method for solving more-than-two-sets feasibility problems, called the $r$-sets-DR method, is not necessarily convergent. To improve the efficiency of the optimization algorithms, the introduction of randomization and the momentum technique has attracted increasing attention. In this paper, we propose the randomized $r$-sets-DR (RrDR) method for solving the feasibility problem derived from linear systems, showing the benefit of the randomization as it brings linear convergence in expectation to the otherwise divergent $r$-sets-DR method. Furthermore, the convergence rate does not depend on the dimension of the coefficient matrix. We also study RrDR with heavy ball momentum and establish its accelerated rate. Numerical experiments are provided to confirm our results and demonstrate the notable improvements in accuracy and efficiency of the DR method, brought by the randomization and the momentum technique.
