求解非線性互補問題的松弛模系矩陣分裂算法

謝水連

(嘉應學院 數學學院,廣東 梅州 514015)

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

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

(1)

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

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

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

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

1 算法及其收斂性

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

(2)

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

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

(3)

即

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

(4)

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

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

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

(5)

得到xk+1,并令

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

其中D,-L,-U分別是矩陣A的對角、嚴格下三角和嚴格上三角部分. 此時，算法1稱為松弛模系AOR法. 特別地，分別取α=β,α=β=1及α=1,β=0,相應的算法分別稱為松弛模系SOR方法、松弛模系Gauss-Seidel方法及松弛模系Jacobi方法.

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

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

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

(6)

由方程(5)得

因此，

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

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

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

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

證明設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*))-

因為Ω+M非奇異, 所以

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

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

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

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

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

進一步地，可得

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

其中

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

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

因此，當ρ(Δ(R))<1時算法1收斂.

2 數值實驗

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

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

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

得到xk+1,并令

在實驗中，我們選擇與文獻[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是一個n×n矩陣,H和I是t×t矩陣，n=t2,Φ(u)=(Φi(ui))是一個對角映射,Φi(ui)=arctan(ui)且q=(-1,1,-1,1,…)T.

我們考慮兩種分裂：

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

表2 采用算法1求解問題1的數值結果

表3 采用算法2求解問題2的數值結果

表4 采用算法1求解問題2的數值結果

3 結語

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