遞歸神經網絡方法解決非光滑偽凸優化問題

喻 昕 胡 悅 馬 崇 伍靈貞 汪炎林

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

0 引 言

近年來，由于人工神經網絡內在的大規模并行機制以及快速執行的硬件結構，其執行效率顯著優于傳統優化算法，這讓使用人工神經網絡解決優化問題成為了當下的熱門研究對象。運用神經網絡求解最優化問題，首先要將目標函數改換成相關動力學模型，進而構造出解決該問題的神經網絡模型。神經網絡是由Tank等[1]最先應用到優化問題的。自此，研究者們開始構造更多模型用于解決優化問題。

目前，關于最優化問題的研討大都局限于光滑優化問題，然而，在實際應用問題的研究上，逐漸出現了很多非光滑問題。因此學者們設計了很多解決非光滑優化問題的方法，文獻[2]通過微分包含的思想創建了一個新型模型用以解決非光滑優化問題。文獻[3]構造了一個遞歸雙層模型來解決非光滑凸優化問題，該模型雖不含懲罰算子，但是層次稍顯復雜。

凸優化問題[3-7]在許多問題上具有非常廣泛的使用背景，但是隨著更深入的研究，學者們逐漸發現非凸優化問題在工程問題中有著更好的應用。因此，部分學者成功構造了可以解決目標函數為非凸的相關問題的模型。如文獻[8]根據梯度思想創建了一種神經網絡模型用以解決非光滑非凸問題，該模型結構簡單，但是需要一個懲罰算子，這限制了該模型的使用范圍。

偽凸優化問題為非凸優化問題的一類，也成了熱門研究對象[9-13]。為了解決非光滑偽凸優化問題，文獻[9]創建了一個層次僅為一層不需要提前計算懲罰算子的新型神經網絡模型， 但是這個模型需要很強的假設條件，且僅僅可以解決帶有等式約束的問題，這就大大減少了其應用范圍。為了解決同時具備等式約束以及方體約束且目標函數是偽凸的優化問題，文獻[10]應用懲罰函數創建了一個層次僅為一層神經網絡模型，該模型能夠較好的收斂，但需要用到懲罰算子，這在實際計算中是很難解決的。為了能夠不用計算懲罰算子，文獻[11]提出了一種新型且不帶懲罰參數的單層模型，并得出了該單層模型的解在一定的條件下可以在一定時間內收斂到可行域的結論，該模型可以較好的收斂，但是需要目標函數存在下界等條件。

本文創建了一種新型的遞歸神經網絡模型，該模型包括以下優點：(1)可以求解目標函數為非光滑且偽凸的問題；(2)模型結構簡單，為單層遞歸神經網絡；(3)不依賴于懲罰參數；(4)可以求解同時帶等式約束和不等式約束的問題。

本文將研究下面的非光滑偽凸優化問題：

minf(x)

s.t.Ax=bg(x)≤0

(1)

式中：x=(x1,x2,…,xn)T∈Rn，A∈Rm×n是行滿秩矩陣，b=(b1,b2,…,bm)T∈Rm，f(x):Rn→R是偽凸函數且局部Lipschitz連續，gi(x):Rn→R是凸函數。設S1={x∈Rn:gi(x)≤0,i=1,2,…,m}S2={x∈Rn:Ax=b}，則式(1)的可行域為S=S1∩S2。

1 預備知識

下面給出部分與后文相關的定義與引理，以方便理解。

定義1對于函數f:Rn→R，若存在正數κ和ε，對于所有的x1,x2∈x+εB(0,1)，滿足:

|f(x2)-f(x1)|≤κ‖x2-x1‖

那么稱函數f(x)在x∈Rn處是Lipschitz連續，其中B(0,1)是Rn上的一個開球。如果函數f(x)在其定義域上的每一點都滿足Lipschitz連續，那么這樣的函數稱為局部Lipschitz函數。

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

定義3設函數f在點x附近是Lipschitz的，則f在點x處沿方向v∈Rn的廣義方向導數為：

另外，f在點x處的Clarke廣義梯度定義為：

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

如果f在點x0處是局部Lipschitz連續的，記Lipschitz常數為κ，則?f(x0)為Rn中的非空緊凸子集，并且對?ξ∈?f(x0)，都有‖ξ‖≤κ。

性質1[9]設f∶Rn→R是凸函數，則有如下性質：

?f(x0)={ξ∈Rn∶f(x0)-f(x)≤〈ξ,x0-x〉,?x∈Rn}?f(·)是極大單調的，即對任意的v∈?f(x)和v0∈?f(x0)，有〈x-x0,v-v0〉≥0。

定義4如果一個函數f:Rn→R，在點x附近是局部Lipschitz，那么當它滿足以下的兩個條件時，稱它在x附近是正則函數。

(2) ?v∈Rn，f′(x,v)=f0(x,v)。

定義5設E?Rn是一個非空凸集，稱函數f:E→R為集合E上的偽凸函數，是指對任意的x,y∈E，若存在η∈?f(x)，使得ηT(y-x)≥0，則必有f(y)≥f(x)。

引理1鏈式法則。設F(x)∶Rn→R是正則的，并且x(t)∶[0,+∞)→Rn在[0,+∞)上的任何緊區間上都是絕對連續的，則對t∈[0,+∞)，x(t)和F(x(t))∶[0,+∞)→R是幾乎處處可微的，并且有：

2 遞歸神經網絡

2.1 定 義

當x∈S2，?P2(x)={AT(AAT)-1Aζ：‖ζ‖≤1}。

引理2[11]如果假設1成立，那么:

(2)X=M，其中X={x∈Rn:g(x)≤0}，M={x∈Rn:G(x)≤0}。

式中：I0(x)={i∈{1,2,…,m}:Gi(x)=0}，I+(x)={i∈{1,2,…,m}:Gi(x)>0}。

針對非光滑偽凸優化問題，本文構造了如下死亡新型遞歸神經網絡模型：

(2)

圖1 遞歸神經網絡模型(2)的網絡硬件實現結構圖

定義6稱向量函數x(·)為式(2)過初始點x(0)=x0的狀態解，若x(t)絕對連續，并對幾乎所有的t都有:

定義7如果對所有的t都有：

0∈-?P2(x*)-ε(t)?P1(x*)-ε2(t)?f(x*)

則稱x*為式(2)的一個平衡點。

2.2 全局解的存在性

引理4如果假設1和假設2均滿足，則式(2)具有局部解x(t)，且x(t)有界。

定理1對于任意的初始點x0∈Rn，式(2)至少存在一個全局解x(t)，且x(t)是有界的。

證明由引理4可知式(2)存在有界局部解，根據解的擴展性理論，可知式(2)存在全局解x(t)，t∈[0,+∞)。類似引理4，可證明全局解x(t)有界。

2.3 遞歸神經網絡的收斂性

定理2過任意初始點的式(2)的解均能在有限時間內進到等式約束集S2，并永駐其中。

-‖η(t)‖2-ε(t)ξ(t)Tη(t)-ε2(t)γ(t)Tη(t)≤

-‖η(t)‖2+ε(t)‖ξ(t)‖‖η(t)‖+

ε2(t)‖γ(t)‖‖η(t)‖

(3)

當x(t)?S2時，‖η(t)‖=1。

‖?f(x(t))‖∶=sup{‖γ‖∶γ∈?f(x(t))}∶lf?x∈B(x,r′)

同理，對于強制的凸函數P1(x)，存在lp>0，使得:

‖?P1(x(t))‖∶=sup{‖ξ‖∶ξ∈?P1(x(t))}≤lp?x∈B(x,r′)

綜上，當x(t)?S2，有：

(4)

若x(T1)∈S2，則T1大于等于x(t)收斂到S2的時間點。

0≤‖AT(AAT)-1(Ax(t0)-b)‖≤

(5)

解以上不等式可以得到:

t0≤2‖AT(AAT)-1(Ax(T1)-b)‖+T1

這意味著，當t>2‖AT(AAT)-1(Ax(T1)-b)‖+T1，必有x(t)∈S2。即狀態解x(t)將在一定時間進入等式約束集S2={x∈Rn|Ax=b},且該上限為:

t0=2‖AT(AAT)-1(Ax(T1)-b)‖+T1

綜上，過任意初始點x0∈Rn的狀態解x(t)必將在有限時間內進入等式約束集。

接下來將證明式(2)的狀態解x(t)一旦進入等式約束集S2，就會一直在S2內。若非如此，假設狀態解x(t)在t1時刻離開等式約束集S2，則一定存在區間(t1,t2)，t1>T1，使得對任意的t∈(t1,t2)都有x(t)?S2，且‖AT(AAT)-1(Ax(t1)-b)‖=0。再結合式(5)，可以得到：

‖AT(AAT)-1(Ax(t2)-b)‖≤

這與‖AT(AAT)-1(Ax(t2)-b)‖>0矛盾。

因此式(2)的狀態解x(t)在有限時間里進入到等式約束集S2，并永駐其中。

引理6[4]

1) 對于所有x∈Rn，ξ2∈?P2(x)，有：

2) 對于任意x∈S2/S1，ξ1∈?P1(x)，有：

3) 對于任意x∈S2/S1，ξ1∈?P1(x)，有:

證明

1) 因為當x∈S2， ?P2(x)={AT(AAT)-1Aζ：‖ζ‖≤1}則:

定理3如果假設滿足，則式(2)從任意一點出發 的狀態解將在有限時間內進入不等式約束集S1={x∈Rn:g(x)≤0},并永駐其中。

ξ(t)T·[(I-P)(-ε(t)ξ(t)-ε2(t)γ(t))]

又因為(I-P)T=I-P且(I-P)2=I-P有：

ε2(t)‖(I-P)ξ(t)‖‖γ(t)‖

若x(T2)∈S1，則T2大于等于x(t)收斂到S1的時間點。

若x(T2)?S1有:

(6)

然后對式(6)兩邊從T2到t進行積分得到：

用反證法，若不在有限時間內進入S1，則當t→+∞可得:

類似于定理2，我們可以證明得到一旦神經網絡的狀態解進入到S1將永駐其中。

綜上可得，式(2)從任意一點出發的狀態解x(t)將在有限時間內進入不等式約束集S1={x∈Rn∶g(x)≤0},并永駐其中。

(7)

又由f(x)是偽凸的，可知：

引理8[11]設x*是式(1)的一個最優解，則對于任意的x∈S1∩S2和γ∈?f(x)，有：

〈γ,x-x*〉≥0

定理4若假設1、2均滿足，式(2)至少有一個平衡點，且式(2)從任意點出發的狀態解x(t)均收斂到式(1)的一個最優解。

證明設x*是式(1)的一個最優解。定義Lyapunov函數如下：

V(x,t)=ε2(t)[f(x)-f(x*)]+

(8)

經過簡單的計算可得:

?V(x)=ε2(t)?f(x)+ε(t)?P1(x)+x-x*

任取x0∈Rn，設x(t)為式(2)過初始點x0的狀態解。另外，由定理2和定理3可知，式(2)的狀態解x(t)在一定時間內進入到等式約束集S1和不等式約束集S2，并永駐其中。因此，不失一般性，我們假設：

x(t)∈S=S1∩S2?t≥0

類似于引理4的證明，存在可測函數ξ(t)∈?P1(x(t))，γ(x(t))∈?f(x(t))，對于a.e.t∈[0,+∞)，滿足：

(9)

由x(t)，x*∈S1可知，P(x(t)-x*)=0，?t≥0。由引理1和式(I-P)2=I-P可知，對于a.e.t∈[0，+∞)，有：

-‖(I-P)(ε(t)ξ(t)+ε2(t)γ(t))‖2-

〈x(t)-x*,ε(t)ξ(t)+ε2(t)γ(t)〉+

(10)

由引理8可知:

0≤〈γ(t),x(t)-x*〉

由凸不等式知:

〈x(t)-x*,ξ(t)〉≥P1(x(t))-P1(x*)=0

令ψ(x(t))=ε2(t)?f(x)+ε(t)?P1(x)，因此：

(11)

V(x(0))-V0<+∞

(12)

3 仿真實驗

為了檢驗上述理論的正確性，下面將利用遞歸神經網絡來求解二類優化問題并列舉幾個數值實例來驗證。仿真實驗在MATLAB 2012a平臺下進行。

實驗1帶有等式和方體約束的非光滑偽凸優化問題：

(13)

s.t.Ax=b-1≤xi≤1i=1,2

式(13)的目標函數是高斯函數。高斯函數是一種局部Lipschitz連續且在Rn上是嚴格偽凸的，且在隨機優化中占有重要的地位。文獻[9-10]分別提出了兩類神經網絡來解決這類問題，但文獻[9]的神經網絡僅能解決帶等式約束的問題，而文獻[10]可以解決上述問題，卻需要提前計算懲罰參數。本文構造的遞歸神經網絡模型可以克服上述兩個缺點。

針對式(13)，取A∈R2,b∈R,σ=(σ1,σ2)=(1,1)T,A=[0.523,0.917],b=0.623。任取4個不同的初始點(0,1.5)、(0,0)、(-1,-2)、(5,6)，仿真實驗結果如圖2所示。可以看出遞歸神經網絡從任意初始點出發的狀態解都能收斂到式(13)的一個最優解x*=(0.436 5,0.436 5)。

圖2 實驗1的任意4個初始點的x(t)的收斂軌跡

實驗2帶有等式和不等式約束的凸優化問題。

凸函數是具有重要實際意義的函數，式(2)也能夠解決目標函數偽凸函數且帶有等式和不等式約束的問題：

(14)

s.t.x1+x2=1

-xi≤0i=1,2

式(14)是一類常見的凸優化問題，很多研究者構造了多種神經網絡來解決此類問題，但這些模型大都必須包含懲罰參數，或是結構會相對復雜。本文構造的遞歸神經網絡模型能夠避免上述缺點。

基于上述問題，通過MATLAB進行模擬實驗，隨機取4個初始點(0,1.5)、(0,0)、(-1,-2)、(5,6)，實驗結果如圖3所示?？梢钥闯?，對任意初始點遞歸神經網絡的狀態解都將收斂到非線性凸問題的一個最優解x*=(0,1)T。

圖3 實驗2的任意4個初始點的x(t)的收斂軌跡

4 結 語

本文創建了一種解決非光滑偽凸優化問題的新型遞歸神經網絡模型。與以往的模型相比較，本文提出的模型層次僅為單層，且不用依賴于懲罰參數的選取，同時還能夠解決同時帶有等式約束和不等式約束的優化問題。本文主要證得了狀態解有全局解，且能夠在有限時間內收斂到原目標函數的可行域，最終收斂到偽凸優化問題的最優解等重要理論。同時，通過兩個實驗驗證了該模型的正確性。