Correcting an inconsistent set of linear inequalities by the generalized Newton method

Abstract

In this paper, we consider correcting an inconsistent set of linear inequalities by minimal changes in problem data using the l ₂-norm. A new formulation of the problem is introduced, which involves minimizing a nonconvex fractional function. Then by utilizing the generalized Newton (GN) method, two heuristic algorithms are developed to solve the fractional minimization problem. We further consider correcting inconsistent linear inequalities with extra non-negativity constraints on the variables. For this specific case, we also propose two heuristic algorithms. Finally, we report encouraging numerical results.

Keywords:

• inconsistent linear inequalities
• fractional optimization
• generalized Newton method
• Dinkelbach's method

AMS Subject Classification :

• 90C30
• 90C31
• 15A39