A linearly convergent derivative-free descent method for strongly monotone complementarity problems

We establish the first rate of convergence result for the class of derivative-free descent methods for solving complementarity problems. The algorithm considered here is based on the implicit Lagrangian reformulation of the nonlinear complementarity problem. We show that in the strongly monotone case, the iterates generated by the method converge globally at a linear rate to the solution of the problem.