Advanced

Linear Convergence and Metric Selection for Douglas-Rachford Splitting and ADMM

Giselsson, Pontus LU and Boyd, Stephen (2017) In IEEE Transactions on Automatic Control 62(2). p.532-544
Abstract

Recently, several convergence rate results for Douglas-Rachford splitting and the alternating direction method of multipliers (ADMM) have been presented in the literature. In this paper, we show global linear convergence rate bounds for Douglas-Rachford splitting and ADMM under strong convexity and smoothness assumptions. We further show that the rate bounds are tight for the class of problems under consideration for all feasible algorithm parameters. For problems that satisfy the assumptions, we show how to select step-size and metric for the algorithm that optimize the derived convergence rate bounds. For problems with a similar structure that do not satisfy the assumptions, we present heuristic step-size and metric selection... (More)

Recently, several convergence rate results for Douglas-Rachford splitting and the alternating direction method of multipliers (ADMM) have been presented in the literature. In this paper, we show global linear convergence rate bounds for Douglas-Rachford splitting and ADMM under strong convexity and smoothness assumptions. We further show that the rate bounds are tight for the class of problems under consideration for all feasible algorithm parameters. For problems that satisfy the assumptions, we show how to select step-size and metric for the algorithm that optimize the derived convergence rate bounds. For problems with a similar structure that do not satisfy the assumptions, we present heuristic step-size and metric selection methods.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Alternating direction method of multipliers (ADMM), Douglas-Rachford splitting, linear convergence, optimization algorithms
in
IEEE Transactions on Automatic Control
volume
62
issue
2
pages
13 pages
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • scopus:85011591304
  • wos:000395510600002
ISSN
0018-9286
DOI
10.1109/TAC.2016.2564160
language
English
LU publication?
yes
id
8c6c0231-0b4e-4166-acd5-98d81f36ec74
date added to LUP
2017-02-15 12:47:36
date last changed
2018-10-07 04:52:55
@article{8c6c0231-0b4e-4166-acd5-98d81f36ec74,
  abstract     = {<p>Recently, several convergence rate results for Douglas-Rachford splitting and the alternating direction method of multipliers (ADMM) have been presented in the literature. In this paper, we show global linear convergence rate bounds for Douglas-Rachford splitting and ADMM under strong convexity and smoothness assumptions. We further show that the rate bounds are tight for the class of problems under consideration for all feasible algorithm parameters. For problems that satisfy the assumptions, we show how to select step-size and metric for the algorithm that optimize the derived convergence rate bounds. For problems with a similar structure that do not satisfy the assumptions, we present heuristic step-size and metric selection methods.</p>},
  articleno    = {7465685},
  author       = {Giselsson, Pontus and Boyd, Stephen},
  issn         = {0018-9286},
  keyword      = {Alternating direction method of multipliers (ADMM),Douglas-Rachford splitting,linear convergence,optimization algorithms},
  language     = {eng},
  month        = {02},
  number       = {2},
  pages        = {532--544},
  publisher    = {IEEE--Institute of Electrical and Electronics Engineers Inc.},
  series       = {IEEE Transactions on Automatic Control},
  title        = {Linear Convergence and Metric Selection for Douglas-Rachford Splitting and ADMM},
  url          = {http://dx.doi.org/10.1109/TAC.2016.2564160},
  volume       = {62},
  year         = {2017},
}