Recently, there has been great interest in connections between continuous-time dynamical systems and optimization algorithms, notably in the context of accelerated methods for smooth and unconstrained problems. In this paper we extend this perspective to nonsmooth and constrained problems by obtaining differential inclusions associated to novel accelerated variants of the alternating direction method of multipliers (ADMM). Through a Lyapunov analysis, we derive rates of convergence for these dynamical systems in different settings that illustrate an interesting tradeoff between decaying versus constant damping strategies. We also obtain perturbed equations capturing fine-grained details of these methods, which have improved stability and preserve the leading order convergence rates.
翻译:最近,人们对连续时动态系统与优化算法之间的联系非常感兴趣,特别是在加速解决顺利和不受限制问题的方法方面。在本文件中,我们通过获得与交替方向乘数法(ADMM)新颖的加速变体相关的差异化包容,将这一视角扩大到非平稳和受限制的问题。通过Lyapunov分析,我们得出在不同环境下这些动态系统的趋同率,表明衰减与持续阻断战略之间的有趣的权衡。我们还获得了捕捉这些方法精细细节的扭曲方程式,这些公式改善了稳定性并保持了主要的顺序趋同率。