雍龍泉

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

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

Ax-|x|=b，

(1)

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

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

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

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

1 絕對值函數(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]給出了絕對值函數(shù)φ(t)=|t|的多個一致光滑逼近函數(shù)，為了便于研究，本文選取如下3個光滑函數(shù)：

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

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

2 絕對值方程的光滑逼近處理

引理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)等價于非線性方程組

H(x)=0，

(2)

其中H(x):=Ax-|x|-b。由于H:Rn→Rn是非光滑函數(shù)，以下構(gòu)造一個光滑函數(shù)Hμ(x)來逼近非光滑函數(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ù)。

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

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

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

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

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

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

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

從而有

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

通過上面的光滑處理，問題(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ù)。到此，求解絕對值方程的近似解已經(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ù)化形式，近年來已廣泛應(yīng)用于求解非線性互補(bǔ)、二階錐規(guī)劃等問題[41-45]。

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

(5)

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

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

下面采用模型(5)來計算一些常見的絕對值方程，以驗證算法的有效性。

4 數(shù)值實驗

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

算例4.1 考慮絕對值方程(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ù)τ取不同值的計算結(jié)果；圖2和圖3分別給出了τ=100時近似解隨時間的變化(軌線)及能量函數(shù)隨時間的變化曲線。

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

算例4.2 絕對值方程(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)。

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

(a) 10維 (b) 50維圖4 能量函數(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 考慮絕對值方程(1)，其中

簡單計算可得

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

圖5 初始點在不同象限時的收斂曲線

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

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

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

下面把上述方法應(yīng)用于求解線性互補(bǔ)問題，為了便于計算，取初始點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)化為絕對值方程Ax-|x|=b，這里A=(M+I)(M-I)-1，b=((M+I)(M-I)-1-I)q；簡單計算可得

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

圖6 近似解隨時間的變化曲線 圖7 能量函數(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)化為絕對值方程Ax-|x|=b，這里A=(M+I)(M-I)-1，b=((M+I)(M-I)-1-I)q；簡單計算可得

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

圖8 近似解隨時間的變化曲線 圖9 能量函數(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)化為絕對值方程Ax-|x|=b，這里A=(M+I)(M-I)-1，b=((M+I)(M-I)-1-I)q；簡單計算可得

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

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

6 結(jié)束語

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