改進的正弦余弦算法求解廣義絕對值方程的最小一范數(shù)解

雍龍泉賈 偉 , 黎延海

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

廣義絕對值方程是指

Ax+B|x|=b，

針對多個解的廣義絕對值方程，尋找稀疏解及最小一范數(shù)解已成為當前的一個研究分支[18-19].廣義絕對值方程的稀疏解即求解如下零范數(shù)優(yōu)化問題

(1)

其中，‖x‖0表示向量x中非零元素個數(shù).零范數(shù)優(yōu)化是一個NP-hard問題，通常的做法是采用凸松弛技巧，把稀疏解問題L0(x)轉(zhuǎn)化為如下L1(x)范數(shù)優(yōu)化

(2)

L1(x)范數(shù)優(yōu)化問題是一個凸優(yōu)化，在一定條件下，L1(x)范數(shù)優(yōu)化問題的解恰好就是原問題L0(x)的稀疏解.因此研究求解L1(x)范數(shù)優(yōu)化具有重要的意義.

求解問題(2)可以采用約束優(yōu)化算法、交替方向法等.筆者采用一種新型的群智能優(yōu)化算法：正弦余弦算法(Sine Cosine Algorithm, 簡稱SCA)來尋找廣義絕對值方程盡可能多的解，進而在其中選取最小一范數(shù)的解.

1 適應(yīng)值函數(shù)的建立

文獻[19]中給出了具有多個解的廣義絕對值方程，并指出廣義絕對值方程解的存在性不僅與矩陣A，B有關(guān)，與向量b也有關(guān).針對具有多個解的廣義絕對值方程，為了采用智能算法求得最小一范數(shù)解，定義智能算法的適應(yīng)值函數(shù)

(3)

作為優(yōu)化目標函數(shù)，當且僅當f(x)=0時，則找到廣義絕對值方程的解.通過多次執(zhí)行算法，就有可能找到廣義絕對值方程盡可能多的解，再從中選取一范數(shù)最小的解.因此，問題的關(guān)鍵還是求解(3).

2 正弦余弦算法

SCA是一種新型的群智能優(yōu)化算法，由澳大利亞學(xué)者 Mirjalili 于 2016 年提出[20].

SCA算法步驟：

設(shè)置參數(shù): 種群大小N，優(yōu)化問題維數(shù)D，常數(shù)a=2，迭代次數(shù)Tmax；在可行域中隨機選取N個個體組成初始種群；t=1；計算當前每個個體的函數(shù)值，并記錄最優(yōu)個體位置P(t)；

while (t

fori= 1 toNdo

forj= 1 toDdo

根據(jù)式r1=a-at/Tmax計算r1的值；

(4)

ifr4< 0.5

；

(5)

else

；

(6)

end if

end for

end for

對每一個新的個體檢驗是否在可行域內(nèi)；若不在可行域內(nèi)則做越界處理；

計算每個個體的適應(yīng)值并更新種群的最優(yōu)個體位置P(t)；t=t+1；

end while

SCA算法的特點是基于正弦函數(shù)(5)和余弦函數(shù)(6)值的震蕩變化來達到尋優(yōu)目的.在SCA算法中，參數(shù)有r1，r2，r3，r4；r1控制算法從全局搜索到局部開發(fā)的轉(zhuǎn)換，r1逐漸減小；當r1>1時，函數(shù)r1sin(r2)與r1cos(r2)值才有可能大于1或者小于-1；當r1≤1時，函數(shù)r1sin(r2)與r1cos(r2)值必在-1和1之間[21].SCA算法設(shè)計原理，當|r1sin(r2)|>1或者|r1cos(r2)|>1時，算法進行全局搜索；當|r1sin(r2)|≤1或者|r1cos(r2)|≤1時，算法進行局部開發(fā)，如圖1所示.

3 改進的正弦余弦算法

SCA提出至今已經(jīng)3年多，發(fā)展迅猛，更多的SCA算法見文獻[22-25].參數(shù)r1線性遞減，控制著算法的搜索過程.因此，對控制參數(shù)r1的改進需要進一步研究，可以進一步考慮非線性遞減的函數(shù)，如拋物線函數(shù)、指數(shù)函數(shù)等來改進r1.

表1中給出了更多參數(shù)r1的表達式.圖2～3給出了r1的圖像.

表1 控制參數(shù)r1的表達式

4 數(shù)值算例

將2個廣義絕對值方程的算例轉(zhuǎn)化為無約束優(yōu)化(3)，采用SCA和ISCA算法求解，程序用MatlabR2009a編寫，參數(shù)設(shè)置N=30,a=2,Tmax=10 000，例1和2搜索空間為-7≤xi≤7.

例1 考慮廣義絕對值方程:Ax+B|x|=b，, 其中

分別采用SCA與ISCA計算可知該問題的2個解為

其中，x(1)為最小一范數(shù)解.

2種算法都能獲得該問題的最小一范數(shù)解，圖3給出了2種算法的收斂性曲線.

例2 考慮廣義絕對值方程:Ax+B|x|=b，其中

分別采用SCA與ISCA計算可知該問題的4個解為

其中，x(2)為最小一范數(shù)解.

2種算法都能獲得該問題的最小一范數(shù)解，圖4給出了優(yōu)化問題目標函數(shù)的圖像及2種算法的收斂性曲線.

綜合圖3和圖4可知，相同條件下，ISCA算法收斂優(yōu)于SCA.最小一范數(shù)解與稀疏解具有一定的內(nèi)在關(guān)系，但是二者并不等價.已有結(jié)果表明在有限等距性質(zhì)(Restricted Isometry Property, RIP)和有限等距常數(shù)(Restricted Isometry Constant, RIC)條件下，最小一范數(shù)解和稀疏解的等價性[26-27].因此,通過研究最小一范數(shù)解，可以為研究稀疏解提供一些近似結(jié)果.