Connections between the total least squares and the correction of an infeasible system of linear inequalities.

Given an infeasible system of linear inequalities, Ax ⩽ b, we address the problem of correcting both the matrix of coefficients A by A + H and vector b by b + p to minimize the Frobenius norm of [H, p]. For a system of linear equations this problem can be solved by an algebraic and well-studied method known as the total least squares. For inequalities, Vatolin [Seminarber., Humboldt-Univ. Berlin, Sekt. Math. 81 (1986) 145–154] was the first to approach this problem, presenting a result with necessary and sufficient conditions for local minimizers. Unfortunately the direct application of these results is impracticable for large problems. Since the sufficient conditions are not necessary, in case of their failure one is unable to draw conclusions on a search path for a local minimizer. We have analyzed the problem using the KKT conditions and derived necessary and sufficient conditions which enabled us to unequivocally characterize local optima in terms of the solution of the total least squares and the set of active constraints. Establishing the common features between these two problems is not only important from a theoretical point of view, but it opens the possibility of using theoretical developments related with the total least squares to solve the problem with inequalities.