Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions

• 成果类型: Article
• 署名作者: Davis, Damek; Yin, Wotao
• 署名单位: Cornell University; University of California System; University of California Los Angeles
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2016.0827
• 发表日期: 2017
• 页码: 783-805
• 关键词: linear convergence; sets; algorithm; convex; projections

摘要

In this paper, we provide a comprehensive convergence rate analysis of the Douglas-Rachford splitting (DRS), Peaceman-Rachford splitting (PRS), and alternating direction method of multipliers (ADMM) algorithms under various regularity assumptions including strong convexity, Lipschitz differentiability, and bounded linear regularity. The main consequence of this work is that relaxed PRS and ADMM automatically adapt to the regularity of the problem and achieve convergence rates that improve upon the (tight) worst-case rates that hold in the absence of such regularity. All of the results are obtained using simple techniques.