%A O. L. Mangasarian %T The Ill-Posed Linear Complementarity Problem %D August 1995 %R 95-15 %I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN %C MADISON, WI %X A regularization of the linear complementarity problem (LCP) is proposed that leads to an exact solution, if one exists, otherwise a minimizer of a natural residual of the problem is obtained. The regularized LCP (RLCP) turns out to be a linear program with equilibrium constraints (LPEC) that is always solvable. For the case when the underlying matrix $M$ of the LCP is in the class $Q_0$ (LCP solvable if feasible), the RLCP can be solved by a quadratic program, which is convex if $M$ is positive semidefinite. An explicitly exact penalty of the RLCP formulation is also given when $M\in Q_0$ and implicitly exact otherwise. Error bounds on the distance between an arbitrary point to the set of LCP residual minimizers follow from LCP error bound theory. Computational algorithms for solving the RLCP consist of solving a convex quadratic program for positive semidefinite $M,$ otherwise a generally nonconvex quadratic program when $M\in Q_0,$ for which a potentially finitely terminating Frank-Wolfe method is proposed. For a completely general $M,$ a parametric method is proposed wherein for each value of the parameter a Frank-Wolfe algorithm is carried out.