Random function iterations for consistent stochastic feasibility
From MaRDI portal
nonexpansive mappingsaveraged mappingsmetric subregularityiterated random functionsparacontractionslinear regularitygeometric convergence of measureslinear convergence in expectationstochastic feasibilitystochastic fixed point problem
Numerical mathematical programming methods (65K05) Discrete-time Markov processes on general state spaces (60J05) Set-valued and variational analysis (49J53) Existence of optimal solutions to problems involving randomness (49J55) Random convex sets and integral geometry (aspects of convex geometry) (52A22)
Abstract: We study the convergence of stochastic fixed point iterations in the consistent case (in the sense of Butnariu and Fl{aa}m (1995)) in several different settings, under decreasingly restrictive regularity assumptions of the fixed point mappings. The iterations are Markov chains and, for the purposes of this study, convergence is understood in very restrictive terms. We show that sufficient conditions for geometric (linear) convergence in expectation of stochastic projection algorithms presented in Nedi'c (2011), are in fact necessary for geometric (linear) convergence in expectation more generally of iterated random functions.
Recommendations
- Random function iterations for stochastic feasibility problems
- scientific article; zbMATH DE number 7733450
- On Convergence of Iterated Random Maps
- Iterative methods of solving stochastic convex feasibility problems and applications
- On the convergence of sequences of iterates of random-valued functions
Cites work
- scientific article; zbMATH DE number 1805738 (Why is no real title available?)
- scientific article; zbMATH DE number 54135 (Why is no real title available?)
- scientific article; zbMATH DE number 3615396 (Why is no real title available?)
- scientific article; zbMATH DE number 3449561 (Why is no real title available?)
- scientific article; zbMATH DE number 3108780 (Why is no real title available?)
- A Remark on a Theorem of M. A. Krasnoselski
- Best approximation in inner product spaces
- Convex analysis and monotone operator theory in Hilbert spaces
- Ergodic Properties of Markov Processes
- Foundations of Modern Probability
- From error bounds to the complexity of first-order descent methods for convex functions
- Mean Value Methods in Iteration
- Measure theory. Vol. I and II
- Necessary conditions for linear convergence of iterated expansive, set-valued mappings
- On Projection Algorithms for Solving Convex Feasibility Problems
- Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings
- Quasi-Concave Programming
- Random algorithms for convex minimization problems
- Set regularities and feasibility problems
- Strong convergence of expected-projection methods in hilbert spaces
- Successive Averages of Firmly Nonexpansive Mappings
- The Expected–Projection Method: Its Behavior and Applications to Linear Operator Equations and Convex Optimization
- The method of projections for finding the common point of convex sets
Cited in
(8)- The method of randomized Bregman projections for stochastic feasibility problems
- Convergence in distribution of randomized algorithms: the case of partially separable optimization
- scientific article; zbMATH DE number 7733450 (Why is no real title available?)
- Fitted value function iteration with probability one contractions
- Finitely convergent deterministic and stochastic iterative methods for solving convex feasibility problems
- Random function iterations for stochastic feasibility problems
- \( \alpha \)-firmly nonexpansive operators on metric spaces
- Single-projection procedure for infinite dimensional convex optimization problems
This page was built for publication: Random function iterations for consistent stochastic feasibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4632357)
