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

Damek Davis () and Wotao Yin ()
Additional contact information
Damek Davis: School of Operations Research and Information Engineering, Cornell University, Ithaca, NY
Wotao Yin: Department of Mathematics, University of California, Los Angeles, California

Mathematics of Operations Research, 2017, vol. 42, issue 3, 783-805

Abstract: 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.

Keywords: Peaceman-Rachford; Douglas-Rachford; Alternating Direction Method of Multipliers (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
https://doi.org/10.1287/moor.2016.0827 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:42:y:2017:i:3:p:783-805

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().