TY - JOUR

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

AU - Chen, Jein Shan

AU - Gao, Hung Ta

AU - Pan, Shaohua

N1 - Funding Information:
The first author is a member of Mathematics Division, National Center for Theoretical Sciences, Taipei Office. The author’s work is partially supported by the National Science Council of Taiwan.

PY - 2009/10/15

Y1 - 2009/10/15

N2 - 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) = frac(1, 2) [{norm of matrix} (a, b) {norm of matrix}p - (a + b)]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 ψ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.

AB - 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) = frac(1, 2) [{norm of matrix} (a, b) {norm of matrix}p - (a + b)]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 ψ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.

KW - Convergence rate

KW - Global error bound

KW - Merit function

KW - NCP-function

KW - Nonlinear complementarity problem

UR - http://www.scopus.com/inward/record.url?scp=68349137939&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=68349137939&partnerID=8YFLogxK

U2 - 10.1016/j.cam.2009.06.022

DO - 10.1016/j.cam.2009.06.022

M3 - Article

AN - SCOPUS:68349137939

VL - 232

SP - 455

EP - 471

JO - Journal of Computational and Applied Mathematics

JF - Journal of Computational and Applied Mathematics

SN - 0377-0427

IS - 2

ER -