The Ill-Posed Linear Complementarity Problem

Abstract

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 linear program with equilibrium constrains (LPEC) that is always solvable. For the case when the underlying matrix M of the LCP is in the class Q0 (LCP solvable if feasible), the RLCP can be solved by quadratic program, which is convex if M is positive semi-definite. An explicitly exact penalty of the RLCP formulation is also given when M E Q0 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 when M E Q0, 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.