The Smallest Correction of an Inconsistent System of Linear Inequalities

The problem of calculating a point x that satisfies a given system of linear inequalities, Ax >= b, arises in many applications. Yet often 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 useful to find the smallest perturbation of b that recovers feasibility. This motivates our interest in the least correction problem and its properties. Let Ax >= b be an inconsistent system of linear inequalities. Then it is always possible to find a correction vector y such that the modified system Ax >= b-y is solvable. The smallest correction vector of this type is obtained by solving the least correction problem minimize P(x, y) = 1/2 parallel to y parallel to(2)(2) subject to Ax + y >= b. Let U denote the convex cone which consists of all the points u is an element of R(m) for which the system Ax >= u is solvable. Let Y denote the polar cone of U. It is shown that the least correction problem has a simple geometric interpretation which is based on the polar decomposition of R(m) into U and Y. A further insight into the least correction concept is gained by exploring the duality relations that characterize such problems.