Block-iterative surrogate projection methods for convex feasibility problems

AbstractA unified framework is presented for studying the convergence of projection methods for finding a common point of finitely many closed convex sets in Rn. Every iteration approximates each set by a half space given either by an approximate projection of the current iterate or by an aggregate inequality derived from the convex inequalities describing this set. The next iterate is found by projecting the current one on a surrogate half space formed by taking a convex combination of the half-space inequalities. Convergence to a solution is established under weak conditions that allow various acceleration techniques and choices of aggregating weights. The resulting methods are block-iterative and hence lend themselves to parallel implementation. We show that the idea of forming cut maps via surrogate inequalities encompasses many classical as well as recently proposed methods for set intersection problems and convex feasibility problems with nondifferentiable inequalities and linear equations and inequalities