Mv. Solodov et Bf. Svaiter, A truly globally convergent Newton-type method for the monotone nonlinear complementarity problem, SIAM J OPTI, 10(2), 2000, pp. 605-625
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.