A Greedy Randomized Average Block Projection Method for Linear Feasibility Problems

Abstract

The randomized projection (RP) method is a simple iterative scheme for solving linear feasibility problems and has gained popularity due to its speed and low memory requirement. This paper develops an accelerated variant of the standard RP method by using two ingredients: the greedy probability criterion and the average block approach, and obtains a greedy randomized average block projection (GRABP) method for solving large-scale systems of linear inequalities. We demonstrate that the GRABP method achieves deterministic linear convergence with various extrapolated step sizes. Numerical experiments on both randomly generated and real-world data show the advantage of GRABP over several state-of-the-art solvers, such as the RP method, the sampling Kaczmarz Motzkin (SKM) method, the generalized SKM method, and the Nesterov acceleration of SKM method.