Creating and sharing knowledge for telecommunications

On optimal zero-preserving corrections for inconsistent linear systems

Júdice, J. J. ; Amaral, P. ; Fernandes, L. M. ; Sherali, H.

Journal of Global Optimization Vol. 45, Nº 1, pp. 645 - 666, January, 2009.

ISSN (print): 0925-5001
ISSN (online): 1573-2916

Journal Impact Factor: 1,062 (in 2008)

Digital Object Identifier: 10.1007/s10898-009-9403-5

This paper addresses the problem of finding an optimal correction of an inconsistent linear system, where only the nonzero coefficients of the constraint matrix are allowed to be perturbed for reconstructing a consistent system. Using the Frobenius norm as a measure for feasibility, a nonconvex minimization problem is formulated, whose objective function is a sum of fractional functions. A branch-and-bound algorithm for solving this nonconvex program is proposed, based on suitability overestimating the denominator function for computing lower bounds. Computational experience is presented to demonstrate the efficacy of this approach.