We combine two iterative algorithms for solving large-scale systems of linear inequalities, the relaxation method of Agmon, Motzkin et al. and the randomized Kaczmarz method. We obtain a family of algorithms that generalize and extend both projection-based techniques. We prove several convergence results, and our computational experiments show our algorithms often outperform the original methods.
© 2016 De Loera, Haddock, Needell
J. A. De Loera, J. Haddock, D. Needell. “A Sampling Kaczmarz-Motzkin Algorithm for Linear Feasibility.” SIAM Journal on Scientific Computing, 2016.