Approximations to Solutions to Systems of Linear Inequalities

Abstract

In this paper we consider a result of Hoffman [J. Res. Nat. Bur. Stand., 49 (1952) pp. 263–265] about approximate solutions to systems of linear inequalities. We obtain a new representation for a corresponding Lipschitz bound via singular values. We also provide geometric representations of these bounds via extreme points. The latter have been developed independently by Bergthaller and Singer [Linear Algebra Appl., 169 (1992), pp. 111–129] and Li [Linear Algebra Appl., 187 (1993), pp. 15–40], but, our proofs are simpler. We obtain a particularly simple proof of Hoffman's existence result which relies only on linear programming duality.