A linearly convergent derivative-free descent method for strongly monotonecomplementarity problems

We establish the first rate of convergence result for the class of derivati ve-free descent methods for solving complementarity problems. The algorithm considered here is based on the implicit Lagrangian reformulation [26, 35] of the nonlinear complementarity problem, and makes use of the descent dir ection proposed in [42], but employs a different Armijo-type linesearch rul e. We show that in the strongly monotone case, the iterates generated by th e method converge globally at a linear rate to the solution of the problem.