Optimization Online


Activity Identification and Local Linear Convergence of Douglas-Rachford/ADMM under Partial Smoothness

Jingwei Liang (jingwei.liang***at***ensicaen.fr)
Jalal Fadili (Jalal.Fadili***at***ensicaen.fr)
Gabriel Peyré (Gabriel.Peyre***at***ceremade.dauphine.fr)
Russell Luke (r.luke***at***math.uni-goettingen.de)

Abstract: Proximal splitting algorithms are becoming popular to solve convex optimization problems in variational image processing. Within this class, Douglas-Rachford (DR) and ADMM are designed to minimize the sum of two proper lower semicontinuous convex functions whose proximity operators are easy to compute. The goal of this work is to understand the local convergence behaviour of DR/ADMM when the involved functions are moreover partly smooth. More precisely, when one of the functions and the conjugate of the other are partly smooth relative to their respective manifolds, we show that DR/ADMM identifies these manifolds in finite time. Moreover, when these manifolds are affine or linear, we prove that DR is locally linearly convergent with a rate in terms of the cosine of the Friedrichs angle between the two tangent subspaces. This is illustrated by several concrete examples and supported by numerical experiments.

Keywords: Douglas-Rachford splitting, 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: 12/21/2014
Entry Accepted: 12/22/2014
Entry Last Modified: 03/03/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