一種解決受約束的復變凸優化問題的新型神經網絡

徐柳明，喻 昕，盧惠霞

(廣西大學 計算機與電子信息學院，南寧 530004) (廣西多媒體通信與網絡技術重點實驗室，南寧 530004)

1 引 言

在信號處理，濾波器設計，醫學成像，系統識別，回歸分析，機器人控制等諸多應用中，優化問題作為一類重點問題一直受到廣泛的關注與發展.自從1986年，Tank和Hopfield[1]創新性的利用神經網絡模擬方法解決限制性的優化問題，就有許多學者紛紛加入到該領域中，例如:Kennedy和Chua[2]利用動態非線性規劃電路方法構造神經網絡去求解非線性優化問題;Zhang[3]等人利用拉格朗日乘子法創建遞歸神經網絡來處理光滑非線性凸優化問題;Xia[4]等人基于投影方法構造了遞歸神經網絡用以解決光滑凸(偽凸)優化問題;Xue[5]等人基于次梯度方法構造神經網絡求解非光滑凸優化問題;Qin[6]等人基于 Tikhonov 正則化提出了動態神經網絡求解非光滑優化問題;Yu[7]等人通過建立了不依賴罰參數的神經網絡模型解決非光滑偽凸優化問題;Chi[8]等人將神經網絡應用到循環分塊的優化預測當中.除了列舉之外的，還有很多學者利用或者構造了神經網絡去求解優化問題.

同時，隨著復變優化問題在自適應濾波[9]和遙感[10]等領域中的應用，越來越多的學者開始研究復變優化問題.人們發現復數相比實數更能體現和表達優化問題中物理特性，例如，Aizenberg[11]中的異或與奇偶N問題是通過復值神經元來表示和解決的，卻不能通過單個實值神經元來實現.且由于柯西黎曼條件下復變實值函數必然是非解析的，所以上述的實數域的神經網絡大多數都不能馬上應用于復數域內的優化問題.因此，Kreutz-Delgado[12]引入一種寬松的柯西黎曼微積分，并且定義了復變量實值函數的復梯度和給出了一些復變優化的理論成果.在此思想的推動與引領下，研究人員開始關注如何使用復變優化方法來解決復變優化問題;Zhang[13]等人提出了一種神經網絡去解決解決復變凸優化問題，但是該神經網絡結構比較復雜，為3層結構;Qin[14]等人利用精確罰函數法設計了一種投影神經網絡來求解復變凸優化問題，但是該神經網絡需要計算精確罰參數，實際應用中不是很方便;Zhang[15]等人利用假設目標函數為正定性設計了一個雙層神經網絡來求解復變非線性凸規劃問題，而本文假設相對寬松且神經網絡結構簡單;Liu[16]等人利用罰函數法構造一種神經網絡，但是該神經網絡只應用于帶等式與盒式限制的偽凸復變優化問題;Wen[17]等人提出一種解決復變偽凸優化問題的神經網絡，但是該神經網絡只能解決帶等式限制的優化問題;Liu[18]等人利用微分包含構造了一種神經動力學方法求解復變凸規劃問題，但是引入諸多假設條件.

利用現有的理論知識[19，20]和受上述文獻的啟發，本文提出一種新型的神經網絡來解決復變凸優化問題.與已經提出的神經網絡相比，本文對神經網絡的初始點無特殊要求，不需要計算精確罰參數，神經網絡結構相對簡單，為單層結構，可解決目標函數為復變實值凸函數的優化問題.

本文研究如下所示的帶約束的復變凸優化問題:

(1)

其中，z=(z1，z2，…，zn)T∈n，f:n→，g(z)=(g1(z)，g2(z)，…gm(z)):n→m是一個m-維向量值函數，f和gi均為n→的凸函數，A∈p×n是行滿秩矩陣以及b∈p.本文總是假設式(1)至少有一個解.

2 預備知識

為方便后續證明，首先給出符號標記以及定義的介紹:

定義1.[10]Re(·)與lm(·)分別代表從復向量或者復矩陣中返回的實部與虛部.對線性映射φ:X→Y，需要做如下分析:

1)當X=n和Y=n，對z∈n，令：

2)當X=m×n和Y=2m×2n，對A∈m×n(n>1)，令:

由此可知φ是從復空間一一對應于實空間的.

性質1.[11]對任意的向量z1，z2∈n，a∈，A，B∈m×n，以及可逆矩陣C∈m×n，有如下論斷:

φ(z1±z2)=φ(z1)+φ(z2);φ(az)=aφ(z)

φ(A±B)=φ(A)±φ(B);φ(aA)=aφ(A)

φ(AB)=φ(A)φ(B);φ(Az)=φ(A)φ(z)

φ(AH)=(φ(A))T;φ(C-1)=(φ(C))-1

通過性質1可以得到:

(2)

定義2.[12]令V?n為一個凸集.對于任意兩個點z1，z2∈V和任意常數λ∈[0，1]，如果f(z):n→是在V上的一個凸函數，可得f(λz1+(1-λ)z2)≤λf(z1)+(1-λ)f(z2).

令z=x+iy，使得f(z)等價于一個實數域的二元映射g(x，y):n×n→，其中x，y∈n，g(x，y)f(x+iy)=f(z).同時，由于x和y分別是復向量z的實部和虛部，可知z的共軛復向量可以表示為因此，有與視為函數的自變量.

定義3.[13]假設偏導數(?g/?x)和(?g/?y)存在.f(z)的偏導數定義如下:

(3)

當f(z):n→為凸函數且偏導數不存在，我們可以根據式(3)定義廣義復梯度.首先，重新定義凸函數g(x，y)關于x和y的次微分:

?xg(x，y)={q∈n:f(x，y)-f(k，y)≤〈q，x-k〉?k∈n}

?yg(x，y)={p∈n:f(x，y)-f(x，s)≤〈p，y-s〉?s∈n}

定義4.[11]對任意的z=x+iy∈n，f(z):n→為凸函數，關于f(z)的復次微分定義如下:?cf(z):=?xg(x，y)+i?yg(x，y).

如果f(z)為凸函數且偏導數(?g/?x)和(?g/?y)存在，復次微分與復梯度是一致的.

引理1.[15]假設f(z):n→為凸函數，對任意的向量z1，z2∈n和任意ξ∈?cf(z1)，有f(z2)-f(z1)≥Re{ξH(z2-z1)}.

引理2.[15](鏈式法則)如果W:n→是在z(t)上的正則函數且z(t):→n對t是Lipschitz連續的且對t可微，則對a.e.t∈[0，+∞)有:

3 提出的神經網絡模型

本節提出了一個單層循環神經網絡用來解決復變凸優化問題和一些下文中需要用到的定義.首先，需要滿足如下的假設條件.

將式(1)的可行域記作S={z∈n:g(z)≤0，Az=b}.另外，不等式可行域記為S1={z∈n:g(z)≤0}，等式可行域記為S2={z∈n:Az=b}.很明顯S=S1∩S2.在本文中，我們假設式(1)至少有一個最優解.

這里:

I+(z)={i∈{1，2，…，m}:gi(z)>0}

I0(z)={i∈{1，2，…，m}:gi(z)=0}

針對上邊提出的式(1)，本文提出一種單層復變循環神經網絡：

(4)

其中I是一個單位矩陣，P=AH(AAH)-1A.A∈m×n是行滿秩矩陣，α是大于零的常數.此外，m，其中，h中的每個分量的定義如下:

函數μ(t)為一個開關函數，其定義如下:

tS2為與等式可行域S2碰撞的時間上限.碰撞時間上限是由式(1)中的等式約束A和b，以及初始點z0決定的.

從表1可知，本文既不需要同文獻[14]一樣提前計算精確罰參數，又不需要同文獻[13]一般需要3層神經網絡，也不同與文獻[17]只能解決帶等式約束條件的復變優化問題，故而具有一定的優越性.同時，在初始點的選擇范圍上沒有特殊要求，因此比文獻[14]和文獻[17]更具優越性.

表1 與現有復變神經網絡性能對比

定義5.[11]設z*為復變神經網絡的一個平衡點，則有：

?cD(z*)]-AHH(Az*-b)

4 主要定理分析

1) 有限時間收斂到S2

定理1.若假設1成立，則過任意初始點z0∈n，神經網絡(式(4))的狀態解z(t)將在有限時間進入等式約束集S2={z∈n:Az=b}，并進入后不再離開.

證明:令L(z)=‖φ(A)φ(z)-φ(b)‖1，且?cL(z)=φ(A)Tφ(H(Az(t)-b)).設z(t)是式(4)經過初始點z0的一個狀態解，存在可測函數γ(t)∈?cf(z(t))，ξ(t)∈?cD(z(t))，η(t)∈H(A(z(t))-b)，對任意的t≥0使得：

(5)

由定義1與性質1，使得式(5)轉變如下形式：

(6)

由于φ(A)φ(I-P)=0，對任意的t≥0可得：

(7)

這里λm(φ(A)φ(A)T)為矩陣φ(A)φ(A)T的最小特征值.由于A是行滿秩矩陣，可知φ(A)也是行滿秩矩陣，故λm(φ(A)φ(A)T)>0.

對于任意的z(t)?S2，存在Az≠b，根據函數H(A(z(t))-b)的定義，可知‖φ(η(t))‖2≥1.對于z(t)?S2，得：

(8)

下面證明神經網絡的狀態解z(t)將在有限時間內進入等式約束集S2中.若存在tS2>0，使得對于任意的t∈[0，tS2)，都有z(t)?S2，由式(7)知：

對等式兩邊從0-tS2進行積分，得:

L(z(tS2))-L(z(0))≤-λm(φ(A)φ(A)T)tS2

也就是:

0≤‖φ(A)φ(z(tS2))-φ(b)‖1

≤‖φ(A)φ(z(0))-φ(b)‖1-λm(φ(A)φ(A)T)tS2

下面需證明過任意初始點的狀態解z(t)一旦進入等式約束集S2，就會永駐其中.如果不是該情形，狀態解z(t)在t1時刻離開S2，必定存在t∈(t1，t2)，使得z(t)?S2，而且‖φ(A)φ(z(t1))-φ(b)‖1=0，再根據式(8)，可得:

‖φ(A)φ(z(t2))-φ(b)‖1≤‖φ(A)φ(z(t1))-φ(b)‖1-λm(φ(A)φ(A)T)(t2-t1)=-λm(φ(A)φ(A)T)(t2-t1)<0

這與‖φ(A)φ(z(t2))-φ(b)‖1>0矛盾.因此，對于任意初始點z0，式(4)的狀態解z(t)都將在有限時間內進入到等式約束集S2，并永駐其中.

2) 狀態變量z(t)有界

定理2.若假設1成立，則式(4)從任意初始點出發的狀態解z(t)都是有界的.

(9)

3) 有限時間收斂到S

定理3.若假設1成立，則過任意初始點z0∈n，式(4)的狀態解z(t)將在有限時間進入可行域S，并永駐其中.

證明:首先，需要證明過任意初始點z0∈n的狀態解z(t)在有限時間內進入不等式可行域S1.由定理1，我們可得經過任意初始點z0∈n，式(4)的狀態解z(t)在有限時間內進入到等式約束集S2，并永駐其中.類似于定理2中，存在可測函數γ(t)∈?f(z(t))，ξ(t)∈?D(z(t))，使得:

(10)

≤‖ξ(t)‖-‖ξ(t)‖-α‖ξ(t)‖2≤-α‖ξ(t)‖2

(11)

(12)

這說明對于任意的初始點z0∈n，神經網絡的狀態解z(t)將在有限時間內進入S，且碰撞的時間上界是

這與D(x(t))≥0矛盾.因此，對于任意的初始點z0，式(4)的狀態解z(t)在有限時間內進入到可行域S，并永駐其中.

4) 神經網絡收斂到最優解

定理4.若假設1成立，則式(4)從任意初始點z0∈n出發的狀態解z(t)都能收斂到式(1)的最優解.

證明:設z*是式(1)的一個最優解.定義如下能量函數:

(13)

進過計算，可得?cM(z)=?cf(z)+?cD(z)+z-z*.

由定理2和定理3可知，復變神經網絡的狀態解z(t)在有限時間內進入可行域S=S1∩S2，并永駐其中.故而,設對于任意的t≥0，都有z(t)∈S=S1∩S2;存在可測函數γ(t)∈?cf(z(t))，ξ(t)∈?cD(z(t))，對于任意的t≥0，滿足:

(14)

(15)

ξ(t)])}=-max{1，‖γ(t)‖}

≤0

(16)

通過z(t)，z*∈S2得，P(z(t)-z*)=0，?t≥0.又因f(z)和D(z)是凸函數，有Re{(z-z*)Hγ(t)}≥f(z(t))-f(z*)≥0和Re{(z-z*)Hξ(t)}≥D(z(t))-D(z*)≥0，所以:

(17)

令:

:γ(t)∈?cf(z)，ξ(t)∈?cD(z)}

并結合式(15)、式(16)和式(17)，最終可以得出：

(18)

下面，證明必然存在一組遞增序列{tk}，滿足以下等式成立:

(19)

(20)

對式(20)從T′到t進行積分，當t→+∞，有：

(21)

而這個結果與M(z(t))的非負性矛盾，因此假設不成立，式(19)得證.

(22)

(23)

(24)

通過式(24)可知：

(25)

對任意的z∈S，可知：

因此可將式(25)簡化為如下:

?z∈S

有：

(26)

根據D(z)為凸函數可知：

(27)

類似于上文的證明，很容易得到:

5 仿真實驗

在Matlab2012a平臺上，通過仿真實驗來驗證本文提出神經網絡(式(4))的準確性與收斂性.

實驗1.考慮如下優化問題:

(28)

針對式(28)，其目標函數為f(z)在z上是非光滑的，意味著在文獻[15]中的投影神經網絡不能解決此問題.文獻[17]中的神經網絡由于只能求解帶等式約束的復變優化問題，同樣也不能解決此問題.文獻[14]中的神經網絡雖然可解此問題，但是要求不等式可行域有界且初始點要在不等式限制區域內.

圖1 式(4)在初始點為(1.2+0.1i，0.4-0.9i)T的收斂狀態圖

實驗2.考慮以下的非線性復值凸優化問題:

(29)

針對式(28)，Zhang等人在文獻[15]構造了一個3層神經網絡來求解;而本文提出的神經網絡為一層，同樣可以求解該問題.Qin等人在文獻[14]中所提出的神經網絡，需要計算精確罰參數，而本文所提出的神經網絡不需要進行這一步驟.

圖3 實驗2式(4)基于5個任意初始點的Re(z(t))和Im(Z(t))的收斂狀態圖

圖4 實驗2中5個隨機初始點的目標函數值圖

6 總 結

本文針對一類帶有不等式約束和等式約束的復變凸優化問題，提出了一種新型的單層循環神經網絡模型.證明了基于罰函數設計的神經網絡，其狀態解能在有限時間內到達可行域并永駐其中;并分析了對任意取值的初始點，神經網絡最終都會收斂到復變凸優化問題的最優解.最后通過兩個仿真實驗，證明了該神經網絡的有效性與準確性.與已有的相關神經網絡相比，該神經網絡能夠有效地求解復變凸優化問題，且不需要計算準確罰參數，對初始點的選取也沒有特殊要求，并且神經網絡結構相對簡單.在未來，我們的工作將以帶約束條件的非凸復變優化問題為目標進行深入研究與探索.