论文标题
基于道格拉斯·拉赫福德（Douglas-Rachford）分裂的非凸ADMM的安德森加速度
Anderson Acceleration for Nonconvex ADMM Based on Douglas-Rachford Splitting
论文作者
论文摘要
交替的方向乘数方法（ADMM）被广泛用于计算机图形中，以解决可能是非平滑室和非convex的优化问题。它迅速收敛到近似解决方案，但可能需要很长时间才能收敛到高临界性解决方案。以前，通过将Anderson加速度应用于ADMM，将其视为双重变量串联和原始变量子集的固定点迭代。在本文中，我们注意到，ADMM和Douglas-Rachford分裂之间的等效性表明，ADMM实际上是较低维空间中的定点迭代。通过将安德森加速度应用于这种较低的定点迭代，我们获得了一种更有效的加速ADMM方法。我们分析了提出的加速方法在非凸问题上的收敛性，并验证其对各种计算机图形问题的有效性，包括几何处理和物理模拟。
The alternating direction multiplier method (ADMM) is widely used in computer graphics for solving optimization problems that can be nonsmooth and nonconvex. It converges quickly to an approximate solution, but can take a long time to converge to a solution of high-accuracy. Previously, Anderson acceleration has been applied to ADMM, by treating it as a fixed-point iteration for the concatenation of the dual variables and a subset of the primal variables. In this paper, we note that the equivalence between ADMM and Douglas-Rachford splitting reveals that ADMM is in fact a fixed-point iteration in a lower-dimensional space. By applying Anderson acceleration to such lower-dimensional fixed-point iteration, we obtain a more effective approach for accelerating ADMM. We analyze the convergence of the proposed acceleration method on nonconvex problems, and verify its effectiveness on a variety of computer graphics problems including geometry processing and physical simulation.
