Regular pseudo-smooth NCP and BVIP functions and globally and quadratically convergent generalized newton methods for complementarity and variational inequality problems

Liqun Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

28 Citations (Scopus)


The nonlinear complementarity problem (NCP) can be reformulated as a system of semismooth equations by some NCP functions. A well-known NCP function is the Fischer-Burmeister function, which is a strongly semismooth function. It is smooth everywhere except at the origin. The generalized Newton direction of the system of semismooth equations formulated with the Fischer-Burmeister function is always a descent direction at a nonsolution point. The generalized Jacobian of the system is nonsingular under mild conditions. Efficient algorithms have been developed based upon these nice properties. In this paper, we define a class of NCP functions, called regular pseudo-smooth NCP functions, and show that they have these nice properties. Regular pseudo-smooth NCP functions can be easily identified. They include the Fischer-Burmeister function, the Tseng-Luo NCP function family, and the Kanzow-Kleinmichel NCP function family. We give two new regular pseudo-smooth NCP function families: the ratio generated NCP function family and the C curve generated NCP function family. We then discuss the box constrained variational inequality problem (BVIP). We define a class of BVIP functions, called regular pseudo-smooth BVIP functions, and show that they have these nice properties too. We present three different approaches to generate regular pseudo-smooth BVIP functions from regular pseudo-smooth NCP functions. Globally and quadratically convergent generalized Newton methods are established for solving the NCP and the BVIP, based upon regular pseudo-smooth NCP and BVIP functions.
Original languageEnglish
Pages (from-to)440-471
Number of pages32
JournalMathematics of Operations Research
Issue number2
Publication statusPublished - 1 Jan 1999
Externally publishedYes

ASJC Scopus subject areas

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Cite this