TY - JOUR

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

AU - Amaral, Paula Alexandra da Costa

AU - Barahona, Pedro Manuel Corrêa Calvente de

PY - 2005/1/15

Y1 - 2005/1/15

N2 - 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.

AB - 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.

KW - Pos-infeasibility analysis

KW - Total least squares

KW - Inconsistent systems

KW - Model reformulation

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-10444280961&origin=inward&txGid=503c8db85550312451011676b1e9222b#

U2 - 10.1016/j.laa.2004.08.022

DO - 10.1016/j.laa.2004.08.022

M3 - Article

VL - 395

SP - 191

EP - 210

JO - Linear Algebra and Applications

JF - Linear Algebra and Applications

IS - 1-3

ER -