Random Function Iterations for Consistent Stochastic Feasibility

AbstractWe study the convergence of iterated random functions for stochastic feasibility in the consistent case (in the sense of Butnariu and Flam [Numer. Funct. Anal. Optimiz., 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 Nedic [Math. Program, 2011], are in fact necessary for geometric (linear) convergence in expectation more generally of iterated random functions.