張 堅(jiān)，李國(guó)成

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

0 引 言

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

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

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

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

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

1 問(wèn)題描述及預(yù)備知識(shí)

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

1.1 問(wèn)題描述

本文研究如下問(wèn)題：

minimizef(x)

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

(1)

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

本文總是假定：

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

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

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

此時(shí)，f在x點(diǎn)處的Clarke廣義梯度定義為：

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

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

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

存在；

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

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

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

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

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

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

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

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

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

定義5對(duì)連續(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點(diǎn)的Clarke廣義梯度為：

?P(x)=

(2)

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

表1 不同模型的性能比較

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

3 主要結(jié)論

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

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

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

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

根據(jù)命題5，

證畢。

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

成立。

引用引理1，有

證畢。

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

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

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

那么

(3)

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

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

(4)

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

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

因?yàn)閤(t)絕對(duì)連續(xù)，易知E(x(t))是非負(fù)正則凸函數(shù)。根據(jù)命題3，存在可測(cè)函數(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ù)解可擴(kuò)展定理，網(wǎng)絡(luò)(2)的解是全局存在的，即x(t)(?t∈[0,+∞))。證畢。

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

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

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

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

接下來(lái)，得到

從而知

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

因?yàn)閁任意，所以

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

因?yàn)镻(x(t))為凸函數(shù)，根據(jù)命題5，則有

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

那么

推出

4 仿真實(shí)例

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

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

下面來(lái)分析這個(gè)原則在理論上的合理性?？紤]如下不等式：

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個(gè)分量。

再來(lái)考察級(jí)數(shù)

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

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

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

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

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

(5)

圖1 實(shí)例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)解，且耗時(shí)都少于7 s。

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

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

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

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

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

圖4 實(shí)例1中步長(zhǎng)為0.02時(shí)，f(x)的變化趨勢(shì)

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

(6)

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

表2 不同固定步長(zhǎng)實(shí)驗(yàn)數(shù)據(jù)與結(jié)果

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

圖6 實(shí)例2步長(zhǎng)為0.01時(shí)，f(x)的變化趨勢(shì)

作為對(duì)照，改用變步長(zhǎng)做實(shí)驗(yàn)。初始點(diǎn)為區(qū)域[-2,2]×[-2,2]內(nèi)任取的100個(gè)點(diǎn)。步長(zhǎng)如下：

其中，

λ=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)解，且耗時(shí)都小于5 s，這遠(yuǎn)小于取固定步長(zhǎng)時(shí)網(wǎng)絡(luò)(2)所需的收斂時(shí)間，證明了變步長(zhǎng)對(duì)網(wǎng)絡(luò)收斂的極大促進(jìn)作用。圖13則是對(duì)網(wǎng)絡(luò)(2)的有限時(shí)間收斂定理的一個(gè)有力佐證。

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

(0.3,-0.165)T0.652

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

圖7 實(shí)例2步長(zhǎng)為0.001時(shí)，f(x)的變化趨勢(shì)

圖8 實(shí)例2步長(zhǎng)為0.000 1時(shí)，f(x)的變化趨勢(shì)

圖9 實(shí)例2步長(zhǎng)為0.000 01時(shí)，f(x)的變化趨勢(shì)

圖10 實(shí)例2步長(zhǎng)為0.000 001時(shí)，f(x)的變化趨勢(shì)

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

圖12 實(shí)例2中x1,x2的變化趨勢(shì)

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

5 結(jié)束語(yǔ)

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

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

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

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