Optimization Online


Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions

Damek Davis (damek***at***math.ucla.edu)
Wotao Yin (wotaoyin***at***math.ucla.edu)

Abstract: Splitting schemes are a class of powerful algorithms that solve complicated monotone inclusion and convex optimization problems that are built from many simpler pieces. They give rise to algorithms in which the simple pieces of the decomposition are processed individually. This leads to easily implementable and highly parallelizable algorithms, which often obtain nearly state-of-the-art performance. 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: Douglas-Rachford Splitting, Peaceman-Rachford Splitting, Alternating Direction Method of Multipliers, nonexpansive operator, averaged operator, fixed-point algorithm

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: UCLA CAM report 14-58, July 2014

Download: [PDF]

Entry Submitted: 07/19/2014
Entry Accepted: 07/19/2014
Entry Last Modified: 04/30/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society