求解凸二次規(guī)劃的連續(xù)型神經(jīng)網(wǎng)絡模型

楊靜俐，吳藝團，陳錦奎

(1.3．泉州信息工程學院 公共教學部，福建 泉州 362000；2.泉州市南安柳城中學，福建 泉州 362000)

0引言

二次規(guī)劃是非線性規(guī)劃的一種特殊類型，具有線性約束的二次規(guī)劃問題廣泛地出現(xiàn)在社會、經(jīng)濟、生產(chǎn)和經(jīng)濟計劃等諸多應用領域[1-2]。 若考慮目標函數(shù)是二次的而約束條件是線性的情況，其一般形式為：

(1.1)

其中可行域Ω是Rn中的一個多面體，x=(x1,x2,…xn)T為n維決策變量，Hesse矩陣Q∈Rn×n是一個n×n的實對稱矩陣，c∈Rn.該二次規(guī)劃有許多方面的應用，如線性回歸問題和序列二次規(guī)劃問題。 二次規(guī)劃現(xiàn)已成為組合優(yōu)化、系統(tǒng)分析、經(jīng)濟數(shù)學、管理科學的基本方法。對二次規(guī)劃問題的研究也引起了眾多學者和專業(yè)人員的廣泛興趣[3-9]。

眾所周知，人工神經(jīng)網(wǎng)絡是由大量簡單的基本元件——神經(jīng)元相互連接，通過模擬人的大腦神經(jīng)處理信息的方式，進行信息并行處理和非線性轉換的復雜網(wǎng)絡系統(tǒng)。由于神經(jīng)網(wǎng)絡具有強大的學習功能，同時具有平行與分布式特征，可以輕松地實現(xiàn)非線性映射過程，并且具有大規(guī)模并行計算能力。 因此，神經(jīng)網(wǎng)絡方法為優(yōu)化問題的計算提供了一條新的途徑，并已成為求解最優(yōu)化問題的重要方法之一。1984年，Hopfield把離散型神經(jīng)網(wǎng)絡進一步發(fā)展成連續(xù)型神經(jīng)網(wǎng)絡[10-11]，連續(xù)型神經(jīng)網(wǎng)絡基本結構與離散型神經(jīng)網(wǎng)絡的基本結構相似，但連續(xù)型神經(jīng)網(wǎng)絡中所有神經(jīng)元都同步工作，各輸入-輸出量均是隨時間連續(xù)變化的模擬量，這就使得連續(xù)型神經(jīng)網(wǎng)絡比離散型神經(jīng)網(wǎng)絡在信息處理的并行性、實時性等方面更接近于實際生物神經(jīng)網(wǎng)絡的工作機理。本文設計的連續(xù)型神經(jīng)網(wǎng)絡模型，網(wǎng)絡規(guī)模為3n，同時不含任何參數(shù)變量，全局指數(shù)穩(wěn)定，復雜度僅僅依賴于目標函數(shù)。

1 連續(xù)型神經(jīng)網(wǎng)絡模型

為了導出結論，本節(jié)先介紹以下定義和引理。

定義 2.1[12]令Ω?Rn是閉凸集，若?x∈Rn，存在唯一的點y∈Ω，使得

‖x-y‖≤‖x-z‖(?z∈Ω).

則稱y為x在集合Ω上的投影，記：y=PΩ(x)=argminz∈Ω‖x-z‖.

定義 2.2[12]令Ω?Rn是閉凸集，連續(xù)函數(shù)F：Rn→Rn，變分不等式VI(F,Ω)是尋找x*∈Ω，使得

(x-x*)F(x*)≥0 ?x∈Ω.

引理 2.1[12]令x*是優(yōu)化問題

(2.1)

的解，其中Ω?Rn是閉凸集，f是連續(xù)可微函數(shù)，那么x*也是變分不等式▽f(x*)T(x-x*)≥0(?x∈Ω)的解。

引理 2.2[12]若f是連續(xù)可微函數(shù)，x*是變分不等式VI(▽f,Ω)的解，則x*也是優(yōu)化問題(2.1)的解。

定義 2.3[12]令U：Rn→Rn，非線性互補問題(NCP)是指尋找x∈Rn,x≥0，使得下列等式和不等式成立：

U(x)≥0

U(x)Tx=0

(2.2)

若U(x)是仿射的，即U(x)=Mx+q，其中M是矩陣，q是向量，則(2.2)為線性互補問題(LCP)。

定義 2.4[12]混合非線性互補問題(MNCP)是指尋找x∈Rn，使得下列等式和不等式成立：

Uixi=0,

Ui≥0,xi≥0,i∈I

(2.3)

Uj=0j∈L-I,

其中U是Rn→Rn的可微映射，L={1,2,…,n}，I?L.若U是仿射的，即U(x)=Mx+q，其中M是矩陣，q是向量，則(2.3)為混合線性互補問題(MLCP)。

引理 2.4[12](投影定理)令Ω?Rn是閉凸集，則x*∈Ω是變分不等式VI(F,Ω)的解，當且僅當對?α>0，x*是映射PΩ(I-αF)：Ω→Ω的不動點，即x*=PΩ(x*-αF(x*)).

引理 2.5[12]令Ω?Rn是閉凸集，則下面兩個不等式成立。

(1)(v-PΩ(v))T(PΩ(v)-u)≥0,?v∈Rn,u∈Ω;

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

由引理2.1、引理2.2和引理2.3，我們可以得出如下結論：

定理 2.1x*∈Rn是問題(1.1)的最優(yōu)解，當且僅當存在y*∈Rn使得

證明 根據(jù)Kuhn-Tucker條件和引理2.1、引理2.2和引理2.3，定理即可證明。

根據(jù)定理2.1和引理2.5，優(yōu)化問題(1.1)的解就是下面投影方程的解，即

PΩ(Dx-(Bx+d))=Dx

(2.4)

其中B=D-TA，d=-D-Tc.

根據(jù)上述預備知識，本文構造如下兩個連續(xù)型神經(jīng)網(wǎng)絡模型用于求解問題(1.1)，其中神經(jīng)網(wǎng)絡(2.5)為直接神經(jīng)網(wǎng)絡，其平衡點即為問題(1.1)的最優(yōu)解；令問題(1.1)中y=Dx，即可得到間接神經(jīng)網(wǎng)絡(2.6)，從而y為神經(jīng)網(wǎng)絡的平衡點，D-1y為問題(1.1)的最優(yōu)解。

直接神經(jīng)網(wǎng)絡模型：

(2.5)

其中PΩ(x)=「PΩ(x1),PΩ(x2),…，PΩ(xn)?T，B=D-TA，d=-D-Tc，同時，投影算子PΩ(xi)為具有如下形式的分段函數(shù)

間接神經(jīng)網(wǎng)絡模型：

(2.6)

其中，W=D-TAD-1，q=D-Tc.

易知，神經(jīng)網(wǎng)絡(2.5)包含2個隱含層，神經(jīng)網(wǎng)絡(2.6)只包含1個隱含層，且這兩個神經(jīng)網(wǎng)絡模型均可以用硬件實現(xiàn)，其電路實現(xiàn)優(yōu)簡單的加法器、放大器、n個用來實現(xiàn)▽f(x)的處理器和n積分器以及分段線性激勵函數(shù)PΩ(·)來實現(xiàn)。下文對神經(jīng)網(wǎng)絡(2.5)、(2.6)的穩(wěn)定性進行討論。

2 穩(wěn)定性分析

本節(jié)首先給出穩(wěn)定性的相關定義。

‖x(t)-x*‖≤k(δ)‖x(t0)-x*‖e-λ(t-t0),?t≥t0.

對于神經(jīng)網(wǎng)絡(2.5)，有如下穩(wěn)定性定理。

定理 3.1 若A是半正定矩陣，則神經(jīng)網(wǎng)絡(2.5)是Lyapunov意義下穩(wěn)定的，且全局收斂到問題(1.1)的最優(yōu)解。若A是正定矩陣，則神經(jīng)網(wǎng)絡(2.5)全局指數(shù)收斂到問題(1.1)的唯一的最優(yōu)解。

證明 令x*是問題(1.1)的最優(yōu)解，由引理2.5知，

{PΩ[Dx-(D-TAx-D-Tc)]-Dx*}T{PΩ[Dx-(D-TAx-D-Tc)]-[Dx-(D-TAx-D-Tc)]}≥0

則

(x*-x)TD{PΩ[Dx-(D-TAx-d)]-Dx}+(x-x*)TAD-1{PΩ[Dx-(D-TAx-d)]-Dx}≥‖PΩ[Dx-(D-TAx-d)]-Dx‖2+(x-x*)TA(x-x*)

取Lyapunov函數(shù)

則有

≤0

所以神經(jīng)網(wǎng)絡(2.5)是Lyapunov意義下穩(wěn)定的且全局收斂到問題(1.1)的最優(yōu)解。

若A是正定矩陣，則有

即

V(x)≤V(x0)e-2μ(t-t0)

從而

‖x(t)-x*‖≤‖x(t0)-x*‖e-2μ1(t-t0)(μ1>0)

即證明神經(jīng)網(wǎng)絡(2.5)全局指數(shù)收斂到平衡點。

定理 3.2 對每一個y∈Rn，神經(jīng)網(wǎng)絡(2.6)在區(qū)間[t0,+∞]上存在唯一的、連續(xù)的解y(t)，且y(t0)=y0.

證明 令T(y)=PΩ(y-(Wy+q))-y，對?y,v∈Rn，有：

‖T(y)-T(v)‖=‖PΩ(y-(Wy+q))-y-PΩ(v-(Wv+q))+v‖

≤‖PΩ(y-Wy-q)-PΩ(v-Wv-q)‖+‖y-v‖

≤2‖y-v‖+‖W‖‖y-v‖

≤(2+‖W‖)‖y-v‖

這表明T(y)滿足Lipschitz條件，由解的存在唯一性定理知，對?y∈Rn，神經(jīng)網(wǎng)絡(2.6)有唯一的連續(xù)解y(t)，且y(t0)=y0.

對于神經(jīng)網(wǎng)絡(2.6)，有如下穩(wěn)定性定理。

定理 3.3 若A是半正定矩陣，則神經(jīng)網(wǎng)絡(2.6)是Lyapunov意義下穩(wěn)定的，且全局收斂到平衡點y*，同時D-1y*是問題(1.1)的最優(yōu)解。若A是正定矩陣，則神經(jīng)網(wǎng)絡(2.6)全局指數(shù)收斂到平衡點y*，同時D-1y*是問題(1.1)的唯一的最優(yōu)解。

證明 定義F(y)=PΩ(y-(Wy+q))-y.

顯然，F(xiàn)(y)=0當且僅當y是投影方程(2.4)的解，這樣神經(jīng)網(wǎng)絡(2.6)的平衡點對應于(2.4)的解，而投影方程(2.4)的解對應于二次規(guī)劃問題(1.1)的解。首先，令y=Dx，則二次規(guī)劃問題(1.1)可以寫成如下形式：

(3.1)

其中W=D-TAD，q=D-Tc.顯然，若y*是問題(3.1)的最優(yōu)解，則D-1y*是問題(1.1)的最優(yōu)解。 同時，W是對稱半正定的，若A是正定矩陣，則W也是正定矩陣。由定理2.3知神經(jīng)網(wǎng)絡(2.6)對任意的初始點均有唯一的連續(xù)解y(t).根據(jù)引理2.5，對?y∈Rn，v∈Ω，有

[v-PΩ(y-(Wy+q))]T[PΩ(y-(Wy+q))-(y-(Wy+q))]≥0.

(3.2)

由于y*是投影方程(2.4)的解，對?v∈Ω，有

(v-y*)T(Wy*+q)≥0

(3.3)

在(3.1)式中令v=y*，在(3.3)式中令v=PΩ(y-(Wy+q))，然后把兩個不等式相加，得到

[y*-PΩ(y-(Wy+q))]T[W(y-y*)-y+PΩ(y-(Wy+q))]≥0.

將上式進行整理，得

即

取Lyapunov函數(shù)

其中y*是問題(3.1)的最優(yōu)解，M2=(I+W)且M是對稱正定矩陣。 則

=(y-y*)TMTMPΩ((y-(Wy-q)-y)

≤0

所以神經(jīng)網(wǎng)絡(2.6)是Lyapunov意義下穩(wěn)定的且全局收斂到問題(1.1)的最優(yōu)解。

若A是正定矩陣，則有

(y-y*)TW(y-y*)≥δ‖y-y*‖2(δ>0).

因此

即

V(y)≤V(y0)e-2δ(t-t0)

從而

‖y(t)-y*‖≤‖y(t0)-y*)‖e-2δ1(t-t0)(δ1>0)

即證明神經(jīng)網(wǎng)絡(2.6)全局指數(shù)收斂到平衡點。

3數(shù)值試驗

本節(jié)構造如下測試問題，以驗證所提出算法的有效性能。

例1 考慮如下具有線性約束的二次規(guī)劃問題

則

此問題的最優(yōu)解x*=[0.5,0.5,0.5]T.

分別用本文構造的連續(xù)型神經(jīng)網(wǎng)絡(2.5)和(2.6)求解該問題。初始輸入均取為[-1.5,0,1.5]T，模擬結果表明神經(jīng)網(wǎng)絡(2.5)總收斂于二次規(guī)劃問題的最優(yōu)解，神經(jīng)網(wǎng)絡(2.6)收斂于其平衡點y*=(0,-1,1)T(y*=Dx*).神經(jīng)網(wǎng)絡(2.5)的軌跡狀態(tài)如圖4.1。

圖4.1 神經(jīng)網(wǎng)絡(2.5)的軌跡狀態(tài)

神經(jīng)網(wǎng)絡(2.6)的軌跡狀態(tài)如圖4.2。

圖4.2 經(jīng)網(wǎng)絡(2.6)的軌跡狀態(tài)

4小結

本文構造連續(xù)型神經(jīng)網(wǎng)絡求解凸二次規(guī)劃問題，模型不含任何參數(shù)，算法簡單，復雜度僅依賴于目標函數(shù)，且是全局指數(shù)穩(wěn)定的，為凸二次規(guī)劃問題的求解提供了一種有效途徑。