Global complexity bound analysis of the Levenberg-Marquardt method for nonsmooth equations and its application to the nonlinear complementarity problem (Q415364)

Let us consider a system of nonsmooth equations \(F(x)=0\), where \(F:\mathbb{R}^n\rightarrow\mathbb{R}^m\) is a locally Lipschitz continuous mapping. Assume in addition that the least squares merit function \(f(x):=\frac12\|F(x)\|^2\) is continously differentiable. The paper investigates a global complexity bound of the Levenberg-Marquardt method (LMM) for the system of nonsmooth equations. The global complexity bound is an upper bound to the number of iterations required to get an approximate stationary point \(x\) such that \(\|\nabla f(x)\|\leq\epsilon\). Sufficient conditions under which the bound of the LMM for nonsmooth equations is the same as a smooth cases are given. This bound is actually \(O(\epsilon^{-2})\). It is also shown that the bound can be reduced to \(O(\hat\epsilon^{-1})\) for \(\|F(x^k)\|\leq\hat\epsilon\) (\(x^k\) being \(k\)-th iterative point of LMM) under some regularity assumption. Furthermore, by applying these results to nonsmooth equations equivalent to the nonlinear complementarity problem (NCP), the authors get global complexity bounds for the NCP. In particular, a reasonable bound \(O(\hat\epsilon^{-1})\) when the mapping involved in the NCP is a uniformly P-function is given.