Optimization based globally convergent methods for the nonlinear complementarity problem

The nonlinear complementarity problem has been used to study and formulate various equilibrium problems including the traffic equilibrium problem, the spatial equilibrium problem and the Nash equilibrium problem. To solve the nonlinear complementarity problem, various iterative methods such as projection methods, linearized methods and Newton method have been proposed and their convergence results have been established. In this paper, the authors propose globally convergent methods based on differentiable optimization formulation of the problem. The methods are applications of a recently proposed method for solving variational inequality problems, but they take full advantage of the special structure of nonlinear complementarity problem. The authors establish global convergence of the proposed methods, which is a refinement of the results obtained for variational inequality counterparts. Some computational experience indicates that the proposed methods are practically efficient.