?

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

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

喻昕,謝緬,李晨宇

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

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

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

1引言

在科學和技術(shù)領(lǐng)域中，如最優(yōu)控制、信號處理以及模式識別等應(yīng)用經(jīng)常會遇到優(yōu)化問題。傳統(tǒng)上一般采用數(shù)值計算的方法來解決線性或非線性規(guī)劃問題，例如牛頓梯度法、罰函數(shù)法等等。很多工程應(yīng)用往往需要得到優(yōu)化問題的實時解。然而傳統(tǒng)的數(shù)值方法往往無法滿足實時的要求，因為它計算解的時間依賴于問題的維數(shù)與結(jié)構(gòu)以及算法的復(fù)雜度。求解優(yōu)化問題實時解的一個可行且很理想的方法就是應(yīng)用人工神經(jīng)網(wǎng)絡(luò)?；谀M電路的神經(jīng)網(wǎng)絡(luò)，由于其內(nèi)在的大規(guī)模并行運算和快速收斂性，可用它進行優(yōu)化問題的實時求解[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ī)劃問題的動態(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ò)模型文獻中，可以發(fā)現(xiàn)它們都有一個顯著的相似點，就是它們所要求的目標函數(shù)必須要滿足李普西茨條件，但是在許多重要的應(yīng)用中，比如圖像修復(fù)、信號重建以及變量選取等應(yīng)用中，最優(yōu)化問題并不滿足李普西茨條件，那么對于這樣的問題，上述文獻所提到的神經(jīng)網(wǎng)絡(luò)模型則不能解決。

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

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

2預(yù)備工作

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

(1)

這里0

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

(2)

定義3對于x*∈S，如果x*滿足:

(3)

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

參考文獻對于本文所提到的正則函數(shù)，絕對連續(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對于任意初始點x0∈b(0，R)，光滑神經(jīng)網(wǎng)絡(luò)至少存在滿足式(4)的一個局部解。

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

□

即:

(5)

(6)

(7)

4主要結(jié)果

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

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

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

因為z∈?H(x),

所以:

因此:

□

證明當x(t)∈b(0，R)S時，可知:

其中,υ(t)∈。

由引理2可知,

所以：

(8)

而

(9)

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

(10)

□

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

□

證明

(11)

由式(2)可知:

(12)

(13)

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

(14)

(15)

因為f(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ù)鏈式法則可得：

(17)

(18)

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

因此，當t≥H(x(0))/k時，H(x(t))≤0。

□

證明因為xt在可行域b(0，R)上一致有界，所以xt至少存在一個聚點。如果x*是xt的一個聚點，則存在數(shù)列{tk}，當limk→∞tk=∞時，limk→∞xtk=x*，limk→∞utk=0。由定理3可知，x*∈S。

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

(19)

對式(19)兩邊取極限:

(20)

(21)

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

□

5實驗仿真結(jié)果

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

實驗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。在本文所做的仿真實驗中，當u<0.018時，程序停止運行。懲罰因子δ根據(jù)式(5)~式(7)估算：

這里δ取值15。

對于原始受限問題，在可行域范圍內(nèi)當x1=x2時目標函數(shù)取得最小值，此時的(x1，x2)T為原始優(yōu)化問題的最優(yōu)解。為了驗證理論的正確性，我們?nèi)我馊∪齻€點(-6，5)T、(-3，4)T和(2，-4)T。圖1表明這三個初始點分別收斂于以下可行域中的三個點(-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)的運動軌跡圖

實驗2

和實驗1的實驗步驟一樣，這里R取值4，δ取值為15，對于初始點分三種情況進行舉例說明：

(1)初始點(-3，-1)T在可行域外。從圖2可以看到，當t>2s時，狀態(tài)向量x(t)在可行域中且趨向穩(wěn)定，程序結(jié)束時的值為(-0.752 5，0.376 3)T。從原始優(yōu)化問題的目標函數(shù)中可以看出，當x1=-2·x2時，目標函數(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　初始點為(-3，-1)T的運動軌跡圖

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

Figure 3　Move track of the initial point (1，1.5)T圖3　初始點為(1，1.5)T的運動軌跡圖

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

Figure 4　Move track of the initial point (-2，0)T圖4　初始點為(-2，0)T的運動軌跡圖

實驗3

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

6結(jié)束語

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

[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].無錫:江南大學，2011．

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

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

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

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

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

謝緬(1990-),女，湖北潛江人，碩士生，研究方向為人工神經(jīng)網(wǎng)絡(luò)和優(yōu)化計算。E-mail:996927697@qq.com

XIEMian,bornin1990,MScandidate,herresearchinterestsincludeartificialneuralnetworks,andoptimizationcalculation.

李晨宇(1989-),男，湖南寧遠人，碩士生，研究方向為人工神經(jīng)網(wǎng)絡(luò)和優(yōu)化計算。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

中圖分類號：TP183

文獻標志碼：A

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

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

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