Advanced

Tight linear convergence rate bounds for Douglas-Rachford splitting and ADMM

Giselsson, Pontus LU (2016) 54th IEEE Conference on Decision and Control, CDC 2015 In Proceedings of the IEEE Conference on Decision and Control 2016. p.3305-3310
Abstract

Douglas-Rachford splitting and the alternating direction method of multipliers (ADMM) can be used to solve convex optimization problems that consist of a sum of two functions. Convergence rate estimates for these algorithms have received much attention lately. In particular, linear convergence rates have been shown by several authors under various assumptions. One such set of assumptions is strong convexity and smoothness of one of the functions in the minimization problem. The authors recently provided a linear convergence rate bound for such problems. In this paper, we show that this rate bound is tight for the class of problems under consideration.

Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Proceedings of the IEEE Conference on Decision and Control
volume
2016
pages
6 pages
publisher
Institute of Electrical and Electronics Engineers Inc.
conference name
54th IEEE Conference on Decision and Control, CDC 2015
external identifiers
  • Scopus:84962013862
ISBN
9781479978861
DOI
10.1109/CDC.2015.7402716
language
English
LU publication?
yes
id
9e273773-ace9-4bbf-a306-1d8949a559f2
date added to LUP
2016-06-23 12:38:30
date last changed
2016-10-04 15:18:58
@misc{9e273773-ace9-4bbf-a306-1d8949a559f2,
  abstract     = {<p>Douglas-Rachford splitting and the alternating direction method of multipliers (ADMM) can be used to solve convex optimization problems that consist of a sum of two functions. Convergence rate estimates for these algorithms have received much attention lately. In particular, linear convergence rates have been shown by several authors under various assumptions. One such set of assumptions is strong convexity and smoothness of one of the functions in the minimization problem. The authors recently provided a linear convergence rate bound for such problems. In this paper, we show that this rate bound is tight for the class of problems under consideration.</p>},
  author       = {Giselsson, Pontus},
  isbn         = {9781479978861},
  language     = {eng},
  month        = {02},
  pages        = {3305--3310},
  publisher    = {ARRAY(0x926d838)},
  series       = {Proceedings of the IEEE Conference on Decision and Control},
  title        = {Tight linear convergence rate bounds for Douglas-Rachford splitting and ADMM},
  url          = {http://dx.doi.org/10.1109/CDC.2015.7402716},
  volume       = {2016},
  year         = {2016},
}