基于神經(jīng)動力系統(tǒng)求解廣義非線性互補問題的優(yōu)化方法

許文杰,歐宜貴

(海南大學(xué) 理學(xué)院,海口 570228)

廣義非線性互補問題(記為GNCP),是指尋找一個點x∈Rn,使得下式成立

G(x)≥0,F(x)≥0,G(x)TF(x)=0,

(1)

其中,F和G:Rn→Rn是連續(xù)函數(shù).當(dāng)G(x)≡x時,GNCP變?yōu)橥ǔ５姆蔷€性互補問題.

由于數(shù)學(xué)、經(jīng)濟(jì)、管理和工程中的許多問題都可以表述為非線性互補問題[1],近幾十年來,人們對求解非線性互補問題的數(shù)值方法的興趣與日俱增.迄今為止,求解問題(1)的主要方法是迭代法(如內(nèi)點法、減勢法、非光滑方程法、磨光方程組法以及投影類方法等),詳見文獻(xiàn)[2-4].

眾所周知,工程應(yīng)用中的許多問題如信號處理、系統(tǒng)辨識、機(jī)器人運動控制等[5-6],通常包含時變參數(shù),因此必須實時求解以便優(yōu)化動態(tài)系統(tǒng)的性能.這樣的實時應(yīng)用問題,對計算時間提出了嚴(yán)格要求,使得上述所說的數(shù)值方法不太有效,而結(jié)合了神經(jīng)網(wǎng)絡(luò)和動力系統(tǒng)的神經(jīng)動力系統(tǒng)模型方法是處理這些優(yōu)化問題的一種有效方法.目前,已有許多神經(jīng)動力系統(tǒng)模型被提出用于解決優(yōu)化問題,并取得了很好的結(jié)果[7-10].

最近,已有學(xué)者研究并提出了求解非線性互補問題的神經(jīng)動力系統(tǒng)模型優(yōu)化方法,例如:XIA和WANG[11]提出了一種可用于求解非線性互補問題的神經(jīng)動力系統(tǒng)模型(記為GPNN):

其中F和G是連續(xù)可微的,M是正對角矩陣.然而GPNN的收斂性分析是建立在F(x)和G(x)的雅可比矩陣存在,并在分析其穩(wěn)定性時要求F(x)+G(x)在Rn中有上界,從而縮小了GPNN的適用范圍.之后,文獻(xiàn)[12]提出了一種基于最速下降型的神經(jīng)動力系統(tǒng)模型,但是該模型只能用于解決G(x)≡x時通常的非線性互補問題,且模型結(jié)構(gòu)復(fù)雜,不容易實施.因此,如何構(gòu)造結(jié)構(gòu)簡單、穩(wěn)定性好且容易實施的神經(jīng)動力系統(tǒng)模型來處理這類特殊優(yōu)化問題就顯得非常必要.

基于上述討論,本文提出一種求解廣義非線性互補問題的神經(jīng)動力系統(tǒng)模型方法.其基本思想是:基于原始優(yōu)化問題構(gòu)造某一微分方程,使得該系統(tǒng)的平衡點和原問題的局部最優(yōu)解相符合.然后再選取適當(dāng)?shù)臄?shù)值方法來求解該系統(tǒng),從而獲得原優(yōu)化問題的最優(yōu)解或近似最優(yōu)解.該方法的優(yōu)勢在于可以系統(tǒng)地研究微分系統(tǒng)解的瞬態(tài)性能和極限行為,從而追蹤初始點與極限點之間的連續(xù)運動軌跡.并且它在分析動力系統(tǒng)的穩(wěn)定性時采用了不同以往的新策略,從而避免使用傳統(tǒng)的Lyapunov函數(shù),使得人們利用這類新方法來研究最優(yōu)化問題時獲得了較先前更好的理論結(jié)果以及更具競爭力的數(shù)值表現(xiàn)性能.

本文結(jié)構(gòu)如下:在第1節(jié)中,給出了一些預(yù)備知識;第2節(jié)中,提出了求解問題(1)的神經(jīng)動力系統(tǒng)模型;第3節(jié)分析了神經(jīng)動力系統(tǒng)模型的收斂性和穩(wěn)定性;第4節(jié)給出了數(shù)值計算結(jié)果,驗證了該方法的有效性,并與文獻(xiàn)[11]的數(shù)值方法進(jìn)行了對比,最后得出結(jié)論.

1 預(yù)備知識

定義1設(shè)Ω是Rn上的非空閉凸集.在歐氏范數(shù)下,點ν∈Rn在Ω的投影定義為[11]:

引理1對于投影算子PΩ,有[13]

(ν-PΩ(ν))T(PΩ(ν)-u)≥0,?ν∈Rn,u∈Ω,

‖PΩ(ν)-PΩ(u)‖≤‖ν-u‖,?ν,u∈Rn.

定義2若有[14]

[F(u)-F(u*)]T[G(u)-G(u*)]≥0，?u∈Rn,

(2)

則稱函數(shù)F在點u*∈Rn處是G-單調(diào)的.特別地,若有

[F(u)-F(ν)]T[G(u)-G(ν)]≥0,?u,ν∈Rn,

則稱函數(shù)F在Rn上是G-單調(diào)的.若有

[F(u)-F(u*)]T[G(u)-G(u*)]≥γ‖u-u*‖,γ>0,?u∈Rn,

(3)

則稱函數(shù)F在點u*∈Rn處是G-強單調(diào)的.注意,當(dāng)G(x)=x時，G-單調(diào)(G-強單調(diào))就變成了通常的單調(diào)(強單調(diào))[14].

為了后面敘述的方便,還需要一階常微分方程(ODE)：

(4)

的一些知識，其中f是定義在Rn上的一個函數(shù).

如果f(x*)=0,則x*∈Rn是方程(4)的平衡點.

定理1假設(shè)函數(shù)f:Rn→Rn是連續(xù)的.則對t0≥0及x0∈Rn,存在常數(shù)τ>t0使得方程(4)總存在一個局部解x(t),t∈[t0,τ).此外,如果f在x0處是局部Lipschitz連續(xù)的,那么此解是唯一的;如果f在Rn上是Lipschitz連續(xù)的,那么τ可以拓展到+∞.

2 神經(jīng)動力系統(tǒng)模型

基于上述預(yù)備知識,利用文獻(xiàn)[16]的思想方法,提出如下求解問題(1)的ODE系統(tǒng)模型：

(5)

其中Λ=diag{λ1,λ2,…,λn}是對角矩陣,λi>0.根據(jù)文獻(xiàn)[16]有一個重要結(jié)論:x*是(5)式的平衡點?x*是問題(1)的解.

注1當(dāng)β=1時,模型(5)就變?yōu)镚PNN模型.事實上,β的不同取值對模型的穩(wěn)定性至關(guān)重要,接下來的理論分析與數(shù)值模擬實驗也驗證了這一點.此外,正如前文所述,GPNN模型在收斂性和穩(wěn)定性分析時要求的條件較強,而本文在分析收斂性時所要條件較弱(詳見本文定理2和定理3).

為了簡化研究,定義

E(x,β)=Λ{G(x)-PX[G(x)-βF(x)]},β>0,

則系統(tǒng)(5)等價于

(6)

利用引理1,對于任意的x,y∈Rn,有

‖E(x,β)-E(y,β)‖≤‖Λ‖{‖PX[G(x)-βF(x)]-PX[G(y)-βF(x)]‖+

‖G(x)-G(y)‖}≤2‖Λ‖‖G(x)-G(y)‖+β‖Λ‖‖F(xiàn)(x)-F(y)‖.

(7)

引理3對于任給的t0≥0,x0∈Rn,當(dāng)τ>t0時,存在唯一的連續(xù)解x(t),t∈[t0,τ)滿足ODE系統(tǒng)(5).此外,如果函數(shù)F和G在Rn上是Lipschitz連續(xù)的,對于任給的初始點x0,ODE系統(tǒng)(5)有唯一的解x(t),t∈[t0,+∞).

證明因為函數(shù)F和G在Rn上是連續(xù)的,則它們是局部Lipschitz連續(xù)的,這與(7)式表明E(x,β)也是局部Lipschitz連續(xù)的.從而由定理1可知,該引理前一部分是正確的.

令LF和LG分別是函數(shù)F和G的Lipschitz常數(shù),由(7)式得:

‖E(x,β)-E(y,β)‖≤2‖Λ‖‖G(x)-G(y)‖+β‖Λ‖‖F(xiàn)(x)-F(y)‖≤

(2‖Λ‖LG+β‖Λ‖LF)‖x-y‖,?x,y∈Rn,

(8)

則E(x,β)在Rn上是Lipschitz連續(xù)的.利用定理1,可證明引理3后一部分是正確的.

引理4[12]如果x*是GNCP(1)的解,則

{G(x)-G(x*)+β[F(x)-F(x*)]}TΛ-1E(x,β)≥E(x,β)TΛ-2E(x,β)+

β[F(x)-F(x*)]T[G(x)-G(x*)],?x∈Rn.

(9)

注2引理4表示對于在x*處的G-單調(diào)函數(shù)F,有

{G(x)-G(x*)+β[F(x)-F(x*)]}TΛ-1E(x,β)≥E(x,β)TΛ-2E(x,β),?x∈Rn,

(10)

因此‖E(x,β)TΛ-1‖≤‖G(x)-G(x*)+β[F(x)-F(x*)]‖,?x∈Rn.

3 收斂性和穩(wěn)定性分析

下面分析模型的收斂性和穩(wěn)定性.為此,建立了一個如下的價值函數(shù):

(x-x*)TΛ-1[βF(x*)+G(x*)],

其中x*是GNCP的解.顯然有下式成立,

V(x)=Λ-1[βF(x)+G(x)-βF(x*)-G(x*)].

(11)

定理2設(shè)x*是GNCP(1)的解.假設(shè)以下條件成立:

(a)F在x*處是G-單調(diào)函數(shù);

(b) 水平集L(x0)={x∈Rn|V(x)≤V(x0)}是有界的;

(12)

證明由引理3和條件(c),ODE系統(tǒng)(6)的解存在且唯一.由條件(a)、(6)、(10)、(11)式可得:

G(x*)}TΛ-1E(x,β)≤-E(x,β)TΛ-2E(x,β)≤0,

(13)

這意味著,如果E(x,β)≠0,V(x(t))在t沿著軌跡x(t)單調(diào)遞減,因此得到

{x(t)|t≥t0}?L(x0),

(14)

(15)

由文獻(xiàn)[17]中定理4的證明可知,存在一個常數(shù)C有

(16)

(17)

(18)

注3對于定理2中的條件(b)是容易實現(xiàn)的.如果函數(shù)βF(x)+G(x)是帶模μ>0強單調(diào)的,則從(11)式和定義3中可以看出,當(dāng)模μ>0時,V(x)也是帶模μ>0強單調(diào)的,則V(x)是一致凸函數(shù)[18],因此水平集L(x0)是有界的[18].

定理3設(shè)x*是GNCP(1)的解.假設(shè)以下條件成立:

(a)F在x*處是G-強單調(diào)函數(shù);

(b)βF(x)+G(x)是帶模μ>0強單調(diào)的;

(c)βF(x)+G(x)存在且在Rn上是對稱的;

(d)F和G在Rn上是Lipschitz連續(xù)的.那么,對于任意t0≥0且x(t0)=x0∈Rn,ODE系統(tǒng)(6)在x*上是全局指數(shù)穩(wěn)定的,其中x*是GNCP(1)的平衡解.

證明由(3)式、引理4和(a)可得

-β[F(x)-F(x*)]T[G(x)-G(x*)]≤-γβ‖x-x*‖2.

(19)

由定理2的證明和注3可知,{x(t)|t≥t0}?L(x0)是有界的,則βF(x)+G(x)是有界的,則存在δ1>0,對于任給的s∈Rn,有‖βF(s)+G(s)‖≤δ1.

注意到

V(x)≤V(x0)exp(-λ(t-t0)),?t≥t0,

(20)

V(x)-V(x*)≥V(x*)(x-x*)+μ‖x-x*‖2,?x∈Rn.

根據(jù)定理3,可以看出β與正對角矩陣Λ中元素λi的大小對模型的穩(wěn)定性有影響.β與λi的值越大,模型穩(wěn)定性越好.然而,β的值太大時,模型實施困難,導(dǎo)致運行時間增加,下一節(jié)的數(shù)值模擬實驗將驗證這一點.

4 數(shù)值模擬實驗

在本節(jié)中,為了驗證神經(jīng)動力系統(tǒng)模型的可行性,選取了以下6個問題來進(jìn)行數(shù)值模擬實驗,并測試了β對‖x(t)-x*‖值的影響.對于其中的一些參數(shù),設(shè)置如下：reltol為10-3,abstol為10-6,β=10,Λ=1.

例1非線性互補問題:

例2非線性互補問題:

例3非線性互補問題:

F(x)=(arctanx1+x2,arctanx2+x3,…,arctanxn-1+xn,arctanxn)T,

例4非線性方程:

Fi(x)=2xi-sin|xi|,i=1,2,…,n,x∈Rn,

X={x∈Rn|l≤x≤u},l=-100(1,1,…,1)T,u=100(1,1,…,1)T,

通過上述數(shù)值模擬實驗,可以得到所提出的神經(jīng)動力系統(tǒng)模型能夠有效解決廣義非線性互補問題.并且,正如上文所說,β的值越大,模型的穩(wěn)定性越好,但是當(dāng)β的值太大時,模型實現(xiàn)困難,會導(dǎo)致運算時間增加.接下來,為了更好地驗證模型的優(yōu)越性,將模型(5)(以下稱為GNCP模型)與GPNN模型[11]的運算性能進(jìn)行比較,具體結(jié)果見表1,其中CPU表示以s為單位的運行時間.

通過表1,可以看出GNCP模型的運算性能是優(yōu)于GPNN模型的.并且,表1中的運行時間也驗證了正對角矩陣Λ中元素λ的大小對模型穩(wěn)定性有影響.

表1 在不同條件下,GNCP模型和GPNN模型的CPU運行時間

5 小 結(jié)

本文提出了一種求解廣義非線性互補問題的神經(jīng)動力系統(tǒng)模型.該模型結(jié)構(gòu)簡單,易于實施.在一定的條件下,得到了該模型的收斂性和指數(shù)穩(wěn)定性.由于在分析所提出模型的收斂性時沒有利用任何形式的雅可比矩陣,因此既能分析更廣泛的動力系統(tǒng),又能簡化分析.數(shù)值模擬結(jié)果表明,該模型具有可行性,能夠有效解決所給出的測試問題,可以應(yīng)用于求解廣義非線性互補問題.