Smoothing newton algorithm for solving generalized complementarity problem

Abstract

The generalized complementarity problem includes the well-known nonlinear complementarity problem and linear complementarity problem as special cases. In this paper, based on a class of smoothing functions, a smoothing Newton-type algorithm is proposed for solving the generalized complementarity problem. Under suitable assumptions, the proposed algorithm is well-defined and global convergent.

Keywords

generalized complementarity problem / smoothing Newton algorithm / NCP function / global convergence

References

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

[2] Tseng P., Yamashita N., Fukushima M. Equivalence of complementarity problems to differentiable minimization: A unified approach[J]. SIAM Journal on Optimization, 1996, 6(2): 446-460.

[3] Kanzow C., Fukushima M. Equivalence of the generalized complementarity problem to differentiable unconstrained minimization[J]. Journal of Optimization Theory and Applications, 1996, 90(3): 581-603.

[4] Fischer A. A special Newton-type optimization method[J]. Optimization, 1992, 24 269-284.

[5] Kanzow C. Some non-interior continuation methods for linear complementarity problems[J]. SIAM Journal on Matrix Analysis and Applications, 1996, 17(4): 851-868.

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

[7] Smale S. Gleason A. M. Algorithms for solving equations[C] Proceedings of International Congress of Mathematicians, 1987, Providence, Rhode Island, USA: American Mathematics Society 172-195.

[8] Huang Z. H. Locating a maximally complementary solution of the monotone NCP by using non-interior-point smoothing algorithms[J]. Mathematical Methods of Operations Research, 2005, 61(1): 41-55.

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

[10] Qi H. D. A regularized smoothing Newton method for box constrained variational inequality problems with P ₀-functions[J]. SIAM Journal on Optimization, 2000, 10(2): 315-330.

[11] Huang Z. H., Sun D., Zhao G. Y. A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming[J]. Computational Optimization and Applications, 2006, 35(2): 199-237.

[12] Huang Z. H., Sun J. A non-interior continuation algorithm for the P ₀ or P _* LCP with strong global local convergence properties[J]. Applied Mathematics and Optimization, 2005, 52(2): 237-262.

[13] Kanzow C., Kleimichel F. A class of semismooth Newton-type methods for nonlinear complementarity problems[J]. Computational Optimization and Applications, 1998, 11(3): 227-251.