謝水連

(嘉應(yīng)學(xué)院 數(shù)學(xué)學(xué)院,廣東 梅州 514015)

本文考慮非線性互補(bǔ)問題(nonlinear complementarity problem, NCP)：尋找u∈Rn使得

u≥0,v=F(u)≥0,uTv=0,

(1)

其中:函數(shù)F(u)的形式為F(u)=Au+Φ(u)+q，這里A=(aij)∈Rn×n是一個(gè)大規(guī)模的稀疏矩陣，q是一個(gè)n維向量,Φ:Rn→Rn是一個(gè)對(duì)角可微映射，即Φ的第i個(gè)分量Φi僅是u的第i個(gè)分量ui的函數(shù):

Φi=Φi(ui),i=1,2,…,n.

顯然, 若Φ是線性函數(shù),則問題(1)就退化為線性互補(bǔ)問題 (linear complementarity problem, LCP).

問題(1)被稱為帶非線性源項(xiàng)的非線性互補(bǔ)問題.該問題在金融、交通運(yùn)輸?shù)阮I(lǐng)域中有廣泛應(yīng)用，見文獻(xiàn)[1-2]. 此問題引起了眾多學(xué)者的廣泛關(guān)注并得到了深入研究. 已有許多關(guān)于求解該問題的算法，如區(qū)域分解算法[3-4]、罰函數(shù)法[5-7]及半光滑Newton法[8]等. 值得注意的是現(xiàn)有的大多數(shù)算法都需要求解線性互補(bǔ)子問題.

1 算法及其收斂性

(Ω+M)x=Nx+(Ω-A)|x|-

(2)

令R∈Rn×n是一個(gè)松弛矩陣. 由恒等式Rx-Rx=0知, 方程(2) 等價(jià)于

(Ω+M)x=Nx+(Ω-A)|x|+R(x-x)-

(3)

即

(Ω+M-R)x=(N-R)x+(Ω-A)|x|-

(4)

基于方程(4),我們給出下列求解非線性互補(bǔ)問題(1)的松弛模系矩陣分裂迭代算法.

算法1令A(yù)=M-N是矩陣A的一個(gè)分裂，Ω是一個(gè)正對(duì)角矩陣，R是一個(gè)松弛矩陣,h是一個(gè)正常數(shù). 給定初始向量x0∈Rn, 對(duì)k=0,1,2,…,求解線性系統(tǒng)

(Ω+M-R)xk+1=(N-R)xk+(Ω-A)|xk|-

(5)

得到xk+1,并令

顯然，當(dāng)R=0時(shí)，算法1就退化為文獻(xiàn)[13]中的算法2.1. 從后面的數(shù)值實(shí)驗(yàn)可以看出，適當(dāng)選擇矩陣R可以使模系矩陣分裂算法能夠更快地收斂到問題的解. 算法1給出了求解非線性互補(bǔ)問題的松弛模系矩陣分裂的一般框架，通過選擇不同的矩陣分裂可以得到一些具體的分裂算法. 例如，令

其中D,-L,-U分別是矩陣A的對(duì)角、嚴(yán)格下三角和嚴(yán)格上三角部分. 此時(shí)，算法1稱為松弛模系A(chǔ)OR法. 特別地，分別取α=β,α=β=1及α=1,β=0,相應(yīng)的算法分別稱為松弛模系SOR方法、松弛模系Gauss-Seidel方法及松弛模系Jacobi方法.

現(xiàn)在給出算法1收斂的2個(gè)充分條件.

當(dāng)δ(R)<1時(shí)，對(duì)任何初始向量x0∈Rn, 由算法1產(chǎn)生的序列{xk}收斂到方程(2)的解x*.

證明設(shè)x*是方程(2)的解，由方程(4)及Ω+M-R非奇異, 可得

(6)

由方程(5)得

因此，

顯然，若δ(R)<1， 則算法1收斂. 證畢.

Δ(R)=(I-|(Ω+M)-1R|)-1×

(|(Ω+M)-1N|+|(Ω+M)-1(Ω-A)|+

當(dāng)ρ(Δ(R))<1時(shí)，對(duì)任何初始向量x0∈Rn, 由算法1產(chǎn)生的序列{xk}收斂到方程(2)的解x*.

證明設(shè)x*滿足方程(3). 將方程(5)改寫為

(Ω+M)xk+1=Nxk+(Ω-A)|xk|+

于是

(Ω+M)(xk+1-x*)=

N(xk-x*)+(Ω-A)(|xk|-|x*|)+

R((xk+1-x*)-(xk-x*))-

因?yàn)棣?M非奇異, 所以

(Ω-A)(|xk|-|x*| )+

|(Ω+M)-1N||xk-x*| +

|(Ω+M)-1(Ω-A)||xk-x*| +

|(Ω+M)-1R||xk+1-x*| +

|(Ω+M)-1R||xk-x*| +

進(jìn)一步地，可得

|xk+1-x*| ≤Δ(R)|xk-x*| ,

其中

Δ(R)=(I-|(Ω+M)-1R|)-1×

(|(Ω+M)-1N|+|(Ω+M)-1(Ω-A)|+

因此，當(dāng)ρ(Δ(R))<1時(shí)算法1收斂.

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

本節(jié)測(cè)試所提出算法的有效性. 程序用 MATLAB編寫并在一臺(tái)3.4 GHz CPU，8.00G RAM電腦上實(shí)現(xiàn). 我們測(cè)試兩個(gè)問題并與文獻(xiàn)[13]中的算法進(jìn)行比較.

算法2[13]令A(yù)=M-N是矩陣A的一個(gè)分裂，Ω是一個(gè)正對(duì)角矩陣，h是一個(gè)正常數(shù). 給定初始向量x0∈Rn, 對(duì)k=0,1,2,…,求解方程

(Ω+M)xk+1=(N)xk+(Ω-A)|xk|-

得到xk+1,并令

在實(shí)驗(yàn)中，我們選擇與文獻(xiàn)[13]相同的Ω和h, 即Ω=I,h=1. 算法1中的R取為-I.

問題1考慮系統(tǒng)(1), 令F(u)=Au+Φ(u)+q, 其中

問題2考慮系統(tǒng) (1), 令F(u)=Au+Φ(u)+q, 其中

A是一個(gè)n×n矩陣,H和I是t×t矩陣，n=t2,Φ(u)=(Φi(ui))是一個(gè)對(duì)角映射,Φi(ui)=arctan(ui)且q=(-1,1,-1,1,…)T.

我們考慮兩種分裂：

(ⅰ) 取M=A,N=0,此時(shí)分別記算法2和算法1為MI和NMI;

表2 采用算法1求解問題1的數(shù)值結(jié)果

表3 采用算法2求解問題2的數(shù)值結(jié)果

表4 采用算法1求解問題2的數(shù)值結(jié)果

3 結(jié)語

本文通過引入松弛變量，提出求解一類非線性互補(bǔ)問題的模系矩陣分裂算法. 在適當(dāng)?shù)臈l件下，建立了算法的收斂性理論. 與已有算法相比，所提出的算法在數(shù)值效果上有了極大改進(jìn). 接下來還有許多問題值得進(jìn)一步研究，如可以考慮將此算法推廣到其他類型的非線性互補(bǔ)問題、隱互補(bǔ)問題、帶M函數(shù)的非線性互補(bǔ)問題等.另外，可以結(jié)合多重分裂算法設(shè)計(jì)求解非線性互補(bǔ)問題的松弛模系多重分裂算法.