一類分布最優問題的指數時間收斂算法

劉書新，韓佳敏，杜海霞，曹若薇

（新疆農業大學數理學院，新疆烏魯木齊，830052）

多智能體系統[1]作為分布式人工智能的一個重要分支，主要研究多個智能體在復雜環境下如何處理協同合作等問題。多智能體系統的一致性問題主要是基于多智能體系統中的智能體相互之間的信息交換，通過設計一致性協議[2]使得智能體的狀態趨于一致。近年來，多智能體系統的一致性問題得到了廣泛的應用，例如分布式傳感器網絡、機器人系統的協作等[3]。另一方面,隨著人工智能和大數據等新興領域的發展，基于多智能體一致性的分布式優化理論[4]得到了越來越多的關注，并逐漸在協同控制、工程計算等各個領域得到廣泛應用。多智能體系統分布式優化是通過多智能體之間的有效合作完成優化任務，在多智能體系統一致性的框架下求解分布式最優問題，其中有代表性的算法有基于迭代框架下的離散時間算法[5]、基于協調控制的連續時間算法[6]、基于有限時間收斂的不連續算法[7]和基于固定時間收斂的連續算法[8]。基于以上討論，提出了一個求解多智能體優化問題的分布式指數時間收斂的算法。

1 預備知識和問題表述

1.1 代數圖論

多智能體系統各智能體之間的通訊拓撲可以用圖進行描述。令G={V,E,B} 表示一個拓撲圖，其中V={v1,v2,…,vn} 表示其節點的集合，n為圖中節點個數，節點的下標集合為In；E?V×V表示邊的集合，eij=(vi,vj)表示圖的邊；鄰接矩陣B=[bij]，其中bij為非負實數，表示節點vi到節點vj的連接權重。如果節點vi可以接收到節點vj的信息，則bij>0；否則，bij=0，假設相連節點之間連接權重均為1，拓撲圖中每個節點沒有自連，即對于所有i∈In，bij=0。如果一個拓撲圖的鄰接矩陣B是對稱矩陣，則稱該拓撲圖是無向的。一個圖的Laplacian 矩陣定義為L=[lij]∈Rn×n。當i=j時當i≠j時，lij=-bij。對于任意節點vi，定義其鄰域節點集為Ni={vj∈V∶(vi,vj∈E)}。如果對于兩個節點vi,vj，存在下標集合{k1,k2,…,ki} 滿足，則稱節點vi到節點vj之間存在一條有向信息傳輸路徑。對于一個無向圖，如果圖中任意兩個節點都存在至少一條有向連接路徑，則稱該圖G是連通的。矩陣L所有特征根都是非負實數。矩陣L第二最小特征根λ2(L)>0，其又被稱作該撲圖的代數連通度，且因此，如果1Tε=0，則有εTLε≥λ2(L)εTε。

引理對于一個無向連通圖的Laplacian 矩陣L具有如下的性質：

(1)0 是矩陣L的一個特征值，1 是其相應的特征向量；

(2)對任意向量ε=[ε1,ε2,…,εn]T，有下式成立

1.2 指數收斂

考慮方程

其中，f∶Rn→Rn為一個連續函數。

定義1方程(1)的解為有界的。如果對于任意的(t0,x0)∈R×Rn，都存在M=M(t0,x0)，使得對于一切t≥t0，有‖x(t0,x0)‖≤M[10]。

定義2方程(1)的解為全局指數收斂的。若存在正常數k,δ，使得任意解x(t)對唯一平衡解x0，當t≥t0時，有

1.3 問題表述

考慮由n個智能體組成的多智能體系統，其中每個智能體具有局部目標函數hi(xi)。要討論的問題是在保持全局等式約束的同時，最小化所有局部目標函數的和，即

x=[x1,x2,…,xn]T是一個決策向量，h(x)是全局目標函數，hi(xi)是局部目標函數，Ci0表示變量，xi是一個常量。

注1問題(2)的等式約束來自一些物理約束，如資源配置、供需平衡、借貸平衡等。

假設1智能體之間的通信拓撲是無向連通圖。

假設2目標函數hi(xi)是強凸的，存在正常數σ使得?2hi(xi)≥σ>0。

由假設2可知問題(2)具有唯一的最優解。

2 指數時間收斂的算法設計

為求解優化問題(2)，提出下面的分布式算法：

其中，r是常數，yi和θi是輔助變量。事實上，根據假設1和bij=bji，則有

表示算法(3)始終滿足問題(2)的等式約束，同時，將問題(2)轉化為下面的無約束優化問題：

其中，y=[y1,y2,…,yn]T是輔助決策向量。

根據(3)式中的第二個式子，把xi(i=1,2,…,n)對yj(j=1,2,…,n)求導得

進一步，有

注意到h(x)的梯度為?h(x)=(θ1,…,θn)T。

由(4)式，得到

其中，L代表通信圖對應的拉普拉斯矩陣。顯然，h(y)的Hessian矩陣滿足

證明算法(3)的收斂性。

定理在假設1 和2 的條件下，分布式算法(3)可以在指數時間內求解問題(2)。

證明假設凸優化問題(2)的唯一最優解用z=[z1,z2,…,zn]T表示。a是任意常數，如果z=a1，則z是平凡解。探討非平凡解的情況。對于任意的凸緊集Q?Rn/a1，和任意的y,w∈Q，由h(y)的強凸性可得

因為通信圖是無向連通的，所以通信圖拉普拉斯矩陣L特征向量1，ξ2,…,ξn的特征值相應的表示為0=λ1<λ2≤…≤λn，其 中‖ξi‖=1,i=2,…,n。向量y-z可以表示如下

其中，τi(i=1,2,…,n)是常數，ξ=τ2ξ2+…+τn ξn，則

注意到

根據假設2，得

由(8)式，進一步得到

將(5)式代入上式的右邊

由于0 是拉普拉斯矩陣L特征向量1 的單特征值，則L1=0。因此

對于(7)式，設w=z。當?h(z)=0，有

將(6)式代入(10)式得

根據假設2得

結合(9)和(11)有

注意，‖ξ‖≠0對非平凡解成立。因此

選取Lyapunov函數

對(14)式求導得

再由(10)式可得y指數收斂到z。即算法(3)在指數時間內能求解問題(2)。

3 數值模擬

用電力調度問題來測試算法(3)的性能。考慮一個由3 臺發電機和3 個負載組成的電力系統，其中節點1、2、3 表示發電機，節點4、5、6 表示對應的負載，如圖1所示。

圖1 電力系統

設xi(i=1,2,3)和C分別表示由第i臺發電機產生的有效功功率和總負載需求。在電力工程中，發電機的成本函數hi(xi)一般由二次函數近似：hi(xi)=其中τi，βi和ηi代表成本系數。考慮的電力系統經濟調度問題可以表達為

顯然，算法(3)可以直接用于解決經濟調度問題(16)。假設總負荷需求C為420 MW，成本系數τi，βi和ηi如表1所示。將初始狀態設為

表1 發電機成本參數

利用算法(3)得到的經濟調度問題(16)解的動態軌跡，模擬結果顯示最優解為

4 結語

對一類等式約束的分布凸優化問題，基于多智能體系統設計了一個指數時間收斂的算法，利用Lyapunov 函數理論，證明了算法的指數收斂性。最后通過實例模擬驗證了理論分析的有效性。