Efficient randomized block Kaczmarz method for linear feasibility

The randomized Kaczmarz and Motzkin algorithms are commonly employed as iterative techniques for solving systems of linear inequalities in the form of \(Ax\le b\). Briskman and Needell (J Math Imaging Vis 52:385–396, 2015) extended the randomized block Kaczmarz algorithm to handle systems of mixed equalities and inequalities. In this paper, we introduce a family of average block Kaczmarz algorithms that leverage a subset of the constraints at each step and employ an adaptive stepsize to efficiently solve systems of linear inequalities. Unlike the block Kaczmarz method proposed by Briskman and Needell, our algorithms possess the advantageous property of linear convergence to a solution for a given system of linear inequalities, without the necessity of computing pseudoinverse matrices. Moreover, the parallel implementation of our algorithm provides additional acceleration, making it well-suited to tackle real-world problems involving large-scale systems of linear inequalities. Numerical experiments conducted using randomly generated and real-world test instances, including classification with support vector machines and Netlib LP, confirm the efficiency of our proposed algorithm, which significantly reduces the required computational time.