Journal Article

Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings

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

2018

Overview

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.

• Publisher: INFORMS,Institute for Operations Research and the Management Sciences
• Subject: Algorithms / analysis of algorithms / Convergence / Convergence (Mathematics) / Convexity / Expansion / feasibility / Fixed point theory / fixed points / Iterative methods (Mathematics) / Kurdyka-Lojasiewicz inequality / linear convergence / Mapping / Mappings (Mathematics) / Mathematical research / metric regularity / nonconvex / nonsmooth / Operations research / Optimization / Picard iterations / proximal algorithms / subtransversality / transversality