Optimization Online


Local Convergence Properties of Douglas--Rachford and ADMM

Jingwei Liang (jingwei.liang***at***ensicaen.fr)
Jalal Fadili (Jalal.Fadili***at***ensicaen.fr)
Gabriel Peyre (Gabriel.Peyre***at***ceremade.dauphine.fr)

Abstract: The Douglas--Rachford (DR) and alternating direction method of multipliers (ADMM) are two proximal splitting algorithms designed to minimize the sum of two proper lower semi-continuous convex functions whose proximity operators are easy to compute. The goal of this work is to understand the local linear convergence behaviour of DR/ADMM when the involved functions are moreover partly smooth. More precisely, when the two functions are partly smooth relative to their respective smooth submanifolds, we show that DR/ADMM (i) identifies these manifolds in finite time; (ii) enters a local linear convergence regime. When both functions are locally polyhedral, we show that the optimal convergence radius is given in terms of the cosine of the Friedrichs angle between the tangent spaces of the identified submanifolds. Under polyhedrality of both functions, we also provide condition sufficient for finite convergence of DR. The obtained results are illustrated by several concrete examples and supported by numerical experiments.

Keywords: Douglas--Rachford, ADMM, Partial Smoothness, Finite Activity Identification, Local Linear Convergence.

Category 1: Convex and Nonsmooth Optimization

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Convex and Nonsmooth Optimization (Nonsmooth Optimization )


Download: [PDF]

Entry Submitted: 06/06/2016
Entry Accepted: 06/06/2016
Entry Last Modified: 08/03/2016

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