On Constructing Interior-Point Path-Following Methods for Certain Semimonotone Linear Complementarity Problems

Detong Zhang and Yin Zhang

Interior-point path-following methods have proven to be effective in solving monotone linear complementarity problems (LCPs). The main objective of this paper is to build a theoretical basis for the construction of interior-point path-following methods for some nonmonotone LCPs. We propose a new homotopy formulation that enables us to establish the existence of solution paths in the interior of the nonnegative orthant for several classes of semimonotone LCPs. These paths connect almost every interior point in the nonnegative orthant to a solution point, while possessing desirable smoothness properties. An algorithmic framework is given based on these paths for solving several classes of semimonotone LCPs.

TR97-19, CAAM, Rice University, July 1997.

Contact: zhang@caam.rice.edu