垂直线性互补问题的一步全局线性和局部二次收敛光滑Newton法

张立平; 高自友

垂直线性互补问题的一步全局线性和局部二次收敛光滑Newton法

张立平¹,
高自友²

1.
清华大学, 数学科学系, 北京, 100084;
2.
北方交通大学, 交通运输学院, 北京, 100044

基金项目: 国家自然科学基金资助项目(10201001);国家杰出青年基金资助项目(70225005)

详细信息

作者简介:
张立平(1970- ),女,山东青岛人,讲师,博士(E-mail:malpzhang@sina.com).

中图分类号: O177.91
计量
- 文章访问数: 1823
- HTML全文浏览量: 52
- PDF下载量: 689
- 被引次数: 0
出版历程
- 收稿日期: 2002-01-29
- 修回日期: 2003-03-15
- 刊出日期: 2003-06-15

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

摘要

摘要: 基于凝聚函数,提出一个求解垂直线性互补问题的光滑Newton法.该算法具有以下优点:(i)每次迭代仅需解一个线性系统和实施一次线性搜索;(ⅱ)算法对垂直分块P0矩阵的线性互补问题有定义且迭代序列的每个聚点都是它的解.而且,对垂直分块P₀+R₀矩阵的线性互补问题,算法产生的迭代序列有界且其任一聚点都是它的解;(ⅲ)在无严格互补条件下证得算法即具有全局线性收敛性又具有局部二次收敛性.许多已存在的求解此问题的光滑Newton法都不具有性质(ⅲ).
- 垂直线性互补 /
- 光滑Newton法 /
- 全局线性收敛 /
- 局部二次收敛
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

HTML全文

参考文献(19)

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