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

作者：Chen Jein Shan^*; Gao Hung Ta; Pan Shaohua

来源：Journal of Computational and Applied Mathematics, 2009, 232(2): 455-471.

DOI：10.1016/j.cam.2009.06.022

• Nonlinear complementarity problem
• NCP-function
• Merit function
• Global error bound
• Convergence rate

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: psi(p(a, b)) = 1/2 vertical bar parallel to(a, b)parallel to(p) - (a + b)vertical bar(2), and observed that the choice of the parameter p 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 psi(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 R-linear convergence rate, and furthermore, its convergence rate will become worse when the parameter p decreases. Numerical results are also reported for the test problems from MCPLIB, which further verify the theoretical results obtained.

• 出版日期2009-10-15
• 单位华南理工大学