Paper Info
Title
Local Convergence Properties of Douglas-Rachford and Alternating Direction Method of Multipliers.
Abstract
The Douglas---Rachford and alternating direction method of multipliers 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 Douglas---Rachford (resp. alternating direction method of multipliers) when the involved functions (resp. their Legendre---Fenchel conjugates) are moreover partly smooth. More precisely, when the two functions (resp. their conjugates) are partly smooth relative to their respective smooth submanifolds, we show that Douglas---Rachford (resp. alternating direction method of multipliers) (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 conditions sufficient for finite convergence. The obtained results are illustrated by several concrete examples and supported by numerical experiments.
Year
DOI
Venue
2017
10.1007/s10957-017-1061-z
J. Optimization Theory and Applications
Keywords
Field
DocType
Douglas–Rachford, ADMM, Partial smoothness, Finite activity identification, Local linear convergence, 49J52, 65K05, 65K10, 90C25
Convergence (routing),Mathematical optimization,Trigonometric functions,Mathematical analysis,Convex function,Operator (computer programming),Rate of convergence,Local convergence,Mathematics,Manifold,Tangent space
Journal
Volume
Issue
ISSN
172
3
1573-2878
Citations 
PageRank 
References 
3
0.40
18
Authors
3
Name
Order
Citations
PageRank
Jingwei Liang1527.41
Jalal Fadili2118480.08
Gabriel Peyré3119579.60