A homotopy method for mixed complementarity problems based on the PATH solver

Abstract

Mixed complementarity problems can be recast as zero finding problems for the normal map, a function that is smooth on the interior o each of the cells of a piecewise linear manifold of IR^n, called normal manifold. We develop a predictor-corrector, or path following, homotopy method based upon using piecewise linear approximations to the piecewise smooth normal map. A description of an implementation using technology found in the PATH solver is given along with computational experience on the MCPLIB test suite.