线性互补问题的一种新Lagrange乘子法  

A NEW MULTIPLIER METHOD FOR SOLVING LINEAR COMPLEMENTARITY PROBLEMS

作　　者：乌力吉[1] 陈国庆[1] 

机构地区：[1]内蒙古大学理工学院数学系

出　　处：《高等学校计算数学学报》2004年第2期162-171,共10页Numerical Mathematics A Journal of Chinese Universities

基　　金：国家自然科学基金(19701016);教育部高等学校骨干教师资助计划资助

摘　　要：1引言 考虑线性互补问题LCP(q,M):求x∈IRn,使 x≥0,v(x):=Mx+q≥0,xTv(x)=0, (1) 其中M=(mij)∈IRn×n为给定的常数矩阵,q=(q1,…,qn)T∈IRn为给定的常向量.因LCP(q,M)基本而广泛的应用,其解法研究一直备受关注[3],[5].特别在最近十几年,互补问题的数值方法有了很大的发展,参见综述文章[11].A new multiplier method for solving the linear complementarity problem LCP(q, M) is proposed. Based on the Lagrangian of LCP(q, M) introduced here, we construct a new differentiable merit function θ(x, λ) which containing a multiplier vector A and satisfying θ(z, λ ≥ 0 and θ(x, λ) = 0 if and if only x solves LCP(g, M). A simple damped Newton-type algorithm which based on the merit function θ(z,λ) is presented. The main feature of the method is that the multiplier self-adjusting step accelerates the local convergence rate without losing global convergence. When M is the P-matrix, the sequence {θ(xk,λ)} where {(xk,λk)} generated by the algorithm is globally linearly convergent to zero and convergent in finite number of iterations if the solution is nonde-generate. Numerical results suggest that the method is high efficient and promising.

关 键 词：线性互补 LAGRANGE乘子法 LAGRANGE函数 乘子参数 线搜索步长 

分 类 号：O241.6[理学—计算数学]