Operations Research Seminar: Ion Necoara

Stochastic algorithms for convex feasibility and convex minimization

Ion Necoara, University of Bucharest

In this talk we present stochastic first-order methods for solving convex feasibility problems or convex minimization problems with many constraints. First, for the convex feasibility problem (that is finding a point in the (in)finite intersection of convex sets) we  propose several equivalent stochastic reformulations, such as stochastic (non)smooth optimization problem, stochastic fixed point problem, or stochastic intersection problem. Based on these reformulations and on new characterization of the conditioning parameters we introduce a general random projection algorithmic framework with an over-relaxed stepsize, which generates either new algorithms or extends to random settings many existing alternating  projection schemes. We  also derive (sub)linear convergence rates for this general algorithm that depend explicitly on the conditioning parameters and on the number of projections computed at each iteration.  Then, we extend this stochastic algorithmic framework to convex minimization problems subject to (in)finite intersection of constraints. For this algorithm we also derive convergence rates in terms of the expected quadratic distance from the iterates to the optimal solution for smooth strongly convex objective functions, which in the best case is of order O(1/k). We also provide necessary and sufficient conditions for linear convergence of this stochastic method. Finally, we give examples of several functional classes satisfying our new conditions and discuss several applications of these results.