Randomized projection methods for convex feasibility problems: conditioning and convergence rates

Abstract

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.

33 pages. First version published in March 2017

Cited by in corpus (5)

• Random minibatch subgradient algorithms for convex problems with functional constraints
• Almost surely constrained convex optimization
• A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functions
• A Stochastic Penalty Model for Convex and Nonconvex Optimization with Big Constraints
• Distributed Algorithms for Computing a Fixed Point of Multi-Agent Nonexpansive Operators