Advanced

Tight global linear convergence rate bounds for Douglas–Rachford splitting

Giselsson, Pontus LU (2017) In Journal of Fixed Point Theory and Applications
Abstract

Recently, several authors have shown local and global convergence rate results for Douglas–Rachford splitting under strong monotonicity, Lipschitz continuity, and cocoercivity assumptions. Most of these focus on the convex optimization setting. In the more general monotone inclusion setting, Lions and Mercier showed a linear convergence rate bound under the assumption that one of the two operators is strongly monotone and Lipschitz continuous. We show that this bound is not tight, meaning that no problem from the considered class converges exactly with that rate. In this paper, we present tight global linear convergence rate bounds for that class of problems. We also provide tight linear convergence rate bounds under the assumptions... (More)

Recently, several authors have shown local and global convergence rate results for Douglas–Rachford splitting under strong monotonicity, Lipschitz continuity, and cocoercivity assumptions. Most of these focus on the convex optimization setting. In the more general monotone inclusion setting, Lions and Mercier showed a linear convergence rate bound under the assumption that one of the two operators is strongly monotone and Lipschitz continuous. We show that this bound is not tight, meaning that no problem from the considered class converges exactly with that rate. In this paper, we present tight global linear convergence rate bounds for that class of problems. We also provide tight linear convergence rate bounds under the assumptions that one of the operators is strongly monotone and cocoercive, and that one of the operators is strongly monotone and the other is cocoercive. All our linear convergence results are obtained by proving the stronger property that the Douglas–Rachford operator is contractive.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
epub
subject
keywords
Douglas–Rachford splitting, Fixed-point iterations, Linear convergence, Monotone operators
in
Journal of Fixed Point Theory and Applications
pages
30 pages
publisher
Springer Science + Business Media
external identifiers
  • scopus:85015059438
ISSN
1661-7738
DOI
10.1007/s11784-017-0417-1
language
English
LU publication?
yes
id
b9459797-a905-4368-8076-95ea4a2edc47
date added to LUP
2017-03-23 08:40:26
date last changed
2017-03-23 08:40:26
@article{b9459797-a905-4368-8076-95ea4a2edc47,
  abstract     = {<p>Recently, several authors have shown local and global convergence rate results for Douglas–Rachford splitting under strong monotonicity, Lipschitz continuity, and cocoercivity assumptions. Most of these focus on the convex optimization setting. In the more general monotone inclusion setting, Lions and Mercier showed a linear convergence rate bound under the assumption that one of the two operators is strongly monotone and Lipschitz continuous. We show that this bound is not tight, meaning that no problem from the considered class converges exactly with that rate. In this paper, we present tight global linear convergence rate bounds for that class of problems. We also provide tight linear convergence rate bounds under the assumptions that one of the operators is strongly monotone and cocoercive, and that one of the operators is strongly monotone and the other is cocoercive. All our linear convergence results are obtained by proving the stronger property that the Douglas–Rachford operator is contractive.</p>},
  author       = {Giselsson, Pontus},
  issn         = {1661-7738},
  keyword      = {Douglas–Rachford splitting,Fixed-point iterations,Linear convergence,Monotone operators},
  language     = {eng},
  month        = {03},
  pages        = {30},
  publisher    = {Springer Science + Business Media},
  series       = {Journal of Fixed Point Theory and Applications},
  title        = {Tight global linear convergence rate bounds for Douglas–Rachford splitting},
  url          = {http://dx.doi.org/10.1007/s11784-017-0417-1},
  year         = {2017},
}