%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.