段班祥,朱小平,吳積軍

解線性互補問題的非精確松弛多分裂算法

段班祥,朱小平,吳積軍

(廣東科學技術職業(yè)學院計算機工程技術學院,廣東珠海519090)

基于矩陣的非精確分裂和多重分裂、處理器的并行計算和松弛迭代算法,提出了求解線性互補問題的非精確松弛多分裂算法,當問題的系數(shù)矩陣為對角元為正的H-矩陣時或對稱半正定時,證明了算法的全局收斂性.并在一定條件下給出了非精確松弛多分裂算法內迭代的特殊形式,分析了該情形下算法的收斂特性.

線性互補問題;非精確分裂;H-矩陣;對稱矩陣;松弛迭代算法;收斂性

0 引言

線性互補問題是一類重要的優(yōu)化問題,它廣泛應用于經濟分析、交通、平衡策略等社會和經濟模型中,為研究線性和二次規(guī)劃提供了一個普遍框架.它與不動點理論、變分不等式問題、線性和非線性分析以及其他領域的應用數(shù)學如經濟、平衡問題等都有密切的聯(lián)系.近三十年,在數(shù)學和工程科學中互補問題得到了充分的發(fā)展.但是在滿足一定的精確度下求近似解時的迭代次數(shù)依然很高.其標準形式為:對給定的n階實方陣M∈Rn×n和n維實向量q∈Rn,求滿足下列條件的實向量z∈Rn,使得

并行多分裂迭代算法最初是O’Leary和White[2]在研究線性方程組Ax=b時提出的概念,Frommer A.和Mayer G.發(fā)展了這類算法,給出一個松弛因子,提出了并行多分裂松弛迭代算法[3].針對大規(guī)模稀疏矩陣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].基于非精確求解與松弛多分裂算法,本文提出了求解線性互補問題的非精確松弛多分裂迭代算法,當問題的系數(shù)矩陣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和數(shù)θ>0,使得Tu≤θu成立,則有ρ(T)≤θ;設T1,T2,…,Ts,…∈Rn×n為非負矩陣序列,如果存在實數(shù)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,…,α和外迭代次數(shù)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.進而,在計算中選擇適當?shù)臋嗑仃?使得整個迭代序列{zr}非退化,例如,可以選擇權矩陣Ei=eiI(i=1,2,…,α),這里,稱該算法為多分裂阻尼牛頓算法.

3 收斂性分析

本節(jié)我們給出算法2.1的收斂性定理.分兩種情況來證明:

3.1 系數(shù)矩陣為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.假設有矩陣范數(shù)‖·‖,使得‖-1|Ci‖<1和‖I‖=1成立.則對任意的初始值z0∈Rn,當式(3)、式(4)成立時,由算法2.1產生的序列{zr}收斂于線性互補問題(1)有唯一解z＊.

證明:因為M為對角元為正的H-矩陣,問題(1)的有唯一解z＊.對于任意的i=1,2,…,α,在第r次外迭代,根據(jù)引理1.1和文獻[9]中的定理4.1的證明,當內迭代次數(shù)充分大時,下述不等式成立

這里

上式中μi,λi為正實數(shù),因此

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

因此,

在定理3.1的證明過程中,存在一個單調矩陣范數(shù)‖·‖,使得‖-1|Ci‖|<1成立.文獻[1]中的推論5.3.16給出了這樣的矩陣范數(shù):

引理3.1[1]設M為對角元為正的H-矩陣,M=D+L+U,這里D,L和U分別為矩陣M的對角部分、下三角部分、上三角部分.設B=L+δ-1D,δ>0,則存在一個一個正向量ˉd,使得ˉd>0成立.進而,如果定義如下向量范數(shù)這就證明了定理.

和正實數(shù)

則有‖·‖ˉd為單調范數(shù),ˉδ∈(1,2],并且對任意的δ∈(0,ˉδ],由(6)式定義的矩陣范數(shù)是單調的且‖-1|C|‖ˉd<1成立.

由引理3.1給出的單調范數(shù)和定理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中要求的一個特殊的單調范數(shù)實例,因此,推論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 系數(shù)矩陣為對稱矩陣類時算法的收斂性分析

本節(jié)我們給出當M為對稱矩陣時算法2.1的收斂性定理.

我們知道,當M為對稱矩陣時,線性互補問題(1)等價于如下二次規(guī)劃問題: (Bi-Ci)(zk-yr,ˉl(r)i)≥0(i=1,2,…,α).

如果M為對稱半正定矩陣,則f(z)為凸函數(shù),因此,當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)二次函數(shù)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 內迭代特殊的實現(xiàn)算法以及該算法的收斂性分析

本節(jié)考慮非精確松弛多分裂算法2.1的特殊實現(xiàn)算法.對于任意的i=1,2,…,α,在第r次外迭代,運用特殊的迭代算法來求解互補子問題(2).

算法4.1(二級松弛多分裂算法)對于任意的i=1,2,…,α,在第r次外迭代,運用特殊的迭代算法來求解互補子問題(2):對每個Bi進行再分裂Bi=Fi+Gi,因此,對矩陣M,有二級多分裂{Bi,Ci,Fi,Gi,Ei}αi=1,稱此算法為二級松弛多分裂算法.

根據(jù)定理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.假設有單調矩陣范數(shù)‖·‖,使得對每個i,‖-1|Ci|‖<1和‖I‖=1成立.則對任意向量q和任意的初始值z0∈Rn,當式(3)、式(4)成立時,由算法4.1產生的唯一定義的序列{zr}收斂于線性互補問題(1)有唯一解z＊.

下面,我們給出另外的收斂性結論以降低定理3.1和定理4.1的收斂性條件.事實上,從下面定理的證明過程可以看出單調矩陣范數(shù)不再需要,在條件中權矩陣Ei被放松了.特別,在第r次外迭代中,內迭代次數(shù)ˉ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都為非負矩陣且沒有全部為空元素的行和列,則存在正整數(shù)p0,當ˉl(r)≥p0時,不等式(9)成立.再由式(14)可得

此外,很容易得到ˉLr

iu≥0,因此,存在實數(shù)θi∈(0,1),使得對所有的外迭代r,當內迭代次數(shù)ˉl(r)充分大時,有

也就是

因此,當內迭代次數(shù)ˉ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].工程數(shù)學學報,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-),男,湖南武岡人,副教授,碩士,主要從事數(shù)值計算、應用軟件開發(fā)等方面的研究.E-mail:duanbanx@hotmail.com