解线性互补问题的非精确松弛多分裂算法

段班祥,朱小平,吴积军

解线性互补问题的非精确松弛多分裂算法

段班祥,朱小平,吴积军

(广东科学技术职业学院计算机工程技术学院,广东珠海519090)

基于矩阵的非精确分裂和多重分裂、处理器的并行计算和松弛迭代算法,提出了求解线性互补问题的非精确松弛多分裂算法,当问题的系数矩阵为对角元为正的H-矩阵时或对称半正定时,证明了算法的全局收敛性.并在一定条件下给出了非精确松弛多分裂算法内迭代的特殊形式,分析了该情形下算法的收敛特性.

线性互补问题;非精确分裂;H-矩阵;对称矩阵;松弛迭代算法;收敛性

0 引言

线性互补问题是一类重要的优化问题,它广泛应用于经济分析、交通、平衡策略等社会和经济模型中,为研究线性和二次规划提供了一个普遍框架.它与不动点理论、变分不等式问题、线性和非线性分析以及其他领域的应用数学如经济、平衡问题等都有密切的联系.近三十年,在数学和工程科学中互补问题得到了充分的发展.但是在满足一定的精确度下求近似解时的迭代次数依然很高.其标准形式为:对给定的n阶实方阵M∈Rn×n和n维实向量q∈Rn,求满足下列条件的实向量z∈Rn,使得

并行多分裂迭代算法最初是O’Leary和White[2]在研究线性方程组Ax=b时提出的概念,Frommer A.和Mayer G.发展了这类算法,给出一个松弛因子,提出了并行多分裂松弛迭代算法[3].针对大规模稀疏矩阵M,为加快收敛速度,文[4]把该算法推广到线性互补问题,提出了求解线性互补问题的并行多分裂迭代算法.

定义1[4]设M为非奇异的n×n实矩阵,Bi,Ci,Ei∈Rn×n,i=1,2,…,α,满足下列条件:①M=Bi+ Ci,i=1,2,…,α,②Mi非奇异,=I(n×n单位阵),则称三元素集(Mi,Bi,Ci)(i= 1,2,…,α)为矩阵M的多分裂.

基于矩阵的多分裂,则求解线性互补问题的多分裂松弛迭代算法定义如下:

算法1(多分裂松弛迭代算法[4])

(1)任意给定初始值z0∈Rn,置r=0;

(2)对M的多重分裂:M=Bi+Ci(i=1,2,…,α),并行求解:

(4)k:=k+1,转第(2)步,直至收敛.

当α≡1时,上述算法1就成为一般的分裂算法.但在实际求解子问题时,往往使用迭代求解,所得结果为近似解,由此产生非精确方法[5,6].基于非精确求解与松弛多分裂算法,本文提出了求解线性互补问题的非精确松弛多分裂迭代算法,当问题的系数矩阵M为对角元为正的H-矩阵或对称正定阵时,分析了算法的收敛性.最后,针对内迭代,提出了一种求解非精确松弛分裂算法的特殊形式,其内迭代利用矩阵的二级分裂算法,分析了该情形下算法的收敛特性.

1 预备知识

首先给出全文使用的一些基本概念:

定义1.1[6]对于向量x∈Rn,如果它的所有分量xi≥0(>0)(i=1,2,…,n),则称x≥0(x>0),设x,y∈Rn,如果x-y≥0(x-y>0),则称x≥y(x>y),用|x|=(|x1|,|x2|,…,|xn|)表示x的绝对值向量.C= (cij)∈Rn×n为n×n阶实矩阵,用diag(C)表示C的对角阵,对于A=(aij),B=(bij)∈Rn×n,若aij≤bij,i,j= 1,2,…,n,则称A≤B.称|A|=(|aij|)∈Rn×n为A=(aij)的绝对值矩阵,显然有|AB|≤|A‖B|.

定义1.2[4]设A∈Rn×n,如果A-1≥0,则称A为单调矩阵;如果对任意给定的i≠j,有aij≤0,且A为单调矩阵,称A为非奇异M-矩阵.设=(bij)∈Rn×n,其中

称为A的比较矩阵;如果Α的比较矩阵是非奇异的M-矩阵,则称A为非奇异的H-矩阵,简称为H-矩阵.

定义1.3[5]设M∈Rn×n,如果对于任意的q∈Rn,线性互补问题LCP(q,M)有唯一解,则称M为Q-矩阵;线性互补问题LCP(0,M)只有一个0解,则称M为R0-矩阵;如果M的所有主子式矩阵都为正,则称M为P-矩阵;一个矩阵M为P-矩阵当且仅当对任意的q∈Rn,线性互补问题LCP(q,M)有唯一解.矩阵M为P-矩阵的一个充分条件为矩阵M对角元为正的H-矩阵.

定义1.4[5]设A∈Rn×n,如果M∈Rn×n是非奇异的且M-1≥0,称A=M+N为矩阵A的一个分裂;如果ρ(M-1N)<1,称分裂A=M+N为收敛的;如果M为Q-矩阵,则称该分裂为Q-分裂.如果-|N|为单调矩阵,则称该分裂为H-分裂;如果=-|N|,则称A=M-N为矩阵A的H-相容分裂.

引理1.1[7,8]设A,M,N∈Rn×n,A=M+N为A的一个分裂,如果该分裂为H-分裂,则矩阵A,M都为H-矩阵且ρ(M-1N)≤ρ(-1|N|)<1;如果该分裂为H-相容分裂且A为H-矩阵,则该分裂为H-分裂.

引理1.2[7,8]设T∈Rn×n且T≥0,如果存在向量u∈Rn,u>0和数θ>0,使得Tu≤θu成立,则有ρ(T)≤θ;设T1,T2,…,Ts,…∈Rn×n为非负矩阵序列,如果存在实数0≤θ<1和向量u∈Rn,u>0,使得Tlu≤θu,l =1,2,…,则有ρ(Hs)≤θs<1,这里Hs=TsTs-1…T1.

2 非精确松弛多分裂算法

设{Bi,Ci,Ei}αi=1为矩阵M的多分裂,首先给出求解线性互补问题(1)的非精确松弛多分裂算法.算法2.1(非精确松弛多分裂算法)

(1)给定初始值z0∈Rn,对每个i,令y0i,0=z0,置r=0;

(2)对于给定的向量zr,令yri,0=zr,对每个i,令yri,l+1为下列互补子问题的任意迭代解:

(3)如果zr+1满足预先给定的外迭代终止原则,则停止计算,否则,设 yri+1,0=zr+1,r=r+1,转第二步,直至收敛.

注2.1 显然,当z0≥0且子问题(2)中的每个解为精确解时,算法2.1就是算法1;当α≡1且ω≡1时,算法2.1就是文献[1]中的非精确分裂算法.此外,在算法1或其他求解线性互补问题的分裂算法中,序列{zr}要求非负,但在算法2.1中不做要求.

注2.2 对每个i=1,2,…,α和外迭代次数r,我们使用特殊的迭代算法求解子问题(2):对每个矩阵Bi再进行分裂:Bi=Fi+Gi,因此,我们得到矩阵M的二级多分裂,用{Bi,Ci,Fi,Gi,Ei}αi=1表示.特别,如果在算法2.1中,每个内迭代使用分裂Bi=Fi+Gi来完成求解,整个迭代序列{zr},包括初始向量z0均非负,则称算法2.1为二级多分裂算法.

注2.3 在每个外迭代和内迭代,如果使用文献[12]中阻尼牛顿算法来求解,这里,要求初始向量z0非退化,即:对每个j =1,2,…,n,(z0)j≠(M z0+q)j.进而,在计算中选择适当的权矩阵,使得整个迭代序列{zr}非退化,例如,可以选择权矩阵Ei=eiI(i=1,2,…,α),这里,称该算法为多分裂阻尼牛顿算法.

3 收敛性分析

本节我们给出算法2.1的收敛性定理.分两种情况来证明:

3.1 系数矩阵为H-矩阵类时算法的收敛性分析

假设算法2.1中的迭代序列满足下列条件:

定理3.1 设M为对角元为正的H-矩阵,{Bi,Ci,Ei}αi=1为矩阵M的一个多分裂.对于任意的i=1,2,…,α,设Ei=eiI,M=Βi+Ci为H-相容分裂,即Bi为对角元为正的H-矩阵,0<ω≤1.假设有矩阵范数‖·‖,使得‖-1|Ci‖<1和‖I‖=1成立.则对任意的初始值z0∈Rn,当式(3)、式(4)成立时,由算法2.1产生的序列{zr}收敛于线性互补问题(1)有唯一解z＊.

证明:因为M为对角元为正的H-矩阵,问题(1)的有唯一解z＊.对于任意的i=1,2,…,α,在第r次外迭代,根据引理1.1和文献[9]中的定理4.1的证明,当内迭代次数充分大时,下述不等式成立

这里

上式中μi,λi为正实数,因此

设θ=max{‖-1|C1|‖,‖-1|C2|‖,…,‖-1|Ci|‖},则由不等式(5)、(6)可得

因此,

在定理3.1的证明过程中,存在一个单调矩阵范数‖·‖,使得‖-1|Ci‖|<1成立.文献[1]中的推论5.3.16给出了这样的矩阵范数:

引理3.1[1]设M为对角元为正的H-矩阵,M=D+L+U,这里D,L和U分别为矩阵M的对角部分、下三角部分、上三角部分.设B=L+δ-1D,δ>0,则存在一个一个正向量¯d,使得¯d>0成立.进而,如果定义如下向量范数这就证明了定理.

和正实数

则有‖·‖¯d为单调范数,¯δ∈(1,2],并且对任意的δ∈(0,¯δ],由(6)式定义的矩阵范数是单调的且‖-1|C|‖¯d<1成立.

由引理3.1给出的单调范数和定理3.1,有如下收敛性结果:

推论3.1 设M为对角元为正的H-矩阵,M=D+L+U,这里D,L和U分别为矩阵M的对角部分、下三角部分、上三角部分.对于任意的i=1,2,…,α,设Ei=eiI,Bi=L+δ-1iD,这里δi>0为给定的向量,0<ω≤1.则存在¯δ∈(1,2],使得对所有的δi∈(0,¯δ],对任意的初始值z0∈Rn,当式(3)、式(4)成立时,由算法2.1产生的序列{zr}收敛于线性互补问题(1)有唯一解z＊.

注3.1引理3.1给出了定理3.1中要求的一个特殊的单调范数实例,因此,推论3.1提供了定理3.1的一个特殊的认识,推论3.1的证明过程由定理3.1和引理3.1直接可得.

引理3.2[1,5.3.2]设M为对称矩阵,Bi+Ci(i=1,2,…,α)为M的弱正则分裂,则对任意向量q∈Rn及任意的初始向量z0∈Rn,z0≥0,由算法2.1产生的序列

3.2 系数矩阵为对称矩阵类时算法的收敛性分析

本节我们给出当M为对称矩阵时算法2.1的收敛性定理.

我们知道,当M为对称矩阵时,线性互补问题(1)等价于如下二次规划问题: (Bi-Ci)(zk-yr,¯l(r)i)≥0(i=1,2,…,α).

如果M为对称半正定矩阵,则f(z)为凸函数,因此,当0<ω≤1时,

由此我们有下面的引理:

引理3.3 设M为对称半正定矩阵,0<ω≤1,Bi+Ci(i=1,2,…,α)为M的弱正则Q-分裂,则

证明: 由上面的分析可得

其中第2个不等式用到引理3.2.

引理3.4 设M为对称半正定矩阵,Bi+Ci(i=1,2,…,α)为M的正则Q-分裂,0<ω≤1,则由算法2.1产生的序列{zk}的每个聚点为问题(1)的解.

证明: 设¯z为序列{zk}的任意聚点,不妨设{zkj}为收敛于¯z的子序列,则有f(zkj)→f(¯z);又由引理3.3知f(zk)非增,因此整个序列f(zk)收敛.仍然设¯i为满足的指标,由已知(B¯i,C¯i)为M的正则Q-分裂,则由式(9)知{zkj-zkj,¯i}→0,所以zkj,¯i→¯z.而由zkj,¯i为下述线性互补问题的解:

因为B¯i+C¯i=M,且当kj→∞时zkj,¯i→¯z,zkj→¯z,对式(10)取极限可得,¯z为问题(1)的解.

下面我们给出M为对称矩阵时松弛迭代算法的收敛性定理.

定理3.2 设M为对称矩阵,Bi+Ci(i=1,2,…,α)为M的正则Q-分裂,0<ω≤1,如果下面两条件成立:

(1)二次函数f(z)=qTz+zTM z对任意的z≥0有下界;

(2)z≠0,z≥0,M z≥0,zTM z=0⇒qTz>0.

则由算法2.1产生的序列{zk}有界,且{zk}的每个聚点为问题(1)的解.

证明:首先用反证法证明序列{zk}有界.假设{zk}无界,则存在子序列{zkj}使得‖zkj‖→∞,由条件(1)及引理3.3知{f(zk)}收敛,仍然设¯i为满足的指标,(B¯i,C¯i)为M的正则Q-分裂,由式(9)知{zkj-zkj,¯i}→0,即‖zkj,¯i‖→∞.

当kj→∞时,我们有M¯z≥0,¯z≥0,¯zTM¯z=0.由已知条件(1)知对任意的z≥0,有zTM z≥0(见文献[1]性质3.7.14).又因为M=B¯i+C¯i,zkj,¯i≥0,所以从

可得

而zkj-zkj,¯i→0,对式(11)右边不等式左右两边除以‖zkj,¯i‖取极限(当kj→∞时)可得:qT¯z≤0,与已知条件(2)矛盾.故由算法2.1产生的序列{zk}有界.

再由引理3.4可得{zk}的每个聚点为问题(1)的解.

证毕.

4 内迭代特殊的实现算法以及该算法的收敛性分析

本节考虑非精确松弛多分裂算法2.1的特殊实现算法.对于任意的i=1,2,…,α,在第r次外迭代,运用特殊的迭代算法来求解互补子问题(2).

算法4.1(二级松弛多分裂算法)对于任意的i=1,2,…,α,在第r次外迭代,运用特殊的迭代算法来求解互补子问题(2):对每个Bi进行再分裂Bi=Fi+Gi,因此,对矩阵M,有二级多分裂{Bi,Ci,Fi,Gi,Ei}αi=1,称此算法为二级松弛多分裂算法.

根据定理3.1和引理1.1,对算法4.1,我们有如下收敛性定理4.1,此结果直接来自内迭代的收敛特性和定理3.1.

定理4.1 设M为对角元为正的H-矩阵,{Bi,Ci,Fi,Gi,Ei}αi=1为矩阵M的二级多分裂.对于任意的i =1,2,…,α,设Ei=eiI,M=Bi+Ci为H-相容分裂,Bi=Fi+Gi为H-分裂,即Bi和Fi都为对角元为正的H-矩阵,0<ω≤1.假设有单调矩阵范数‖·‖,使得对每个i,‖-1|Ci|‖<1和‖I‖=1成立.则对任意向量q和任意的初始值z0∈Rn,当式(3)、式(4)成立时,由算法4.1产生的唯一定义的序列{zr}收敛于线性互补问题(1)有唯一解z＊.

下面,我们给出另外的收敛性结论以降低定理3.1和定理4.1的收敛性条件.事实上,从下面定理的证明过程可以看出单调矩阵范数不再需要,在条件中权矩阵Ei被放松了.特别,在第r次外迭代中,内迭代次数¯l(r)仅要求满足:

2(-1|Gi|)¯l(r)-1-(I+(-1|Gi|)¯l(r))-1<0(12)

定理4.2 设M为对角元为正的H-矩阵,{Bi,Ci,Fi,Gi,Ei}αi=1为矩阵M的二级多分裂.对于任意的i =1,2,…,α,设M=Bi+Ci为H-相容分裂,Bi=Fi+Gi为H-分裂,即Bi和Fi都为对角元为正的H-矩阵,0 <ω≤1.则对任意向量q和任意的初始值z0∈Rn,z0≥0,当式(12)成立时,由算法4.1产生的唯一定义的序列{zr}收敛于线性互补问题(1)的有一解z＊.

证明:因为M为对角元为正的H-矩阵,问题(1)的有唯一解z＊.对于任意的i=1,2,…,α,由引理1.1可得M=Bi+Ci为H-分裂,再由文献[13]中的定理4.3可得这里因此

令Hr=TrTr-1…T0,为证明算法的收敛性,我们只需证明

考虑向量e=(1,1,…,1)T∈Rn,令u=-1e,由定理的条件M=Bi+Ci为H-相容分裂,即:=< Bi>-|Ci|,我们有-1≥0,同时注意-1没有全部为空元素的行和列,因此,u>0,且有

又由于Bi=Fi+Gi为H-分裂,则有

因此

此外,又由于-1和-1都为非负矩阵且没有全部为空元素的行和列,则存在正整数p0,当¯l(r)≥p0时,不等式(9)成立.再由式(14)可得

此外,很容易得到¯Lr

iu≥0,因此,存在实数θi∈(0,1),使得对所有的外迭代r,当内迭代次数¯l(r)充分大时,有

也就是

因此,当内迭代次数¯l(r)充分大时,由式(15)可得

这里,

令～θ=1+ω¯θ-ω,再由定理的条件0<ω≤1,我们有0<～θ<1.因此

推论4.1 设M为对角元为正的H-矩阵,{Bi,Ci,Fi,Gi,Ei}为矩阵M的二级多分裂.对于任意的i =1,2,…,α,设M=Bi+Ci和Bi=Fi+Gi均为H-相容分裂,即Bi和Fi都为对角元为正的H-矩阵,0<ω≤1.则对任意向量q和任意的初始值z0∈Rn,z0≥0,当式(12)成立时,由算法4.1产生的唯一定义的序列{zr}收敛于线性互补问题(1)的唯一解z＊.

证明:因为M为H-矩阵,M=Bi+Ci为H-相容分裂,由引理1.1可得Bi为H-矩阵.再由引理1.1可得Bi=Fi+Gi为H-分裂.当条件(12)成立时,直接由定理4.2可得由算法4.1产生的唯一定义的序列{zr}收敛于线性互补问题(1)的唯一解z＊.

[1] COTTLE R W,PANG J S,STONE R E.The Linear Complementarity Problem[M].San Diego:Academic Press,1992.

[2] O’LEARY D P,WH ITE R E.Multi-splittings ofMatrix and Parallel Solution of Linear Systems[J].SIAM J Algebraic D iscrete M ethods,1985,6:630-640.

[3] FROMMER A,SZYLD D B.H-splitting and Two-stage IterativeMethods[J].Num erM ath,1992,63:345-356.

[4] 段班祥,李郴良,徐安农.线性互补问题的并行多分裂松弛迭代算法[J].运筹学学报,2006,10(3):77-84.

[5] 段班祥,李郴良,徐安农.线性互补问题的二级多重分裂并行算法[J].工程数学学报,2005,22(1):59-64.

[6] BA I Z Z,EVANS D J.Matrix Multisplitting Methods with Applications to Linear Complementarity Problems:Parallel AsynchronousMethods[J].Int J Com putM ath,2002,79:205-232.

[7] DONG J L.InexactMultisplittingMethods forLinear Complementarity Problems[J].J Comput and ApplM ath,2009,223:714-724.

[8] BA I Z Z,SUN J C,WANGD R.A Unified Framework for the Construction ofVariousMatrixMultisplitting IterativeMethods for Large Sparse System ofLinear Equations[J].Com putM ath Appl,1996,32:51-76.

[9] BA I Z Z,DONG J L.A ModifiedDampedNewtonMethod forLinearComplementarity Problems[J].Num erA lgorithm s,2006,42: 207-228.

[10] J I ANGM Q,DONG J L.On Convergence of Two-stage SplittingMethods for Linear Complementarity Problems[J].J Comput ApplM ath,2005,181:58-69.

Inexact RelaxedM ultisplittingM ethods for L inear Complementarity Problem

DUAN Ban-xiang,ZHU Xiao-ping,Wu Ji-jun
(College of Com puter Engineering and Technology, Guangdong Vocational Institute of Science and Technology,Zhuhai519090,China)

The inexact relaxed multi-splitting iterative method for solving the linear complementarity problem was introduced,which was based on the inexact splittingmethod,parallel computation and the multi-splittingmethod.This method provides a specific realization for the multi-splitting method and generalizes many existing matrix splitting methods for linear complementarity problem.Moreover,the global convergence theory of thismethod is proved when the coefficientmatrix is anH-matrix or symmetric matrix.Finally,a specific iteration for m for this inexact multisplittingmethod is presented,where the inner iterations are implemented through a matrix splittingmethod.Convergence properties for this specific form are analyzed.

linear complementarity problem;inexact multi-splitting;H-matrix;symmetric matrix;relaxed iterative method;convergence property

O241.6

A

0253-2395(2010)04-0525-08

2009-10-17;

2010-01-29

广东省自然科学基金(8151064007000004)

段班祥(1971-),男,湖南武冈人,副教授,硕士,主要从事数值计算、应用软件开发等方面的研究.E-mail:duanbanx@hotmail.com