New Error Bounds for the Linear Complementarity Problem
New Error Bounds for the Linear Complementarity Problem
复制标题
DOI：
10.1287/moor.19.4.880
复制
发表时间：
1994-11
期刊：
影响因子：
--
通讯作者：
Z. Luo;O. Mangasarian;J. Ren;M. Solodov
中科院分区：
文献类型：
--
作者：
Z. Luo;O. Mangasarian;J. Ren;M. Solodov
最近Mangasarian和Solodov（1993）证明了每个非线性互补问题（NCP）等价于某个隐拉格朗日量的无约束极小化。特别是，它表明，这个隐式拉格朗日是非负的地方，其零点集与原来的NCP的解决方案集相一致。本文考虑线性互补问题，证明了从充分接近解集的任意点到解集的距离可以被线性互补问题的隐式拉格朗日量的平方根上界.换句话说，隐式拉格朗日量的平方根是LCP的局部误差界。我们的证明是基于显示的平方根的隐式拉格朗日是等价的残差函数中使用的一个已知的局部误差界（罗宾逊1981年，罗和曾1992年）。当与LCP相关的矩阵是非退化的，新的误差界实际上是全局的。这扩展了Mathias和.
Recently Mangasarian and Solodov (1993) showed that every nonlinear complementarity problem (NCP) is equivalent to the unconstrained minimization of a certain implicit Lagrangian. In particular, it was shown that this implicit Lagrangian is nonnegative everywhere and its set of zeros coincides with the solution set of the original NCP. In this paper, we consider the linear complementarity problem (LCP), and show that the distance to the solution set of the LCP from any point sufficiently close to the set can be bounded above by the square root of the implicit Lagrangian for the LCP. In other words, the square root of the implicit Lagrangian is a local error bound for the LCP. Our proof is based on showing that the square root of the implicit Lagrangian is equivalent to the residual function used in a known local error bound (Robinson 1981, Luo and Tseng 1992). When the matrix associated with the LCP is nondegenerate, the new error bound is in fact global. This extends the error bound result of Mathias and...