Global Linear and Quadratic One-Step Smoothing Newton Method for Vertical Linear Complementarity Problems

ZHANG Li-ping; GAO Zi-you

Article Contents

Article Navigation > Applied Mathematics and Mechanics > 2003 > 24(6): 653-660

ZHANG Li-ping, GAO Zi-you. Global Linear and Quadratic One-Step Smoothing Newton Method for Vertical Linear Complementarity Problems[J]. Applied Mathematics and Mechanics, 2003, 24(6): 653-660.

Citation:

ZHANG Li-ping, GAO Zi-you. Global Linear and Quadratic One-Step Smoothing Newton Method for Vertical Linear Complementarity Problems[J]. Applied Mathematics and Mechanics, 2003, 24(6): 653-660.

Citation:

ZHANG Li-ping, GAO Zi-you. Global Linear and Quadratic One-Step Smoothing Newton Method for Vertical Linear Complementarity Problems[J]. Applied Mathematics and Mechanics, 2003, 24(6): 653-660.

PDF( 342 KB)

Global Linear and Quadratic One-Step Smoothing Newton Method for Vertical Linear Complementarity Problems

ZHANG Li-ping¹,
GAO Zi-you²

1.
Department of Methematical Sciences, Tsinghua University, Beijing 100084, P. R. China;
2.
School of Traffic and Transportation, Northern Jiaotong University, Beijing 100044, P. R. China

Received Date: 2002-01-29
Rev Recd Date: 2003-03-15
Publish Date: 2003-06-15

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: (i) 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(ⅲ).
- vertical linear complementarity problems,
- smoothing Newton method,
- global linear convergence,
- quadratic convergence

FullText(HTML)

References(19)

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 P0-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.