×

zbMATH — the first resource for mathematics

Superlinear/quadratic one-step smoothing Newton method for \(P_0\)-NCP. (English) Zbl 1124.90037
Summary: We propose a one-step smoothing Newton method for solving the non-linear complementarity problem with \(P_0\)-function (\(P_0\)-NCP) based on the smoothing symmetric perturbed Fisher function (for short, denoted as the SSPF-function). The proposed algorithm has to solve only one linear system of equations and performs only one line search per iteration. Without requiring any strict complementarity assumption at the \(P_0\)-NCP solution, we show that the proposed algorithm converges globally and superlinearly under mild conditions. Furthermore, the algorithm has local quadratic convergence under suitable conditions. The main feature of our global convergence results is that we do not assume a priori the existence of an accumulation point. Compared to the previous literatures, our algorithm has stronger convergence results under weaker conditions.

MSC:
90C30 Nonlinear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65H10 Numerical computation of solutions to systems of equations
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Harker, P. T., Pang, J.–S.: Finite–dimensional variational inequality and non–linear complementarity problems: a survey of theory, algorithms and applications. Mathematical Programming, 48(1), 161–220 (1990) · Zbl 0734.90098
[2] Ferris, M. C., Pang, J.–S.: Engineering and economic applications of complementarity problems. SIAM Review, 39(3), 669–713 (1997) · Zbl 0891.90158
[3] Chen, B., Harker, P. T.: Smoothing approximations to non–linear complementarity problems. SIAM Journal on Optimization, 7(1), 403–420 (1997) · Zbl 0879.90177
[4] Chen, B., Xiu, N.: A global linear and local quadratic non–interior continuation method for non–linear complementarity problems based on Chen–Mangasarian smoothing functions. SIAM Journal on Optimization, 9(2), 605–623 (1999) · Zbl 1037.90052
[5] Chen. X., Qi, L., Sun, D.: Global and superlinear convergence of the smoothing Newton method and its application to general box–constrained variational inequalities. Mathematics of Computation, 67(1), 519–540 (1998) · Zbl 0894.90143
[6] Fischer, A.: Solution of monotone complementarity problems with locally Lipschitz functions. Mathematical Programming, 76(2), 513–532 (1997) · Zbl 0871.90097
[7] Qi, H.: A regularized smoothing Newton method for box constrained variational inequality problems with P 0–functions. SIAM Journal on Optimization, 10(1), 315–330 (2000) · Zbl 0955.90136
[8] Qi, L., Sun, D.: Improving the convergence of non–interior point algorithm for non–linear complementarity problems. Mathematics of Computation, 69(1), 283–304 (2000) · Zbl 0947.90117
[9] Tseng, P.: Error bounds and superlinear convergence analysis of some Newton–type methods in optimization, in non–linear Optimization and Related Topics, Edited by Di Pillo, G., and Giannessi, F., Kluwer Academic Publishers, Boston, 445–462 (2000) · Zbl 0965.65091
[10] Billups, S. C., Dirkse, S. P., Ferris, M. C.: A comparison of algorithms for largescale mixed complementarity problems. Computational Optimization and Applications, 7(1), 3–25 (1997) · Zbl 0883.90116
[11] Qi, L., Sun, D., Zhou, G.: A new look at smoothing Newton methods for non–linear complementarity problems and box constrained variational inequality problems. Mathematical Programming, 87(1), 1–35 (2000) · Zbl 0989.90124
[12] Zhou, G., Sun, D., Qi, L.: Numerical experiences for a class of squared smoothing Newton methods for box constrained variational inequality problems. In Reformulation–Nonsmooth, Piecewise Smooth, semi–smooth and Smoothing Methods, Edited by Fukushima, M., and Qi, L., Kluwer Academic Publishers, Boston, 421–441 (1998) · Zbl 0928.65080
[13] Huang, Z. H., Qi, L., Sun, D.: Sub–quadratic convergence of a smoothing Newton algorithm for the P 0– and monotone LCP. Manuscript, August 17, 2001
[14] Sun, D.: A regularization Newton method for solving non–linear complementarity problems. Applied Mathematics and Optimization, 35(1), 315–339 (1999) · Zbl 0937.90110
[15] Huang, Z., Han, J., Xu, D., Zhang, L.: The non–interior continuation methods for solving the P 0–function non–linear complementarity problem. Science in China, 44(2), 1107–1114 (2001) · Zbl 1002.90072
[16] Chen, B., Xiu, N.: Superlinear noninterior one–step continuation method for monotone LCP in absence of strict complementarity. Journal of Optimization Theory and Applications, 108(1), 317–332 (2001) · Zbl 1041.90056
[17] Fischer, A.: A special Newton–type optimization method. Optimization, 24(1), 269–284 (1992) · Zbl 0814.65063
[18] Mifflin, R.: semis–mooth and semiconvex functions in constrained optimization. SIAM J. Control Optim., 15(1), 957–972 (1977) · Zbl 0376.90081
[19] Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Mathematical Programming, 58(2), 353–367 (1993) · Zbl 0780.90090
[20] Clarke, F. H.: Optimization and Nonsmooth Analysis, Wiley, New York, 1983 · Zbl 0582.49001
[21] Mo√©, J. J., and Rheinboldt, W. C.: On P– and S–functions and related classes of n–dimensional non–linear mappings. Linear Algebra Applications, 6(1), 45–68 (1973). · Zbl 0247.65038
[22] Chen, B., Harker, P. T.: A non–interior–point continuation method for linear complementarity problems. SIAM Journal on Matrix Analysis and Applications, 14(2), 1168–1190 (1993) · Zbl 0788.65073
[23] Kanzow, C.: Global convergence properities of some interative methods for linear complementarity problems. SIAM Journal on Optimization, 6(1), 326–341 (1996) · Zbl 0847.90132
[24] Facchinei, F., Kanzow, C.: Beyond monotonicity in regularization methods for non–linear complementarity problems. SIAM J. Control Optim., 37(2), 1150–1161 (1999) · Zbl 0997.90085
[25] Qi. L.: Convergence analysis of some algorithms for solving nonsmooth equations. Mathematics of Operations Research, 18(1), 227–244 (1993) · Zbl 0776.65037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.