On the optimal correction of infeasible systems of linear inequalities
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.
scientific article; zbMATH DE number 7383047
scientific article