Local Convergence Properties of Douglas--Rachford and ADMM
arXiv:1606.02116
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.
This paper is the generalization of our previous work, the SSVM conference proceeding and the arxiv preprint arXiv:1412.6858, with more far-reaching result, e.g. the convergence rate result is established for the general manifolds other than just affine subspaces of the previous work
References in corpus (4)
- Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions
- On Slater's condition and finite convergence of the Douglas-Rachford algorithm
- Activity Identification and Local Linear Convergence of Forward--Backward-type methods
- On the order of the operators in the Douglas-Rachford algorithm