時(shí)間依賴凸約束可行性問(wèn)題的神經(jīng)動(dòng)力學(xué)方法

張宸寧，李國(guó)成

(北京信息科技大學(xué)信息與計(jì)算科學(xué)系，北京 100192)

0 引言

本文考慮如下時(shí)間依賴約束可行性問(wèn)題：

(1)

這里x∈n為狀態(tài)變量；F=(f1,f2,…,fm)T:+×n→m為m維向量值函數(shù)，其分量fi(t,x)關(guān)于變量x是凸函數(shù)(i=1,2,…,m)。對(duì)任意δ>0，存在Li(δ)>0，使得

t,s≥0，x1,x2∈B(0,δ)，其中B(0,δ)={x∈n:‖x‖<δ}是以0為中心δ為半徑的開(kāi)球。A∈r×n為具有行滿秩系數(shù)矩陣，b是一個(gè)r維向量。問(wèn)題(1)等價(jià)于找到x(t)∈C(t)，其中C(t)={x∈n:F(t,x)≤0且Ax=b}為問(wèn)題(1)的可行集。令C1(t)={x∈n:F(t,x)≤0}，C2={x∈n:Ax=b}。顯然，C(t)=C1(t)∩C2。在本文中，我們假定問(wèn)題(1)至少有一個(gè)可行解x(t)∈C(t)(t≥t0)。

工程應(yīng)用中的許多問(wèn)題，如控制理論、信號(hào)處理、安全通信和圖像重建，都可以歸結(jié)為可行性問(wèn)題，其中許多問(wèn)題涉及時(shí)變環(huán)境，在很短的時(shí)間內(nèi)提供解決方案是至關(guān)重要的。例如，機(jī)器人的實(shí)時(shí)運(yùn)動(dòng)規(guī)劃和控制、非線性模型預(yù)測(cè)控制、用于多媒體數(shù)據(jù)安全性的快速信號(hào)加密、無(wú)線傳感器網(wǎng)絡(luò)中的定位、計(jì)算機(jī)斷層攝影術(shù)中投影的圖像重建以及使用魯棒掩模波束成形的安全通信方案等。當(dāng)需要實(shí)時(shí)獲得可行解決方案時(shí)，特別是存在不確定性時(shí)，時(shí)間依賴約束可行性問(wèn)題的難度明顯增大。在這樣的應(yīng)用中，與傳統(tǒng)的數(shù)值可行性算法相比，基于遞歸神經(jīng)網(wǎng)絡(luò)的神經(jīng)動(dòng)力學(xué)方法具有獨(dú)特的優(yōu)點(diǎn)：可以設(shè)計(jì)硬件實(shí)現(xiàn)。例如，超大規(guī)模集成電路(VLSI)、可重配置模擬芯片、光學(xué)芯片、圖形處理單元(GPU)、現(xiàn)場(chǎng)可編程門陣列(FPGA)、數(shù)字信號(hào)處理器(DSP)等。新技術(shù)的產(chǎn)生使神經(jīng)網(wǎng)絡(luò)的設(shè)計(jì)和實(shí)現(xiàn)更合理、更可行。

基于遞歸神經(jīng)網(wǎng)絡(luò)的神經(jīng)動(dòng)力學(xué)方法在過(guò)去30年取得了巨大的成功，可參考文獻(xiàn)[1-16]。其中，Tank等[1]率先采用神經(jīng)動(dòng)力學(xué)方法求解線性規(guī)劃問(wèn)題； Wang[3]提出了一種求解線性和非線性凸規(guī)劃問(wèn)題的確定性模擬退火神經(jīng)網(wǎng)絡(luò)；Kennedy等[5]等提出了解決非線性優(yōu)化的遞歸神經(jīng)網(wǎng)絡(luò)，利用有限懲罰方法來(lái)逼近最優(yōu)解；Forti等[6]引入了一種廣義非線性規(guī)劃電路(G-NPC)，它將文獻(xiàn)[5]中的規(guī)劃電路擴(kuò)展到非光滑情形。G-NPC利用基于高增益非線性約束神經(jīng)元實(shí)現(xiàn)非光滑爆破函數(shù)的精確罰函數(shù)法來(lái)優(yōu)化不可微目標(biāo)函數(shù)。對(duì)比文獻(xiàn)[5]中的光滑電路，G-NPC的優(yōu)勢(shì)是滑模的存在，由于滑模的存在，網(wǎng)絡(luò)狀態(tài)軌道能夠在有限時(shí)間內(nèi)收斂到可行集。Ban等[8]進(jìn)一步推進(jìn)了Forti的工作[6]，提出了一種求解非凸優(yōu)化問(wèn)題的神經(jīng)網(wǎng)絡(luò)模型，并證明了對(duì)于一個(gè)足夠大的懲罰參數(shù)，網(wǎng)絡(luò)的狀態(tài)軌道都可以在有限時(shí)間到達(dá)可行域，并在此之后停留在可行域中。實(shí)際上，已有的神經(jīng)網(wǎng)絡(luò)模型是在假設(shè)目標(biāo)函數(shù)和約束不依賴于時(shí)間來(lái)設(shè)計(jì)的。在文獻(xiàn)[8]中，Marco等首先提出了時(shí)間依賴非光滑神經(jīng)網(wǎng)絡(luò)模型，用于解決帶有不等式約束的時(shí)間依賴可行性問(wèn)題。

從文獻(xiàn) [8-9]得到啟發(fā)，本文考慮了帶有等式和不等式約束的時(shí)間依賴可行性問(wèn)題，并提出了基于精確罰函數(shù)法設(shè)計(jì)的神經(jīng)動(dòng)力學(xué)模型。對(duì)于懲罰參數(shù)的適當(dāng)值，證明了所提出的神經(jīng)動(dòng)力學(xué)模型的狀態(tài)軌道在有限時(shí)間到達(dá)移動(dòng)集，且隨時(shí)間跟蹤移動(dòng)集。同時(shí)估計(jì)了懲罰參數(shù)和收斂時(shí)間的下界。

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

在本節(jié)中，我們將介紹有關(guān)集值分析中的某些定義和性質(zhì)，以及本文所需的凸分析的知識(shí)。讀者可參考文獻(xiàn) [17-21]。

定義1Q:+×n→n稱為集值映射。每個(gè)點(diǎn)(t,x)∈+×n，對(duì)應(yīng)唯一非空集合Q(t,x)?n[17]。

定義2設(shè)Q是一個(gè)集值映射。如果?ε>0,?δ>0，使得?(t,x)∈B(t0,δ)×B(x0,δ)，Q(t,x)?Q(t0,x0)×B(x0,ε)，則稱Q在(t0,x0)∈+×n處是上半連續(xù)的(u.s.c)。若對(duì)任意(t0,x0)∈+×n都上半連續(xù)，則稱Q為上半連續(xù)(u.s.c)。

設(shè)G?n是一個(gè)非空閉凸集，x∈n，則存在唯一的元PG(x)∈n滿足‖x-PG(x)‖=miny∈G‖x-y‖，稱PG(·)為G上投影算子。此外，m(G)=PG(0)表示G上取最小范數(shù)的向量。

設(shè)f:n→是一個(gè)凸函數(shù)，則f是局部Lipschitz連續(xù)的，但未必是可微的。我們可以引入f的次微分。

定義3設(shè)f:n→是凸函數(shù)，則f在x處的次微分定義如下：

?f(x):=

{ξ∈n:?y∈n,f(y)≥f(x)+〈ξ,y-x〉}

向量ξ∈?f(x)稱為f在x處的次梯度。映射x→?f(x)具有非空緊凸集值，具有閉圖像且局部有界[21]。因此，x→?f(x)將n的緊集映成n的緊集。此外，如果f在通常意義下在x處是可微的，那么?f(x)={f(x)}是單值的。

在本文中，我們將使用以下微分運(yùn)算規(guī)則來(lái)描述凸函數(shù)的次微分。

1)設(shè)f1,f2,…,fm是從n到的m個(gè)凸函數(shù)，λ1,λ2,…,λm為正實(shí)數(shù)，則

2)設(shè)f1,f2,…,fm是從n到的m個(gè)凸函數(shù)，

f(x)=max{f1(x),f2(x),…,fm(x)}(x∈n)，I(x)={i:f(x)=fi(x)}表示指標(biāo)集，則

?f(x)=co{∪?fi(x):i∈I(x)}

其中，co(G)表示集合G的凸包。

3)鏈?zhǔn)椒▌t[22]。設(shè)V:n→是一個(gè)凸函數(shù)，x:+→n在+的任一緊區(qū)間上是絕對(duì)連續(xù)的，則，對(duì)幾乎所有的t≥0，t→V(x(t))是可微的，且

Hausdorff距離：設(shè)G1,G2?n為非空閉集，G1和G2之間的Hausdorff距離定義為[20]]

dist(G1,G2)=

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

在本節(jié)，提出了一個(gè)基于精確罰函數(shù)法的神經(jīng)動(dòng)力學(xué)模型來(lái)求解時(shí)間依賴凸約束可行性問(wèn)題。

下面給出一些需要的符號(hào)和假設(shè)。對(duì)于給定的(t,x)∈+×n，令

I+(t,x)={i:fi(t,x)>0,1≤i≤m}

I0(t,x)={i:fi(t,x)=0,1≤i≤m}

I-(t,x)={i:fi(t,x)<0,1≤i≤m}

為(t,x)的指標(biāo)集。

在本文中，需要以下假定。

假定1集值映射t→C(t)在Hausdorff距離下是連續(xù)的，并且存在R>0，使得C1(t)?B(0,R)及intC1(t)≠?。

假定2存在一個(gè)選擇s(t)∈intC1(t)∩C2，滿足Lipschitz條件，Lipschitz常數(shù)Ls>0。

假定3存在ρ>0，使得對(duì)于任何t≥0，i=1,2,…,m，fi(t,s(t))≤-ρ。

由條件1知，C1(t)是非空緊凸的，則對(duì)于幾乎所有t≥0，t→C1(t)在Hausdorff度量下存在Lipschitz選擇s(t)∈C1(t)[20]。此外，由于intC1(t)≠?，則s(t)∈intC1(t)[20]。如果“Steiner點(diǎn)映射”g滿足g(C1(t))∈C2，或“重心選擇映射”h滿足h(C1(t))∈C2，則在假定2下存在Lipschitz選擇，并且可以估計(jì)Lipschitz系數(shù)Ls[17-20]。

本節(jié)目的是設(shè)計(jì)一個(gè)神經(jīng)網(wǎng)絡(luò)模型，使得在t=0時(shí)，在C1(0)外面開(kāi)始的任何狀態(tài)在有限時(shí)間內(nèi)到達(dá)移動(dòng)集C(·)，并且此后保持在C(·)之內(nèi)。為此，定義能量函數(shù)E:+×n→如下：

其中θ>0是一個(gè)待定常數(shù)。P=AT(AAT)-1A，AT是A的轉(zhuǎn)置，c=AT(AAT)-1b。矩陣P稱為投影矩陣。顯然，對(duì)于任何t≥0，x→E(t,x)是凸的。

神經(jīng)網(wǎng)絡(luò)模型由如下微分包含方程給出：

(2)

其中σ>0是一個(gè)待選擇的懲罰參數(shù)，對(duì)于幾乎所有t≥0， ?xE(t,x)是凸函數(shù)x→E(t,x)的次微分。?xE(t,x)表示如下：

(3)

注意到，C2={x:Px=c}={x:Ax=b}。當(dāng)x?C2時(shí)，‖Px-c‖是嚴(yán)格可微的，其微分為?‖Px-c‖=‖Px-c‖=PT(Px-c)/‖Px-c‖；當(dāng)x∈C2時(shí)，?‖Px-c‖={PTξ:‖ξ‖≤1,ξ∈n}。

給定x0∈n且t1>0，柯西問(wèn)題(2)的解是一個(gè)絕對(duì)連續(xù)函數(shù)x(t)，滿足x(0)=x0，且對(duì)幾乎所有的

由假定1)，(t,x)→E(t,x)是局部Lipschitz連續(xù)函數(shù)，(t,x)→?xE(t,x)是具有非空緊凸集值的上半連續(xù)集值映射[18]，且(t,x)→m(?xE(t,x))是局部緊的，則對(duì)于任意x0∈n，對(duì)于初始條件x0，微分包含式(2)至少存在一個(gè)狀態(tài)解[17]。

3 動(dòng)態(tài)分析

在本節(jié)中，首先研究在初始條件下，問(wèn)題(2)狀態(tài)解的有界性和唯一性。然后我們證明，通過(guò)適當(dāng)選擇懲罰參數(shù)σ，在初始條件x(0)?C1(0)時(shí)，問(wèn)題(2)的任意狀態(tài)解x(·)在有限時(shí)間th到達(dá)移動(dòng)集合C(·)。換言之，x(th)∈C(th)，其中th可根據(jù)網(wǎng)絡(luò)參數(shù)估計(jì)。在到達(dá)移動(dòng)集C(·)后，狀態(tài)解能夠跟蹤移動(dòng)集，即對(duì)于任何t≥th，x(t)∈C(t)。

3.1 狀態(tài)解的有界性與唯一性

本節(jié)給出主要結(jié)果之前，首先需要引入如下2個(gè)引理。

引理1若假定1～3滿足，那么，對(duì)于任何t≥0，x∈n，x?C1(t)，有

〈z,x-s(t)〉≥ρ?z∈?xV(t,x)

(4)

其中，t→s(t)在假定2中定義，并且

證明固定t≥0，x?C1(t)，則I+(t,x)≠?。由定義3，有

0<-fi(t,s(t))<-fi(t,s(t))+fi(t,x)≤

〈zi,x-s(t)〉 ?zi∈?xfi(t,x)

其中i∈I+(t,x)。如果I0(t,x)≠?，則

0<-fi(t,s(t))<-fi(t,s(t))+fi(t,x)≤

〈zi,x-s(t)〉 ?zi∈?xfi(t,x)

其中i∈I0(t,x)。則對(duì)任意z∈?xV(t,x)，有

引理2若假定1～3滿足，則對(duì)任意的x∈n，z∈?‖Px-c‖，有

(5)

證明若x∈C2，則Px-c=Ps(t)-c=0。對(duì)任意的ξ∈n使得‖ξ‖≤1，有

〈PTξ,x-s(t)〉=〈ξ,Px-Ps(t)〉=0

如果x?C2，則

?‖Px-c‖=‖Px-c‖=PT(Px-c)/‖Px-c‖

〈PT(Px-c),x-s(t)〉/‖Px-c‖=‖Px-c‖

證明首先 證明狀態(tài)解的有界性。為此，定義如下Lyapunov函數(shù)：

其中選擇s(t)在假設(shè)2中定義。

由于

σ(?xV(t,x(t))+θ?x‖Px-c‖)

σθ〈x(t)-s(t),z2(t)〉-

根據(jù)引理1～2，如果x(t)?C1(t)，‖x(t)-s(t)‖≤2R，那么

(6)

對(duì)于任意t≥0，x→E(t,x)是凸的，則x→-σ?xE(t,x)是極大單調(diào)算子[17]，類似文獻(xiàn) [23]中性質(zhì)3的證明，可以得到結(jié)論：對(duì)于初始條件x(0)∈B(0,R)，問(wèn)題(2)存在唯一狀態(tài)解x(t)。

3.2 到達(dá)階段

下面的結(jié)果表明問(wèn)題(2)的狀態(tài)解在有限時(shí)間到達(dá)隨時(shí)間移動(dòng)的可行集。

注意到s(t)∈intC1(t)∩C2，則

‖x(t)-s(t)‖2<

‖x(0)-s(0)‖2-2RLst，

0

因此，對(duì)于任意t∈[0,te)，x(te)∈C(te)，存在te≤Te使得x(t)?C1(t)。

3.3 跟蹤階段

在本節(jié)中，我們將證明：?jiǎn)栴}(2)的狀態(tài)解達(dá)到移動(dòng)集合C(·)后，它將保持在移動(dòng)可行集內(nèi)。為此，構(gòu)造問(wèn)題(2)的Lyapunov函數(shù)如下：

在證明主要結(jié)果之前，需要以下引理。

(7)

其中z(t)∈?xE(t,x(t))。

由鏈?zhǔn)椒▌t，可以得到

另一方面，由于|E(t+τ,x(t+τ))-E(t,x(t+τ))|=|V(t+τ,x(t+τ))-V(t,x(t+τ))|，‖x(t)‖<3R，可得

證明對(duì)于初始點(diǎn)x(0)∈B(0,R)C1(0)，x(t)是問(wèn)題(2)的狀態(tài)解。由定理1可知，存在te使得x(te)∈C(te)。

下面證明x(t)∈C(t)，t≥te。

采用反證法。

一方面，當(dāng)x(t)?C1(t)時(shí)，由式(4)、(5)可知，對(duì)于任意z(t)∈?xE(t,x(t))有〈z(t),x(t)-s(t)〉≥ρ，那么

由式(7)得

另一方面，當(dāng)x(t)∈C1(t)C2(t)時(shí)，選擇W(x(t))=θ‖Px(t)-C‖作為問(wèn)題(2)的Lyapunov函數(shù)，那么，對(duì)于任何v(t)∈?xV(t,x(t))，有

σ‖W(x(t))‖·‖v(t)‖-

-σθ<0

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

本文提出了一個(gè)基于精確罰函數(shù)法的神經(jīng)動(dòng)力學(xué)模型來(lái)求解時(shí)間依賴凸約束可行性問(wèn)題。首先研究了問(wèn)題(2)狀態(tài)解的有界性和唯一性?；诖耍ㄟ^(guò)適當(dāng)選擇懲罰參數(shù)σ，在初始條件x(0)?C1(0)情形下，問(wèn)題(2)的任意狀態(tài)解x(·)在有限時(shí)間th到達(dá)移動(dòng)集合C(·)，即x(th)∈C(th)，其中th可根據(jù)網(wǎng)絡(luò)參數(shù)估計(jì)。此外，證明了狀態(tài)解能夠跟蹤移動(dòng)集合，即t≥th，x(t)∈C(t)。