求解廣義凸規劃的神經網絡方法

楊靜俐

（福州海峽職業技術學院基礎教學部，福建福州350002）

求解廣義凸規劃的神經網絡方法

楊靜俐

（福州海峽職業技術學院基礎教學部，福建福州350002）

提出了一種求解具有線性約束的廣義凸規劃的神經網絡方法，其基本思想是從數值逼近的方法出發，基于Fibonacci法的基本思想，結合神經網絡的結構特性，構造出一種求解廣義凸規劃的神經網絡學習算法。此算法收斂速度快，求解精度高，對目標函數要求較低，仿真實驗驗證了其有效性。

廣義凸規劃；Fibonacci法；神經網絡；學習算法

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

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

1 預備知識

1.1 凸分析基礎理論

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

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

圖1 擬凸函數

考慮如下優化問題：

若問題（GCP）的可行集F是凸集，f（x）是F上的（嚴格）擬凸函數或（嚴格）偽凸函數，則稱問題（GCP）為廣義凸規劃問題。

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

1.2 Fibonacci法基本思想

Fibonacci數定義如下：

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

可以用以下公式來描述：

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

根據最終區間長度的上界ε，由（2）式可以求出Fibonocci數Fn，再根據（3）式，可以確定出n，從而搜索一直進行到第n個搜索點為止。

基于Fibonacci法求解優化問題的步驟如下：

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

令k=1；

步驟2：若|bk-ak|＜ε，計算結束，最優解x＊∈[ak-bk]，可取x＊=（bk-ak）/2，否則，令

計算f（λk），f（μk），若f（λk）＞f（μk），則轉步驟3，若f（λk）≤f（μk），則轉步驟4；

計算f（μk）；

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

計算f（λk+1）；

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

2 神經網絡拓撲結構

基于Fibonacci法的基本思想，本文構造如下前向神經網絡，網絡結構圖為：

圖2 基于Fibonacci法神經網絡的拓撲結構圖

文中符號表示為：

Ni,j：第i層的第j個神經元，i＝0為輸入層；neti,j：神經元Ni,j的輸入值；Oi,j：神經元Ni,j的輸出值；

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

本文構造了一個包含1個輸入層、3個隱含層、1個輸出層和1個反饋層的6層神經網絡。圖2構造的神經網絡計算步驟為：

(Ⅰ)輸入層：將迭代區間[ak,bk]的兩端點作為神經網絡的輸入，N0,1與N0,2對應的輸入分別為：

（Ⅴ）迭代：將輸出神經元同時作為反饋部分的輸入，若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，循環，直到滿足要求的精度為止。

3 神經網絡學習算法

對于具有線性約束的廣義凸規劃問題，利用上文構造的神經網絡模型，提出的學習算法如下：

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

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

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

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

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

5 結論

本文結合Fibonacci的基本思想，利用神經網絡的結構特性，提出了一種求解具有線性約束廣義凸規劃的神經網絡模型，此模型對具有雙邊約束的線性規劃問題同樣適用。而且隨著優化問題維數的不斷升高，神經網絡學習算法的優越性越發明顯。

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

[2]杜廷松,費浦生,蹇繼貴.非凸二次規劃全局極小問題的新型分枝定界算法[J].計算機工程與應用,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].運籌學學報.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]楊靜俐,杜廷松.求解線性約束的二次規劃神經網絡學習新算法[J].計算機工程與應用,2010(24):37-39,192.

O224

A

1673-8535(2013)06-0047-06

楊靜俐（1983-）,女，湖北荊門人，福州海峽職業技術學院教師，研究方向：優化理論與算法、神經網絡及其應用。

（責任編輯：高堅）

2013-09-30