解決約束偽凸優(yōu)化問題的神經(jīng)網(wǎng)絡(luò)模型

張 堅，李國成

(北京信息科技大學(xué) 理學(xué)院，北京 100192)

0 引 言

近年來，隨著科技的進步，神經(jīng)網(wǎng)絡(luò)因其大規(guī)模實時并行計算的特點被廣泛用于解決工程應(yīng)用和科學(xué)研究中遇到的優(yōu)化問題。神經(jīng)網(wǎng)絡(luò)優(yōu)化算法始于Hopfield和Tank[1-2]在1985-1986年的工作。他們將Hopfield型神經(jīng)網(wǎng)絡(luò)[3-4]，用于解決旅行商(TSP)問題及非線性光滑優(yōu)化問題，并取得巨大成功。

基于Hopfield和Tank開創(chuàng)性的工作，許多研究者針對光滑優(yōu)化問題，提出了不同的神經(jīng)網(wǎng)絡(luò)優(yōu)化模型。例如，Kennedy等[5]為解決非線性規(guī)劃問題，提出了帶懲罰參數(shù)的動態(tài)正則非線性規(guī)劃電路(NPC)。Xia等[6]為解決約束優(yōu)化問題，提出了投影算子神經(jīng)網(wǎng)絡(luò)模型。Hu等[7]針對一類二次規(guī)劃問題提出了一個改進的對偶神經(jīng)網(wǎng)絡(luò)模型，并將它用于解決贏者通吃問題，等等。但上述模型無法解決非光滑優(yōu)化問題。這時，人們嘗試引進新理論、新方法。例如，微分包含理論及Clarke非光滑分析等。

Forti等[8]基于微分包含及Clarke次梯度理論，提出了一種廣義神經(jīng)網(wǎng)絡(luò)模型用以解決非光滑非線性優(yōu)化問題(G-NPC)。Bian等[9-10]為解決非光滑非凸優(yōu)化問題，提出了基于次梯度的神經(jīng)網(wǎng)絡(luò)；同時較為系統(tǒng)地研究了Rn中的非光滑優(yōu)化問題，并提出了基于微分包含理論并帶有精確罰因子的神經(jīng)網(wǎng)絡(luò)。Li等[11]基于微分包含理論及精確罰函數(shù)的思想提出了一種單層的遞歸神經(jīng)網(wǎng)絡(luò)來解決不等式約束的非凸優(yōu)化問題。

遺憾的是，精確罰因子計算復(fù)雜且須在網(wǎng)絡(luò)運行前給出，同時取值不同也影響神經(jīng)網(wǎng)絡(luò)的性能。這促使研究者們傾向不帶精確罰因子的神經(jīng)網(wǎng)絡(luò)。比如，Qin等[12]針對非光滑凸優(yōu)化問題，提出了不帶精確罰因子的雙層神經(jīng)網(wǎng)絡(luò)。但它相較單層網(wǎng)絡(luò)，計算復(fù)雜度有所增加。鑒于此，Qin等[13]針對帶有等式和不等式約束的偽凸優(yōu)化問題，提出了不帶精確罰因子的單層神經(jīng)網(wǎng)絡(luò)。回曉丹[14]針對帶凸不等式約束的偽凸優(yōu)化問題提出了基于微分包含理論和罰函數(shù)思想的不帶精確罰函數(shù)但含有粘性正則項的單層遞歸網(wǎng)絡(luò)模型。Bian等[15]則利用光滑逼近的方法，提出了解決廣義凸約束的非光滑偽凸優(yōu)化問題的神經(jīng)網(wǎng)絡(luò)。但該網(wǎng)絡(luò)的初始點必須選在等式約束的范圍內(nèi)，降低了適用性。此外，喻昕等[16-18]也提出了基于微分包含理論且不帶精確罰因子的神經(jīng)網(wǎng)絡(luò)模型以解決約束偽凸優(yōu)化問題。

為解決凸不等式約束的非光滑偽凸優(yōu)化問題，本文基于微分包含理論和罰函數(shù)思想，構(gòu)建了不帶精確罰因子的神經(jīng)網(wǎng)絡(luò)模型。本文的網(wǎng)絡(luò)模型與文獻[18]一樣巧妙地利用了凸函數(shù)的性質(zhì)，從而能夠在有限時間內(nèi)收斂到可行域，且永駐其中。同時，借助于偽凸函數(shù)的性質(zhì)，本文的網(wǎng)絡(luò)模型最終能夠快速收斂到原優(yōu)化問題的最優(yōu)解集。本文最大的亮點在于引入變步長，并給出了變步長選取原則及兩個選取公式。變步長的引入使得網(wǎng)絡(luò)的收斂效率有了極大的提升。

1 問題描述及預(yù)備知識

本節(jié)首先闡述所要研究的問題，然后給出一些必要的預(yù)備知識。

1.1 問題描述

本文研究如下問題：

minimizef(x)

subject togi(x)≤0i=1，2，…,m

(1)

問題(1)的最優(yōu)解集設(shè)為：

本文總是假定：

1.2 預(yù)備知識

定義1設(shè)X，Y均為Rn的非空子集。若?x∈X都有非空子集F(x)?Y，則稱F:X→Y為集值映射。若?x0∈X，V?F(x0)，都存在x0的一個鄰域U使得F(U)?V，則稱F在x0處上半連續(xù)(u.s.c)。若F在X的每一點處都上半連續(xù)，則稱F是上半連續(xù)函數(shù)。

定義2設(shè)函數(shù)f在x點處附近Lipschitz，則f在x點處沿方向υ∈Rn的廣義方向?qū)?shù)為：

此時，f在x點處的Clarke廣義梯度定義為：

?f(x)={ξ∈Rn∶f°(x;υ)≥〈υ,ξ〉,?υ∈Rn}

定義3若函數(shù)f:Rn→R在x點附近Lipschitz且滿足以下兩個條件：

1) ?υ∈Rn,單邊方向?qū)?shù)

存在；

2) ?υ∈Rn,f′(x;υ)=f°(x;υ)

則稱f在x點正則。若f在其定義域的每一點都正則，則稱f為正則函數(shù)。

命題1[10]設(shè)f:Rn→R在x點附近Lipschitz，

1) 若f在x點嚴(yán)格可微，則f在x點正則；

2) 若f是凸函數(shù)，則f在x點正則。

命題3[10](鏈?zhǔn)椒▌t) 如果f(x)∶Rn→R在x(t)處正則,且x(t):[0,+∞)→Rn在t點可導(dǎo)同時在t點附近Lipschitz，那么

命題5[10]若f:Rn→R為凸函數(shù)，則有

ξ∈?f(x)??y∈Rn

f(y)≥f(x)+〈ξ,y-x〉

定義5對連續(xù)函數(shù)f:Rn→R，若?x，y∈Rn，有

?η∈?f(x)

s.t.〈η,y-x〉≥0?f(y)≥f(x)

則稱f為偽凸函數(shù)。

2 構(gòu)造神經(jīng)網(wǎng)絡(luò)模型

本節(jié)根據(jù)懲罰函數(shù)的思想構(gòu)造網(wǎng)絡(luò)?？紤]如下函數(shù)：

I0(x)={i∶gi(x)=0 ?i∈I}

I+(x)={i∶gi(x)>0 ?i∈I}

再根據(jù)命題1到命題3，得到P(x)在x點的Clarke廣義梯度為：

?P(x)=

(2)

與已有模型性能比較如表1所示。

表1 不同模型的性能比較

表1表明，本文的神經(jīng)網(wǎng)絡(luò)模型同文獻[13]和[15]中的模型相比是有一定優(yōu)勢的，至少可行域無需有界。而與文獻[14]及[18]中的模型相比，因為彼此都是針對凸不等式約束偽凸優(yōu)化問題的神經(jīng)網(wǎng)絡(luò)優(yōu)化模型，故它們具有諸多相似的優(yōu)點。比如：無需計算精確罰因子，初始點的選取任意，可行域無需有界，能夠快速收斂到原優(yōu)化問題的最優(yōu)解集等。不同點在于，與文獻[14]相比，本文的神經(jīng)網(wǎng)絡(luò)參數(shù)更少，不含時間粘性正則項，僅需目標(biāo)函數(shù)的Clarke廣義梯度信息就能起到與時間粘性正則項相似的作用，即加速網(wǎng)絡(luò)收斂。而與文獻[18]相比，在某種程度上，本文可看作其改進模型，針對性更強，在滿足精度要求的條件下收斂速度也更快。

3 主要結(jié)論

本節(jié)證明網(wǎng)絡(luò)(2)的優(yōu)化性能。

定理1對任意初始點，網(wǎng)絡(luò)(2)都存在至少一個局部解。

證明易知網(wǎng)絡(luò)(2)的右端是一個非空緊凸的上半連續(xù)集值映射。根據(jù)命題4，對任意初始點x(t0)=x0∈Rn，網(wǎng)絡(luò)(2)都存在至少一個局部解x(t)(t∈[0,T))。其中T表示局部解的最大存在時刻。證畢。

其中，I+(x)非空。又?P(x)是非空緊凸的上半連續(xù)集值映射，則?η∈?P(x)，存在αi∈[0,1]使得

根據(jù)命題5，

證畢。

注解1文獻[18]雖給出了引理1但并未給予證明，這里給出完整的證明過程以及更清晰合理的表述。

成立。

引用引理1，有

證畢。

據(jù)引理1～2，得到網(wǎng)絡(luò)的有限時間收斂定理：

定理2對任意初始點，網(wǎng)絡(luò)(2)的狀態(tài)向量x(t)都會在有限時間內(nèi)收斂到可行域，并永駐其中。

以及?α∈?f(x(t))使得

那么

(3)

對式(3)兩邊從0到t積分得到

{t:P(x(t))>0,t∈[0,t1)}?

(4)

在證明網(wǎng)絡(luò)(2)解的全局存在性前，需要如下的引理：

定理3對任意初始點，狀態(tài)向量x(t)有界，網(wǎng)絡(luò)(2)具有全局解。

因為x(t)絕對連續(xù)，易知E(x(t))是非負正則凸函數(shù)。根據(jù)命題3，存在可測函數(shù)α′(t)∈?f(x(t))，β′(t)∈?P(x(t))，使得

以及

根據(jù)命題5又有

于是得到

從而，E(x(t))是單調(diào)不增的。立即有

那么

也即x(t)有界。再聯(lián)合推論1，知?x0=x(0)∈Rn，x(t)仍是有界的。根據(jù)解可擴展定理，網(wǎng)絡(luò)(2)的解是全局存在的，即x(t)(?t∈[0,+∞))。證畢。

設(shè)網(wǎng)絡(luò)(2)的平衡點集為

定理4對任意初始點，網(wǎng)絡(luò)(2)的狀態(tài)向量x(t)都會收斂到其平衡點集E。

?β(t)∈?P(x(t))

再由命題3，存在可測函數(shù)α(t)∈?f(x(t))，使得

接下來，得到

從而知

又因為?f(x(t))及?P(x(t))是非空緊凸上半連續(xù)的，故對0的任意一個閉鄰域U，存在k0≥0，當(dāng)k>k0時，有

因為U任意，所以

進一步地，可以得到如下關(guān)于網(wǎng)絡(luò)(2)的更好的性質(zhì)：

因為P(x(t))為凸函數(shù)，根據(jù)命題5，則有

〈x-x(tk),β(tk)〉≤P(x)-P(x(tk))≤0

那么

推出

4 仿真實例

本節(jié)將驗證網(wǎng)絡(luò)(2)的優(yōu)化性能。實驗在MatlabR2019a平臺進行。誤差精度(即程序運行過程中，相鄰前后兩次迭代得到的目標(biāo)函數(shù)值之差的絕對值)取10-9。程序終止條件為誤差精度小于10-9。

對于步長的選取，已有文獻中普遍選用固定步長，但選用固定步長時，對于某些初始點，網(wǎng)絡(luò)不能收斂到最優(yōu)解，或者迭代次數(shù)會暴增，導(dǎo)致收斂時間大大增加。對此，是否可以取到這樣的步長：它在網(wǎng)絡(luò)的狀態(tài)向量距離最優(yōu)值點較遠時，比較大；而當(dāng)狀態(tài)向量距離最優(yōu)值點較近時，變得很小？

下面來分析這個原則在理論上的合理性?？紤]如下不等式：

x(k+1)=x(k)+a(k)×D

其中

寫成分量的形式就是：

xi(k+1)=xi(k)+a(k)×Dii=1,2,…,n其中，n為狀態(tài)向量的維數(shù)。而

其中，i=1，2，…，n。且fi(x(k))與Pi(x(k))分別為?f(x(k))與?P(x(k))的第i個分量。

再來考察級數(shù)

另一方面，遵循變步長選取原則，經(jīng)過仿真實例的大量編程嘗試以及不斷改善，本文最終總結(jié)出了兩個較為適用的變步長選取公式：

1)a=a(k)=θ-b0-b1k-b2k2k≥2θ≥e常用的有θ=e，或θ=10。

此外，一般而言：若選用固定步長，網(wǎng)絡(luò)能夠快速收斂到原優(yōu)化問題的最優(yōu)解；那么，改用變步長時，網(wǎng)絡(luò)仍然能夠以相近或更快的速度收斂到最優(yōu)解；但反過來，卻不一定成立。

我們將通過兩個仿真實例來驗證網(wǎng)絡(luò)(2)的各項性能：其中，實例1用于與已有模型做性能比較；而實例2則主要突出變步長的作用——即它對網(wǎng)絡(luò)收斂速度的促進作用。

實例1[18]考慮如下非光滑偽凸優(yōu)化問題：

(5)

圖1 實例1中f(x)的局部圖像

其中

λ=2c0=100

c1=2×10-13c2=2×10-20

c3=2×10-19c4=5×10-23

最終狀態(tài)向量收斂于式(5)的(近似)最優(yōu)解：

x*=

(1.031 224 571 303 325,-1.000 004 386 209 420)T相應(yīng)地，f(x*)≈-16.015 609 770 914 857。

圖2表明網(wǎng)絡(luò)(2)能夠快速收斂到最優(yōu)解，且耗時都少于7 s。

圖2 實例1采用網(wǎng)絡(luò)(2)求解時f(x)的變化趨勢

需要指出的是文獻[18]給出的最優(yōu)解及函數(shù)最小值分別為(1,-1)T，-21。這與事實不符，因為點(1,-1)T對應(yīng)的目標(biāo)函數(shù)值為-16，但文獻[18]中的圖3和圖4又明顯地表明網(wǎng)絡(luò)的狀態(tài)向量及目標(biāo)函數(shù)值分別收斂于點(1，-1)T及-21，不得不說文獻[18]中圖4的引用是一個令人遺憾的錯誤。

為突出網(wǎng)絡(luò)(2)的先進性，仍然選取文獻[18]中的模型重新進行實驗，初始點、內(nèi)點、步長及誤差精度與前述一致，運行結(jié)果如圖3所示?？梢钥闯?，網(wǎng)絡(luò)也能快速收斂但目標(biāo)函數(shù)值并不都收斂到優(yōu)化問題的可行最小值，而且有的點耗時比網(wǎng)絡(luò)(2)增加一倍以上，這說明與之相比較，網(wǎng)絡(luò)(2)確實收斂得更快了。

圖3 實例1采用文獻[18]的模型求解時f(x)的變化趨勢

另外，當(dāng)步長固定為0.02時，網(wǎng)絡(luò)(2)也能快速收斂，耗時不長但仍多于選用變步長的情形。效果如圖4所示。

圖4 實例1中步長為0.02時，f(x)的變化趨勢

實例2[14]考慮如下非光滑偽凸優(yōu)化問題：

(6)

圖5 實例2中f(x)的局部圖像

表2 不同固定步長實驗數(shù)據(jù)與結(jié)果

表2的數(shù)據(jù)表明，網(wǎng)絡(luò)(2)從同一點(-1,1)T出發(fā)，以不同步長行進，迭代相同次數(shù)(5 000 000)后得到的目標(biāo)函數(shù)值各不相同，且都沒有達到目標(biāo)函數(shù)在可行域內(nèi)的最小值。結(jié)果如圖6～10所示。從圖中可以判斷出：步長取0.000 1或0.000 01都較為合適。取0.01或0.001時，因為步長過大，造成振蕩現(xiàn)象(步長取0.01時，振蕩現(xiàn)象尤為明顯)；取0.000 001時，網(wǎng)絡(luò)收斂速度最慢，說明步長并不是越小越好。同時，圖6～10也表明，網(wǎng)絡(luò)(2)的運行時間很長，都超過了35 s，這說明取固定步長時，網(wǎng)絡(luò)(2)的收斂時間遠大于35 s。

圖6 實例2步長為0.01時，f(x)的變化趨勢

作為對照，改用變步長做實驗。初始點為區(qū)域[-2,2]×[-2,2]內(nèi)任取的100個點。步長如下：

其中，

λ=1c0=1 083

c1=1×10-9c2=1×10-12

c3=1×10-13c4=1×10-15

最終狀態(tài)向量收斂于式(6)的(近似)最優(yōu)解：

x*=

(0.298 031 938 515 289,-0.161 176 963 583 877)T相應(yīng)地，f(x*)≈0.655 592 147 866 133。

結(jié)果如圖11～13所示，可以看到網(wǎng)絡(luò)(2)快速收斂到式(6)的(近似)最優(yōu)解，且耗時都小于5 s，這遠小于取固定步長時網(wǎng)絡(luò)(2)所需的收斂時間，證明了變步長對網(wǎng)絡(luò)收斂的極大促進作用。圖13則是對網(wǎng)絡(luò)(2)的有限時間收斂定理的一個有力佐證。

值得注意的是，文獻[14]給出的最優(yōu)解及目標(biāo)函數(shù)最小值分別為

(0.3,-0.165)T0.652

看起來比通過網(wǎng)絡(luò)(2)獲得的結(jié)果更優(yōu)，實質(zhì)上，點(0.3,-0.165)T不是可行解。導(dǎo)致出現(xiàn)該問題的原因：一方面很可能是數(shù)據(jù)處理不當(dāng)，另一方面可能意味著文獻[14]中的模型并不能保證狀態(tài)向量進入可行域后不再離開。

圖7 實例2步長為0.001時，f(x)的變化趨勢

圖8 實例2步長為0.000 1時，f(x)的變化趨勢

圖9 實例2步長為0.000 01時，f(x)的變化趨勢

圖10 實例2步長為0.000 001時，f(x)的變化趨勢

圖11 實例2中f(x)的變化趨勢

圖12 實例2中x1,x2的變化趨勢

圖13 實例2中P(x)的變化趨勢

5 結(jié)束語

本文針對凸不等式約束的非光滑偽凸優(yōu)化問題，提出了基于微分包含理論和罰函數(shù)思想的不帶精確罰因子的神經(jīng)網(wǎng)絡(luò)模型。證明了網(wǎng)絡(luò)存在全局解、可在有限時間內(nèi)進入可行域且永駐其中，并最終收斂到原優(yōu)化問題的最優(yōu)解集。

為驗證網(wǎng)絡(luò)的性能，在MatlabR2019a平臺用網(wǎng)絡(luò)(2)對兩個仿真實例進行求解。網(wǎng)絡(luò)優(yōu)化結(jié)果表明，對任意初始點，網(wǎng)絡(luò)都能夠快速收斂到原優(yōu)化問題的最優(yōu)解集。與已有模型相比，網(wǎng)絡(luò)(2)能更快速地收斂到最優(yōu)解，具有一定的優(yōu)越性。

此外，有別于已有的文獻大多采用固定步長進行網(wǎng)絡(luò)求解，本文采用變步長進行網(wǎng)絡(luò)求解，并給出了選擇變步長時應(yīng)當(dāng)遵循的選取原則。同時在大量仿真實例的編程數(shù)據(jù)基礎(chǔ)上總結(jié)出了兩個較為適用的變步長選取公式。最后通過對比實驗展示了變步長對加速網(wǎng)絡(luò)收斂的極大促進作用。

下一步的研究方向可考慮非光滑混合約束偽凸優(yōu)化問題的神經(jīng)網(wǎng)絡(luò)構(gòu)造問題，以及進一步優(yōu)化變步長選取過程。