Regular pseudo-smooth NCP and BVIP functions and globally and quadratically convergent generalized Newton methods for complementarity and variationalinequality problems

Authors
Citation
Lq. Qi, Regular pseudo-smooth NCP and BVIP functions and globally and quadratically convergent generalized Newton methods for complementarity and variationalinequality problems, MATH OPER R, 24(2), 1999, pp. 440-471
Citations number
25
Categorie Soggetti
Mathematics
Journal title
MATHEMATICS OF OPERATIONS RESEARCH
ISSN journal
0364765X → ACNP
Volume
24
Issue
2
Year of publication
1999
Pages
440 - 471
Database
ISI
SICI code
0364-765X(199905)24:2<440:RPNABF>2.0.ZU;2-F
Abstract
The nonlinear complementarity problem (NCP) can be reformulated as a system of semismooth equations by some NCP functions. A well-known NCP function i s the Fischer-Burmeister function, which is a strongly semismooth function. It is smooth everywhere except at the origin. The generalized Newton direc tion of the system of semismooth equations formulated with the Fischer-Burm eister function is always a descent direction at a nonsolution point. The g eneralized Jacobian of the system is nonsingular under mild conditions. Eff icient algorithms have been developed based upon these nice properties. In this paper, we define a class of NCP functions, called regular pseudo-smoot h NCP functions, and show that they have these nice properties. Regular pse udo-smooth NCP functions can be easily identified. They include the Fischer -Burmeister function, the Tseng-Luo NCP function family, and the Kanzow-Kle inmichel NCP function family. We give two new regular pseudo-smooth NCP fun ction families: the ratio generated NCP function family and the C curve gen erated NCP function family. We then discuss the box constrained variational inequality problem (BVIP). We define a class of BVIP functions, called reg ular pseudo-smooth BVIP functions, and show that they have these nice prope rties too. We present three different approaches to generate regular pseudo -smooth BVIP functions from regular pseudo-smooth NCP functions. Globally a nd quadratically convergent generalized Newton methods are established for solving the NCP and the BVIP, based upon regular pseudo-smooth NCP and BVIP functions.