On unconstrained and constrained stationary points of the implicit Lagrangian

Mangasarian and Solodov (Ref. 1) proposed to solve nonlinear complementarity problems by seeking the unconstrained global minima of a new merit function, which they called implicit Lagrangian. A crucial point in such an approach is to determine conditions which guarantee that every unconstrained stationary point of the implicit Lagrangian is a global solution, since standard unconstrained minimization techniques are only able to locate stationary points. Some authors partially answered this question by giving sufficient conditions which guarantee this key property. In this paper, we settle the issue by giving a necessary and sufficient condition for a stationary point of the implicit Lagrangian to be a global solution and, hence, a solution of the nonlinear complementarity problem. We show that this new condition easily allows us to recover all previous results and to establish new sufficient conditions. We then consider a constrained reformulation based on the implicit Lagrangian in which nonnegative constraints on the variables are added to the original unconstrained reformulation. This is motivated by the fact that often, in applications, the function which defines the complementarity problem is defined only on the nonnegative orthant. We consider the KKT-points of this new reformulation and show that the same necessary and sufficient condition which guarantees, in the unconstrained case, that every unconstrained stationary point is a global solution, also guarantees that every KKT-point of the new problem is a global solution.