The ℓ1ℓ1 solution of linear inequalities

The need for solving a system of linear inequalities arises in many applications. In some cases it is not known in advance whether the system is solvable or not. If the system happens to be inconsistent then it is often desirable to calculate a point for which the violating part of the residual vector has a minimal norm. The use of the “robust” ℓ1ℓ1 norm is of particular interest. A new theorem of the alternative is established to characterize the optimality conditions and the duality relations of the resulting least absolute deviations problem. The structure of the dual problem paves the way for effective implementation of the affine scaling algorithm. Numerical experiments illustrate interesting features of the proposed method.