An RR-linearly convergent derivative-free algorithm for nonlinear complementarity problems based on the generalized Fischer–Burmeister merit function

In the paper [J.-S. Chen, S. Pan, A family of NCP-functions and a descent method for the nonlinear complementarity problem, Computational Optimization and Applications, 40 (2008) 389–404], the authors proposed a derivative-free descent algorithm for nonlinear complementarity problems (NCPs) by the generalized Fischer–Burmeister merit function: ψp(a,b)=12[‖(a,b)‖p−(a+b)]2, and observed that the choice of the parameter pp has a great influence on the numerical performance of the algorithm. In this paper, we analyze the phenomenon theoretically for a derivative-free descent algorithm which is based on a penalized form of ψpψp and uses a different direction from that of Chen and Pan. More specifically, we show that the algorithm proposed is globally convergent and has a locally RR-linear convergence rate, and furthermore, its convergence rate will become worse when the parameter pp decreases. Numerical results are also reported for the test problems from MCPLIB, which further verify the theoretical results obtained.