GLOBAL LINEAR AND QUADRATIC ONE-STEP SMOOTHING NEWTON METHOD FOR VERTICAL LINEAR COMPLEMENTARITY PROBLEMS

Abstract

Abstract: A one-step smoothing Newton method is proposed for solving the vertical linear complementarity problem based on the so-called aggregation function. The proposed algorithm has the following good features: (ⅰ) It solves only one linear system of equations and does only one line search at each iteration;(ⅱ) It is well-defined for the vertical linear complementarity problem with vertical block P₀ matrix and any accumulation point of iteration sequence is its solution.Moreover, the iteration sequence is bounded for the vertical linear complementarity problem with vertical block P₀+R₀ matrix;(ⅲ) It has both global linear and local quadratic convergence without strict complementarity. Many existing smoothing Newton methods do not have the property (ⅲ).

2010 MSC Number:

O177.91

ZHANG Li-ping;GAO Zi-you. GLOBAL LINEAR AND QUADRATIC ONE-STEP SMOOTHING NEWTON METHOD FOR VERTICAL LINEAR COMPLEMENTARITY PROBLEMS. Applied Mathematics and Mechanics (English Edition), 2003, 24(6): 738-746.

TrendMD

References

[1] Cottle R W,Pang J S,Stone R W.The Linear Complementarity Problem[M].Boston:Academic Press,1992.
[2] Cottle R W,Dantzig G B.A generalization of the linear complementarity problem[J].Journal of Combinatorial Theory,1970,8(1):79-90.
[3] Sun M.Monotonicity of mangsarian's iterative algorithm for generalized linear complementarity problems[J].J Math Anal Appl,1989,144(2):474-485.
[4] Gowda M S,Sznajder R.A generalization of the Nash equilibrium theorem on bimatrix games[J].Internat J Game Theory,1996,25(1):1-12.
[5] Ebiefung A A,Kostreva M M.The generalized Leontief input-output model and its application to the choice of the new technology[J].Ann Oper Res,1993,44(1):161-172.
[6] Fujisawa T,Kuh E S.Piecewise-linear theory of nonlinear networks[J].SIAM J Appl Math,1972,22(1):307-328.
[7] Peng J M,Lin Z H.A noninterior continuation method for generalized linear complementarity problems[J].Math Programming,1999,86(2):533-563.
[8] Qi H,Liao L Z.A smoothing Newton method for extended vertical linear complementarity problems[J].SIAM J Matrix Anal Appl,1999,21(1):45-66.
[9] Billups S C,Dirkse S P,Ferris M C.A Comparison of algorithms for large-scale mixed complementarity problems[J].Computational Optimization and Applications,1997,7(1):3-25.
[10] Qi L,Sun D,Zhou G.A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems[J].Math Programming,2000,87(1):1-35.
[11] Zhou G,Sun D,Qi L.Numerical experiences for a class of squared smoothing Newton methods for box constrained variational inequality problems[A].In:Fukushima M,Qi L Eds.Reformulation-Nonsmooth,Piecewise Smooth,Semismooth and Smoothing Methods[C].Boston:Kluwer Academic Publishers,1998,421-441.
[12] Qi H.A regularized smoothing Newton method for box constrained variational inequality problems with P₀-functions[J].SIAM Journal on Optimization,2000,10(1):315-330.
[13] Sun D.A regularization Newton method for solving nonlinear complementarity problems[J].Applied Mathematics and Optimization,1999,35(1):315-339.
[14] Chen X,Qi L,Sun D.Global and superlinear convergence of the smoothing Newton method and its application to general box-constrained variational inequalities[J].Mathematics of Computation,1998,67(2):519-540.
[15] Kanzow C,Pieper H.Jacobian smoothing methods for nonlinear complementarity problems[J].SIAM Journal on Optimization,1999,9(1):342-373.
[16] LI X S.An aggregate function method for nonlinear programming[J].Science in China, Ser A,1991,34(3):1467-1473.
[17] Qi L,Sun J.A nonsmooth version of Newton's method[J].Math Programming,1993,58(1):353-367.
[18] Qi L.Convergence analysis of some algorithms for solving nonsmooth equations[J].Mathematics of Operations Research,1993,18(1):227-244.
[19] Chen B,Xiu N.Superlinear noninterior one-step continuation method for monotone LCP in absence of strict complementarity[J].Journal of Optimization Theory and Applications,2001,108(1):317-332.