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

Jein Shan Chen, Hung Ta Gao, Shaohua Pan

    Research output: Contribution to journalArticlepeer-review

    19 Citations (Scopus)

    Abstract

    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.

    Original languageEnglish
    Pages (from-to)455-471
    Number of pages17
    JournalJournal of Computational and Applied Mathematics
    Volume232
    Issue number2
    DOIs
    Publication statusPublished - 2009 Oct 15

    Keywords

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

    ASJC Scopus subject areas

    • Computational Mathematics
    • Applied Mathematics

    Fingerprint Dive into the research topics of 'An R-linearly convergent derivative-free algorithm for nonlinear complementarity problems based on the generalized Fischer-Burmeister merit function'. Together they form a unique fingerprint.

    Cite this