Smoothing inexact Newton method for solving P ₀-NCP problems

Abstract

Based on a smoothing symmetric disturbance FB-function, a smoothing inexact Newton method for solving the nonlinear complementarity problem with P ₀-function was proposed. It was proved that under mild conditions, the given algorithm performed global and superlinear convergence without strict complementarity. For the same linear complementarity problem(LCP), the algorithm needs similar iteration times to the literature. However, its accuracy is improved by at least 4 orders with calculation time reduced by almost 50%, and the iterative number is insensitive to the size of the LCP. Moreover, fewer iterations and shorter time are required for solving the problem by using inexact Newton methods for different initial points.

Keywords

nonlinear complementarity problem / smoothing Newton method / global convergence / superlinear convergence / quadratic convergence

References

[1] Facchinei F, Pang J S. Finite-dimensional Variational Inequalities and Complementarity Problems[M]. 2003, New York, USA: Springer.

[2] Isac G. Topological Methods in Complementarity Theroy [M]. 2000, Boston, USA: Kluwer Academic Publishers.

[3] Zhang L, Wu S-Y, Gao Tingran. Improved smoothing Newton methods for P ₀ nonlinear complementarity problems[J]. Applied Mathematics and Computation, 2009, 215(1): 324 332

[4] Huang Z, Han J, Xu D, et al. The noninterior continuation methods for solving the P ₀ function nonlinear complementarity problem [J]. Science in China (Series A), 2001, 44(9): 1107 1114

[5] Fang Liang. A new one-step smoothing Newton method for nonlinear complementarity problem with P ₀-function[J]. Applied Mathematics and Computation, 2010, 216(4): 1087 1095

[6] Fischer A. A special Newton type optimization method [J]. Optimization, 1992, 24(3/4): 269 284

[7] Qi L, Sun Jie. A nonsmooth version of Newton’s method [J]. Mathematical Programming, 1993, 58(1–3): 353 367

[8] Kanzow C. Global convergence properties of some iterative methods for linear complementarity problems[J]. SIAM Journal on Optimization, 1996, 6(2): 326 341

[9] Chen B, Harker P T. A non-interior-point continuation method for linear complementarity problems[J]. SIAM Journal on Matrix Analysis and Applications, 1993, 14(4): 1168 1190

[10] Qi L Q. Convergence analysis of some algorithms for solving nonsmooth equations[J]. Mathematics of Operations Research, 1993, 18(1): 227 244

[11] Murty K G, Yu V F. Linear Complementarity, Linear and Nonlinear Programming [M]. 1988, Berlin, Germany: Heldermann-Verlag.

[12] Qi L, Sun D, Zhou Guanglu. A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities[J]. Mathematical Programming, 2000, 87(1): 1-35.

[13] Rui S, Xu Chengxian. A smoothing inexact Newton method for nonlinear complementarity problems[J]. Journal of Computational and Applied Mathematics, 2010, 233(9): 2332 2338

[14] Ma C, Chen Xiaohong. The convergence of a one-step smoothing Newton method for P0-NCP based on a new smoothing NCP-function[J]. Journal of Computational and Applied Mathematics, 2008, 216(1): 1 13

[15] Zhu J, Liu H, Liu Changhe. A family of new smoothing functions and a nonmonotone smoothing Newton method for the nonlinear complementarity problems[J]. Journal of Applied Mathematics and Computing, 2011, 37(1/2): 647 662