Quantitative convergence analysis of iterated expansive, set-valued mappings

D. Russell Luke, Nguyen H. Thao, Matthew K. Tam

Research output: Contribution to journalArticleScientificpeer-review

26 Citations (Scopus)
221 Downloads (Pure)

Abstract

We develop a framework for quantitative convergence analysis of Picard iterations of expansive set-valued fixed point mappings. There are two key components of the analysis. The first is a natural generalization of single-valued averaged mappings to expansive set-valued mappings that characterizes a type of strong calmness of the fixed point mapping. The second component to this analysis is an extension of the well-established notion of metric subregularity - or inverse calmness - of the mapping at fixed points. Convergence of expansive fixed point iterations is proved using these two properties, and quantitative estimates are a natural by-product of the framework. To demonstrate the application of the theory, we prove, for the first time, a number of results showing local linear convergence of nonconvex cyclic projections for inconsistent (and consistent) feasibility problems, local linear convergence of the forward-backward algorithm for structured optimization without convexity, strong or otherwise, and local linear convergence of the Douglas-Rachford algorithm for structured nonconvex minimization. This theory includes earlier approaches for known results, convex and nonconvex, as special cases.

Original languageEnglish
Pages (from-to)1143-1176
JournalMathematics of Operations Research
Volume43
Issue number4
DOIs
Publication statusPublished - 2018

Keywords

  • Analysis of algorithms
  • Feasibility
  • Fixed points
  • Kurdyka-Lojasiewicz inequality
  • Linear convergence
  • Metric regularity
  • Nonconvex
  • Nonsmooth
  • Proximal algorithms
  • Subtransversality
  • Transversality

Fingerprint

Dive into the research topics of 'Quantitative convergence analysis of iterated expansive, set-valued mappings'. Together they form a unique fingerprint.

Cite this