光滑神經(jīng)網(wǎng)絡(luò)解決非李普西茨優(yōu)化問題的研究*

?

光滑神經(jīng)網(wǎng)絡(luò)解決非李普西茨優(yōu)化問題的研究*

通信地址：530004 廣西南寧市廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院Address:School of Computer & Electronics and Information,Guangxi University,Nanning 530004,Guangxi,P.R.China

喻昕,謝緬,李晨宇

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

摘要：為尋求滿足約束條件的優(yōu)化問題的最優(yōu)解，針對(duì)目標(biāo)函數(shù)是非李普西茨函數(shù)，可行域由線性不等式或非線性不等式約束函數(shù)組成的區(qū)域的優(yōu)化問題，構(gòu)造了一種光滑神經(jīng)網(wǎng)絡(luò)模型。此模型通過引進(jìn)光滑逼近技術(shù)將目標(biāo)函數(shù)由非光滑函數(shù)轉(zhuǎn)換成相應(yīng)的光滑函數(shù)以及結(jié)合懲罰函數(shù)方法所構(gòu)造而成。通過詳細(xì)的理論分析證明了不論初始點(diǎn)在可行域內(nèi)還是在可行域外，光滑神經(jīng)網(wǎng)絡(luò)的解都具有一致有界性和全局性，以及光滑神經(jīng)網(wǎng)絡(luò)的任意聚點(diǎn)都是原始優(yōu)化問題的穩(wěn)定點(diǎn)等結(jié)論。最后通過幾個(gè)簡單的仿真實(shí)驗(yàn)證明了理論的正確性。

關(guān)鍵詞：非李普西茨函數(shù)；光滑逼近技術(shù)；穩(wěn)定點(diǎn)；聚點(diǎn)

1引言

在科學(xué)和技術(shù)領(lǐng)域中，如最優(yōu)控制、信號(hào)處理以及模式識(shí)別等應(yīng)用經(jīng)常會(huì)遇到優(yōu)化問題。傳統(tǒng)上一般采用數(shù)值計(jì)算的方法來解決線性或非線性規(guī)劃問題，例如牛頓梯度法、罰函數(shù)法等等。很多工程應(yīng)用往往需要得到優(yōu)化問題的實(shí)時(shí)解。然而傳統(tǒng)的數(shù)值方法往往無法滿足實(shí)時(shí)的要求，因?yàn)樗?jì)算解的時(shí)間依賴于問題的維數(shù)與結(jié)構(gòu)以及算法的復(fù)雜度。求解優(yōu)化問題實(shí)時(shí)解的一個(gè)可行且很理想的方法就是應(yīng)用人工神經(jīng)網(wǎng)絡(luò)。基于模擬電路的神經(jīng)網(wǎng)絡(luò)，由于其內(nèi)在的大規(guī)模并行運(yùn)算和快速收斂性，可用它進(jìn)行優(yōu)化問題的實(shí)時(shí)求解[1]。

近年來用神經(jīng)網(wǎng)絡(luò)來解決非線性規(guī)劃問題已經(jīng)得到了很大的發(fā)展，并取得了很好的應(yīng)用。在1986年，TankDW和HopfieldIJ[2]應(yīng)用Hopfield神經(jīng)網(wǎng)絡(luò)模型方法解決了線性規(guī)劃問題。在1988年，KennedyM和ChuaL[3]提出了解決非線性規(guī)劃問題的動(dòng)態(tài)規(guī)格非線性規(guī)劃單元NPC(NonlinearProgrammingCircuit)模型，該神經(jīng)網(wǎng)絡(luò)模型采用懲罰函數(shù)方法來估算最優(yōu)解。此后，用來解決最優(yōu)化問題的神經(jīng)網(wǎng)絡(luò)模型層出不窮，比如基于拉格朗日方法的拉格朗日神經(jīng)網(wǎng)絡(luò)模型[4,5]、基于投影方法的投影神經(jīng)網(wǎng)絡(luò)模型[6]、用來解決非光滑非凸或凸問題的單層遞歸神經(jīng)網(wǎng)絡(luò)模型[7,8]。

然而，從上述所提到的神經(jīng)網(wǎng)絡(luò)模型文獻(xiàn)中，可以發(fā)現(xiàn)它們都有一個(gè)顯著的相似點(diǎn)，就是它們所要求的目標(biāo)函數(shù)必須要滿足李普西茨條件，但是在許多重要的應(yīng)用中，比如圖像修復(fù)、信號(hào)重建以及變量選取等應(yīng)用中，最優(yōu)化問題并不滿足李普西茨條件，那么對(duì)于這樣的問題，上述文獻(xiàn)所提到的神經(jīng)網(wǎng)絡(luò)模型則不能解決。

最近幾十年，人們發(fā)現(xiàn)光滑逼近技術(shù)能夠解決目標(biāo)函數(shù)是一般非光滑(滿足李普西茨條件)非凸甚至不滿足李普西茨條件的優(yōu)化問題。光滑逼近技術(shù)是針對(duì)具有特殊結(jié)構(gòu)的一類目標(biāo)函數(shù)，這類目標(biāo)函數(shù)可能是一般非光滑、非凸甚至是非李普西茨函數(shù)，通過將目標(biāo)函數(shù)與光滑函數(shù)結(jié)合來形成具有光滑性質(zhì)的新目標(biāo)函數(shù)[9]。文獻(xiàn)[10]采用投影方法與光滑技術(shù)結(jié)合構(gòu)造了光滑神經(jīng)網(wǎng)絡(luò)模型，解決了原始優(yōu)化問題的目標(biāo)函數(shù)是非李普西茨函數(shù)的問題，但是在此文獻(xiàn)中約束條件為非函數(shù)定義的凸性區(qū)域，因此在某些情況下進(jìn)行投影計(jì)算是困難的。在文獻(xiàn)[11]中，廣義動(dòng)態(tài)規(guī)格非線性規(guī)劃單元G-NPC(GeneralizedNPC)模型被提出,它可以解決非光滑非線性優(yōu)化問題，此模型采用懲罰函數(shù)方法來求解原始問題的最優(yōu)解。然而，此模型要求目標(biāo)函數(shù)必須滿足李普西茨條件。鑒于文獻(xiàn)[10]和文獻(xiàn)[11]中出現(xiàn)的不足，本文提出一類新的解決優(yōu)化問題的神經(jīng)網(wǎng)絡(luò)，其限制條件為不等式區(qū)域，與文獻(xiàn)[10]相比不需進(jìn)行投影計(jì)算。此外，問題的目標(biāo)函數(shù)可以是非李普西茨函數(shù)，克服了文獻(xiàn)[11]中要求目標(biāo)函數(shù)須滿足李普西茨條件的不足。

本論文的結(jié)構(gòu)組織如下：第1節(jié)詳細(xì)地描述了在本論文將出現(xiàn)的相關(guān)符號(hào)、定義以及要解決的優(yōu)化問題；第2節(jié)提出光滑神經(jīng)網(wǎng)絡(luò)模型；第3節(jié)對(duì)光滑神經(jīng)網(wǎng)絡(luò)能夠解決原始優(yōu)化問題做了充分的理論分析；第4節(jié)提出兩個(gè)仿真實(shí)驗(yàn)例子，證明了理論的有效性。

2預(yù)備工作

本部分主要對(duì)相關(guān)問題做一個(gè)簡要的介紹，以及對(duì)相關(guān)概念、符號(hào)做一個(gè)簡要的描述。本文要解決的最優(yōu)化問題的描述如下：

(1)

這里0

定義1如果存在正數(shù)κ和ε，使得對(duì)于任意x1，x2∈x+εb(0，1)，|f(x2)-f(x1)|≤κ‖x2-x1‖成立，那么函數(shù)f:Rn→R在x∈Rn處滿足李普西茨條件，若f:Rn→R在其定義域內(nèi)所有點(diǎn)都滿足李普西茨條件，則函數(shù)f:Rn→R是局部李普希茨函數(shù)。

(2)

定義3對(duì)于x*∈S，如果x*滿足:

(3)

則x*為式(1)所述優(yōu)化問題的一個(gè)穩(wěn)定點(diǎn)。

參考文獻(xiàn)對(duì)于本文所提到的正則函數(shù)，絕對(duì)連續(xù)函數(shù)以及上半連續(xù)函可以[6,12,15]，在此不贅述。 附中文

3模型描述

為了解決式(1)所述優(yōu)化問題，本文所提出的光滑神經(jīng)網(wǎng)絡(luò)的模型描述如下：

(4)

其中，懲罰因子δ>0,

假設(shè)1約束函數(shù)-hj(x):Rn→R，j=1，2,…,q是凸函數(shù)，且存在0∈int(S)，使得hj(0)>0，j=1，2,…,q。

引理1對(duì)于任意初始點(diǎn)x0∈b(0，R)，光滑神經(jīng)網(wǎng)絡(luò)至少存在滿足式(4)的一個(gè)局部解。

證明因-hj(x)：Rn→R，j=1，2,…,q滿足局部李普西茨條件，式(4)的右邊是一個(gè)上半連續(xù)的極值映射函數(shù)，所以在[0，t1]內(nèi)必存在局部解x(t)滿足式(4)，其中x(0)=x0是其初始點(diǎn)，[0，t1]為最大時(shí)間間隔。

□

即:

(5)

(6)

(7)

4主要結(jié)果

這部分主要介紹光滑神經(jīng)網(wǎng)絡(luò)解的有界性、全局性、神經(jīng)網(wǎng)絡(luò)的聚點(diǎn)和穩(wěn)定點(diǎn)的關(guān)系。在本文的主要理論證明中，我們將使用xt和ut來表示x(t)和u(t)。

證明因?yàn)?hj在Rn→R上是凸函數(shù)且hj(0)>0。那么對(duì)于任意x∈RnS，以下關(guān)系式成立：

其中zj∈?(-hj(x))。

因?yàn)閦∈?H(x),

所以:

因此:

□

證明當(dāng)x(t)∈b(0，R)S時(shí)，可知:

其中,υ(t)∈。

由引理2可知,

所以：

(8)

而

(9)

由式(8)和式(9)可得:

(10)

□

因?yàn)閤(t)在局部解存在的最大時(shí)間間隔[0，t1]內(nèi)一致有界，通過解的擴(kuò)展性定理[14]可知光滑神經(jīng)網(wǎng)絡(luò)在[0，∞)內(nèi)有解，即存在全局解。

□

證明

(11)

由式(2)可知:

(12)

(13)

由式(11)和式(13)可得:

(14)

(15)

因?yàn)閒(xt)+δH(xt)是連續(xù)函數(shù)，由定理1和推論1可知x(t)∈b(0，R)，?t∈[0，∞)，所以f(xt)+δH(xt)在xt∈b(0，R)上必有下界，結(jié)合式(15)可得:

(16)

□

證明根據(jù)H(x)的定義以及假設(shè)1，可知H(x)是正則函數(shù)。根據(jù)鏈?zhǔn)椒▌t可得：

(17)

(18)

對(duì)式(18)從[0，t](t>0)上積分得：

因此，當(dāng)t≥H(x(0))/k時(shí)，H(x(t))≤0。

□

證明因?yàn)閤t在可行域b(0，R)上一致有界，所以xt至少存在一個(gè)聚點(diǎn)。如果x*是xt的一個(gè)聚點(diǎn)，則存在數(shù)列{tk}，當(dāng)limk→∞tk=∞時(shí)，limk→∞xtk=x*，limk→∞utk=0。由定理3可知，x*∈S。

式(4)兩邊乘以x(tk)可變?yōu)?

(19)

對(duì)式(19)兩邊取極限:

(20)

(21)

如果xt有兩個(gè)聚點(diǎn)x*和y*，則存在兩個(gè)數(shù)列{tk}和{sk}使得limk→∞tk=limk→∞sk=∞，limk→∞xtk=x*，limk→∞xsk=y*。因?yàn)閤(t)∈b(0，R)是連續(xù)有界函數(shù)，所以x*到y(tǒng)*之間必存在一條路徑o(x*，y*)，使得o(x*，y*)上的所有點(diǎn)都是聚點(diǎn),從而都是式(1)所述優(yōu)化問題的穩(wěn)定點(diǎn)，這與假定式(1)所有的穩(wěn)定點(diǎn)是孤立點(diǎn)相矛盾。

□

5實(shí)驗(yàn)仿真結(jié)果

為了證明所提出神經(jīng)網(wǎng)絡(luò)模型及相關(guān)理論的有效性，用以下三個(gè)受限問題的仿真實(shí)驗(yàn)進(jìn)行驗(yàn)證。仿真實(shí)驗(yàn)是在Matlab R2012a平臺(tái)下進(jìn)行的。實(shí)驗(yàn)1的最優(yōu)化問題的目標(biāo)函數(shù)是非李普西茨函數(shù)，可行域由線性不等式函數(shù)組成。實(shí)驗(yàn)2的最優(yōu)化問題的目標(biāo)函數(shù)是非李普西茨函數(shù)，可行域由線性不等式和非線性不等式函數(shù)組成。實(shí)驗(yàn)3主要是為了將本文和文獻(xiàn)[10]進(jìn)行比較，以證明在實(shí)驗(yàn)3滿足文獻(xiàn)[10]的目標(biāo)函數(shù)和可行域的條件下，當(dāng)實(shí)驗(yàn)3和實(shí)驗(yàn)1的初始點(diǎn)相同時(shí)，實(shí)驗(yàn)3依然能實(shí)現(xiàn)實(shí)驗(yàn)1的效果，即本文中所闡述的理論和文獻(xiàn)[10]一樣能找到最優(yōu)點(diǎn)，只是本文和文獻(xiàn)[10]相比，沒有使用投影算子，減少了計(jì)算量。

實(shí)驗(yàn)1

可行域：h(x)=0.5x1-x2+4≥0

首先，確定球形區(qū)域b(0，R)中的R、懲罰因子δ以及連續(xù)單調(diào)函數(shù)u。根據(jù)可行域覆蓋范圍，R取值為8，連續(xù)單調(diào)遞減函數(shù)為u=e-0.1·t-2。在本文所做的仿真實(shí)驗(yàn)中，當(dāng)u<0.018時(shí)，程序停止運(yùn)行。懲罰因子δ根據(jù)式(5)~式(7)估算：

這里δ取值15。

對(duì)于原始受限問題，在可行域范圍內(nèi)當(dāng)x1=x2時(shí)目標(biāo)函數(shù)取得最小值，此時(shí)的(x1，x2)T為原始優(yōu)化問題的最優(yōu)解。為了驗(yàn)證理論的正確性，我們?nèi)我馊∪齻€(gè)點(diǎn)(-6，5)T、(-3，4)T和(2，-4)T。圖1表明這三個(gè)初始點(diǎn)分別收斂于以下可行域中的三個(gè)點(diǎn)(-1.325，-1.325)T、(0.2，0.2)T和(-1，-1)T。顯然它們都是原始優(yōu)化問題的最小值。

Figure 1　Move track of the state vector x(t)圖1　狀態(tài)向量x(t)的運(yùn)動(dòng)軌跡圖

實(shí)驗(yàn)2

和實(shí)驗(yàn)1的實(shí)驗(yàn)步驟一樣，這里R取值4，δ取值為15，對(duì)于初始點(diǎn)分三種情況進(jìn)行舉例說明：

(1)初始點(diǎn)(-3，-1)T在可行域外。從圖2可以看到，當(dāng)t>2s時(shí)，狀態(tài)向量x(t)在可行域中且趨向穩(wěn)定，程序結(jié)束時(shí)的值為(-0.752 5，0.376 3)T。從原始優(yōu)化問題的目標(biāo)函數(shù)中可以看出，當(dāng)x1=-2·x2時(shí)，目標(biāo)函數(shù)取得最優(yōu)解，可知(-0.752 5，0.376 3)T非常接近原始優(yōu)化問題的最優(yōu)解。

Figure 2　Move track of the initial point (-3，-1)T圖2　初始點(diǎn)為(-3，-1)T的運(yùn)動(dòng)軌跡圖

(2)初始點(diǎn)(1，1.5)T在可行域內(nèi)。從圖3可以看到，當(dāng)t>2s時(shí)，狀態(tài)向量x(t)在可行域內(nèi)且趨向穩(wěn)定，程序結(jié)束時(shí)的值為(0.2，-0.1)T，顯然是原始優(yōu)化問題的最優(yōu)解。

Figure 3　Move track of the initial point (1，1.5)T圖3　初始點(diǎn)為(1，1.5)T的運(yùn)動(dòng)軌跡圖

(3)初始點(diǎn)(-2，0)T在可行域的邊界上。從圖4可以看到，當(dāng)t>0.5s時(shí)狀態(tài)向量x(t)在可行域內(nèi)且趨向穩(wěn)定，程序結(jié)束時(shí)的值為(-1.102 8，0.551 4)T，顯然是原始優(yōu)化問題的最優(yōu)解。

Figure 4　Move track of the initial point (-2，0)T圖4　初始點(diǎn)為(-2，0)T的運(yùn)動(dòng)軌跡圖

實(shí)驗(yàn)3

Figure 5　Move tracks of three additional state vectors圖5　附加狀態(tài)向量運(yùn)動(dòng)軌跡圖

6結(jié)束語

本文介紹了一類非李普西茨受限優(yōu)化問題，通過光滑逼近技術(shù)以及結(jié)合懲罰函數(shù)方法，構(gòu)建了光滑神經(jīng)網(wǎng)絡(luò)模型，擴(kuò)大了G-NPC模型的應(yīng)用范圍，為解決信號(hào)重建、圖像修復(fù)等應(yīng)用提供了一種新的神經(jīng)網(wǎng)絡(luò)模型。本文對(duì)受限非李普西茨優(yōu)化問題的穩(wěn)定點(diǎn)進(jìn)行了定義。在一個(gè)比較溫和的條件下，證明了解的全局性、有界性，以及所建光滑神經(jīng)網(wǎng)絡(luò)的任意聚點(diǎn)是原始優(yōu)化問題的穩(wěn)定點(diǎn)等結(jié)論。最后，通過幾個(gè)仿真實(shí)驗(yàn)驗(yàn)證了理論的確性。除此之外，通過詳細(xì)的實(shí)驗(yàn)對(duì)比，證明本理論和文獻(xiàn)[10]提出的理論一樣，都能實(shí)現(xiàn)找到原始優(yōu)化問題最優(yōu)解的目的，只是本文不需進(jìn)行投影計(jì)算而已。

[1]GaoYun.Theneuralnetworkforsovingoptimationproblems[D].Wuxi:JiangnanUniversity，2011．(inChinese)

[2]TankDW,HopfieldJJ.Simpleneuraloptimizationnetworks:Ana/dconverter,signaldecisioncircuit,andalinearprogrammingcircuit[J].IEEETransactionsonCircuitsSystem，1986，33(5):533-541．

[3]KennedyM,ChuaL.Neuralnetworksfornonlinearprogramming[J].IEEETransactionsonCircuitsSystem,1988，35(5):554-562.

[4]HuangYuan-can.Lagrange-typeneuralnetworksfornonlinearprogrammingproblemswithinequalityconstraints[C]∥Procofthe44thIEEEConferenceonDecisionandControl，andtheEuropeanControlConference,2005:4129-4133．

[5]HuangYuan-can.AnewtypeofLagrangenonlinearprogrammingneuralnetwork[J].ACTAElectronicaSinica，2002，30(1):27-29．(inChinese)

[6]LiGuo-cheng,SongShi-ji,WuCheng.Generalizedgradientprojectionneuralnetworksfornonsmoothoptimizationproblems[J].ScienceChinaInformationSciences,2010,53(5):990-1005．

[7]LiuQing-shan,WangJun.Aone-layerrecurrentneuralnetworkforconstrainednonsmoothoptimization[J].IEEETransactionsonSystems,Man,andCybernetics—PARTB:Cybernetics，2011，41(5):1323-1333．

[8]LiuQing-shan，TangChuang-ying，HuangTing-wen.Aone-layerrecurrentneuralnetworkforreal-timeportfoliooptimizationwithprobabilitycriterion[J].IEEETransactionsonCybernetics，2013，43(1):14-23．

[9]ChenXiao-jun.Smoothingmethodsfornonsmoothnonconvexminimization[J].MathematicalProgramming，2012，134(1):71-99．

[10]BianWei,ChenXiao-jun.Smoothingneuralnetworkforconstrainednon-Lipschitzoptimizationwithapplication[J].IEEETransactionsonNeuralNetworkandLearningSystems,2012,23(3):399-411．

[11]FortiM,NistriP,QuincampoixM.Generalizedneuralnetworkfornonsmoothnonlinearprogrammingproblems[J].IEEETransactionsonCircuitsandSystems—I，2004，41(5):1741-1754．

[12]HanZheng-zhi,CaiXiu-shan,HuangJun.Thetheoryforcontrolsystemsdescribedbydifferentialconclusions[M].Shanghai:ShanghaiJiaoTongUniversityPress，2013．(inChinese)

[13]FilippovAF.Differentialequationswithdiscontinuousright-handside[M]∥MathematicsandItsApplications(SovietSeries).Boston,MA:Kluwer,1988．

[14]BetounesD.Differentialequations:Theoryandapplications[M].NewYork:Springer-Verlag,2009．

[15]AubinJP,CellinaA.Differentialinclusion:Set-valuedmapsandviabilitytheory[M].NewYork:Springer-Verlag,1984．

[16]HamFM,KostanicI.Principlesofneurocomputingforscience&engineering[M].YeShi-wei，WangHai-juanTranslated.Beijing:ChinaMachinePress，2007．(inChinese)

[1]高云.求解優(yōu)化問題的神經(jīng)網(wǎng)絡(luò)方法[D].無錫:江南大學(xué)，2011．

[4]黃遠(yuǎn)燦.一種新型的Lagrange非線性規(guī)劃神經(jīng)網(wǎng)絡(luò)[J].電子學(xué)報(bào)，2002，30(1):27-29．

[12]韓正之，蔡秀珊，黃俊.微分包含控制系統(tǒng)理論[M].上海:上海交通大學(xué)出版社，2013．

[16]HamFM,KostanicI.神經(jīng)計(jì)算原理[M].葉世偉,王海娟,譯.北京:機(jī)械工業(yè)出版社,2007．

喻昕(1973-),男，重慶榮昌人，博士，教授，CCF會(huì)員(E200011072M)，研究方向?yàn)槿斯ど窠?jīng)網(wǎng)絡(luò)和優(yōu)化計(jì)算。E-mail:Yuxin21@126.com

YUXin,bornin1973,PhD,professor,CCFmember(E200011072M)，hisresearchinterestsincludeartificialneuralnetworks,andoptimizationcalculation.

謝緬(1990-),女，湖北潛江人，碩士生，研究方向?yàn)槿斯ど窠?jīng)網(wǎng)絡(luò)和優(yōu)化計(jì)算。E-mail:996927697@qq.com

XIEMian,bornin1990,MScandidate,herresearchinterestsincludeartificialneuralnetworks,andoptimizationcalculation.

李晨宇(1989-),男，湖南寧遠(yuǎn)人，碩士生，研究方向?yàn)槿斯ど窠?jīng)網(wǎng)絡(luò)和優(yōu)化計(jì)算。E-mail:329243522@qq.com

LIChen-yu,bornin1989,MScandidate,hisresearchinterestsincludeartificialneuralnetworks,andoptimizationcalculation.

Solvingnon-Lipschitzoptimizationproblemsbysmoothingneuralnetworks

YUXin,XIEMian,LIChen-yu

(SchoolofComputer&ElectronicsandInformation，GuangxiUniversity,Nanning530004,China)

Abstract:In order to seek to optimal solution satisfying the necessary conditions of optimality, aiming at the optimization problems that objective functions are non-Lipschitz and the feasible region consists of linear inequality or nonlinear inequality, we design a new smooth neural network by the penalty function method and the smoothing approximate techniques which convert non-smoothing objective functions into smoothing functions. Detailed theoretical analysis proves the uniform boundedness and globality of the solutions to smooth neural networks, regardless of the initial points inside or outside of the feasible domain. Moreover, any accumulation point of the solutions of to smooth neural networks is a stationary point of the optimization promble. Numerical examples also demonstrate the effectiveness of the method.

Key words:non-Lipschitz function;smoothing approximate techniques;stationary point;accumulation point

作者簡介:

doi:10.3969/j.issn.1007-130X.2015.12.011

中圖分類號(hào)：TP183

文獻(xiàn)標(biāo)志碼：A

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61462006)；廣西區(qū)自然科學(xué)基金資助項(xiàng)目(2014GXNSFAA118391)

收稿日期：修回日期：2015-03-23

文章編號(hào)：1007-130X(2015)12-2262-08