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

Applied Mathematics and Mechanics (English Edition) ›› 2003, Vol. 24 ›› Issue (6): 738-746.

• 论文 • 上一篇

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

张立平¹, 高自友²

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

收稿日期:2002-01-29 修回日期:2003-03-15 出版日期:2003-06-18 发布日期:2003-06-18
基金资助:
the National Natural Science Foundation of China(10201001);the National Outstanding Young Investigator Grant(70225005)

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:2002-01-29 Revised:2003-03-15 Online:2003-06-18 Published:2003-06-18
Supported by:
the National Natural Science Foundation of China(10201001);the National Outstanding Young Investigator Grant(70225005)

摘要/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 (ⅲ).

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 (ⅲ).

中图分类号:

O177.91

张立平;高自友. GLOBAL LINEAR AND QUADRATIC ONE-STEP SMOOTHING NEWTON METHOD FOR VERTICAL LINEAR COMPLEMENTARITY PROBLEMS[J]. Applied Mathematics and Mechanics (English Edition), 2003, 24(6): 738-746.

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 (English Edition), 2003, 24(6): 738-746.

参考文献

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

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	Xieping DING, SALAHUDDIN. A system of general nonlinear variational inclusions in Banach spaces[J]. Applied Mathematics and Mechanics (English Edition), 2015, 36(12): 1663-1672.
[2]	丁协平. Behavior of solution set for bilevel generalized mixed equilibrium problems in topological vector spaces[J]. Applied Mathematics and Mechanics (English Edition), 2014, 35(7): 925-934.
[3]	王方磊;安玉坤. 非线性电报方程组的3个双周期正解问题[J]. Applied Mathematics and Mechanics (English Edition), 2009, 30(1): 81-88 .
[4]	张石生;李向荣;陈志坚. 拟变分包含及不动点问题公解的算法[J]. Applied Mathematics and Mechanics (English Edition), 2008, 29(5): 571-582 .
[5]	臧小燕;邓磊. Iterative algorithm of solutions for multivalued general mixed implicit equilibrium-like problems[J]. Applied Mathematics and Mechanics (English Edition), 2008, 29(4): 477-484 .
[6]	丁协平. Maximal elements and generalized games involving condensing mappings in locally FC-uniform spaces and applications (II)[J]. Applied Mathematics and Mechanics (English Edition), 2007, 28(12): 1569-1579 .
[7]	张石生;杨莉;柳京爱. Strong convergence theorems for nonexpansive semi-groups in Banach spaces[J]. Applied Mathematics and Mechanics (English Edition), 2007, 28(10): 1287-1297 .
[8]	丁协平;林炎诚;姚任文. Three-step relaxed hybrid steepest-descent methods for variational inequalities[J]. Applied Mathematics and Mechanics (English Edition), 2007, 28(8): 1029-1036 .
[9]	崔登兰;李养成. Stability of equivariant bifurcation problems with two types of state variables and their unfoldings in presence of parameter symmetry[J]. Applied Mathematics and Mechanics (English Edition), 2007, 28(2): 229-235 .
[10]	曾六川;姚任之. Sensitivity analysis of generalized set-valued quasi-variational inclusion in Banach spaces[J]. Applied Mathematics and Mechanics (English Edition), 2007, 28(1): 97-102 .
[11]	邓磊;杨明歌. Weakly R-KKM mappings---intersection theorems and minimax inequalities in topological spaces[J]. Applied Mathematics and Mechanics (English Edition), 2007, 28(1): 103-109 .
[12]	张清邦;丁协平. g-η-Monotone mapping and resolvent operator technique for solving generalized implicit variational-like inclusions[J]. Applied Mathematics and Mechanics (English Edition), 2007, 28(1): 11-18 .
[13]	丁协平. MAXIMAL ELEMENTS OF A FAMILY OF G_B-MAJORIZED MAPPINGS IN PRODUCT FC-SPACES AND APPLICATIONS[J]. Applied Mathematics and Mechanics (English Edition), 2006, 27(12): 1607-1618 .
[14]	. FIXED POINT THEOREMS FOR MAPPINGS SATISFYING IMPLICIT RELATION ON TWO COMPLETE AND COMPACT METRIC SPACES[J]. Applied Mathematics and Mechanics (English Edition), 2006, 27(9): 1217-1222 .
[15]	张石生. ON PROBLEM OF NEAREST COMMON FIXED POINT OF NONEXPANSIVE MAPPINGS[J]. Applied Mathematics and Mechanics (English Edition), 2006, 27(7): 883-889 .