一種解決受約束的非光滑偽凸優(yōu)化問題的新型神經(jīng)網(wǎng)絡(luò)方法

喻 昕,伍靈貞,汪炎林

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

(廣西多媒體通信與網(wǎng)絡(luò)技術(shù)重點實驗室,南寧 530004)

E-mail:327467000@qq.com

1 引 言

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

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

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

在前人工作的基礎(chǔ)上,本文提出了一種基于微分包含理論的神經(jīng)網(wǎng)絡(luò),用以解決帶有等式與不等式約束條件的非光滑偽凸優(yōu)化問題.與現(xiàn)有的神經(jīng)網(wǎng)絡(luò)相比,本文的神經(jīng)網(wǎng)絡(luò)具有如下的優(yōu)勢:

1)本文神經(jīng)網(wǎng)絡(luò)不需要提前計算精確的罰因子;

2)對神經(jīng)網(wǎng)絡(luò)初始點的選取沒有限制,可以任意取值;

3)這里的神經(jīng)網(wǎng)絡(luò)是單層的,結(jié)構(gòu)相對簡單.值得注意的是,本文的神經(jīng)網(wǎng)絡(luò)狀態(tài)向量是一步證明進入可行域的,而大多數(shù)的神經(jīng)網(wǎng)絡(luò)會分兩步求證,即先進入等式約束范圍,再進入不等式約束范圍.

2 預(yù)備知識

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

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 預(yù)備知識

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

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

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

3 神經(jīng)網(wǎng)絡(luò)模型的提出

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

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

(3)

因為gi(x),i=1,…,p是凸函數(shù),則G(x)也是凸函數(shù).因此,對所有的x∈n都存在著對應(yīng)?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)‖,經(jīng)過計算可得{x∈n:H(x)≤0}={x∈n:Ax-b=0}=S2,就是說對等式限制條件進行了等價的變換.

基于上文的理論知識,本文提出的用以解決帶有等式與不等式約束條件的偽凸優(yōu)化問題的神經(jīng)網(wǎng)絡(luò)模型如下所示:

(4)

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

(5)

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

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

4 主要定理分析

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

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

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

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

證明:

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

(6)

那么,

(7)

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

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

(8)

4.1 神經(jīng)網(wǎng)絡(luò)存在局部解

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

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

4.2 全局解的存在性

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

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

(9)

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

(10)

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

(11)

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

(12)

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

(13)

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

(14)

(15)

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

4.3 有限時間內(nèi)收斂到可行域S

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

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

那么,神經(jīng)網(wǎng)絡(luò)狀態(tài)變量x(t)會在有限時間內(nèi)到達{x:V(x)≤0}范圍內(nèi),且不再離開此區(qū)域.

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

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

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

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

(15)

(16)

(17)

(18)

(19)

聯(lián)立引理1,得:

(20)

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

(21)

(22)

根據(jù)引理4,可知神經(jīng)網(wǎng)絡(luò)狀態(tài)變量x(t)會在有限時間內(nèi)進入到可行域S,且不再離開.

4.4 神經(jīng)網(wǎng)絡(luò)收斂到最優(yōu)解

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

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

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

(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范圍中是偽凸函數(shù),則有：

(26)

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

(27)

聯(lián)立式(24),有：

(28)

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

聯(lián)立式(24),可得：

(29)

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

(30)

(31)

(32)

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

(33)

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

(34)

(35)

聯(lián)立式(28),可知：

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

(36)

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

(37)

因此,

(38)

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

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

(39)

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

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

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

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

(40)

5 仿真實驗

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

5.1 實驗1

考慮如下的二次結(jié)構(gòu)的偽凸優(yōu)化問題:

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

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

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

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

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

圖1 神經(jīng)網(wǎng)絡(luò)(4)在初始點為(3,2,8,4)T的軌跡圖

圖2 神經(jīng)網(wǎng)絡(luò)(4)在初始點為(5,2,5,0)T時的軌跡圖

圖3 文獻[20]神經(jīng)網(wǎng)絡(luò)(4)初始點為(5,2,5,0)T時的軌跡圖

5.2 實驗2

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

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

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

圖4 實驗2神經(jīng)網(wǎng)絡(luò)(4)任取5個初始點的收斂軌跡圖

由此可見,仿真實驗的結(jié)論再一次驗證了本文理論分析的正確性,本文所提出的神經(jīng)網(wǎng)絡(luò)的有效性與準確性,與理論分析的結(jié)果一致.

6 結(jié) 論

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