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.