CONVERGENCE CONDITIONS FOR NEWTON-TYPE METHODS APPLIED TO COMPLEMENTARITY SYSTEMS WITH NONISOLATED SOLUTIONS∗

Abstract. We consider a class of Newton-type methods for constrained systems of equations that involve complementarity conditions. In particular, at issue are the constrained Levenberg–Marquardt method and the recently introduced Linear-Programming-Newton method, designed for the difficult case when solutions need not be isolated, and the equation mapping need not be differentiable at the solutions. We show that the only structural assumption needed for rapid local convergence of those algorithms is the piecewise error bound, i.e., a local error bound holding for the branches of the solution set resulting from partitions of the bi-active com-plementarity indices. The latter error bound is implied by various piecewise constraint qualifications, including some relatively weak ones. As further applications of our results, we consider Karush–Kuhn–Tucker systems arising from optimization or variational problems, and from generalized Nash equilibrium problems. In the first case, we show convergence under the assumption that the dual part of the solution is a noncritical Lagrange multiplier, and in the second case convergence follows under a certain relaxed constant rank condition. In both cases, this improves on results previously available for the corresponding problems