BLOCK-ITERATIVE SURROGATE PROJECTION METHODS FOR CONVEX FEASIBILITY PROBLEMS

A unified framework is presented for studying the convergence of proje ction methods for finding a common point of finitely many closed conve x sets in R(n). 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 describi ng this set. The next iterate is found by projecting the current one o n a surrogate half space formed by taking a convex combination of the half-space inequalities. Convergence to a solution is established unde r weak conditions that allow various acceleration techniques and choic es of aggregating weights. The resulting methods are block-iterative a nd hence lend themselves to parallel implementation. We show that the idea of forming cut maps via surrogate inequalities encompasses many c lassical as well as recently proposed methods for set intersection pro blems and convex feasibility problems with nondifferentiable inequalit ies and linear equations and inequalities.