A convergent relaxation of the Douglas–Rachford algorithm

Research output: Contribution to journalArticleScientificpeer-review

3 Citations (Scopus)
21 Downloads (Pure)

Abstract

This paper proposes an algorithm for solving structured optimization problems, which covers both the backward–backward and the Douglas–Rachford algorithms as special cases, and analyzes its convergence. The set of fixed points of the corresponding operator is characterized in several cases. Convergence criteria of the algorithm in terms of general fixed point iterations are established. When applied to nonconvex feasibility including potentially inconsistent problems, we prove local linear convergence results under mild assumptions on regularity of individual sets and of the collection of sets. In this special case, we refine known linear convergence criteria for the Douglas–Rachford (DR) algorithm. As a consequence, for feasibility problem with one of the sets being affine, we establish criteria for linear and sublinear convergence of convex combinations of the alternating projection and the DR methods. These results seem to be new. We also demonstrate the seemingly improved numerical performance of this algorithm compared to the RAAR algorithm for both consistent and inconsistent sparse feasibility problems.

Original languageEnglish
Pages (from-to)841-863
JournalComputational Optimization and Applications
Volume70
Issue number3
DOIs
Publication statusPublished - 2018

Keywords

  • Almost averagedness
  • Alternating projection method
  • Collection of sets
  • Douglas–Rachford method
  • Krasnoselski–Mann relaxation
  • Metric subregularity
  • Picard iteration
  • RAAR algorithm
  • Transversality

Fingerprint Dive into the research topics of 'A convergent relaxation of the Douglas–Rachford algorithm'. Together they form a unique fingerprint.

Cite this