A New Merit Function For Nonlinear Complementarity Problems And A Related Algorithm

We investigate the properties of a new merit function which allows us to reduce a nonlinear complementarity problem to an unconstrained global minimization one. Assuming that the complementarity problem is defined by a P₀-function, we prove that every stationary point of the unconstrained problem is a global solution; furthermore, if the complementarity problem is defined by a uniform P-function, the level sets of the merit function are bounded. The properties of the new merit function are compared with those of Mangasarian--Solodov's implicit Lagrangian and Fukushima's regularized gap function. We also introduce a new simple active-set local method for the solution of complementarity problems and show how this local algorithm can be made globally convergent by using the new merit function.