|Start Page Number:||783|
|End Page Number:||805|
|Publication Date:||Aug 2017|
|Journal:||Mathematics of Operations Research|
|Authors:||Davis Damek, Yin Wotao|
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.