A New Class Of Merit Functions For The Nonlinear Complementarity Problem

Zhi-Quan Luo and Paul Tseng

The paper considers a new class of merit functions for the nonlinear complementarity problem (NCP). A merit function from this class has nice differentiability and convexity properties and, in the monotone case, each of its stationary points is a solution of the NCP. In general, a certain regularity condition is both necessary and sufficient for a stationary point to be a solution of the NCP. In addition, under suitable conditions, this merit function provides a local/global error bound for the NCP and/or has bounded level sets. In the monotone case, this merit function has a derivative-free descent direction. Using this direction, we develop a practical descent method for solving the NCP and we report our numerical experience with this method.