Quantitative convergence analysis of iterated expansive, set-valued mappings

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 byproduct 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.

41 pages 70 references. Detailed examples added and more historical commentary (with citations)

References in corpus (4)

• The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than $1/k^2$
• Convergence rate analysis for averaged fixed point iterations in the presence of Hölder regularity
• Set Regularities and Feasibility Problems
• A Globally Linearly Convergent Method for Pointwise Quadratically Supportable Convex-Concave Saddle Point Problems

Cited by in corpus (19)

• Convolutional Proximal Neural Networks and Plug-and-Play Algorithms
• Linear convergence of the generalized Douglas-Rachford algorithm for feasibility problems
• Necessary conditions for linear convergence of iterated expansive, set-valued mappings with application to alternating projections
• Optimization on Spheres: Models and Proximal Algorithms with Computational Performance Comparisons
• Convergence Analysis of the Relaxed Douglas-Rachford Algorithm
• Random Function Iterations for Consistent Stochastic Feasibility
• A Globally Linearly Convergent Method for Pointwise Quadratically Supportable Convex-Concave Saddle Point Problems
• Golden Ratio Algorithms for Variational Inequalities
• Characterizations of Super-regularity and its Variants
• Radius Theorems for Subregularity in Infinite Dimensions
• A minimalist approach to 3D photoemission orbital tomography: algorithms and data requirements
• Convergence of Proximal Splitting Algorithms in CAT(k) Spaces and Beyond
• Provable Phase Retrieval with Mirror Descent
• Uniform Regularity of Set-Valued Mappings and Stability of Implicit Multifunctions
• Phase retrieval with sparse phase constraint
• Projection methods for high numerical aperture phase retrieval
• Concrete convergence rates for common fixed point problems under Karamata regularity
• On $\alpha$-Firmly Nonexpansive Operators in $r$-Uniformly Convex Spaces
• On a notion of averaged operators in CAT(0) spaces