Boundedness Theorems for the Relaxation Method

A classical theorem by Block and Levin (Block, H. D., S. A. Levin. 1970. On the boundedness of an iterative procedure for solving a system of linear inequalities. Proc. Amer. Math. Soc.26 229–235) states that certain variants of the relaxation method for solving systems of linear inequalities generate bounded sequences of intermediate solutions, even when applied to infeasible systems. Using a new approach, we prove a more general version of this result and answer an old open problem of quantifying the bound as a function of the input data.