论文标题
在Anderson加速度的渐近线性收敛速度上
On the Asymptotic Linear Convergence Speed of Anderson Acceleration Applied to ADMM
论文作者
论文摘要
经验结果表明，安德森加速度（AA）可以是提高乘数乘数（admm）的渐近线性收敛速度（ADMM）的强大机制。但是，量化此改进的理论结果尚不存在。在本文中，我们解释并量化了对ADM的固定版本的特殊情况的线性渐近收敛速度的改善。我们这样做是通过考虑ADMM雅各布人的光谱特性以及在固定点评估的AA的固定版本，其中计算了固定AA方法的系数，以使其渐近线性收敛因子是最佳的。该固定AA-ADMM方法的最佳线性收敛因子是根据先前在最佳固定AA加速度上的工作来分析或通过优化计算的。使用这些光谱图和这些分析结果，我们的方法为固定AA方法的方式和数量提供了新的见解，可以改善ADMM的渐近线性收敛因子。数值结果还表明，固定AA方法的最佳线性收敛因子为实践中使用的非平稳AA方法的渐近线性收敛速度提供了有用的估计值。
Empirical results show that Anderson acceleration (AA) can be a powerful mechanism to improve the asymptotic linear convergence speed of the Alternating Direction Method of Multipliers (ADMM) when ADMM by itself converges linearly. However, theoretical results to quantify this improvement do not exist yet. In this paper we explain and quantify this improvement in linear asymptotic convergence speed for the special case of a stationary version of AA applied to ADMM. We do so by considering the spectral properties of the Jacobians of ADMM and the stationary version of AA evaluated at the fixed point, where the coefficients of the stationary AA method are computed such that its asymptotic linear convergence factor is optimal. The optimal linear convergence factors of this stationary AA-ADMM method are computed analytically or by optimization, based on previous work on optimal stationary AA acceleration. Using this spectral picture and those analytical results, our approach provides new insight into how and by how much the stationary AA method can improve the asymptotic linear convergence factor of ADMM. Numerical results also indicate that the optimal linear convergence factor of the stationary AA methods gives a useful estimate for the asymptotic linear convergence speed of the non-stationary AA method that is used in practice.
