Worst-case evaluation complexity of derivative-free nonmonotone line search methods for solving nonlinear systems of equations

In this paper we study a class of derivative-free nonmonotone line search methods for solving nonlinear systems of equations, which includes the method N-DF-SANE proposed in (IMA J. Numer. Anal. 29: 814--825, 2009). These methods correspond to derivative-free optimization methods applied to the minimization of a suitable merit function. Assuming that the mapping defining the system of nonlinear equations has Lipschitz continuous Jacobian, we show that the methods in the referred class need at most $\mathcal{O}\left(|\log(\epsilon)|\epsilon^{-2}\right)$ function evaluations to generate an $\epsilon$-approximate stationary point to the merit function. For the case in which the mapping is strongly monotone, we present two methods with evaluation-complexity of $\mathcal{O}\left(|\log(\epsilon)|\right)$.