Necessary conditions for linear convergence of iterated expansive, set-valued mappings

D. Russell Luke, Marc Teboulle, Thao Nguyen

Research output: Contribution to journalArticleScientificpeer-review

6 Citations (Scopus)
24 Downloads (Pure)

Abstract

We present necessary conditions for monotonicity of fixed point iterations of mappings that may violate the usual nonexpansive property. Notions of linear-type monotonicity of fixed point sequences—weaker than Fejér monotonicity—are shown to imply metric subregularity. This, together with the almost averaging property recently introduced by Luke et al. (Math Oper Res, 2018. https://doi.org/10.1287/moor.2017.0898), guarantees linear convergence of the sequence to a fixed point. We specialize these results to the alternating projections iteration where the metric subregularity property takes on a distinct geometric characterization of sets at points of intersection called subtransversality. Subtransversality is shown to be necessary for linear convergence of alternating projections for consistent feasibility.

Original languageEnglish
Pages (from-to)1-31
JournalMathematical Programming
Volume180 (2020)
DOIs
Publication statusPublished - 2018

Keywords

  • Almost averaged mappings
  • Averaged operators
  • Calmness
  • Cyclic projections
  • Elemental regularity
  • Feasibility
  • Fejér monotone
  • Fixed point iteration
  • Fixed points
  • Metric regularity
  • Metric subregularity
  • Nonconvex
  • Nonexpansive
  • Subtransversality
  • Transversality

Fingerprint Dive into the research topics of 'Necessary conditions for linear convergence of iterated expansive, set-valued mappings'. Together they form a unique fingerprint.

  • Cite this