On the optimal correction of infeasible systems of linear inequalities (Q2046550)

The purpose of this paper is to describe a method for correcting infeasible systems of linear inequality. Specifically, given a system \(Ax\leq b\), the algorithm aims to find a matrix \(A^*\) and a vector \(b^*\) such that \(A^*x\leq b^*\) is feasible, and the sum of the Fröbenius norms of \(A-A^*\) and \(b-b^*\) are minimised. The problem is investigated in depth: it is shown that it is NP-hard, optimality conditions are described (when the minimium is attained, which is not guaranteed), and the problem is reformulated as a parametric optimisation problem that can be used to design a trust-region algorithm. Each subproblem in this trust-region method is solved using SQP. In the final part of the paper, the results of numerical experiments are presented to demonstrate that the method is reasonably accurate and efficient.