Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings

• 成果类型: Article
• 署名作者: Luke, D. Russell; Thao, Nguyen H.; Tama, Matthew K.
• 署名单位: University of Gottingen; Delft University of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2017.0898
• 发表日期: 2018
• 页码: 1143-1176
• 关键词: local linear convergence; proximal point algorithm; alternating projections; douglas-rachford; thresholding algorithm; metric regularity; phase retrieval; convex; collections; STABILITY

摘要

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.