Finding a point in the intersection of a collection of closed convex sets, that is the convex feasibility problem, represents the main modeling strategy for many computational problems. In this paper we analyze new stochastic reformulations of the convex feasibility problem in order to facilitate the development of new algorithmic schemes. We also analyze the conditioning problem parameters using certain (linear) regularity assumptions on the individual convex sets. Then, we introduce a general random projection algorithmic framework, which extends to the random settings many existing projection schemes, designed for the general convex feasibility problem. Our general random projection algorithm allows to project simultaneously on several sets, thus providing great flexibility in matching the implementation of the algorithm on the parallel architecture at hand. Based on the conditioning parameters, besides the asymptotic convergence results, we also derive explicit sublinear and linear convergence rates for this general algorithmic framework. History : First version: March 2017. 1. Introduction Finding a point in the intersection of a collection of closed convex sets, that is the convex feasibility problem, represents a modeling paradigm which has been used for many decades for posing and solving engineering and physics problems. Among the most important applications modeled by the convex feasibility formalism are: radiation therapy treatment planning [20] [38] . Convex feasibility problems have various formulations, such as finding the fixed points of a nonexpansive operator, the set of optimal solutions of a specific optimization problem or the set of solutions to some convex inequalities. Projection methods were first used for solving systems of linear equalities [21] or linear inequalities [25] , and then extended to general convex feasibility problems, e.g. in [14] . Projection methods are very attractive in applications since they are able to handle problems of huge dimensions with a very large number of convex sets in the intersection. For instance, the projection algorithm which represents one of the first iterative algorithms for feasibility problems, rely at each iteration on orthogonal projections onto given individual sets. Its simple algorithmic structure supports the current large scale setting and can be easily adapted to parallel environments, making such schemes adequate to modern computational architectures. If the iteration of a given projection algorithm rely on an alternating sequence of projections onto sets over the iterations, then it belongs to an alternating projection schemes [5, 6, 27, 31] . Furthermore, depending on the variant of the alternating projection algorithm, the current set (or sets) on which the projection is made can be chosen, for example, in a random, cyclic or greedy manner.
The case when f (x, ξ) = 0 which corresponds to the convex feasibility problem is studied in REF .
Randomized projection methods for convex feasibility problems: conditioning and convergence rates
arXiv: Optimization and Control
Mathematics