A truly globally convergent Newton-type method for the monotone nonlinear complementarity problem

The Josephy-Newton method for solving a nonlinear complementarity problem c onsists of solving, possibly inexactly, a sequence of linear complementarit y problems. Under appropriate regularity assumptions, this method is known to be locally (superlinearly) convergent. To enlarge the domain of converge nce of the Newton method, some globalization strategy based on a chosen mer it function is typically used. However, to ensure global convergence to a s olution, some additional restrictive assumptions are needed. These assumpti ons imply boundedness of level sets of the merit function and often even (g lobal) uniqueness of the solution. We present a new globalization strategy for monotone problems which is not based on any merit function. Our linesea rch procedure utilizes the regularized Newton direction and the monotonicit y structure of the problem to force global convergence by means of a (compu tationally explicit) projection step which reduces the distance to the solu tion set of the problem. The resulting algorithm is truly globally converge nt in the sense that the subproblems are always solvable, and the whole seq uence of iterates converges to a solution of the problem without any regula rity assumptions. In fact, the solution set can even be unbounded. Each ite ration of the new method has the same order of computational cost as an ite ration of the damped Newton method. Under natural assumptions, the local su perlinear rate of convergence is also achieved.