A hybrid algorithm for solving linear inequalities in a least squares sense

The need for solving a system of linear inequalities, Ax >= b, arises in many applications. Yet in some cases the system to be solved turns out to be inconsistent due to measurement errors in the data vector b. In such a case it is often desired to find the smallest correction of b that recovers feasibility. That is, we are looking for a small nonnegative vector, y >= 0, for which the modified system Ax >= b - y is solvable. The problem of calculating the smallest correction vector is called the least deviation problem. In this paper we present new algorithms for solving this problem. Numerical experiments illustrate the usefulness of the proposed methods.