No label defined (Q4547593)

The authors investigate the backward error for a linear program \(P(A,b,c): \min c^Tx\) s.t. \(A^TX\leq b\) where \(A\) denotes the \(n\times p\) matrix, \(c\in\mathbb{R}^n\) and \(b\in\mathbb{R}^p\). A solution \((X,Y)\) of this program satisfies the conditions (C): \(A^TX\leq b\), \(Y\geq 0\), \(Y^T(A^TX-b)=0\) and \(Y^TA= c\). For practical situations, the authors state the desirability of obtaining an approximate solution \((X',Y')\) to \(P(A,b,c)\) where \((X',Y')\) is an exact solution of an approximate problem \(P'(A',b',c')\). For this the best approximation problem considered is \[ (\text{BE}):\inf_{(A',b',c')\in C}\bigl \|(A', b',c')-(A,b,c) \bigr\|^2 \] where \(\|(A',b',c')- (A,b,c)\|^2= \|A'-A \|^2_F+ \|b'-b\|^2 +\|c'-c\|^2\), \(\|\cdot \|_F\) is the Frobenius norm for \(n\times p\) matrices, and where \(C\), the set of constraints, is the set of \((A',b',c')\in \mathbb{R}^{np} \times\mathbb{R}^p \times\mathbb{R}^n\) such that \((A',b',c',X',Y')\) satisfies (C) above. The solution \((A^*,b^*,c^*)\) of \((\text{BE}) \) is computed explicitly together with the estimate of the distance \(\|A^*-A\|_F\). The backward error analysis viewpoint is known in the literature and in the context of linear programming is discussed by \textit{N. Megiddo} [Contemp. Math. 114, 35-50 (1990; Zbl 0747.90065)].