一種解決非光滑非凸優化問題的暫態混沌神經網絡

喻 昕，汪炎林，徐柳明，伍靈貞

(廣西大學 計算機與電子信息學院，南寧 530004)

1 前 言

在科學與工程應用中，優化問題作為一類重點問題在最近幾十年內得到了廣泛的關注與發展.在1986年，由Hopfield 和 Tank[1]提出一種Hopfield神經網絡(Hopfield Neural Network,HNN)作為解決優化問題的并行計算模型，引起了大家的興趣并開始廣泛應用.Zhang等人[2]利用Lagarange乘子法創建了一個新的遞歸神經網絡來處理凸光滑非線性優化問題，Xia等人[3]提出了基于投影方法的遞歸神經網絡用以解決光滑凸(偽凸)優化問題.

不久后，應用范圍從光滑問題發展到非光滑優化問題，如Li等人[4]在基于Clark次梯度的遞歸神經網絡模型之中引入投影方法以解決n上閉凸子集的非凸非光滑優化問題.Liu等人[5]嘗試投影方法建立遞歸神經網絡模型解構線性等式和n上閉凸子集共同約束的非光滑非凸優化問題.Bian等人[6]也開始利用光滑遞歸神經網絡來解決非光滑非凸的優化問題，使用光滑逼近技術即用一個與目標函數逼近的光滑函數構造光滑神經網絡模型.Yu等人[7]基于微分包含的思想，建立了一個不依賴罰參數的神經網絡模型用以解決非光滑非凸優化問題.

然而上述的模型的本質仍是基于“梯度”或“次梯度”下降的動力系統，無法避免“陷入”局部最優解.尤其是當優化的目標函數是非凸時會存在多處局部最優解，這將無法保證獲得全局最優解.

為了解決這個問題，Aihara等人[8]受生物神經元混沌特性的啟發，于1990年在HNN中增加一個自反饋項以引入混沌機制開創了混沌神經網絡(Chaotic Neural Network,CNN).此后，Chen和Aihara[9]將模擬退火優化算法引入到CNN中提出了暫態混沌神經網絡(Transiently Chaotic Neural Network,TCNN).TCNN的動力系統對自反饋鏈接權值敏感，它可以類比模擬退火算法中一直衰減的溫度.當“溫度”較大時，整個系統處于“粗搜索”階段,搜索過程符合混沌動態的特性，會按照混沌軌道進行遍歷，并且不受目標函數的限制，能克服陷入局部最優解；當“溫度”開始減少并達到一定程度時，系統進入“細搜索”階段，這時的自反饋權值對系統的影響變得很小，這時的神經網絡類似于HNN，以粗搜索得到的解為初始點，根據HNN梯度下降機制在小范圍進行搜索，并收斂到一個平衡點，最終TCNN會收斂到一個全局最優解.

TCNN提出后，不少學者對此展開研究.文獻[10，11]分別將TCNN應用于解決組播路由和蜂窩信道分配等組合優化問題；Zhang等人[12]利用小波函數作為激活函數的TCNN來解決函數優化問題；Babak等人[13]利用TCNN改進了反應曲面法在函數優化問題中應用的性能.

借助腦電波的生物機制，分析不同頻率的正弦信號疊加形成的腦電波模型,Hu等人[14]用變頻正弦(Frequency Conversion Sinusoidal,FCS)函數與 Sigmoid 函數加權和作為混沌神經元的激勵函數,建立了一個新的神經網絡模型 —變頻正弦混沌神經網絡(Frequency Conversion Sinusoidal Chaotic Neural Network,FCSCNN)模型，并在文獻[15，16]進一步分析和優化了這種新的模型.

綜上，為了解決非凸非光滑優化問題，本文提出一個能收斂到優化問題關鍵點集的遞歸神經網絡，并在此基礎上構建了一個暫態混沌神經網絡，用于實現非凸優化問題的全局尋優.

2 預備知識

考慮如下問題:

minf(x)s.t.g(x)≤0Ax=b

(1)

當x=(x1,x2,…,xn)T∈n，f:n→，目標函數是正則的，但可以是非凸的和非光滑的，g(x)=(g1(x),g2(x),…,gp(x))T:n→p是p-維向量值函數，gj(x)(j=1,2,…,p)是凸的，但可能是非光滑的，A∈m×n是滿行秩矩陣，而且b=(b1,b2,…,bm)T∈m.我們假設優化問題(1)具有至少一個局部最小解.

定義：

S1={x:g(x)≤0}

S2={x:Ax=b}

則S=S1∩S2，S={x∈n:g(x)≤0,Ax=b}是優化問題(1)的可行域.

為便于后續的證明，首先給出下面兩個假設：

這里:

J+(x)={j∈{1,2,…,p}:gj(x)>0}J0(x)={j∈{1,2,…,p}:gj(x)=0}

定義1.若對于集合E?Rn上的任意點x，都存在一個非空集合F(x)?Rn，則x→F(x)是E→Rn上的集值映射.若對于任意的開集V?F(x0)，都有一個相應的鄰域U，使得F(U)?V，則稱集值映射F:E→Rn在點x0∈E是上半連續.

定義2.如果存在正整數k，ε，對任意的x1,x2∈x+εB(0,1)，|f(x1)-f(x2)|≤k(x1-x2)成立，則稱函數f:Rn→R在x∈Rn附近是Lipschitz的，如果f在其定義域每一個點的附近都是Lipschitz的，則稱f為局部Lipschitz的.

定義3.如果f:Rn→R在Rn上是局部Lipschitz的，則f在點x沿方向v∈Rn的廣義方向導數為：

如果f0(x;v)是有定義且有限的，f在x處的次微分可以定義為：

?f(x)={ξ∈Rn:f0(x;v)≥,?v∈Rn}

引理1(鏈式法則).

本文提出的神經網絡動力學模型:

(2)

這里α是一個正比例罰參數，I是一個單位矩陣，P=AT(AAT)-1A.

函數β(t)是一個單調非減的函數，其形式如下：

tS2為進入可行域S2的時間上限.

3 收斂性分析

1)有限時間收斂到S2

定理1.若假設1,2成立，則從任意點x0∈Rn出發，神經網絡(2)的狀態向量將在有限時間收斂進S2，其后不再離開.

證明：令K(x)=‖Ax(t)-b‖1，則K(x)是正則函數且?K(x)=ATh(Ax(t)-b).根據鏈式法則，存在ψ(t)∈h(Ax(t)-b)，θ(t)∈?f(x)，σ(t)∈?D(x)，使得:

由于A(I-P)=A-AAT(AAT)-1A=0,AAT是正定矩陣，則：

這里λm是矩陣AAT的最小特征值.由于A是行滿秩矩，所以λm(AAT)>0.對于任意x(t)?S2，根據函數h(x)的定義可知‖ψ(t)‖2≥1，因此:

(3)

若存在tS2

K(x(tS2))-K(x0)≤-λm(AAT)tS2

2)狀態變量x(t)有界

證明：第1步：當t∈[0,tS2]，β(t)=0神經網絡(2)可以寫成:

(4)

根據鏈式法則，存在ψ(t)∈h(Ax(t)-b)，使得：

第2步：當t>tS2，由定理1可知，x(t)將在有限時間內收斂到S2，其后不再離開，且進入的時間上限為tS2.所以對t>tS2，有β(t)=1，x(t)∈S2，Ax(t)=b，神經網絡(2)可以寫成:

(5)

根據鏈式法則，存在θ(t)∈?f(x)，σ(t)∈?D(x)，使得:

當x(t)∈S2S1，因為‖(I-P)θ(t)‖≤‖θ(t)‖，結合引理2，有:

此外，因為神經網絡(2)的右邊部分是上半連續，且為非空緊凸值。因此在t∈[0,T)，對于初始條件x(0)=x0，神經網絡(2)至少存在一個局部解x(t).

結合定理2和解的可擴展理論，局部解可以從t∈[0,T)擴展到t∈[0,+)，即神經網絡(2)存在全局解.

3)有限時間收斂到S

因(I-P)2=I-P，(I-P)T=I-P，根據鏈式法則,存在θ(t)∈?f(x)，σ(t)∈?D(x)，使得:

將上式兩邊從tS2到t進行積分，得到:

D(x(t))≤D(x(tS2))-ε0(t-tS2)

(6)

當t≥D(x(tS2))/ε0+tS2時，D(x(t))≤0.

而D(x(t))≥0且有上界，結合{x:D(x(t))≤0}=S1，說明x(t)會在一定時間內進入S1，即進入可行域S.類似定理1，可證明神經網絡的狀態變量x(t)在進入S后，不再離開.綜上，定理3證畢.

4)神經網絡的精確性

定義4.優化問題的關鍵點集合C為C={x∈S:0∈?f(x)+NS(x)}，其中NS(x)是x在可行域S上的法錐.

證明：由定理3可知，x(t)會進入S，并停留其中，不妨令x0∈S，則x(t)∈S，Ax(t)=b，β(t)=1，?D(x(t))=0.

(7)

其中θtn∈?f(xtn)，σtn∈?D(xtn).

因為?f(x)，?D(x)是上半連續的集值映射，可知:

那么，可以得出:

(8)

(9)

綜上，神經網絡(2)的任一聚點都是優化問題(1)的關鍵點，定理4得證.

5)收斂到C

證明：在定理4證明過程中得到，對于x0∈S，S有界，則f(x(t))有界.

假定:

對任意x(t)∈W，有0?κ(x(t)).因為κ(x(t))是緊凸集，則在W上存在最大值于最小值，分別表示為：

對任意時間間隔t∈[tn,tn+τ]，x(t)∈W，有0≤τ≤k/(4MW)，結合式(7)，有:

4 暫態混沌神經網絡

若假設1,2成立，在神經網絡(2)的基礎上，引入文獻[14]的FCSCNN模型，提出一種解決非光滑非凸優化問題的暫態混沌神經網絡.

(10)

yi(t+1)=kyi(t)+λ(t){-(I-P)[?f(x)+α‖?f(x)‖?D(x)]-ATh(Ax-b)}-zi(t)(xi(t)-I0)

(11)

zi(t+1)=(1-β1)zi(t)

(12)

(13)

(14)

S2(yi(t),ε2)=A(0)·exp(-u1|yi(t)|)· sin(yi(t)/(ε2·exp(-u2|yi(t)|)))

(15)

其中：

yi(t)為神經元內部狀態；

xi(t)為神經元輸出；

zi(t)神經元自反饋連接權值；

ω是輸出比例系數，控制著函數的輸出范圍；

ε1為 Sigmoid 函數的陡度參數，ε2為FCS函數的陡度參數；

k為神經隔膜的阻尼因子；

λ(t)為正值縮放因子；

I0為正值參數；

β1為z(t)的退火衰減因子,β2為λ(t)的退火衰減因子.

相對于神經網絡(2)，暫態混沌神經網絡可以看成在神經網絡(2)的單層神經網絡基礎上擴展成多層神經網絡，所以對應的輸入輸出函數會有相應的調整.

式(11)表示神經元內部狀態，同時也是神經網絡的輸入層,其中大括號內的部分為遞歸神經網絡，參數定義與神經網絡(2)相同。由于暫態混沌神經網絡的特性，初始點的選取范圍是n，即從神經網絡(2)的擴展到無限制，這對神經網絡的性能來說是一個提升.

式(12)是神經元自反饋連接權值，控制著神經網絡的混沌狀態的發生與結束.

式(13)是神經網絡(2)的系數，控制著遞歸神經網絡對混沌的影響.λ(t)一般需要一個較大的初始值保證足夠的影響.由于考慮的優化問題是非凸的，為了防止輸出變量的波動，所以需要讓系數逐步縮小以保證能最終收斂到最優點，所以用β2為退火衰減因子來控制λ(t)的縮小.

式(15)表示FCS函數，表示的是不同頻率正弦信號疊加的腦電波模型.將Sigmoid函數(式(14))與FCS函數的加權和作為混沌神經元的激勵函數(式(10))，作用是非單調化激勵函數，得到更豐富的混沌特性，并且讓激勵函數更加接近真實生物神經元的激活抑制模型同時還能滿足腦神經不同活躍狀態的特點.yi(t)為函數自變量,表示腦電波活動的強弱;A(0)為正弦函數的幅值;ε2為正弦函數的陡度參數,控制著正弦函數頻率;u1,u2均為正值參數；ε1為Sigmoid函數的陡度參數，c為FCS函數的比例系數(c≥0).令ε1=10，A(0)=0.8，ε2=0.02，u1=6，u2=1，c=0.5，S1(t)與x(t)的函數圖像如圖1所示.

圖1 Sigmoid和Sigmoid+0.5FCS激勵函數曲線對比Fig.1 Comparison of excitation function curves between sigmoid and sigmoid + 0.5FCS

圖1(a)為Sigmoid函數，圖1(b)為Sigmoid+0.5FCS函數，通過圖1的對比能看出，相對于最常見的激勵函數Sigmoid函數，加入FCS函數后的激勵函數不僅有著很強的非單調性，還表現出了Sigmoid函數的生物學特性，這意味著新的暫態混沌神經網絡的神經元動力特性更好，混沌的程度更高，這決定了新的神經網絡模型具備更好的全局尋優能力.

新的暫態混沌神經網絡與HNN的優化機制類似，將優化問題的目標函數當做能量函數，之后的神經網絡的動力學演化過程便是能量函數的全局尋優過程，當神經網絡最終能收斂到一個穩定點時，與之相對神經元的輸出結果就是優化問題的(最優/次優)解.

表1 與現有神經網絡性能對比Table 1 Performance comparison with existing neural networks

通過表1可以看出，本文不需如文獻[5]一樣初始點受限，雖然本文可行域有界，但是本文有著其他參考文獻不具有的全局尋優能力，且可行域有界是全局尋優能力的保障.

接下來將通過仿真實驗來驗證本文提出的暫態混沌神經網絡的全局尋優能力.

5 仿真實驗

為了驗證本文提出的神經網絡的性能，在Matlab2012a平臺上，用仿真實驗來驗證神經網絡(2)和本文提出的暫態混沌神經網絡的表現.

例1.

minf(x)=-0.25x12+1.2x22+0.1x1x2+2x1-2x2s.t.g1(x)=-x1+x2-2≤0g2(x)=x1-2x2-2≤0g3(x)=-x1x2≤0x1+2x2=3

(16)

在例1中，f(x)和g3(x)非凸，但把x1=-2x2+3帶入后，f(x)和g3(x)在可行域上為凸函數，且可行域有界，那么優化問題(16)有唯一全局最優點x*=(0,1.5)T且能用神經網絡(2)解決.

圖2 神經網絡(2)在優化問題(16)的運行軌跡圖Fig.2 Transient behaviors of neural network(2)in optimization problem(16)

例2.

(17)

容易看出優化問題(17)中，可行域有界，且在可行域上，f(x)非凸，并有著多個關鍵點.

令步長l=0.001，α=3，選取2個不同的初始點(-3,5)T，(-3,-1)T，神經網絡(2)最終分別收斂到(-2.9839,2.9859)T，(0.001,0.001)T，收斂軌跡如圖3、圖4所示.

圖3 神經網絡(2)在初始點為(-3,5)T的軌跡圖Fig.3 Transient behaviors of neural network (2) with initial point (-3,5)T

從圖3、圖4可以看出，神經網絡(2)在非凸優化問題上有著一定的收斂能力，但是缺乏全局尋優能力.同樣的問題在文獻[5-7]的模型上也存在，選初始點(-3,5)T，文獻[7]的模型的軌跡圖如圖5，能看出這個模型也沒有全局尋優能力.那么，在優化問題(17)上對本文提出的暫態混沌神經網絡進行測試.

對例2，在本文提出的暫態混沌神經網絡中選取參數如下：

圖4 神經網絡(2)在初始點為(-3,-1)T的軌跡圖Fig.4 Transient behaviors of neural network (2) with initial point (-3,-1)T

圖5 文獻[7]的模型在初始點為(-3,5)T的軌跡圖Fig.5 Trajectories of the model in [7] at the initial point (-3,5)T

選神經網絡(2)未能收斂到最優點的初始點(-3,5)T，令z1(1)=z2(1)=3,λ(0)=0.5.運行結果見圖6，最終收斂到點(2.372×10-4,2.372×10-4)T，可以看成收斂到全局最優點.

圖6 Fig.6

通過圖6(a)，圖6(b)可以看出，神經網絡的輸出值x1,x2在前期的“粗搜索”過程中體現了明顯的混沌搜索的遍歷性，偽隨機性的特點，在160步時已收斂到最優解附近，而圖6(c)則展示了神經網絡的能量函數f(x)在經過前期的混沌搜索后，約在同時收斂到最低點附近，并且馬上穩點在最低點.這種準確，快速的尋優效果很好的證明了本文提出的暫態混沌神經網絡在函數優化方面的全局尋優能力.

圖7 Fig.7

6 總 結

本文提出了一種新型的遞歸神經網絡方法，用來解決帶有不等式約束以及等式約束的非光滑非凸優化問題.對神經網絡的準確性與收斂性進行了嚴謹的理論分析，并通過仿真實驗驗證了神經網絡的性能.為實現神經網絡的全局尋優，在遞歸神經網絡的基礎上構建了一個新的暫態混沌神經網絡，并放開了遞歸神經網絡對初始點的限制.通過仿真實驗，驗證了當可行域有界時，暫態混沌神經網絡具有一定的全局尋優能力.