Activity Identification and Local Linear Convergence of Douglas--Rachford/ADMM under Partial Smoothness
arXiv:1412.6858
Abstract
Convex optimization has become ubiquitous in most quantitative disciplines of science, including variational image processing. Proximal splitting algorithms are becoming popular to solve such structured convex optimization problems. Within this class of algorithms, Douglas--Rachford (DR) and alternating direction method of multipliers (ADMM) are 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 convergence behaviour of DR (resp. ADMM) when the involved functions (resp. their Legendre-Fenchel conjugates) are moreover partly smooth. More precisely, when both of the two functions (resp. their conjugates) are partly smooth relative to their respective manifolds, we show that DR (resp. ADMM) identifies these manifolds in finite time. Moreover, when these manifolds are affine or linear, we prove that DR/ADMM is locally linearly convergent. When and 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 manifolds. This is illustrated by several concrete examples and supported by numerical experiments.
arXiv comment17 pages, 1 figure, published in the proceedings of the Fifth International Conference on Scale Space and Variational Methods in Computer Vision
References in corpus (5)
- Generalized Forward-Backward Splitting
- Local Linear Convergence of Forward-Backward under Partial Smoothness
- Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions
- Optimal rates of convergence of matrices with applications
- Linear Convergence of the Douglas-Rachford Method for Two Closed Sets