雍龍泉

(1.陜西理工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院， 陜西 漢中 723000；2.陜西省工業(yè)自動(dòng)化重點(diǎn)實(shí)驗(yàn)室， 陜西 漢中 723000)

絕對(duì)值方程(Absolute Value Equations，AVE)是指：

Ax-|x|=b，

(1)

其中A∈Rn×n，x、b∈Rn，|x|表示對(duì)x的各個(gè)分量取絕對(duì)值。絕對(duì)值方程的研究來(lái)源于兩個(gè)方面，一個(gè)是區(qū)間線性方程，另一個(gè)是線性互補(bǔ)問題。由于任意的線性互補(bǔ)都能轉(zhuǎn)化為絕對(duì)值方程，而絕對(duì)值方程具有簡(jiǎn)單的結(jié)構(gòu)，因此關(guān)于絕對(duì)值方程的研究引起了眾多學(xué)者的關(guān)注[1-2]。其中Rohn[3]在理論方面做出了奠基性的工作，Mangasarian[4-7]在理論和算法方面做出了巨大的貢獻(xiàn)，指出絕對(duì)值方程等價(jià)于雙線性規(guī)劃，并給出了相應(yīng)的求解算法。

近年來(lái)，針對(duì)唯一解的絕對(duì)值方程，求解算法主要有5類：(1)通過(guò)把絕對(duì)值方程轉(zhuǎn)化為線性互補(bǔ)問題進(jìn)行求解[1]；(2)把絕對(duì)值方程轉(zhuǎn)化為一個(gè)非光滑方程，采用廣義牛頓法或非光滑牛頓法進(jìn)行求解[7-10]；(3)通過(guò)光滑處理，絕對(duì)值方程轉(zhuǎn)化為一個(gè)光滑優(yōu)化問題，采用光滑牛頓法求解[11-18]；(4)采用矩陣分裂技術(shù)，求解某些具有特殊結(jié)構(gòu)的絕對(duì)值方程[19-24]；(5)采用神經(jīng)網(wǎng)絡(luò)方法進(jìn)行求解[25-30]。此外，智能優(yōu)化算法近年來(lái)也用于求解絕對(duì)值方程[31]。針對(duì)多個(gè)解的絕對(duì)值方程，可以借助聚類技術(shù)，找到盡可能多的解，該方面研究較多的是具有2n個(gè)解的絕對(duì)值方程[32-34]。此外，針對(duì)多個(gè)解的絕對(duì)值方程，稀疏解的研究目前也成為了一個(gè)熱點(diǎn)[35-37]。

本文選取逼近性質(zhì)較好且不易發(fā)生溢出的一致光滑逼近函數(shù)來(lái)處理絕對(duì)值方程，建立求解無(wú)約束優(yōu)化問題的梯度下降神經(jīng)網(wǎng)絡(luò)模型，并應(yīng)用于求解絕對(duì)值方程和線性互補(bǔ)問題。

文中I表示單位矩陣，‖‖表示2范數(shù)。

1 絕對(duì)值函數(shù)的一致光滑逼近函數(shù)

定義1(光滑逼近函數(shù)) 給定非光滑函數(shù)f(t):R→R，我們稱光滑函數(shù)fμ(t),μ>0為f(t)的光滑逼近函數(shù)，如果?t∈R，存在κ>0，使得

|fμ(t)-f(t)|≤κμ，?μ>0，

如果κ不依賴于t，則稱fμ(t)為f(t)的一致光滑逼近函數(shù)[18,38-40]。

一致光滑逼近函數(shù)可以分為從上方一致逼近和從下方一致逼近。文獻(xiàn)[38-39]給出了絕對(duì)值函數(shù)φ(t)=|t|的多個(gè)一致光滑逼近函數(shù)，為了便于研究，本文選取如下3個(gè)光滑函數(shù)：

下面給出這3個(gè)一致光滑逼近函數(shù)的性質(zhì)[38-39]。

(a) μ=0.4 (b) μ=0.2圖與φ(t)=|t|的圖像

2 絕對(duì)值方程的光滑逼近處理

引理1[1]若A∈Rn×n，且矩陣A的所有奇異值都大于1，則矩陣A可逆，且‖A-1‖<1。

引理2[1](ⅰ)若A∈Rn×n，且矩陣A的所有奇異值都大于1，則?b∈Rn，AVE存在唯一解；

(ⅱ)若A∈Rn×n，且矩陣A滿足‖A-1‖<1，則?b∈Rn，AVE存在唯一解。

引理3[16]若A∈Rn×n，且矩陣A滿足‖A-1‖<1，矩陣D=diag(d1,d2,…,dn)，這里|di|≤1，i=1,2,…,n，則A±D非奇異。

問題(1)等價(jià)于非線性方程組

H(x)=0，

(2)

其中H(x):=Ax-|x|-b。由于H:Rn→Rn是非光滑函數(shù)，以下構(gòu)造一個(gè)光滑函數(shù)Hμ(x)來(lái)逼近非光滑函數(shù)H(x)。

定義2[17]給定非光滑函數(shù)H:Rn→Rn，稱光滑函數(shù)Hμ:Rn→Rn(μ>0)為H的光滑逼近函數(shù)，如果?x∈Rn，存在κ>0，使得

‖Hμ(x)-H(x)‖≤κμ，?μ>0，

如果κ不依賴于x，則稱Hμ為H的一致光滑逼近函數(shù)。

記向量絕對(duì)值函數(shù)φ(x)=|x|=(|x1|,|x2|,…,|xn|)T的每一個(gè)分量為

φ(xi):=|xi|，i=1,2,…,n，

對(duì)每一個(gè)φ(xi)，采用定理1中的光滑函數(shù)

進(jìn)行光滑化處理，就得到向量絕對(duì)值函數(shù)φ(x)的光滑逼近函數(shù)為

φμ(x)=(φμ(x1),φμ(x2),…,φμ(xn))T，

且每一個(gè)分量φμ(xi)滿足

0<φμ(xi)-φ(xi)<μ，i=1,2,…,n。

從而有

于是當(dāng)μ→0時(shí)，φμ(x)一致光滑逼近絕對(duì)值函數(shù)φ(x)。

通過(guò)上面的光滑處理，問題(2)轉(zhuǎn)化為如下光滑方程組：

Hμ(x)=0，

(3)

其中Hμ(x)=Ax-φμ(x)-b，φμ(x)=(φμ(x1),φμ(x2),…,φμ(xn))T。

下面研究光滑函數(shù)Hμ(x)的一些性質(zhì)。

定理2 ?μ>0，Hμ(x)一致光滑逼近H(x)。

證明?μ>0，由于Hμ(x)可微，且滿足

則Hμ(x)一致光滑逼近H(x)。

3 梯度下降神經(jīng)網(wǎng)絡(luò)模型

定義函數(shù)

(4)

稱Eμ(x)為能量函數(shù)。到此，求解絕對(duì)值方程的近似解已經(jīng)轉(zhuǎn)化為求解連續(xù)可微的優(yōu)化問題minEμ(x)。

定理4 ?μ>0，矩陣A滿足‖A-1‖<1，若Eμ(x)=0，則Eμ(x)=0。

證明?μ>0，由于

Eμ(x)=[(x)]THμ(x)，

梯度神經(jīng)網(wǎng)絡(luò)是基于求解問題(4)的最速下降模型的連續(xù)化形式，近年來(lái)已廣泛應(yīng)用于求解非線性互補(bǔ)、二階錐規(guī)劃等問題[41-45]。

下面給出求解光滑優(yōu)化問題(4)的梯度下降神經(jīng)網(wǎng)絡(luò)模型：

(5)

這里參數(shù)τ表示梯度下降算法的步長(zhǎng)。本文直接給出該神經(jīng)網(wǎng)絡(luò)的收斂性結(jié)果，詳細(xì)的證明見文獻(xiàn)[25-27]。

定理5 ?μ>0，矩陣A滿足‖A-1‖<1，神經(jīng)網(wǎng)絡(luò)(5)的平衡點(diǎn)是絕對(duì)值方程的解，反之，絕對(duì)值方程的解是神經(jīng)網(wǎng)絡(luò)(5)的平衡點(diǎn)。

下面采用模型(5)來(lái)計(jì)算一些常見的絕對(duì)值方程，以驗(yàn)證算法的有效性。

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

給出3個(gè)絕對(duì)值方程(前2個(gè)具有唯一解，最后一個(gè)有4個(gè)解)，通過(guò)將其轉(zhuǎn)化為神經(jīng)網(wǎng)絡(luò)模型(5)，采用四階Runge-Kutta法求解微分方程組(對(duì)應(yīng)MATLAB中的函數(shù)ode45)，程序采用MATLAB R2009a編寫。設(shè)置μ=0.01，終止條件Eμ(x)≤1.0×10-10。

算例4.1 考慮絕對(duì)值方程(1)，其中

由于矩陣A的奇異值(SVD(A)=[17.434 9,12.262 9,9.638 9,7.598 4])大于1，因此該AVE問題存在唯一解x*=(1,1,1,1)T。表1給出了參數(shù)τ取不同值的計(jì)算結(jié)果；圖2和圖3分別給出了τ=100時(shí)近似解隨時(shí)間的變化(軌線)及能量函數(shù)隨時(shí)間的變化曲線。

圖2 近似解隨時(shí)間的變化曲線 圖3 能量函數(shù)隨時(shí)間的變化曲線

算例4.2 絕對(duì)值方程(1)中所有奇異值大于1，矩陣A由如下MATLAB命令產(chǎn)生

rand(′state′,0);

R=rand(n,n);

A=R′*R+n*eye(n);

b=(A-eye(n,n))*ones(n,1)。

說(shuō)明：給出矩陣維數(shù)n后，可以用上述代碼產(chǎn)生和本文相同的數(shù)據(jù)，該AVE具有唯一解x*=(1,1,…,1)T。取不同的維數(shù)n，表1給出了參數(shù)τ取不同值的計(jì)算結(jié)果。圖4給出了τ=100時(shí)維數(shù)n取10和50的能量函數(shù)隨時(shí)間的變化曲線。

(a) 10維 (b) 50維圖4 能量函數(shù)隨時(shí)間的變化曲線

參數(shù)τ值tf‖x(tf)-x*‖E(x(tf))算例4.1(唯一解)τ=10.367.241×10-67.132×10-11τ=100.046.876×10-61.425×10-11τ=1000.0046.875×10-61.025×10-12算例4.2(n=10)(唯一解)τ=10.215.157×10-68.938×10-11τ=100.035.187×10-63.834×10-17τ=1000.0035.187×10-63.828×10-17算例4.2(n=50)(唯一解)τ=10.0097.221×10-71.957×10-12τ=100.0017.276×10-71.820×10-14τ=1000.000 17.276×10-71.826×10-14

算例4.3 考慮絕對(duì)值方程(1)，其中

簡(jiǎn)單計(jì)算可得

圖5給出了τ=100時(shí)，初始點(diǎn)在不同象限時(shí)的近似解隨時(shí)間的變化曲線。

圖5 初始點(diǎn)在不同象限時(shí)的收斂曲線

從圖5可以看出，由于該問題的解分布在4個(gè)象限，初始點(diǎn)在哪個(gè)象限，則算法收斂到相應(yīng)象限的解。

5 應(yīng)用于線性互補(bǔ)問題

線性互補(bǔ)問題就是求一個(gè)向量z∈Rn，使得zT(Mz+q)=0，z≥0，Mz+q≥0。這里M∈Rn×n，q∈Rn，線性互補(bǔ)問題簡(jiǎn)記為L(zhǎng)CP(M,q)。文獻(xiàn)[2]中詳細(xì)研究了AVE與LCP(M,q)的轉(zhuǎn)化，指出若1不是矩陣M的特征值，則LCP(M,q)等價(jià)于絕對(duì)值方程(M+I)(M-I)-1x-|x|=((M+I)(M-I)-1-I)q，這里x=(M-I)z+q。

下面把上述方法應(yīng)用于求解線性互補(bǔ)問題，為了便于計(jì)算，取初始點(diǎn)x(0)=(0,0,…,0)T，設(shè)置μ=0.01，終止條件Eμ(x)≤1.0×10-10。

算例5.1 考慮線性互補(bǔ)問題LCP(M,q)，其中

由于1不是矩陣M特征值，因此線性互補(bǔ)可以轉(zhuǎn)化為絕對(duì)值方程Ax-|x|=b，這里A=(M+I)(M-I)-1，b=((M+I)(M-I)-1-I)q；簡(jiǎn)單計(jì)算可得

圖6和圖7給出了τ=100時(shí)，近似解隨時(shí)間的變化(軌線)及能量函數(shù)隨時(shí)間的變化曲線。

圖6 近似解隨時(shí)間的變化曲線 圖7 能量函數(shù)隨時(shí)間的變化曲線

算例5.2 考慮線性互補(bǔ)問題LCP(M,q)，其中

?z，這里z=(z1,z2,z3,z4)T。由于

這里z4前面的系數(shù)為0，因此矩陣M是半正定矩陣[46]；且該線性互補(bǔ)問題具有唯一解z*=(2.5,0.5,0,2.5)T。由于1是矩陣M的特征值，因此令λ=3，則λM的特征值就不為1，且LCP(λM,λq)與LCP(M,q)具有共同最優(yōu)解z*，而LCP(λM,λq)就可以轉(zhuǎn)化為絕對(duì)值方程Ax-|x|=b，這里A=(M+I)(M-I)-1，b=((M+I)(M-I)-1-I)q；簡(jiǎn)單計(jì)算可得

圖8和圖9給出了τ=100時(shí)，近似解隨時(shí)間的變化(軌線)及能量函數(shù)隨時(shí)間的變化曲線。

圖8 近似解隨時(shí)間的變化曲線 圖9 能量函數(shù)隨時(shí)間的變化曲線

算例5.3 考慮線性互補(bǔ)問題LCP(M,q)，其中

矩陣M是半正定矩陣[47]，且該線性互補(bǔ)問題具有唯一解z*=(0,0,…,0,1)T。

取n=4，由于1是矩陣M的特征值，因此令λ=3，則λM的特征值就不為1，且LCP(λM,λq)與LCP(M,q)具有共同最優(yōu)解z*，而LCP(λM,λq)就可以轉(zhuǎn)化為絕對(duì)值方程Ax-|x|=b，這里A=(M+I)(M-I)-1，b=((M+I)(M-I)-1-I)q；簡(jiǎn)單計(jì)算可得

圖10和圖11給出了τ=100時(shí)，近似解隨時(shí)間的變化(軌線)及能量函數(shù)隨時(shí)間的變化曲線。

圖10 近似解隨時(shí)間的變化曲線 圖11 能量函數(shù)隨時(shí)間的變化曲線

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

本文選取逼近性質(zhì)較好且不易發(fā)生溢出的光滑逼近函數(shù)來(lái)處理絕對(duì)值方程，通過(guò)構(gòu)造梯度下降神經(jīng)網(wǎng)絡(luò)模型求解無(wú)約束優(yōu)化問題而得到絕對(duì)值方程的近似解。結(jié)果表明該方法不依賴初始點(diǎn)，且具有收斂快等優(yōu)點(diǎn)。文獻(xiàn)[39]中系統(tǒng)地給出了絕對(duì)值函數(shù)的上方和下方一致光滑逼近函數(shù)，下一步可以通過(guò)改變光滑逼近函數(shù)，以期獲得更好的計(jì)算結(jié)果。