Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings
From MaRDI portal
Publication:5219693
analysis of algorithmsfeasibilityfixed pointsKurdyka-Łojasiewicz inequalitylinear convergencemetric regularitynonconvexnonsmoothproximal algorithmssubtransversalitytransversality
Set-valued and variational analysis (49J53) Sensitivity, stability, well-posedness (49K40) Numerical methods based on necessary conditions (49M05) Decomposition methods (49M27) Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10) Nonconvex programming, global optimization (90C26)
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.
Recommendations
- Convergence of perturbed iterates of set-valued mappings
- scientific article; zbMATH DE number 1867412
- scientific article; zbMATH DE number 2197676
- scientific article; zbMATH DE number 1314817
- scientific article; zbMATH DE number 6401203
- Convergence of inexact iterative schemes for nonexpansive set-valued mappings
- Convergence and existence of fixed points of set-valued nonexpansive mapping
- Asymptotic behavior of perturbed iterates of set-valued mappings
- Necessary conditions for linear convergence of iterated expansive, set-valued mappings
- Convergence of iterative set sequences for multivalued asymptotically \({\Psi_i}\)-quasi-pseudocontractive type mappings
Cites work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A globally linearly convergent method for pointwise quadratically supportable convex-concave saddle point problems
- A Remark on a Theorem of M. A. Krasnoselski
- A unified theory for metric regularity of multifunctions
- About regularity of collections of sets
- Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility
- Alternating Projections on Manifolds
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
- Approximate convexity and submonotonicity.
- Asymptotic behaviour of almost nonexpansive sequences in a Hilbert space
- Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
- Convergence of the Proximal Point Method for Metrically Regular Mappings
- Convergence rate analysis for averaged fixed point iterations in common fixed point problems
- Convex analysis and monotone operator theory in Hilbert spaces
- Degree theory for local condensing maps
- Error bounds and convergence analysis of feasible descent methods: A general approach
- Error bounds and implicit multifunction theorem in smooth Banach spaces and applications to optimization
- Error Bounds in Metric Spaces and Application to the Perturbation Stability of Metric Regularity
- Extension problems for accretive sets in Banach spaces
- Finding Best Approximation Pairs Relative to a Convex and Prox-Regular Set in a Hilbert Space
- Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
- Fixed points of condensing functions
- scientific article; zbMATH DE number 3595777 (Why is no real title available?)
- scientific article; zbMATH DE number 3615396 (Why is no real title available?)
- scientific article; zbMATH DE number 1009689 (Why is no real title available?)
- scientific article; zbMATH DE number 1529036 (Why is no real title available?)
- scientific article; zbMATH DE number 3192366 (Why is no real title available?)
- scientific article; zbMATH DE number 3108780 (Why is no real title available?)
- Implicit Functions and Solution Mappings
- Inexact Variants of the Proximal Point Algorithm without Monotonicity
- Linear convergence of the Douglas-Rachford method for two closed sets
- Local Convergence of the Proximal Point Algorithm and Multiplier Methods Without Monotonicity
- Local differentiability of distance functions
- Local linear convergence for alternating and averaged nonconvex projections
- Local linear convergence of approximate projections onto regularized sets
- Local linear convergence of the ADMM/Douglas-Rachford algorithms without strong convexity and application to statistical imaging
- Mean Value Methods in Iteration
- Metric regularity, openness and Lipschitzian behavior of multifunctions
- Monotone (nonlinear) operators in Hilbert space
- Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems
- Nonlinear regularity models
- On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
- On the convergence of von Neumann's alternating projection algorithm for two sets
- Optical Wavefront Reconstruction: Theory and Numerical Methods
- Optimization methods and stability of inclusions in Banach spaces
- Phase retrieval via matrix completion
- Proximal heterogeneous block implicit-explicit method and application to blind ptychographic diffraction imaging
- Proximal Methods for Cohypomonotone Operators
- Proximité et dualité dans un espace hilbertien
- Quantitative asymptotic regularity results for the composition of two mappings
- Quantitative characterizations of regularity properties of collections of sets
- Regularity on a Fixed Set
- Relaxed averaged alternating reflections for diffraction imaging
- Restricted normal cones and sparsity optimization with affine constraints
- Restricted normal cones and the method of alternating projections: applications
- Restricted normal cones and the method of alternating projections: theory
- Set regularities and feasibility problems
- Set-valued analysis
- Submonotone Subdifferentials of Lipschitz Functions
- The Douglas-Rachford algorithm for two (not necessarily intersecting) affine subspaces
- The method of projections for finding the common point of convex sets
- The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k^2
- Transversality and alternating projections for nonconvex sets
- Uniformity and inexact version of a proximal method for metrically regular mappings
- Variational Analysis
- Variational Analysis Applied to the Problem of Optical Phase Retrieval
- Weak convergence of the sequence of successive approximations for nonexpansive mappings
- Über die Methode sukzessiver Approximationen
Cited in
(38)- A simple globally convergent algorithm for the nonsmooth nonconvex single source localization problem
- Subgradient projectors: extensions, theory, and characterizations
- About intrinsic transversality of pairs of sets
- Convex combination of alternating projection and Douglas-Rachford operators for phase retrieval
- On -firmly nonexpansive operators in r-uniformly convex spaces
- Constraint reduction reformulations for projection algorithms with applications to wavelet construction
- Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems
- \( \alpha \)-firmly nonexpansive operators on metric spaces
- Convergence of proximal splitting algorithms in \(\operatorname{CAT}(\kappa)\) spaces and beyond
- Scaled relative graphs: nonexpansive operators via 2D Euclidean geometry
- On a notion of averaged mappings in \(\operatorname{CAT}(0)\) spaces
- Non-convex split Feasibility problems: models, algorithms and theory
- The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
- Golden ratio algorithms for variational inequalities
- Convolutional proximal neural networks and plug-and-play algorithms
- Necessary conditions for linear convergence of iterated expansive, set-valued mappings
- Metric regularity relative to a cone
- Convergence rate analysis for fixed-point iterations of generalized averaged nonexpansive operators
- Asymptotic behavior of perturbed iterates of set-valued mappings
- Algorithms for structured nonconvex optimization: theory and practice
- Random function iterations for consistent stochastic feasibility
- Optimization on Spheres: Models and Proximal Algorithms with Computational Performance Comparisons
- Phase retrieval with sparse phase constraint
- Convergence Analysis of the Relaxed Douglas--Rachford Algorithm
- Linear convergence of projection algorithms
- Projection methods for high numerical aperture phase retrieval
- Radius theorems for subregularity in infinite dimensions
- Provable Phase Retrieval with Mirror Descent
- scientific article; zbMATH DE number 7733450 (Why is no real title available?)
- Exact convergence rates of alternating projections for nontransversal intersections
- A semi-Bregman proximal alternating method for a class of nonconvex problems: local and global convergence analysis
- Regularity of the product of two relaxed cutters with relaxation parameters beyond two
- Convergence in distribution of randomized algorithms: the case of partially separable optimization
- Quasi -firmly nonexpansive mappings in Wasserstein spaces
- Algorithms based on unions of nonexpansive maps
- Cyclic relaxed Douglas-Rachford splitting for inconsistent nonconvex feasibility
- Stochastic algorithms for large-scale composite optimization: the case of likelihood maximization for X-FEL imaging
- Inexact subgradient methods for semialgebraic functions
This page was built for publication: Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5219693)
