MONOTONE GRAM MATRICES AND DEEPEST SURROGATE INEQUALITIES IN ACCELERATED RELAXATION METHODS FOR CONVEX FEASIBILITY PROBLEMS

The relaxation method for linear inequalities iterates by projecting t he current point onto the most violated constraint. Accelerated method s project onto the intersection of several halfspaces or onto a surrog ate halfspace corresponding to a nonnegative combination of constraint s. We extend Todds conditions for finding best surrogate inequalities via the solution of systems of linear equations. Our techniques may be used for accelerating various methods for convex feasibility and opti mization problems. (C) Elsevier Science Inc., 1997