Solving Linear Inequalities In A Least Squares Sense

. In 1980, Han [6] described a finitely terminating algorithm for solving a system Ax 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. Key Words. iterative methods, linear inequalities, least squares, linear separability AMS(MOS) subject classification. 65F10, 65F20, 65F30, 65K05 1. Introduction. Let A 2 ! m\Thetan be an arbitrary real matrix, ..