Solving linear inequalities in a least squares sense

In 1980, S.-P. Han [Least-Squares Solution of Linear Inequalities, Tech. Report TR-2141, Mathematics Research Center, University of Wisconsin-Madison, 1980] described a finitely terminating algorithm for solving a system Ax less than or equal to b of linear inequalities in a least squares sense. The algorithm uses a singular value decomposition of a submatrix of A on each iteration, making it impractical for all but the smallest problems. This paper shows that a modification of Han's algorithm allows the iterates to be computed using QR factorization with column pivoting, which significantly reduces the computational cost and allows efficient updating/downdating techniques to be used. The effectiveness of this modification is demonstrated, implementation details are given, and the behaviour of the algorithm discussed. Theoretical and numerical results are shown from the application of the algorithm to linear separability problems.