求解P*(τ)陣線性互補(bǔ)問(wèn)題的寬鄰域路徑跟蹤算法

張莉，張濤

(1.四川省高等學(xué)校 數(shù)值仿真重點(diǎn)實(shí)驗(yàn)室，四川 內(nèi)江 641112;2.內(nèi)江師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，四川 內(nèi)江 641112)

線性互補(bǔ)問(wèn)題是規(guī)劃論中的重要問(wèn)題之一，線性互補(bǔ)問(wèn)題從20世紀(jì)60年代提出到現(xiàn)在，已經(jīng)出現(xiàn)了很多優(yōu)秀的算法．總體上可以分為兩類：一類是直接法，如Lemke算法，Cottle-Danting法；另一類是迭代法，如Mangrian法．到1984年,Karmarkar[1-2]提出內(nèi)點(diǎn)算法以后，出現(xiàn)了很多求解線性互補(bǔ)問(wèn)題的內(nèi)點(diǎn)算法.文獻(xiàn)[3]定理3.3.7證明了線性互補(bǔ)問(wèn)題的解是存在唯一的，文獻(xiàn)[4]給出求解一類非單調(diào)線性互補(bǔ)問(wèn)題的內(nèi)點(diǎn)算法的一般框架，文獻(xiàn)[5]給出求解一類非單調(diào)線性互補(bǔ)問(wèn)題的一種勢(shì)能函數(shù)約減法，文獻(xiàn)[6]給出(P-矩陣)線性互補(bǔ)問(wèn)題的一階窄鄰域路徑跟蹤算法，文獻(xiàn)[7]給出了(P-矩陣)線性互補(bǔ)問(wèn)題的一階寬鄰域路徑跟蹤算法，并討論了計(jì)算復(fù)雜性．然而，對(duì)于p*(τ)陣線性互補(bǔ)問(wèn)題的內(nèi)點(diǎn)算法研究甚少，本文在文獻(xiàn)[7]的基礎(chǔ)上，克服了p*(τ)陣線性互補(bǔ)問(wèn)題關(guān)鍵性的困難，提出了一種寬鄰域路徑跟蹤算法，討論了計(jì)算復(fù)雜性，并給出了數(shù)值實(shí)驗(yàn).

線性互補(bǔ)問(wèn)題的一般形式是：求(x,z)∈Rn×Rn，使得：

z=Mx+b,(x,z)≥0,xTz=0

(1)

其中M∈Rn×n,b∈Rn.記

W=(x,z)|z=Mx+b,(x,z)>0，C=(x,z)∈W|Xz=μe,μ>0，

N2(β)=(x,z)∈W‖Xz-μe‖≤μβ，N∞(β)=(x,z)∈W‖Xz-μe‖∞≤μβ，

其中nμ=xTz,β∈(0,1)是適當(dāng)確定的常數(shù)．稱W為問(wèn)題(1)的嚴(yán)格可行內(nèi)點(diǎn)集，稱C為問(wèn)題(1)的中心路徑，N2(β)和N∞(β)分別為包含中心路徑C的一個(gè)2-范數(shù)的窄鄰域和∞-范數(shù)的寬鄰域．本文假設(shè)W非空．約定當(dāng)英文小寫(xiě)字母例如x表示向量時(shí)，對(duì)應(yīng)的大寫(xiě)字表示對(duì)角矩陣X=diag(x),e=(1,…,1)T，‖·‖和‖·‖∞分別表示2-范數(shù)和∞-范數(shù)．

本文假設(shè)M為P*(τ)陣[8]．所謂P*(τ)陣即存在實(shí)數(shù)τ≥0，使得對(duì)?x∈Rn，有

其中I=i|1≤i≤n,xi[(Mx)]i≥0．

1 算法描述

求解問(wèn)題(1)的路徑跟蹤算法的基本思想是通過(guò)產(chǎn)生中心路徑的一個(gè)鄰域中的迭代點(diǎn)列逼近問(wèn)題的解．對(duì)問(wèn)題(1)的近似解(x,z)∈N∞(β)，在當(dāng)前迭代點(diǎn)求解下面的方程組得到迭代方向(Δx,Δz)．

Δz-MΔx=0

(2)

ZΔx+XΔz=γμe-Xz

(3)

其中γ,β是適當(dāng)選取的常數(shù)：γ∈(0,2/3),β∈(0,1)，且γ≤2(1-β)

(4)

記

x(θ)=x+θΔx,z(θ)=z+θΔz,nμ(θ)=x(θ)Tz(θ)

(5)

然后適當(dāng)選取步長(zhǎng)θ*，并取x+=x(θ*)=x+θ*Δx,z+=z(θ*)=z+θ*Δz，作為新的近似解．

下面給出算法步驟：

①選取初始點(diǎn)(x0,z0)∈N∞(β)，按(4)式選取常數(shù)β,γ，允許誤差ε，置k=0;

②若(xk)Tzk≤ε，則停止，否則轉(zhuǎn)步驟③;

③置(x,z)=(xk,zk)，解方程組(2)，(3)得迭代方向(Δx,Δz);

⑤置(xk+1,zk+1)=(xk,zk)+(θ*Δx,θ*Δz),k=k+1,轉(zhuǎn)步驟②.

2 算法的收斂性及迭代復(fù)雜性分析

利用(5)和(3)式，直接計(jì)算可以得到下面兩個(gè)重要關(guān)系式

μ(θ)=(1-θ)μ+θγμ+θ2ΔxTΔz/n

(6)

X(θ)z(θ)-μ(θ)e=(1-θ)(Xz-μe)+θ2ΔXΔz-θ2ΔxTΔze/n

(7)

這里著重指出，對(duì)于線性規(guī)劃，ΔxTΔz=0；對(duì)于凸二次規(guī)劃及單調(diào)線性互補(bǔ)問(wèn)題，ΔxTΔz≥0；但是對(duì)于P*(τ)陣非單調(diào)線性互補(bǔ)問(wèn)題，正如下面的引理1指出的那樣，ΔxTΔz≥某一個(gè)負(fù)數(shù)．從而在收斂性分析中帶來(lái)一系列的困難，無(wú)論是窄鄰域還是寬鄰域，解決這些困難都成為解決問(wèn)題(1)的關(guān)鍵所在．

引理1 設(shè)(x,z)∈N∞(β),(Δx,Δz)是方程組(2)，(3)的解，則有

① 2ΔxTΔz≥-τ‖r‖2

(8)

(9)

引理1的證明用類似于文獻(xiàn)[9]中引理1的證明方法，易證(8)式.

(10)

(11)

(11)式i=1,2,…,n.兩邊累加后，得

‖DΔx‖2+‖D-1Δz‖2+2ΔxTΔz=‖r‖2

(12)

這就證明了(9)式．

引理2 設(shè)(x,z)∈N∞(β),(Δx,Δz)是方程組(2)，(3)的解，β,γ按(4)式取值，則有

(13)

(14)

引理2的證明由(x,z)∈N∞(β)，有0≤(1-β)μ≤xizi≤(1+β)μ,i=1,2,…,n.

再由γ≤2(1-β)，有

再由(9)和(13)式，有

‖ΔXΔz‖≤‖DΔXD-1Δz‖≤‖DΔX‖‖D-1Δz‖=‖DΔx‖∞‖D-1Δz‖≤

即(14)式成立.

①0<[1-(1-γ/2)θ]μ≤μ(θ)≤[1-(1-3γ/2)θ]μ

(15)

②θ‖ΔXΔz-ΔxTΔze/n‖∞≤βγμ/2

(16)

引理3的證明?θ∈(0,θ0]，有θ‖ΔXΔz‖≤θ0‖ΔXΔz‖≤βγμ/2，注意

|ΔxTΔz|/n≤‖ΔXΔz‖∞≤‖ΔXΔz‖，

有

θ2ΔxTΔz/n≥-θ2‖ΔXΔz‖≥-θβγμ/2≥-θγμ/2，θ2ΔxTΔz/n≤θ2‖ΔXΔz‖≤θβγμ/2≤θγμ/2,

將上述2式分別代入(6)式得(15)式．

由于‖ΔXΔz-ΔxTΔze/n‖2=‖ΔXΔz‖2-2(ΔxTΔz)2/n+(ΔxTΔz)2/n≤‖ΔXΔz‖2,

因此θ‖ΔXΔz-ΔxTΔze/n‖∞≤θ‖ΔXΔz‖≤βγμ/2.

引理4 在引理3的條件下，?θ∈(0,θ0]，有(x(θ),z(θ))∈N∞(β)，于是算法步驟④中的θ1≥θ0.

引理4的證明1)?θ∈(0,θ0]，由(7)、(16)、(15)式，注意(x,z)∈N∞(β)，有

‖X(θ)z(θ)-μ(θ)e‖∞≤(1-θ)‖Xz-μe‖∞+θ2‖ΔXΔz-ΔxTΔze/n‖∞≤

(1-θ)βμ+θβγμ/2=[1-(1-γ/2)θ]μ·β≤μ(θ)β,

即

‖X(θ)z(θ)-μ(θ)e‖∞≤μ(θ)β.

2)由所證結(jié)論1)、(15)式及μ(θ)>0，得

?θ∈(0,θ0]，有xi(θ)zi(θ)≥(1-β)μ(θ)>0,i=1,2,…,n

(17)

下面證明必有(x(θ),z(θ))>0.否則(注意(17)式)，?i，?θ2∈(0,θ0],使得xi(θ2)<0,zi(θ2)<0.

由xi(θ2)=xi+θ2Δxi<0,xi>0,θ2>0，知Δxi<0，故?θ3∈(0,θ2],使得xi(θ3)=xi+θ3Δxi=0，這與(17)式矛盾.

3)容易知道，(x(θ),z(θ))滿足z(θ)=Mx(θ)+b.因此最后得到(x(θ),z(θ))∈N∞(β)，于是由算法步驟④中的θ1的定義知，θ1≥θ0.

定理1的證明由(14)式，‖ΔXΔz‖≤(n+τ)μ，注意到βγ/2(n+τ)<1，因此在每次迭代中，有θ0=βγμ/2‖ΔXΔz‖≥βγ/2(n+τ).由算法步驟④中的θ*的定義及(15)式，有

(xk+1)Tzk+1=x(θ*)Tz(θ*)≤x(θ0)Tz(θ0)=nμ(θ0)k≤[1-(1-3γ/2)θ0]nμk≤

[1-((1-3γ/2)βγ)/2(n+τ)](xk)Tzk.

因此

(18)

于是當(dāng)k≥K時(shí)，有l(wèi)og(xk)Tzk≤logε，(xk)Tzk≤ε，即算法的迭代次數(shù)不超過(guò)K.

定理1表明，算法的迭代復(fù)雜性為O((n+τ)log((x0)Tz0ε-1))，與p*(τ)陣的參數(shù)τ有關(guān)．特別當(dāng)τ=0時(shí)(即單調(diào)線性互補(bǔ)問(wèn)題)，則迭代復(fù)雜性為O(nlog((x0)Tz0ε-1)).

3 數(shù)值實(shí)驗(yàn)

本節(jié)討論本文中給出的算法用Matlab語(yǔ)言編程對(duì)幾個(gè)標(biāo)準(zhǔn)的測(cè)試問(wèn)題進(jìn)行測(cè)試，并給出了實(shí)驗(yàn)結(jié)果，見(jiàn)表1和表2．

表1 Murty問(wèn)題及Fathi問(wèn)題的數(shù)值實(shí)驗(yàn)結(jié)果

表2 隨機(jī)產(chǎn)生的P-矩陣數(shù)值實(shí)驗(yàn)結(jié)果

例3.3(產(chǎn)生隨機(jī)的P-矩陣[10]) 由機(jī)器的隨機(jī)數(shù)發(fā)生器產(chǎn)生偽隨機(jī)數(shù)aij∈(-5,5),ηi∈(0.0,0.3),1≤i,j≤n,bij∈(-5,5),1≤i,j≤n,設(shè)A=(aij),B為由bij構(gòu)造的反對(duì)稱矩陣，取M=ATA+B+diag(η),(a)產(chǎn)生偽隨機(jī)數(shù)qi∈(-500,500),1≤i≤n；(b)產(chǎn)生偽隨機(jī)數(shù)qi∈(-500,0),1≤i≤n.

4 結(jié)束語(yǔ)

針對(duì)P*(τ)陣線性互補(bǔ)問(wèn)題，提出了一種新的內(nèi)點(diǎn)算法—寬鄰域路徑跟蹤算法．該算法基于精典線性規(guī)劃路徑跟蹤算法思想，把寬鄰域路徑跟蹤算法推廣到P*(τ)陣非單調(diào)線性互補(bǔ)問(wèn)題，給出了算法的具體步驟，討論了算法的迭代復(fù)雜性．由于P*(τ)陣線性互補(bǔ)問(wèn)題沒(méi)有現(xiàn)成的測(cè)試函數(shù)，自己構(gòu)造一是比較困難，二是不便于與其它算法進(jìn)行比較．因此，本文給出的數(shù)值實(shí)驗(yàn)實(shí)際上是P*(τ)陣線性互補(bǔ)問(wèn)題的一個(gè)特殊問(wèn)題——P-矩陣線性互補(bǔ)問(wèn)題，從實(shí)驗(yàn)的結(jié)果可以看到效果比較理想，也可以預(yù)測(cè)到只要有P*(τ)陣線性互補(bǔ)問(wèn)題的測(cè)試函數(shù)，效果也應(yīng)該比較理想，并且有望推廣到大規(guī)模計(jì)算問(wèn)題上．

參考文獻(xiàn)：

[1] Karmarlcar N.A new polynomial-time algorithm for linear programming[C].Proceedings of the 16th Annual ACM Symposium on the Theory of Computing,1984:302-311.

[2] Karmarlcar N.A new polynomial-time algorithm for linear programming[J].Combindtoricd,1984,4:373-395.

[3] Cottle R W, Pang J S,Stone R E.The linear complementary problems[M].Boston:Acedemic Press,1992.

[4] Kojima M,Megiddo N, Mizuno S.A general framework of continuation methods for complementary problems [J].Mathematics of Operations Research,1993,18(4): 945-963.

[5] Kojima M,Megiddo N,Ye Y.An interior-point potential reduction algorithms for the linear complementary problems[J].Mathematical Programming,1992,54(2):267-279.

[6] 何尚錄，徐成賢.求解一類非單調(diào)線性互補(bǔ)問(wèn)題的路徑跟蹤算法及其計(jì)算復(fù)雜性[J].計(jì)算數(shù)學(xué)，2001,23(3):299-306.

[7] 張莉，王浚嶺，張明望.修正一類非單調(diào)線性互補(bǔ)問(wèn)題的寬鄰域路徑跟蹤算法[J].工程數(shù)學(xué)學(xué)報(bào)，2007，24(4):707-711.

[9] Mizuno S,Todd M J,Ye Y.On adaptive-step primal-dual interior-point algorithms for linear research[J].Mathematics of Operations Research,1993,18:964-981.

[10] Kanzow C. Some noniterior continuation methods for linear complementarity problem[J].SIAM J Matrix Anal,1996,17:851-868.