基于分塊矩陣的投影型神經網絡收斂性分析

(1.電子科技大學 a.應用數學學院; b.計算機科學與工程學院， 成都 610054； 2.貴州財經學院 數學與統計學院，貴陽 550004)

摘 要：

投影神經網絡算法被譽為最有希望解決優化問題的算法之一，可用于求解優化問題的前提是它應具有全局收斂性。根據凸二次規劃約束條件的特點，利用常微分方程理論、M-矩陣理論，通過構造適當的Lyapunov函數，獲得了該網絡求解一類凸二次規劃問題的全局指數收斂性條件，該條件只與神經元連接權矩陣的部分元素有關，其比現有文獻所得的收斂條件更弱。最后給出一組實例，說明該網絡計算上是可行和有效的。

關鍵詞：神經網絡;凸二次規劃； 投影算子； 指數收斂

中圖分類號：TP18文獻標志碼：A

文章編號：1001-3695(2009)04-1286-03

Convergence analysis of projective neural networks based on partial matrix

LIU Zi-xin1a，2， LV Shu1a， ZHONG Shou-ming1a， YE Mao1b

(1. a.School of Applied Mathematics， b. School of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu 610054， China； 2. School of Mathematics Statistics， Guizhou College of Finance Economics， Guiyang 550004， China)

Abstract:

Projective neural network is the most promising method for solving programming problems， but before it application in practice， neural system must be stable. Based on ordinary differential theory， M-matrix theory， and the character of activate function， by constructing appropriate Lyapunov functional， obtained some globally convergent conditions， this conditions were only relate to some elements of the weight matrix， they were more weaker than previous publications. It presented one simulation example to show the validity of the main results.

Key words：neural networks; convex quadratic program; projective operator; exponential convergence

0 引言

在科學技術領域中經常遇到求解變分不等式或凸二次規劃問題。為了求解該類問題，諸多數值算法被提出[1~4]。自從Hopfield和Tank的開創性工作以來[5，6]，用于最優化問題的神經網絡方法得到了迅速的發展，求解各類帶約束條件的投影神經網絡模型相繼被提出[7，9]。與其他求解最優化問題的數值方法相比，神經網絡具有易于硬件實現、并行計算、自然保解等優點，因此神經網絡逐漸成為了解決最優化問題的最佳選擇之一。但是以往文獻對所構造的投影型神經網絡算法的收斂性分析均未能充分利用規劃問題約束條件的特點，這在很大程度上使得算法的收斂條件具有相當的保守性。針對這一缺點，本文將給出一些新的收斂準則，該準則只與連接權矩陣的部分子塊元素相關，與以往文獻所得的收斂準則相比，具有較小的保守性。

1 問題的數學分析

考慮如下二次規劃問題

minx∈Ω1/2xTAx+bTx(1)

其中:A是一n階（半）正定矩陣；x，b，a∈Rn，Ω＝{x∈Rn|ai≤xi≤bi，i∈L，L={1，2，…，n}}，是一閉凸子集。在文獻[10]中，作者采用可行方向法設計了以下投影型神經網絡模型：

dx(t)/dt=-x(t)+PΩ(x(t)-ρAx(t)-ρb) t＞t0x(t0)=x0t=t0(2)

其中：ρ是任意正數，PΩ∶Rn→Ω是一投影算子，滿足

PΩ(xi)=ai xi＜aixi ai≤xi≤bibi xi＞bi(3)

其中：‖#8226;‖表示任意向量（矩陣）范數。由文獻[11]知，算子 PΩ有如下性質：

a)〈(u-PΩ(u))，(PΩ(u)-v)〉≥0，u∈Rn，v∈Ω

b)‖PΩ(u)-PΩ(v)‖≤‖u-v‖，u， v∈Rn

性質b)表明，算子PΩ是Lipschitz連續的并且Lipschitz常數等于1。由文獻[12]可知，當矩陣A為正定或半正定時，式(1)的最優解等價于投影神經網絡式(2)的平衡解。本文的重點則是對式(2)求解問題式(1)的算法收斂性作分析。

2 指數收斂性分析

首先給出全局指數收斂的定義如下：

定義1[11] 投影神經網絡式(2)被稱為是全局指數收斂的，如果存在正數η、μ使得式(2)過初始點x0的解x(t，x0)滿足：

‖x(t，x0)-x*‖≤μ‖x(t0)-x*‖e-η(t-t0)

若η、μ的選取與初始點無關，則稱模型式(2)具有全局指數收斂性。其中：x*為式(2)的平衡解；η稱為指數收斂率。

令u(t)=(I-ρA)x(t)-ρb，則式(2)可轉換為如下等價形式：

du(t)/dt=-u(t)+(I-ρA)PΩ(u(t))-ρb，t＞t0(4)

設u*為式(4)的平衡解，則有

u*=(I-ρA)PΩ(u*)-ρb(5)

令y(t)=u-u*由式(4)(5)可得

dy(t)/dt=-y(t)+(I-ρA)[PΩ(y+u*)-PΩ(u*)](6)

將L={1，2，…，n}分解為子集L1，L2，L3的并，L1={i∈L|u*＞bi}，L2={i∈L|ai≤u*≤bi}，L3={i∈L|u*＜ai}，并且重新排列變量y1，…，yn使得L1={1，2，…，r}，L2={r+1，r+2，…，r+k}，L3={r+k+1，r+k+2，…，n}。其中:r、k、n-k-r均為非負整數。顯然式(6)的變量已經重新排序，但為方便起見仍沿用原記號。令

y(t)=[y(1)（t），y(2)（t），y(3)(t)]T

M=I-ρA=M11M12M13M21M22M23M31M32M33

 PΩ(y)=PΩ(y+u*)-PΩ(u*)

其中

y(1)(t)=[y1(t)，y2(t)，…，yr(t)]T

y(2)(t)=[yr+1(t)，yr+2(t)，…，yr+k(t)]T

y(3)(t)=[yr+k+1(t)，yr+k+2(t)，…，yn(t)]T

類似于文獻[13]的處理方法，則一定存在T， 使得t∈[t0，T]，式(6)有如下等價形式：

dy(1)(t)/dt=-y(1)(t)+M12PΩ(y(2)(t))

dy(2)(t)/dt=-y(2)(t)+M22PΩ(y(2)(t))

dy(3)(t)/dt=-y(3)(t)+M32PΩ(y(2)(t))

(7)

其中：T＞t0，并且t∈[t0，T]滿足yi(t)＜min{mini∈L1(u*i-bi)，mini∈L3(ai-u*i)}，于是可以得到如下收斂定理。

定理1 如果‖M22‖＜1，則式(2)的解x(t，x0)指數收斂到式(1)的最優解。

證明 t∈[t0，T]，由式(7)的第二個方程可知：

y(2)(t)=e-(t-t0)y(2)(t0)+∫tt0e-(t-s)M22PΩ(y(2)(s))ds，

‖y(2)(t)‖≤e-(t-t0)‖y(2)(t0)‖+

∫tt0e-(t-s)‖M22PΩ(y(2)(s))‖ds≤e-(t-t0)‖y(2)(t0)‖+

∫tt0e-(t-s)‖M22‖#8226;‖ PΩ(y(2)(s))‖ds≤e-(t-t0)‖y(2)(t0)‖+

∫tt0e-(t-s)‖M22‖#8226;‖ (y(2)(s))‖ds

從而有

‖y(2)(t)‖et≤et0‖y(2)(t0)‖+∫tt0es‖M22‖#8226;‖ y(2)(s)‖ds

由Gronwall積分不等式得到

‖y(2)(t)‖et≤et0‖y(2)(t0)‖e∫tt0‖M22‖ds=

et0‖y(2)(t0)‖e‖M22‖(t-t0)

即

‖y（2）（t）‖≤e-t(t-t0)‖y(2)(t0)‖e‖M22‖(t-t0)=

‖y(2)(t0)‖e-(1-‖M22‖)(t-t0)

由 ‖m22‖＜1以及定義1可知，當‖m22‖＜1時，y(2)(t)指數收斂。另一方面，由式(7)第一、三方程可得

y(i)(t)=e-(t-t0)y(i)(t0)+∫tt0e-(t-s)Mi2PΩ(y(2)(s))ds

其中：i=1，3。于是

‖y(i)(t)‖≤e-(t-t0)‖y(i)(t0)‖+

∫tt0e-(t-s)‖Mi2‖‖y(2)(t0)‖e-(1-‖M22‖)(s-t0)ds=

e-(t-t0)‖y(i)(t0)‖+‖Mi2‖×

‖y(2)(t0)‖∫tt0e-(t-s)e-(1-‖M22‖)(s-t0)ds≤

[1+‖Mi2‖/‖M22‖]‖‖y(t0)‖e-(1-‖M22‖)(t-t0)

類似地，當t∈[T，T1]，…，[Tn-1，Tn)時，Tn→∞，可以得到同樣的結果，再由式(7)與(2)的等價性可知，當‖M22‖＜1時，式(2)的解x(t，x0)指數收斂到式(1)的最優解，定理得證。

定理2 如果I-‖M22‖是一個M-矩陣，則式(2)的解x(t，x0)指數收斂到式(1)的最優解。其中|M22|=(mij)k×k（i，j=r+1，…，r+k）；I表示單位矩陣。

證明 由于I-|M22| 是M-矩陣，則存在一組常數ζ＞0，ε＞0使得

-(1-ε)ζi+∑r+kj=r+1ζi|mji|＜0(i=r+1，…，r+k)

構造如下形式的Lyapunov函數

V(t，y(2))=∑r+ki=r+1ζi|yi|eεt

沿式(7)的第二個方程求Dini導數

D+V=∑r+ki=r+1ζi[sgn(yi)dyi/dteεt+ε|yi|eεt]=

eεt∑r+ki=r+1ζi{sgn(yi)[-yi+∑r+kj=r+1mijPΩj(yj)]+ε|yi|}≤

eεt∑r+ki=r+1ζi[-|yi|+∑r+kj=r+1|mij‖PΩj(yj)|+ε|yi|]≤

eεt∑r+ki=r+1ζi[-|yi|+∑r+kj=r+1|mij|yj|+ε|yi|]=

eεt∑r+ki=r+1[-(1-ε)ζi+∑r+kj=r+1ζj|mji|]|yi|≤0

所以有

eεtminr+1≤i≤r+k(ζi)∑r+ki=r+1|yi|≤V(t，y(2))≤V(t0，y(2)(t0))

 V(t0，y(2)(t0))=∑r+ki=r+1ζi|yi(t0)|eεt0≤

maxr+1≤r+1(ζi)eεt0∑r+ki=r+1|yi(t0)|=

maxr+1≤r+1(ζi)eεt0‖y(2)(t0)‖1

即‖y(2)(t)‖≤maxr+1≤i≤k(ζi)/minr+1≤i≤k(ζi)‖y(2)(t0)‖e-(t-t0)‖。于是y(2)（t）指數收斂。類似于定理1的證明，容易得到y(1)（t），y(3)(t)也指數收斂，定理得證。

定理3 如果存在正定矩陣P及正對角陣D滿足-2P+PM22D2MT22P+D-2＜0，則式(2)的解x(t，x0)指數收斂到式(1)的最優解。

證明 由于-2P+PM22D2MT22P+D-2＜0 ， 存在任意小正常數ε使得

-2P+εP+PM22D2MT22P+D-2＜0

構造如下形式的Lyapunov函數：

V(t，y(2))=yT(2)(t)Py(2)(t)eεt

沿式(7)的第二個方程求Dini導數得到

D+V=2yT(2)(t)P[-y(2)(t)+M22PΩ(y(2)(t))]eεt+

εeεtyT(2)(t)Py（2）（t）

因為

2yT(2)(t)PM22PΩ(y(2)(t))≤yT(2)(t)PM22D2MT22Py(2)(t)+

PΩT(y(2)(t))D-2PΩ(y(2)(t))≤

yT(2)(t)PMx22D2MT22Py(2)(t)+

yT(2)(t)D-2y(2)(t)

所以

D+V≤eεtyT(2)(t)[（ε-2）P+PM22D2MT22P+D-2]y(2)(t)

由于-2P+εP+PM22D2MT22P+D-2＜0，V(t，y(2)）≤V(t0，y(2)(t0))，通過簡單運算容易得到‖y(2)(t)‖≤λmax(P)/λmin(P)‖y(2)(t0)‖e-ε(t-t0)/2。同理，類似于定理1、2的證明，容易得到定理3的結果。

3 仿真例子

考慮如下二次規劃問題

 min 1/2xTAx+bTx

x∈Ω，Ω={x∈R3|-4≤xi≤4，i∈L}(8)

其中：L={1，2，3}，A=61111.60.610.61.8，b=(5，2，6)T。該問題可構造如下神經網絡進行求解：dx(t)/dt=-x(t)+PΩ(x(t)-ρAx(t)-ρb)。

PΩ(x)=-4 xi＜-4xi-4≤xi≤4，ρ=0.54xi＞4

容易算得I-ρA=-2-0.5-0.5-0.50.2-0.3-0.5-0.30.1。類似于式(5)~(7)的處理，可以得到

 dy1(t)/dt=-y1(t)-0.5PΩ(y2(t))

dy2(t)/dt=-y2(t)+0.2PΩ(y2(t))

dy3(t)/dt=-y3(t)-0.3PΩ(y2(t))

(9)

顯然式(9)滿足定理1的條件，即其解指數收斂于式(8)的最優解(圖1)。



4 結束語

本文結果表明，投影神經網絡的收斂性與其約束條件密切相關。當可行域是矩陣約束時，其收斂條件只與連接權矩陣的部分元相關，其結果比以往收斂判定條件弱、實用性更強。

參考文獻：

[1]YASHTINI M， MALEK A. Solving complementarity and variational inequalities problems using neural networks[J]. Applied Mathematics and Computation， 2007， 190（1）:216-230.

[2]BNOUHACHEM A. A new projection and contraction method for lin-ear variational inequalities[J]. Journal of Mathematical Analysis and Applications， 2006， 314（2）: 513-525.

[3]BEN-ISRAEL A， LEVIN G， LEVIN Y， et al. Approximate methods for convex minimization problems with series-parallel structure[J]. European Journal of Operational Research， 2008， 189(3): 841-855.

[4]KHORRAM E， HASSANZADEH R. Solving nonlinear optimization problems subjected to fuzzy relation equation constraints with max-average composition using a modified genetic algorithm[J]. Compu-ters Industrial Engineering， 2008， 55(1): 1-14.

[5]HARKER P T， PANG J S. Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory， algorithms and applications[J]. Math Program， 1990， 48(1-3): 161-220.

[6]FACCHINEI F， PANG J S. Finite-dimensional variational inequalities and complementarity problems [M]. New York:Springer-Verlag， 2003.

[7]EFFATI S， JAFARZADEH M. A new nonlinear neural network for solving a class of constrained parametric optimization problems[J]. Applied Mathematics and Computation， 2007， 186(1): 814-819.

[8]YANG Yong-qing ， CAO Jin-de. A feedback neural network for solving convex constraint optimization problems[J]. Applied Mathematics and Computation， 2008， 201(1): 340-350.

[9]陶卿， 方廷健， 孫德敏. 基于約束區域的BSB聯想記憶模型[J]. 計算機學報，2000，23(3):266-271.

[10]XIA You-shen. Further results on global convergence and stability of globally projected dynamical systems [J]. Journal of Optimization Theory and Applications， 2004， 122(3): 627-649.

[11]李有梅，申建中，徐宗本. 投影型神經網絡算法的全局收斂性分析[J]. 計算機學報，2005，28(7):1178-1184.

[12]HU Xiao-lin， WANG Jun. Design of general projection neural networks for solving monotone linear variational inequalities and linear and quadratic optimization problems [J]. IEEE Trans on Circuits Syst， 2007， 37(3): 1414-1421.

[13]ZHONG Shou-ming， LIU Xin-zhi. Exponential stability and periodic-ity of cellular neural networks with time delay [J]. Mathematical and Computer Modelling， 2007， 45(9-10): 1231-1240.