Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings

D. Russell Luke (), Nguyen H. Thao () and Matthew K. Tam ()
Additional contact information
D. Russell Luke: Institut für Numerische und Angewandte Mathematik, Universität Göttingen, 37083 Göttingen, Germany
Nguyen H. Thao: Delft Center for Systems and Control, Delft University of Technology, 2628 CD Delft, Netherlands
Matthew K. Tam: Institut für Numerische und Angewandte Mathematik, Universität Göttingen, 37083 Göttingen, Germany

Mathematics of Operations Research, 2018, vol. 43, issue 4, 1143-1176

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.

Keywords: analysis of algorithms; feasibility; fixed points; Kurdyka-Lojasiewicz inequality; linear convergence; metric regularity; nonconvex; nonsmooth; proximal algorithms; subtransversality; transversality (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/moor.2017.0898 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:43:y:2018:i:4:p:1143-1176

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().