Monotone gram matrices and deepest surrogate inequalities in accelerated relaxation methods for convex feasibility problems

AbstractThe relaxation method for linear inequalities iterates by projecting the current point onto the most violated constraint. Accelerated methods project onto the intersection of several halfspaces or onto a surrogate halfspace corresponding to a nonnegative combination of constraints. We extend Todd's 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 optimization problems