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

Pontus Giselsson

doi:10.1109/CDC.2015.7402716

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

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding › peer-review

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.

Original language	English
Title of host publication	Proceedings of the IEEE Conference on Decision and Control
Publisher	IEEE - Institute of Electrical and Electronics Engineers Inc.
Pages	3305-3310
Number of pages	6
Volume	2016
ISBN (Print)	9781479978861
DOIs	https://doi.org/10.1109/CDC.2015.7402716
Publication status	Published - 2016 Feb 8
Event	54th IEEE Conference on Decision and Control, CDC 2015 - Osaka, Japan Duration: 2015 Dec 15 → 2015 Dec 18 Conference number: 54

Conference

Conference	54th IEEE Conference on Decision and Control, CDC 2015
Abbreviated title	CDC 2015
Country/Territory	Japan
City	Osaka
Period	2015/12/15 → 2015/12/18

Subject classification (UKÄ)

Mathematics

Access to Document

10.1109/CDC.2015.7402716

Cite this

@inproceedings{9e273773ace94bbfa3061d8949a559f2,

title = "Tight linear convergence rate bounds for Douglas-Rachford splitting and ADMM",

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.",

author = "Pontus Giselsson",

year = "2016",

month = feb,

day = "8",

doi = "10.1109/CDC.2015.7402716",

language = "English",

isbn = "9781479978861",

volume = "2016",

pages = "3305--3310",

booktitle = "Proceedings of the IEEE Conference on Decision and Control",

publisher = "IEEE - Institute of Electrical and Electronics Engineers Inc.",

address = "United States",

note = "54th IEEE Conference on Decision and Control, CDC 2015, CDC 2015 ; Conference date: 15-12-2015 Through 18-12-2015",

}

Giselsson, P 2016, Tight linear convergence rate bounds for Douglas-Rachford splitting and ADMM. in Proceedings of the IEEE Conference on Decision and Control. vol. 2016, 7402716, IEEE - Institute of Electrical and Electronics Engineers Inc., pp. 3305-3310, 54th IEEE Conference on Decision and Control, CDC 2015, Osaka, Japan, 2015/12/15. https://doi.org/10.1109/CDC.2015.7402716

Tight linear convergence rate bounds for Douglas-Rachford splitting and ADMM. / Giselsson, Pontus.
Proceedings of the IEEE Conference on Decision and Control. Vol. 2016 IEEE - Institute of Electrical and Electronics Engineers Inc., 2016. p. 3305-3310 7402716.

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding › peer-review

TY - GEN

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

AU - Giselsson, Pontus

N1 - Conference code: 54

PY - 2016/2/8

Y1 - 2016/2/8

N2 - 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.

AB - 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.

U2 - 10.1109/CDC.2015.7402716

DO - 10.1109/CDC.2015.7402716

M3 - Paper in conference proceeding

AN - SCOPUS:84962013862

SN - 9781479978861

VL - 2016

SP - 3305

EP - 3310

BT - Proceedings of the IEEE Conference on Decision and Control

PB - IEEE - Institute of Electrical and Electronics Engineers Inc.

T2 - 54th IEEE Conference on Decision and Control, CDC 2015

Y2 - 15 December 2015 through 18 December 2015

ER -

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

Abstract

Conference

Subject classification (UKÄ)

Access to Document

Fingerprint

Cite this