Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings

A publication (journal article) of the University of Göttingen

Jump to: Cite & Linked | Documents & Media | Details | Version history

Cite this publication

​Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings​
Thao, N. H. ; Tam, M. K.   & Luke, R. ​ (2018) 
Mathematics of Operations Research43(4) pp. 1143​-1176​.​

Documents & Media

moor.2017.0898.pdf486.9 kBAdobe PDF

License

Published Version

Attribution 4.0 CC BY 4.0

Details

Authors
Thao, Nguyen H. 
Tam, Matthew K. 
Luke, Russell 
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.
Issue Date
2018
Type
Journal Article
Journal
Mathematics of Operations Research 
Project
RTG 2088: Research Training Group 2088 Discovering structure in complex data: Statistics meets Optimization and Inverse Problems 
Language
English

Reference

Citations


Social Media