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 -