RightThe final publication is available at www.springerlink.com Type Journal Article

Global complexity bound analysis of the Levenberg-Marquardt method for nonsmooth equations and its application to the nonlinear complementarity problem Kenji Ueda and Nobuo Yamashitay We investigate a global complexity bound of the Levenberg-Marquardt Method (LMM) for non-smooth equations F (x) = 0. The global complexity bound is an upper bound to the number of iterations required to get an approximate solution such that ∥∇f(x) ∥ ≤ ϵ, where f is a least square merit function and ϵ is a given positive constant. We show that the bound of the LMM is O(ϵ2). We also show that it is reduced to O(log ϵ1) under some regularity assumption on the generalized Jacobian of F. Furthermore, by applying these results to nonsmooth equations equivalent to the nonlinear complementarity problem (NCP), we get global complexity bounds for the NCP. In par-ticular, we show that the bound is O(log ϵ1) when the mapping involved in the NCP is a uniformly P-function