喻 昕,舒浩帆,林植良,黃曉燕

(廣西大學 計算機與電子信息學院,南寧 530004)(廣西多媒體通信與網(wǎng)絡(luò)技術(shù)重點實驗室,南寧 530004) E-mail：enigma_hf@qq.com

1 引 言

近年來,在科學研究和工程應(yīng)用中使用神經(jīng)網(wǎng)絡(luò)解決帶約束的優(yōu)化問題受到諸多學者的關(guān)注.1986年,Tank和Hopfield[1]提出了Hopfield神經(jīng)網(wǎng)絡(luò)用于解決線性規(guī)劃問題,這啟發(fā)了許多研究者使用神經(jīng)網(wǎng)絡(luò)的思想去解決優(yōu)化問題.1988年,Kennedy和Chua[2]提出一種解決非線性規(guī)劃的神經(jīng)網(wǎng)絡(luò),該網(wǎng)絡(luò)能夠通過硬件實現(xiàn)從而解決實時問題.隨后為了解決非光滑優(yōu)化問題,Forti在文獻[3]中,基于微分包含的思想,提出了一種使用了次梯度方法的神經(jīng)網(wǎng)絡(luò)解決非光滑凸優(yōu)化問題.隨著優(yōu)化理論發(fā)展和深入,非凸優(yōu)化的重要性逐漸得到重視.Liu[4]等人為了解決帶盒約束和線性等式約束的非光滑偽凸問題,設(shè)計了一種使用罰函數(shù)方法的遞歸神經(jīng)網(wǎng)絡(luò),Hu和Wang在文獻[5]中提出一種解決不等式約束偽凸優(yōu)化問題的投影神經(jīng)網(wǎng)絡(luò),但這兩種方法的有效性依賴于精確的罰因子.為了避免計算精確的罰因子,文獻[6-8]分別提出不需要罰因子的神經(jīng)網(wǎng)絡(luò)來解決優(yōu)化問題.而Bian[9]等人基于光滑化原理,提出了一種非自治的光滑神經(jīng)網(wǎng)絡(luò)來解決非光滑偽凸優(yōu)化問題,但該模型的初始點必須在等式可行域內(nèi).

以上研究的非光滑問題,都必須滿足Lipschitz連續(xù)性來定義Clarke穩(wěn)定點[10],所以往往無法用來解決在現(xiàn)實世界中廣泛存在著的非Lipschitz連續(xù)優(yōu)化問題,例如稀疏表示、圖像復原、信號恢復、變量選擇等問題[11-15].在這些問題中,l2-lp問題得到廣泛關(guān)注,當p=1時,它是l2-l0問題的最佳凸近似,而當p∈(0, 1)時,它被發(fā)現(xiàn)在許多稀疏恢復問題中擁有比p=1時更好的表現(xiàn)[16-18].但由于p∈(0,1)時的非Lipschitz性,找到l2-lp問題的全局最小點被證明是強NP難的[19].Bian和Chen[18]為了解決一類帶有盒約束的l2-lp問題提出了一種光滑神經(jīng)網(wǎng)絡(luò).Li和Bian在文獻[20]中定義了一種非Lipschitz的廣義平穩(wěn)點,并提出了一種基于光滑化的投影神經(jīng)網(wǎng)絡(luò)去解決一類帶有線性不等式約束的非Lipschitz問題,但是線性不等式約束的投影算子往往難以計算.Yu[21]等人提出一種基于罰函數(shù)的光滑神經(jīng)網(wǎng)絡(luò),不再需要投影算子,可惜仍然依賴精確罰參數(shù). Zhao[22]等人提出一種平滑慣性神經(jīng)動力學方法構(gòu)建的神經(jīng)網(wǎng)絡(luò)來解決lp范數(shù)最小化問題,但模型只適用于線性等式約束的優(yōu)化問題,具有一定局限性.

在諸多學者先前工作的基礎(chǔ)上,本文提出一種基于光滑化和微分包含理論的神經(jīng)網(wǎng)絡(luò),用以解決一類具有線性不等式約束的非Lipschitz優(yōu)化問題.與現(xiàn)有的解決此類問題的神經(jīng)網(wǎng)絡(luò)相比,本文提出的神經(jīng)網(wǎng)絡(luò)模型具有以下優(yōu)勢：

1)模型不需要提前計算精確的罰參數(shù).

2)無需限制神經(jīng)網(wǎng)絡(luò)的初始點選取.

3)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)簡單,沒有復雜的投影算子.

2 問題描述與預備知識

2.1 問題描述

本文研究的非Lipschitz優(yōu)化問題如式(1)所示：

(1)

其中f：n→+是連續(xù)可微函數(shù),在可行域內(nèi)有下界;φ：+→+在++上連續(xù)可微函數(shù),且在+上全局Lipschitz連續(xù),其Lipschitz常數(shù)為lφ;A∈r×n,b∈r,p∈(0,1).記D=(d1,d2,…,dn)∈n×m,di是D的第i列,+表示非負實數(shù)的集合,++表示正實數(shù)的集合.

這里給出一個全文假設(shè)：

2.2 預備知識

這里為了方便讀者理解,在這部分給出與本文相關(guān)的一些知識和定義.關(guān)于局部Lipschitz連續(xù)、Clarke廣義梯度和法錐的定義參考文獻[10],在此不再贅述.

定義1[20].對于x*∈S,如果x*滿足：

定義2[23].令h：n→是一個連續(xù)函數(shù),如果滿足下列條件,那么稱n·++→是h的一個光滑函數(shù)：

1)對于任意給定的μ∈是連續(xù)可微函數(shù),對于任意給定的x∈在μ∈++上是可微函數(shù);

2)對于任意給定的x∈

在提出神經(jīng)網(wǎng)絡(luò)模型之前先需要對目標問題進行光滑化處理.對任意s∈,μ>0,定義|s|的光滑函數(shù)為：

(2)

接下來引入光滑函數(shù)的一些性質(zhì).

1)對于?x∈

2)對于?x∈≤mlφμp;

4)如果φ′在++上全局(局部)Lipschitz連續(xù),那么對于任意給定的μ>0,有關(guān)于x全局(局部)Lipschitz連續(xù).

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

首先構(gòu)建懲罰函數(shù)如下：

(3)

其中g(shù)i(x)=Aix-bi,Ai表示A的第i行.易知式(3)是凸函數(shù),且S={x∈n：G(x)≤0}.對于任意x∈n,都存在?G(x),有：

(4)

其中,I0={i∈{1,2,3,…,r}：gi(x)=0},I+={i∈{1,2,3,…,r}：gi(x)>0}.

基于上文罰函數(shù)的定義,本文提出如下神經(jīng)網(wǎng)絡(luò)模型：

(5)

表1 與現(xiàn)有神經(jīng)網(wǎng)絡(luò)相比Table 1 Compared with existing neural networks

如表1所示,神經(jīng)網(wǎng)絡(luò)(5)與現(xiàn)有模型相比,約束條件更加寬松,沒有限制初始點選取范圍,不需要計算精確罰參數(shù)和投影算子,具有一定優(yōu)勢.

4 主要定理和證明

4.1 全局解的存在性

接下來給出需要用到的部分引理以保證證明的連貫性.

引理2[10].如果V：n→在x處是正則函數(shù),x：→n在t處是可微函數(shù),且是Lipschitz連續(xù)的,那么有：

定理1.若假設(shè)P成立,對于任意的初始點x0∈n,神經(jīng)網(wǎng)絡(luò)(5)存在全局解.并且對于任何狀態(tài)解x(t),存在一個足夠大的R使得

證明：因為?G(x)是非空緊凸的上半連續(xù)集值映射,神經(jīng)網(wǎng)絡(luò)的右邊是一個非空緊凸的上半連續(xù)集值映射,所以對于任意的初始點x0∈n,存在一個時間T和一個連續(xù)函數(shù)x：[0,T]→n,使得x(t)是神經(jīng)網(wǎng)絡(luò)的一個局部解,其中[0,T)表示解的最大存在區(qū)間[26].

(6)

(7)

結(jié)合引理3得：

(8)

顯然式(8)表明x(t)在[0,T)上有界.根據(jù)解的可拓展性,可知神經(jīng)網(wǎng)絡(luò)(5)的狀態(tài)解全局存在.

(9)

(10)

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

定理2.若假設(shè)P成立,對于任意初始點x0∈n,神經(jīng)網(wǎng)絡(luò)(5)的軌跡將會在有限時間內(nèi)進入到可行域且不再離開.

(11)

根據(jù)引理4和定理1,可以得到：

(12)

(13)

對式(13)的兩側(cè)求從T3到t的積分：

(14)

所以存在一個時間T4≥T3,使得G(x(T4))≤0,對于任意初始點x0∈n,神經(jīng)網(wǎng)絡(luò)(5)的軌跡在有限時間T4進入到可行域S.

接下來需要證明x(t)在t>T4時,神經(jīng)網(wǎng)絡(luò)(5)的軌跡進入可行域后,便不再離開.

假設(shè)存在t2>t1>T4,使得x(t1)∈S,并且x(t)?S,?t∈(t1,t2].

值得一提的是,本文提出的神經(jīng)網(wǎng)絡(luò)模型與有些需要初始點在可行域內(nèi)的神經(jīng)網(wǎng)絡(luò)不同,它能夠任意選取初始點,保證其在有限時間內(nèi)進入可行域并永駐其中,也就是說不需要額外的操作來選取合適的初始點.

4.3 神經(jīng)網(wǎng)絡(luò)收斂到廣義穩(wěn)定點

引理5[27].對于任意的x∈S,在x處的法錐可以表示為NS(x)={ATγ：γ≥0 and(Ax-b)Tγ=0}.

定理3.若假設(shè)P成立,對于任意初始點x0∈n,神經(jīng)網(wǎng)絡(luò)(5)的解有以下性質(zhì)：

2)x(t)的任何聚點是原始問題(1)的廣義穩(wěn)定點.

3)如果原始問題(1)的聚點是孤立的,那么x(t)收斂到問題(1)的一個廣義穩(wěn)定點.

證明：

(15)

由G(x(t))=0,?x(t)∈S和引理2可知：

(16)

又由式(15)、式(16)和引理1得：

(17)

(18)

(19)

再對式(18)兩邊積分,得到：

(20)

從而有：

(21)

2)由可行域S的有界性可知,x(t)存在至少一個聚點.設(shè)x*是x(t)的任意一個聚點,存在一個時間序列t∈{tk}(k→+∞,tk→+∞),使得：

(22)

更進一步,根據(jù)神經(jīng)網(wǎng)絡(luò)微分包含式(5)得到：

(23)

由式(4)和引理5可知,存在ζ∈n,使得當x*∈S時：

(24)

此處ζ滿足ζi∈{i：Aix-b<0}=0,ζi∈{i：Aix-b=0}≥0.

又根據(jù)定義1和式(2),有：

(25)

聯(lián)立式(23)～式(25)得到：

(26)

所以x*是優(yōu)化問題(1)的一個廣義穩(wěn)定點.

3)如果優(yōu)化問題(1)的廣義穩(wěn)定點是唯一的,那么顯然結(jié)論成立.如果優(yōu)化問題(1)的廣義穩(wěn)定點是孤立但不是唯一的,可以使用反證法證明.

5 仿真實驗

本節(jié)在MATLAB R2018b平臺上進行3個仿真實驗,來展示神經(jīng)網(wǎng)絡(luò)(5)解決目標問題的良好表現(xiàn).

5.1 盒式約束的數(shù)值實驗

考慮如下優(yōu)化問題：

s.t.x∈S：={x∈S：xi∈[l,u],i={1,2,3,4,5}}

(27)

問題(27)是一個具有盒式約束的非光滑非Lipschitz優(yōu)化問題,有著廣泛的應(yīng)用場景,但由于其具有非Lipschitz性,導致此類問題的求解較為困難.本文所提出的神經(jīng)網(wǎng)絡(luò)(5)對于解決此類問題有著不錯的效果,如圖1所示,實驗選取ε0=μ0=1,任意選取5個未必在可行域內(nèi)的點作為初始點,狀態(tài)向量都收斂到點x*=(0,0,0,0.5645,0)T.

圖1 神經(jīng)網(wǎng)絡(luò)(5)在不同初始點的狀態(tài)軌跡Fig.1 State trajectories of neural network(5)at different initial points

另外使用神經(jīng)網(wǎng)絡(luò)(5)與文獻[18]所提出的光滑神經(jīng)網(wǎng)絡(luò)(SNN)進行對比實驗.設(shè)置兩個神經(jīng)網(wǎng)絡(luò)模型的初始點為x0=(-17,10,9,4,-5)T,實驗結(jié)果如圖2所示,可以看到神經(jīng)網(wǎng)絡(luò)(5)具有與SNN相似的收斂效果.

圖2 神經(jīng)網(wǎng)絡(luò)(5)與文獻[18]神經(jīng)網(wǎng)絡(luò)狀態(tài)軌跡對比Fig.2 Comparison between neural network (5) and state trajectories of neural network in reference[18]

圖3 狀態(tài)解局部軌跡對比Fig.3 Comparison of local trajectories of state solutions

由上述的實驗結(jié)果可以看出,神經(jīng)網(wǎng)絡(luò)(5)能夠有效解決此類具有盒式約束的非Lipschitz優(yōu)化問題,并且有能夠任意選取初始點的優(yōu)勢.

5.2 線性不等式約束的數(shù)值實驗

考慮如下優(yōu)化問題：

s.t.x∈S：={x∈S：Bx≤c}

(28)

其中：

b=(1,0,3)T,c=(1,1,1,1,1,0,1,1,1)T,φ(z)=(z/1+z),p=0.3.

問題(28)是一個非光滑非Lipschitz優(yōu)化問題,該問題具有線性不等式約束,用一般方法較難處理這類問題,而本文所提出的神經(jīng)網(wǎng)絡(luò)(5)能夠較好地解決這類問題.

圖4 神經(jīng)網(wǎng)絡(luò)(5)在不同初始點的狀態(tài)軌跡Fig.4 State trajectories of neural network(5) at different initial points

實驗中選取ε0=μ0=1,隨機在xi∈[-3,3]范圍內(nèi)任意選取5個未必在可行域范圍內(nèi)的初始點,由圖4可知,無論初始點如何選取,最終狀態(tài)向量x(t)的軌跡都收斂到(0,0,-0.0790,0.6147,0)T.

圖5 神經(jīng)網(wǎng)絡(luò)(5)與文獻[21]神經(jīng)網(wǎng)絡(luò)狀態(tài)軌跡對比

為了驗證神經(jīng)網(wǎng)絡(luò)(5)的有效性和優(yōu)勢,選取文獻[21]中的神經(jīng)網(wǎng)絡(luò)模型與本文模型對比.值得說明的是,文獻[20]中的投影神經(jīng)網(wǎng)絡(luò)(PNN)在解決這類問題時,較難計算線性不等式可行域的投影算子,并且同實驗5.1中的SNN一樣,無法任意選取初始點.

圖6 神經(jīng)網(wǎng)絡(luò)(5)與文獻[21]神經(jīng)網(wǎng)絡(luò)目標函數(shù)值對比Fig.6 Comparison between the objective fuction value of neural network(5)and neural network in reference [21]

對比實驗選取(-1,2,-1,-1,0.2)T作為初始點,兩類神經(jīng)網(wǎng)絡(luò)的狀態(tài)解收斂軌跡如圖5所示,能夠看出文獻[21]中的神經(jīng)網(wǎng)絡(luò)狀態(tài)解收斂到與本文神經(jīng)網(wǎng)絡(luò)(5)的狀態(tài)解不一樣的位置.而通過圖 6中顯示出的兩類神經(jīng)網(wǎng)絡(luò)狀態(tài)解的目標函數(shù)值f(x)的變化軌跡,能夠看出神經(jīng)網(wǎng)絡(luò)(5)的顯然小于文獻[21]的神經(jīng)網(wǎng)絡(luò).也就是說,在解決這類問題時,本文神經(jīng)網(wǎng)絡(luò)(5)具有良好表現(xiàn),而且并不需要計算罰參數(shù)來保證神經(jīng)網(wǎng)絡(luò)的收斂,具有一定的優(yōu)越性.

5.3 圖像恢復實驗

在實驗中,通過對64×64像素的退化觀測圖像進行復原驗證神經(jīng)網(wǎng)絡(luò)(5).圖7中的(a)和(b)分別展示了原始圖像和退化的觀測圖像,觀測圖像的退化是由于模糊和隨機噪聲導致,其中模糊核由7×7尺寸的二維高斯函數(shù)h(i,j)=e-2(i/3)2-2(j/3)2構(gòu)造,隨機噪聲由零均值、0.05標準差的高斯噪聲組成.退化后圖像的PSNR為15.57dB.

圖7 原始圖像和觀測圖像Fig.7 Original image and observed image

將上述圖像復原問題建模為如下優(yōu)化問題：

(29)

其中,n=642,A∈n×n是由模糊核構(gòu)造的模糊矩陣,b∈n是觀測圖像,n表示圖像的一階微分算子矩陣D的第i列.矩陣A和D分別由文獻[28]和文獻[12]中的方法構(gòu)造.

圖8 復原圖象Fig.8 Restored images

在該實驗中,令μ0=1,x0=b,使用神經(jīng)網(wǎng)絡(luò)(5)分別在p=0.3和p=0.5的情況下進行復原,復原效果如圖8所示.在圖 9中給出了神經(jīng)網(wǎng)絡(luò)(5)的PSNR變化軌跡,可以看出當p=0.3時,具有更好的效果.

圖9 p=0.3和p=0.5時PSNR的變化軌跡Fig.9 Trajectories of PSNRs with p=0.3 and p=0.5

與文獻[12]中的GNC算法和文獻[17]中的SPG算法的PSNR對比如表 2所示,顯然神經(jīng)網(wǎng)絡(luò)(5)在處理問題(29)時更具優(yōu)勢,證明了本文的神經(jīng)網(wǎng)絡(luò)模型在處理這類圖像復原問題時具有良好表現(xiàn).

表2 PSNR與其他算法的PSNR對比Table 2 Comparison of PSNR with other algorithms

6 結(jié) 論

本文為了解決稀疏優(yōu)化領(lǐng)域中常見的一類非光滑非Lipschitz問題,提出一種新型的光滑神經(jīng)網(wǎng)絡(luò)模型,在文中證明了所提神經(jīng)網(wǎng)絡(luò)的狀態(tài)解全局存在,并能夠在一個有限時間進入可行域內(nèi)不再離開,還證明了神經(jīng)網(wǎng)絡(luò)的任意聚點都是目標問題的廣義穩(wěn)定點.與現(xiàn)有神經(jīng)網(wǎng)絡(luò)相比,該模型不需要計算投影算子和額外的罰參數(shù),結(jié)構(gòu)簡單,任意選取初始點,具有一定的優(yōu)越性.最后,通過數(shù)值仿真實驗展示了所提神經(jīng)網(wǎng)絡(luò)對目標問題的有效性,并且通過圖像恢復實驗展示了它應(yīng)用在實際問題中的良好表現(xiàn).