On randomized multiple row-action methods for linear feasibility problems

In this paper, for solving linear feasibility problems we propose two randomized methods: a multiple row-action method (RMR) based on partial rows of residual vectors and its generalized method (GRMR) with history information in updating the current update. By introducing a linear combination of the information from the previous and subsequent iterative steps with the relaxation parameter $\xi$, the GRMR method unifies various RMR-type algorithms. A thorough convergence analysis for the proposed methods is provided. The theoretical results show the theoretical convergence rate of the GRMR method with $0\le \xi \le 1$ is always worse or equal compared to that of the RMR method. Therefore, a global linear rate for the GRMR method is explored for $-1\le \xi \le 0$. Finally, numerical experiments on both randomly generated and real-world data show our algorithms outperform the original methods in terms of computing time and iteration counts. In particular, when the appropriate parameters are selected, the GRMR method is the competitive row-action method for solving linear feasibility problems.