A smoothing inexact Newton method for P₀ nonlinear complementarity problem

Abstract

We first propose a new class of smoothing functions for the nonlinear complementarity function which contains the well-known Chen-Harker-Kanzow-Smale smoothing function and Huang-Han-Chen smoothing function as special cases, and then present a smoothing inexact Newton algorithm for the P₀ nonlinear complementarity problem. The global convergence and local superlinear convergence are established. Preliminary numerical results indicate the feasibility and efficiency of the algorithm.

Keywords

Nonlinear complementarity problem (NCP) / inexact Newton methods / P₀-function / smoothing function

References

[1] Chen B., Harker P. T. A non-interior-point continuation method for linear complementarity problems. SIAM J Matrix Anal Appl, 1993, 14(4): 1168-1190

[2] Chen B., Ma C. A new smoothing Broyden-like method for solving nonlinear complementarity problem with a P₀ function. J Global Optim, 2011, 51(3): 473-495

[3] Chen X., Qi L., Sun D. Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities. Math Comput, 1998, 67(222): 519-540

[4] Clarke F. H. Optimization and Nonsmooth Analysis, 1983, New York: Wiley

[5] Ferris M. C., Pang J. S. Engineering and economic applications of complementarity problems. SIAM Review, 1997, 39(4): 669-713

[6] Geiger C., Kanzow C. On the resolution of monotone complementarity problems. Comput Optim Appl, 1996, 5: 155-173

[7] Harker P. T., Pang J. S. Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications. Math Program, 1990, 48(2): 161-220

[8] Hotta K., Yoshise A. Global convergence of a class of non-interior point algorithms using Chen-Harker-Kanzow-Smale functions for nonlinear complementarity problems. Math Program, 1999, 86: 105-133

[9] Huang Z., Han J., Chen Z. Predictor-Corrector Smoothing Newton Method, Based on a New Smoothing Function, for Solving the Nonlinear Complementarity Problem with a P₀ Function. J Optim Theory Appl, 2003, 117(1): 39-68

[10] Kanzow C. Some noninterior continuation methods for linear complementarity problems. SIAM J Matrix Anal Appl, 1996, 17(4): 851-868

[11] Kanzow C., Kleinmichel H. A new class of semismooth Newton-type methods for nonlinear complementarity problems. Comput Optim Appl, 1998, 11: 227-251

[12] Luca T. D., Facchinei F., Kanzow C. A semismooth equation approach to the solution of nonlinear complementarity problems. Math Program, 1996, 75(3): 407-439

[13] Ma C., Chen X. The convergence of a one-step smoothing Newton method for P₀-NCP base on a new smoothing NCP-function. J Comput Appl Math, 2008, 216(1): 1-13

[14] Mathiesen L. An algorithm based on a sequence of a linear complementarity problems applied to a Walrasian equilibrium model: an example. Math Program, 1987, 37(1): 1-18

[15] Mifflin R. Semismooth and semiconvex functions in constrained optimization. SIAM J Control Optim, 1977, 15(6): 957-972

[16] Natasa K., Sanja R. Globally convergent Jacobian smoothing inexact Newton methods for NCP. Comput Optim Appl, 2008, 41(2): 243-261

[17] Pang J. S., Gabriel A. NE/SQP: a robust algorithm for nonlinear complementarity problems. Math Program, 1993, 60: 295-337

[18] Qi L. Convergence analysis of some algorithms for solving nonsmooth equations. Math Oper Res, 1993, 18(1): 227-244

[19] Qi L., Sun D., Zhou G. A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities. Math Program, 2000, 87(1): 1-35

[20] Qi L., Sun J. A nonsmooth version of Newton,s method. Math Programming, 1993, 58(3): 353-367

[21] Sun D., Qi L. On NCP functions. Comput Optim Appl, 1999, 13: 201-220

[22] Xie D., Ni Q. An incomplete Hessian Newton minimization method and its application in a chemical database problem. Comput Optim Appl, 2009, 44(3): 467-485

[23] Zhang X., Jiang H., Wang Y. A smoothing Newton method for generalized nonlinear complementarity problem over a polyhedral cone. J Comput Appl Math, 2008, 212: 75-85

[24] Zhang J., Zhang K. A variant smoothing Newton method for P₀-NCP based on a new smoothing function. J Comput Appl Math, 2009, 225(1): 1-8