一種解決受約束的非光滑偽凸優化問題的新型神經網絡方法

喻 昕,伍靈貞,汪炎林

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

(廣西多媒體通信與網絡技術重點實驗室,南寧 530004)

E-mail:327467000@qq.com

1 引 言

不管是在工程應用還是科學研究領域,帶有約束條件的優化問題都是非常常見的,例如熱門的視覺識別、信號控制、人工智能等領域.諸多研究學者就約束優化問題提出了各式各樣的算法,詳見文獻[1-3].但是上述文獻涉及到的算法,在求優化問題的實時解時,效果往往不好,甚至難以求解.自從1986年,Tank 和Hopfield[4]提出了神經優化思想,發現神經網絡方法可以最有效的求解出實時解,研究學者相繼提出了諸多類型的神經網絡.在1988年,Kennedy 和 Chua[5]為解決非線性規劃問題(NPC),而提出了一種能用硬件實現求解實時問題的神經網絡,該模型為后續學者的研究提供了理論基礎.隨后,出現了為解決各種類型的優化問題而提出的神經網絡,例如文獻[6]的對偶神經網絡,文獻[7]的投影算子神經網絡等.

上述涉及到的神經網絡,基本都是針對光滑問題.而就非光滑優化問題,文獻[8] Forti等人基于微分包含理論以及次梯度的理念提出了一種神經網絡模型,用以解決廣義非線性優化問題(G-NPC),也就是說可以解決目標函數是非光滑非凸函數的優化問題.同樣基于次梯度理念以及罰因子原理,Bian 和 Xue[9]也提出了一種解決非光滑凸優化問題,通常情況下,罰因子的計算與選取會與神經網絡的收斂情況密切相關.為了避免計算罰因子,Qin等人[10]提出了一種雙層神經網絡,遺憾的是該模型結構為雙層,增加了時間與空間的計算復雜度.除此之外,還有很多為解決非光滑優化問題所提出的神經網絡模型,如基于正則項原理的神經網絡[11]、基于廣義梯度投影原理的神經網絡[12]等.

隨著微分包含理論與凸優化問題的深入發展,研究學者們開始向非光滑非凸優化領域進軍.而作為非凸優化問題具有特殊代表性意義的偽凸優化問題,自然成為了研究的熱門話題,研究學者們提出了不同種類的神經網絡,詳見文獻[13-21].Hu 和 Wang[13]使用投影的方式提出了一種帶有罰因子的神經網絡解決帶有不等式約束的偽凸優化問題.而文獻[14]中,作者提出了一種解決只帶有等式約束的偽凸優化問題的神經網絡模型.Liu 和Guo 等人[15]則為了解決既帶有不等式約束,又帶有等式約束的偽凸優化問題,提出了一種基于罰因子的神經網絡.當然,文獻[16]也針對上述問題提出了另外一種基于罰因子的神經網絡.文獻[17],文獻[18]和文獻[19]則分別提出了一種不依賴于罰因子的神經網絡,且都能解決原始優化問題.Bian 等人[20]利用光滑函數的原理,提出了一種解決非光滑偽凸優化問題的神經網絡,遺憾的是,該模型的初始點的選取必須在等式約束范圍內,降低了神經網絡的應用范圍.除此之外,還有一些研究學者將神經網絡運用到各種具體的優化問題中,如文獻[23]將神經網絡運用到地鐵的客流預測服務,文獻[24]用神經網絡的方法求解稀疏性正則化問題等.

在前人工作的基礎上,本文提出了一種基于微分包含理論的神經網絡,用以解決帶有等式與不等式約束條件的非光滑偽凸優化問題.與現有的神經網絡相比,本文的神經網絡具有如下的優勢:

1)本文神經網絡不需要提前計算精確的罰因子;

2)對神經網絡初始點的選取沒有限制,可以任意取值;

3)這里的神經網絡是單層的,結構相對簡單.值得注意的是,本文的神經網絡狀態向量是一步證明進入可行域的,而大多數的神經網絡會分兩步求證,即先進入等式約束范圍,再進入不等式約束范圍.

2 預備知識

本章節首先闡述本文所要研究的問題類型,隨后介紹相關的定理,便于讀者理解后文的證明過程.

2.1 問題描述

本文研究的問題如下:

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

(1)

為了后文的證明,我們定義：

S1={x∈n:g(x)≤0}S2={x∈n:Ax=b}S=S1∩S2={x∈n:g(x)≤0,Ax=b}

(2)

2.2 預備知識

定義1[19](上半連續集值映射).要是集合E?n中的所有的x,都存在一個一一對應的非空集合F(x)?n,那么可以說x→F(x)在E→n空間為集值映射.要是任取一個開集V?F(x0),對每一個初始點x0都存在對應的領域U,滿足F(U)?V,那么稱集值映射F:E→n在x0∈E為上半連續集值映射.

定義2[1](偽凸函數).令E?n為一個非空緊集,若對于任選的x,y∈E,存在η∈?f(x),且ηT(y-x)≥0,使得f(y)≥f(x)成立,則稱函數f:E→在集合E中是偽凸函數.

定義3[9](鏈式法則).若在任意的x(t)處,函數V:n→是一個正則函數,且x(·):→n在t處是可微的,同時也是Lipschitz的,則有

3 神經網絡模型的提出

這里,我們將要構建一個基于微分包含理論的神經網絡模型,用以解決這類帶有不等式與等式約束條件的偽凸優化問題.在給出模型之前,我們先給出一些必要的定義.

首先,對原不等式限制條件進行一定的變換,定義一個罰函數:

(3)

因為gi(x),i=1,…,p是凸函數,則G(x)也是凸函數.因此,對所有的x∈n都存在著對應?G(x),且：

其中,

I+(x)={i∈{1,2,…,m}:gi(x)>0}

I0(x)={i∈{1,2,…,m}:gi(x)=0}

令H(x)=‖AT(AA)-1(Ax-b)‖,經過計算可得{x∈n:H(x)≤0}={x∈n:Ax-b=0}=S2,就是說對等式限制條件進行了等價的變換.

基于上文的理論知識,本文提出的用以解決帶有等式與不等式約束條件的偽凸優化問題的神經網絡模型如下所示:

(4)

這里,γ∈?f(x),η∈?G(x),l∈?H(x),ε:[0,∞)→(0,∞)為遞減函數,定義為:

(5)

下面給出一個全文所必須的前提假設:

另外,本文定義P=AT(AAT)-1A,c=AT(AAT)-1b.

4 主要定理分析

本章節根據所提出的神經網絡模型進行收斂性地分析,并給出一些必要的定理.首先,說明神經網絡存在局部解,為后文的證明奠定研究基礎;隨后,求證神經網絡的狀態向量會在有限的時間內進入到可行域范圍內,且隨著時間的推移神經網絡狀態向量將會一直在可行域范圍內運動;接著,求證神經網絡的解是全局解;最后,求證神經網絡的穩定點就是原始優化問題的最優解,從而保證神經網絡的有效性與準確性.

接下來,我們將會給出詳細的推導過程.這里,先給出幾個必要的引理.

引理1.若假定1成立,則下面兩個結論成立:

?l∈?H(x),?x∈n

證明:

1)由H(x)的定義,可得當x?S2時,H(x),x∈n是嚴格可微函數且有：

(6)

那么,

(7)

考慮另外一種情況,當x∈S2時,?H(x)={PTζ:‖ζ‖≤1},于是有‖?H(x)‖=‖PTξ‖≤‖P‖‖ζ‖≤1.

另外一方面,當x?S2時,有：

(8)

4.1 神經網絡存在局部解

定理1.若假定1成立,對于任意的初始點x0∈n,在區間[0,T)上,神經網絡(4)至少存在一個局部解x(t).

證明:因為神經網絡模型(4)的右邊是一個非空緊凸的上半連續集值映射(U.S.C),則根據[22,Th.1,p.77]有,對任意的初始點x0∈n,至少存在一個局部解x(t),t∈(0,T],其中T表示的是最大時間間隔的時刻.

4.2 全局解的存在性

因為局部解具有一定的局限性,所以我們接下來求證神經網絡(4)存在全局解.

定理2.若假定1成立,對于任意初始點x0∈n,神經網絡(4)都存在全局解x(t),也就是說全局解為x(t),其中t∈[0,+∞).

(9)

因為G(x)是凸函數,所以：

(10)

聯立式(9),式(10)以及引理1,可得：

(11)

根據ε(t)的定義,可知它是一個可積函數,再結合引理3,不難得到：

(12)

若x(t)?S1,則存在一個正數α>0,滿足：

(13)

聯立式(11),式(12)和式(13),得：

(14)

(15)

此外,結合S1是有界的,那么必然存在一個足夠大的R,對于任意x(t)∈n,滿足也就是說神經網絡狀態變量x(t)是有界的.因此,通過解的可擴展性,可得神經網絡模型(4)具有全局解.

4.3 有限時間內收斂到可行域S

在求證神經網絡狀態向量收斂到可行域過程中,一般會先求證神經網絡(4)的狀態向量會在有限時間內進入到等式可行域S2,且不再離開;然后,再求證神經網絡(4)的狀態向量會在有限時間內進入到不等式可行域S1中,且不再離開.但是本文沒有使用這種傳統的思維,我們直接求證神經網絡(4)的狀態向量進入到可行域S.

引理4[22].令x(t)為神經網絡模型(4)的一個全局解.若存在一個在t∈[0,+∞)上絕對連續的函數V(x(t)):n→,對于幾乎所有的時間t∈[0,+∞),要是滿足x(t)∈{x:V(x)>0},則必然存在一個正數σ>0,使得：

那么,神經網絡狀態變量x(t)會在有限時間內到達{x:V(x)≤0}范圍內,且不再離開此區域.

定理3.若假定1成立,對于任意初始點x0∈n,神經網絡狀態向量x(t)都會在有限時間內進入到等式可行域S中,且不再離開.

證明:定義一個能量函數M(x)=G(x)+H(x).通過簡單的分析可知,{x∈n:M(x)≤0}=S.

因為{x∈nS}={x∈nS1}∪{x∈S1S2},所以定理3可分兩種情況討論.

首先,考慮{x∈nS1}.根據引理1以及引理2,對于任意η(t)∈?G(x),l(t)∈?H(x),有

(15)

(16)

(17)

(18)

(19)

聯立引理1,得:

(20)

令t1=ε0-2,當t≥t1時,必然存在一個正數δ1,滿足:

(21)

(22)

根據引理4,可知神經網絡狀態變量x(t)會在有限時間內進入到可行域S,且不再離開.

4.4 神經網絡收斂到最優解

為了便于后文的證明,記W(x)=f(x).

定理4.若假定1成立,對于任意初始點x0∈n,神經網絡(4)的軌跡會收斂到原優化問題(1)的最優解集M,換句話就是,

證明:由定理3可知,神經網絡的狀態向量x(t)會在有限時間內進入到可行域S,且永駐其中.這里,我們不妨假設x0∈S,且x(t)∈S.記PM(x)為x(t)由n到M的投影算子,根據鏈式法則,可知存在則：

(23)

因為G(x),H(x)都具有凸性,而η(t)∈?G(x(t)),l(t)∈?H(x(t)),所以：

(24)

下面我們需要分三種情況進行分析.在分析之前,先給出兩個集合的定義.

I={t∈[0,+∞):≤0}

J={t∈[0,+∞):>0}

(25)

由于f(x)在S1范圍中是偽凸函數,則有：

(26)

第二種情況:若存在T≥0,使得t∈J,?t∈[T,+∞),則相當于：

(27)

聯立式(24),有：

(28)

由此說明,limt→+∞dist(x(t),M)是存在的.

聯立式(24),可得：

(29)

對上式兩邊同時從T1到t積分,有：

(30)

(31)

(32)

又由于f(x)在可行域S中是偽凸函數,則由其定義可得：

(33)

第三種情況:集合I,J都是無界時,首先討論t∈I的情況.類似于第一種情況的證明,證得：

(34)

(35)

聯立式(28),可知：

dist(x(t),M)≤dist(x(τ(t)),M)?t∈J

(36)

而τ(t)∈I,聯立式(34)和式(36),得：

(37)

因此,

(38)

再聯立式(34)和式(38),有：

limt→+∞dist(x(t),M)=0

(39)

綜上可得,對于任意初始點x0∈n,limt→+∞dist(x(t),M)=0,該定理得證.

引理5[19].令x*為原始偽凸優化問題(1)的一個最優解,那么對于所有的x∈S1∩S2,γ∈?f(x),則有<γ,x-x*>≥0.

定理5.若假定1成立,對于任意初始點x0∈n,必然存在一個x*,神經網絡模型(4)的軌跡最終會收斂于x*,并且x*∈M.

證明:由定理3,我們不妨假設存在一個時間T,使得對于任意的t∈[T,+∞),神經網絡模型(4)的狀態向量x(t)∈S.令x*為神經網絡模型(4)狀態變量x(t)的一個簇點,由定理4,可知x*∈M,并且存在一個序列{x(tk)},滿足limk→∞x(tk)=x*.同時,類似于定理3的證明,對于幾乎所有的時間t>T,有：

(40)

5 仿真實驗

為了可以有效的驗證本文所提出新型神經網絡的準確性與收斂性,本章將在Matlab2012a平臺上,用仿真實驗來模擬神經網絡(4)在解決偽凸優化問題上的表現.下面是詳細的實驗說明.

5.1 實驗1

考慮如下的二次結構的偽凸優化問題:

s.t.Ax=b5≤xi≤10,i=1,2,3,4

這是個典型的二次型優化問題,該問題中擁有四個變量,用一般的辦法處理較為復雜.不難得出,f(x)在可行域中是偽凸函數.因此,可以使用本文所提出的神經網絡來解決這類問題.

因為本文神經網絡的初始點選取可以是隨機的,不管是選取可行域內部的點或者是可行域外部的點都可以使得神經網絡狀態向量最終收斂到可行域內,且穩定于原始優化問題的最優解.圖1展示了隨機初始點(3,2,8,4)T隨著時間不斷向可行域內部靠近,最后穩定于(6,5,7,5)T不再發生變化.另外,圖2展示了另外一個初始點(5,2,5,0)T,同樣神經網絡的軌跡也是不斷向可行域靠近,最終也穩定于(6,5,7,5)T.此時,目標函數值f(x*)=25.2143.

為了更好的突出本文所提出神經網絡的優越性,下面做一個對比實驗.應用文獻[20]所提出的神經網絡做相同的實驗,初始點為(5,2,5,0)T?S2,注意這里的初始點沒有選擇在等式可行域內.圖3展示了該神經網絡在相同時間內的網絡軌跡收斂情況,其收斂效果不如本文所提出的神經網絡.

本次仿真實驗的結果表明,文中所提出的神經網絡模型在解決帶有等式與不等式約束條件的偽凸優化問題是準確且有效的,不管初始點位于何處,最終都會收斂于原始優化問題的最優解,與本文的理論證明吻合.而對比仿真實驗中,選取同樣的初始點,其收斂效果不如神經網絡(4).

圖1 神經網絡(4)在初始點為(3,2,8,4)T的軌跡圖

圖2 神經網絡(4)在初始點為(5,2,5,0)T時的軌跡圖

圖3 文獻[20]神經網絡(4)初始點為(5,2,5,0)T時的軌跡圖

5.2 實驗2

由于上一個仿真實驗針對的是光滑偽凸優化問題,接下來考慮非光滑優化問題.

這是一個三元二次優化問題,具有一定求解難度.因為不等式可行域S1有界,且目標函數f(x)在n是一個凸函數(凸函數是一種特殊的偽凸函數)而約束條件是非光滑凸函數,所以可以使用本文所提出的神經網絡進行求解.

圖4展示了實驗2中神經網絡任取五個初始點的運動軌跡,從圖中可以清晰的看到神經網絡軌跡不斷向可行域靠攏,且最終不再隨著時間的變化而變化,不同的初始點最終都會收斂于一個點x*=(0.1248,0.5806,0.2952)T,f(x*)=0.2297,而這個點正是原始優化問題(1)的最優解.

圖4 實驗2神經網絡(4)任取5個初始點的收斂軌跡圖

由此可見,仿真實驗的結論再一次驗證了本文理論分析的正確性,本文所提出的神經網絡的有效性與準確性,與理論分析的結果一致.

6 結 論

本文提出了一種新型的神經網絡方法,用來解決帶有不等式約束以及等式約束的偽凸優化問題.文中對神經網絡的準確性與收斂性進行了嚴謹的分析,先求證神經網絡存在局部解,再求證神經網絡具有全局解.在此基礎上,分析神經網絡狀態向量會在有限時間內進入到可行域中,且永駐其中.最后,分析對于任意初始點,神經網絡會收斂于一個最優解.為了驗證理論分析,進行了兩個仿真實驗,將理論與仿真緊密結合在一起.實驗結果表明,本文所提出的新型神經網絡方法具有收斂性與準確性,與現有神經網絡相比,它不需要提前計算準確罰因子,對初始點的選取也沒有任何要求,且它也是一種單層神經網絡,因此具有一定的先進性.