New error bounds for the linear complementarity problem

Recently Mangasarian and Solodov showed that every nonlinear complementarity problem (NCP) is equivalent to the unconstrained minimization of a certain implicit Lagrangean. In particular, it was shown that this implicit Lagrangean is nonnegative everywhere and its set of zeros coincides with the solution set of the original NCP. In this paper the authors 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 Lagrangean for the LCP. In other words, the square root of the implicit Lagrangean is a local error bound for the LCP. The present proof is based on showing that the square root of the implicit Lagrangean is equivalent to the residual function used in a known local error bound. 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 Pang for the LCP with a P-matrix.