求解廣義凸規(guī)劃的神經(jīng)網(wǎng)絡(luò)方法

楊靜俐

（福州海峽職業(yè)技術(shù)學(xué)院基礎(chǔ)教學(xué)部，福建福州350002）

求解廣義凸規(guī)劃的神經(jīng)網(wǎng)絡(luò)方法

楊靜俐

（福州海峽職業(yè)技術(shù)學(xué)院基礎(chǔ)教學(xué)部，福建福州350002）

提出了一種求解具有線性約束的廣義凸規(guī)劃的神經(jīng)網(wǎng)絡(luò)方法，其基本思想是從數(shù)值逼近的方法出發(fā)，基于Fibonacci法的基本思想，結(jié)合神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)特性，構(gòu)造出一種求解廣義凸規(guī)劃的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法。此算法收斂速度快，求解精度高，對(duì)目標(biāo)函數(shù)要求較低，仿真實(shí)驗(yàn)驗(yàn)證了其有效性。

廣義凸規(guī)劃；Fibonacci法；神經(jīng)網(wǎng)絡(luò)；學(xué)習(xí)算法

最優(yōu)化問題是運(yùn)籌學(xué)的一個(gè)重要組成部分，在自然科學(xué)、社會(huì)科學(xué)、生產(chǎn)實(shí)踐中有著重要的實(shí)用價(jià)值[1]，因此，在最近40多年中得到了迅速的發(fā)展和廣泛的應(yīng)用，而作為運(yùn)籌學(xué)中一個(gè)重要分支的數(shù)學(xué)規(guī)劃，影響則更為深遠(yuǎn)。近30年來，凸性理論已廣泛應(yīng)用到數(shù)學(xué)規(guī)劃的各個(gè)領(lǐng)域中[2]，但是在多種情況下，凸性對(duì)于數(shù)學(xué)規(guī)劃的結(jié)果只是充分條件而不是必要條件。同時(shí)，凸分析中很多重要性質(zhì)并不要求所討論的函數(shù)是凸函數(shù)，而只需要它的水平集是凸集，即函數(shù)具有廣義凸性[3]。因此，廣義凸性已成為數(shù)學(xué)規(guī)劃研究的一個(gè)新的發(fā)展趨勢(shì)。1970年，學(xué)者B.De Finetti首先研究了水平集是凸集的函數(shù)[4]，他發(fā)現(xiàn)這一類函數(shù)包括所有的凸函數(shù)，同時(shí)還包含一些非凸函數(shù)。W.Fenchel[5]把這類函數(shù)定義為擬凸函數(shù)，同時(shí)比較系統(tǒng)地研究了它的性質(zhì)。M.Slater較早的將Kuhn-Tucker鞍點(diǎn)等價(jià)定理推廣應(yīng)用于廣義凸規(guī)劃中，此后，從事廣義凸性研究的學(xué)者逐漸多起來，并且取得了一系列重要的成果，其中比較突出的是J.A.Ferland,J.P. Crouzeix[6]和楊新民[7]等人的工作。

人工神經(jīng)網(wǎng)絡(luò)是由許多并行工作的處理單元組成的系統(tǒng)，它的學(xué)習(xí)功能非常強(qiáng)大，還具有大規(guī)模并行計(jì)算的能力[8]。因此，神經(jīng)網(wǎng)絡(luò)為優(yōu)化問題的計(jì)算提供了一條非常有效的途徑，并成為求解最優(yōu)化問題的重要方法之一。1985年，Hopfield J.J和Tank D.W利用神經(jīng)網(wǎng)絡(luò)成功地解決了TSP問題[9]。此后，人們提出了許多神經(jīng)網(wǎng)絡(luò)模型，并將它們應(yīng)用于線性和非線性規(guī)劃中。然而，目前大多數(shù)學(xué)者都是研究求解凸二次規(guī)劃的神經(jīng)網(wǎng)絡(luò)模型[10]，對(duì)廣義凸規(guī)劃的求解，尚未建立較好的神經(jīng)網(wǎng)絡(luò)模型。基于此，本文從數(shù)值逼近的方法出發(fā)，基于Fibonacci法的基本思想，并結(jié)合神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)特性，提出了求解廣義凸規(guī)劃的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)新算法。同時(shí)構(gòu)造數(shù)值實(shí)例，對(duì)提出的神經(jīng)網(wǎng)絡(luò)算法進(jìn)行了仿真實(shí)驗(yàn)，驗(yàn)證了結(jié)果的有效性。

1 預(yù)備知識(shí)

1.1 凸分析基礎(chǔ)理論

引理1[11]設(shè)Ω∩Rn為非空凸集，f∶Ω→R，則f（x）為Ω上的擬凸函數(shù)的充要條件是：Ar∈R，水平集Hr（f）=｛x|x∈Ω，f（x）≤r｝是凸集。

注1：由于凸函數(shù)的水平集是凸集，則由引理1可知，凸函數(shù)一定是擬凸函數(shù)，而擬凸函數(shù)不一定是凸函數(shù)。如圖1，f（x）是擬凸函數(shù)，但不是凸函數(shù)。

圖1 擬凸函數(shù)

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

若問題（GCP）的可行集F是凸集，f（x）是F上的（嚴(yán)格）擬凸函數(shù)或（嚴(yán)格）偽凸函數(shù)，則稱問題（GCP）為廣義凸規(guī)劃問題。

定理1設(shè)問題（GCP）的可行集F是凸集，f（x）是F上的嚴(yán)格擬凸函數(shù)，則廣義凸規(guī)劃(GCP)的任一局部最優(yōu)解x＊也是它的全局最優(yōu)解。證明用反證法證明。

1.2 Fibonacci法基本思想

Fibonacci數(shù)定義如下：

從產(chǎn)量降低到幾無經(jīng)濟(jì)收益時(shí)開始，到大部分植株不能正常結(jié)果以及死亡時(shí)為止。由于骨干枝，特別是主干過于衰老，更新復(fù)壯的可能性除部分果樹（如某些柑桔類）外都很小，也無經(jīng)濟(jì)價(jià)值。應(yīng)砍伐清園，另建新園。

可以用以下公式來描述：

利用Fibonacci法求解優(yōu)化問題的基本思想是：確定初始搜索迭代區(qū)間[a1，b1]和迭代精度ε，在n次迭代之后，可以獲得最后搜索區(qū)間[a2，b2]，且滿足bn-an≤ε，則搜索區(qū)間長度的縮短率滿足

根據(jù)最終區(qū)間長度的上界ε，由（2）式可以求出Fibonocci數(shù)Fn，再根據(jù)（3）式，可以確定出n，從而搜索一直進(jìn)行到第n個(gè)搜索點(diǎn)為止。

基于Fibonacci法求解優(yōu)化問題的步驟如下：

步驟1：根據(jù)決策變量的約束條件a1≤x≤b1，確定初始搜索區(qū)間為[a1，b1]，設(shè)ε＞0為允許的最后搜索區(qū)間長度，根據(jù)（2）式和（3）式可以確定n，從而得到Fn，F(xiàn)n-1，F(xiàn)n-2，令

令k=1；

步驟2：若|bk-ak|＜ε，計(jì)算結(jié)束，最優(yōu)解x＊∈[ak-bk]，可取x＊=（bk-ak）/2，否則，令

計(jì)算f（λk），f（μk），若f（λk）＞f（μk），則轉(zhuǎn)步驟3，若f（λk）≤f（μk），則轉(zhuǎn)步驟4；

計(jì)算f（μk）；

步驟4：令ak+1＝ak，bk+1＝μk，再令

計(jì)算f（λk+1）；

步驟5：令k=k+1，返回步驟2。

2 神經(jīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

基于Fibonacci法的基本思想，本文構(gòu)造如下前向神經(jīng)網(wǎng)絡(luò)，網(wǎng)絡(luò)結(jié)構(gòu)圖為：

圖2 基于Fibonacci法神經(jīng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)圖

文中符號(hào)表示為：

Ni,j：第i層的第j個(gè)神經(jīng)元，i＝0為輸入層；neti,j：神經(jīng)元Ni,j的輸入值；Oi,j：神經(jīng)元Ni,j的輸出值；

ω（i,j）（k,l）：神經(jīng)元Ni,j與神經(jīng)元Nk,l的連接權(quán)值；閾值向量：θ＝0。

本文構(gòu)造了一個(gè)包含1個(gè)輸入層、3個(gè)隱含層、1個(gè)輸出層和1個(gè)反饋層的6層神經(jīng)網(wǎng)絡(luò)。圖2構(gòu)造的神經(jīng)網(wǎng)絡(luò)計(jì)算步驟為：

(Ⅰ)輸入層：將迭代區(qū)間[ak,bk]的兩端點(diǎn)作為神經(jīng)網(wǎng)絡(luò)的輸入，N0,1與N0,2對(duì)應(yīng)的輸入分別為：

（Ⅴ）迭代：將輸出神經(jīng)元同時(shí)作為反饋部分的輸入，若f（λk）＞f（μk），則ak+1＝λk，ak+1=bk，否則，若f（λk）≥f（μk），則令ak+1＝λk，bk+1＝μk。令k=1，k=k+1，循環(huán)，直到滿足要求的精度為止。

3 神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法

對(duì)于具有線性約束的廣義凸規(guī)劃問題，利用上文構(gòu)造的神經(jīng)網(wǎng)絡(luò)模型，提出的學(xué)習(xí)算法如下：

步驟1：根據(jù)約束條件，可以求出x的上界和下界，記為a1，b1，令網(wǎng)絡(luò)的初始輸入net0,1=a1，net0,2=b1，并給出迭代精度ε＞0，若｜b1-a1｜＜ε，則令最優(yōu)解x＊＝（a1+b1)/2，否則，取初始點(diǎn)x（0）=（a1+b1)，進(jìn)行下面步驟；

圖3 f（x1，x2)=-x1，x2的圖形

根據(jù)引理3可以判斷，目標(biāo)函數(shù)f（x1，x2)不是凸函數(shù)，而是擬凸函數(shù)。利用Matlab工具箱中quadprog命令求解，得理論最優(yōu)解為x*[2.0，3.0]T，理論最優(yōu)值為f*=-6。

利用文中構(gòu)造的神經(jīng)網(wǎng)絡(luò)模型求解，用Matlab軟件編程，令神經(jīng)網(wǎng)絡(luò)的初始輸入為x（0）=[1，2.5]T，取ε＝10－4，經(jīng)過20次迭代，得近似最優(yōu)解x*＝[1.999，3.000]T，近似最優(yōu)值為f*=-5.9997。決策變量的迭代收斂路徑如圖4：

圖4 x 1,x2的迭代收斂變化路徑

5 結(jié)論

本文結(jié)合Fibonacci的基本思想，利用神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)特性，提出了一種求解具有線性約束廣義凸規(guī)劃的神經(jīng)網(wǎng)絡(luò)模型，此模型對(duì)具有雙邊約束的線性規(guī)劃問題同樣適用。而且隨著優(yōu)化問題維數(shù)的不斷升高，神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法的優(yōu)越性越發(fā)明顯。

[1]HorstR,Pardalos PM,ThoaiNV.Introduction toglobaloptimization[M].Kluwer Academic Publisher,Chap 1-6,2000.

[2]杜廷松,費(fèi)浦生,蹇繼貴.非凸二次規(guī)劃全局極小問題的新型分枝定界算法[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(17):49-52.

[3]Stephem Boyd,Lieven Vandenberghe.Convex optimization[M].Cambridgeuniversity press.2004.

[4]Greenberg H J,PierskallaW P.A review ofquasi-convex function[J].OR,1971,19:1553-1570.

[5]FenchelW.Convex cones,setand functions[J].Princeton University,Princeton New Jersey,1951.

[6]Crouzeix JP,Ferland JA.Criteria for quasi-convexity and pseudoconvexity:ralationship and comparison[J]s.Math prog.1982,23: 193-205.

[7]Yang XM.A noteon criteriaofquasiconvex functiom[J].運(yùn)籌學(xué)學(xué)報(bào).2001,5(2):55-56.

[8]Xia Y S,Feng G,Wang J.A recurrentneuralnetwork with exponential convergence for solving convex quadratic program and related linear piecewiseequation[J].NeuralNetworks,2004,17:1003-1015.

[9]Hopfield JJ,Tank DW.Neuralcomputation ofdecisions in optimi-zation problems[J].Biol.Cybern,1985,52:141-152.

[10]楊靜俐,杜廷松.求解線性約束的二次規(guī)劃神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)新算法[J].計(jì)算機(jī)工程與應(yīng)用,2010(24):37-39,192.

O224

A

1673-8535(2013)06-0047-06

楊靜俐（1983-）,女，湖北荊門人，福州海峽職業(yè)技術(shù)學(xué)院教師，研究方向：優(yōu)化理論與算法、神經(jīng)網(wǎng)絡(luò)及其應(yīng)用。

（責(zé)任編輯：高堅(jiān)）

2013-09-30