基于事件觸發的分布式優化算法

2022-02-17 10:47:34易新蕾張圣軍陳蕊娟李渝哲

自動化學報 2022年1期

楊濤徐磊易新蕾張圣軍陳蕊娟李渝哲

在多智能體系統中,每個智能體(節點)都具有一個局部成本函數,分布式優化的目標是使由局部成本函數之和所構成的全局成本函數最小.分布式優化的研究由來已久,至少可以追溯到[1?2].近年來,由于其在電力系統、機器學習和傳感器網絡等領域的廣泛應用,這一研究重新引起了關注.研究者設計了多種分布式優化算法,詳見綜述文章[3?10],大致可分為離散時間算法和連續時間算法.

現有的大多數離散時間算法均基于一致性算法和分布式次梯度下降(Distributed gradient descent,DGD)算法[11?15].盡管DGD 算法可以處理非光滑凸函數的分布式優化問題,并在通訊延遲、丟包等多個方向上進行擴展以處理更為實際的情況,但由于使用了衰減步長,因此收斂速度較慢.在步長固定的情況下,雖然DGD 算法收斂速度快,但只能收斂到最小值點的鄰域[16?17].最近的研究集中在利用歷史信息來設計具有固定步長的加速算法.具體而言,文獻[18?19]中提出的算法是基于比例積分(Proportional integral,PI)控制策略,文獻[20?25]中提出的算法是基于分布式不精確梯度算法和分布式動態平均梯度跟蹤技術[26].現有的連續時間算法可以分為兩類:第一類是文獻[27?29]中提出的基于梯度的算法,這類算法本質上都是基于PI 控制策略,其中每個智能體使用一個輔助狀態(積分反饋)來校正由不同局部梯度引起的誤差;第二類算法使用二階Hessian 信息,例如文獻[30?32].

為了避免連續通信和減少通信負擔,事件觸發通信和控制的思想最初是針對單個系統[33?35]提出的.后來這種思想被應用到分布式一致性問題[36?42].近年來,研究者提出了基于事件觸發通信的分布式優化算法[29,43?50].文獻[29]提出了一種不存在Zeno行為[51]的事件觸發算法,即在有限時間內不會觸發無限多次事件,并針對無向連通圖,在局部成本函數強凸以及梯度局部Lipschitz 且可微的條件下,證明了算法指數收斂到最小值點的鄰域.受文獻[30]提出的零梯度和 (Zero-gradient-sum,ZGS)算法的啟發,文獻[44]提出周期性的事件觸發機制;文獻[45]則設計了基于動態事件觸發的ZGS 算法.針對無向連通圖或權平衡強連通的有向圖,在局部成本函數強凸且具有局部Lipschitz Hessians 的條件下,證明了算法的指數收斂性.

本文提出了兩種基于比例積分策略的分布式優化算法,并證明了算法的收斂性.在此基礎上,為了減少通信負擔,我們提出了基于事件觸發的分布式優化算法,并證明了提出的基于事件觸發的優化算法不存在Zeno 行為,且保持了與連續通信下分布式優化算法相同的收斂性.文獻[29]提出的事件觸發算法只有在局部成本函數強凸且具有局部Lipschitz梯度的條件下收斂到全局最小值點的一個鄰域,而我們提出的算法在局部成本函數可微且凸的條件下,即可精確地指數收斂到唯一的全局最小值點.與文獻[46]中提出的算法相比,我們提出的算法更簡單,因為在執行文獻[46]中的算法時需要一些特殊設計的增益參數.與文獻[44?45]中提出的基于二階Hessian 信息的事件觸發ZGS 算法相比,我們提出的算法是基于一階梯度的,易于實現.此外,ZGS 算法需要特殊的初始化,而我們提出的算法允許任意初始化.

本文其余部分安排如下.第1 節介紹圖論的基礎知識.第2 節介紹本文所考慮的分布式優化問題.第3 節提出兩種基于PI 控制策略的分布式優化算法,并分析所提算法的收斂性.第4 節提出基于事件觸發通信機制的分布式優化算法并分析其收斂性.第5 節利用數值仿真驗證理論結果.第6 節總結本文的主要結果并介紹未來的研究方向.

1 基礎概念

在這一部分,我們介紹圖論的一些基本知識[52].考慮一個包含N個智能體的無向圖G=(V,E,A),其中V={1,2,···,N}表示智能體的集合,E={(i,j):表示邊的集合,A=[aij]∈RN×N表示加權鄰接矩陣,其中,當 (i,j)∈E時,aij >0 ;當(i,j)∈/E時,aij=0 .在本文中,我們還假設圖中沒有自環邊,即對于所有的i ∈V,aii=0 .智能體i的鄰居集合定義為Ni={j ∈V|aij>0}.在無向圖中從節點i1到節點ik的路徑是指存在節點序列i1,···,ik,使得 (ij,ij+1)∈E,j=1,···,k ?1 .

對于無向加權圖G,加權Laplacian 矩陣L=的定義是對于,有Lij=?aij,因此,Laplacian 矩陣的行和為零.如果無向加權圖G是連通的,則Laplacian 矩陣L有唯一的0 特征值,其對應的右特征向量為1,其他所有特征值均大于零.

符號說明:給定一個矩陣A,AT表示其轉置矩陣.對稱矩陣A是半正(負)定的當且僅當其所有特征值均為非負(非正)時.給定兩個對稱矩陣M,N,M ≤N意味著M ?N是半負定的.記號A ?B表示矩陣A和B之間的Kronecker 積.ρ(·) 代表矩陣的譜半徑,ρ2(·) 表示非負矩陣的最小正特征值.In表示維數為n×n的單位矩陣.1n表示n維的列向量,其每個元素都為1.∥·∥表示向量的歐幾里德范數或矩陣的誘導2 范數.給定一個向量[a1,···,aN]T∈RN,diag{a1,···,aN}是第i個對角線元素為ai的對角矩陣.對于列向量x1,x2,···,xN,那么由其組成的堆棧列向量用 [x1,x2,···,xN] 表示.

2 問題描述

考慮由N個智能體組成的網絡,每個智能體都有一個局部凸函數fi:Rn →R,i ∈V.所有智能體共同協作以找到一個最小值點x?,使全局成本函數f(x)=最小,即:

智能體之間的通信用無向加權圖G=(V,E,A)來描述,其中V={1,2,···,N}是智能體的集合,E ?V ×V是邊的集合,A是加權鄰接矩陣.

如引言部分所述,為了避免智能體之間的連續通信,研究者設計了一些分布式事件觸發算法.然而,大多數現有的算法要么需要特殊的初始化,要么只收斂到全局最小值點的一個鄰域,這些啟發了本文的研究.更具體地說,我們的目標是設計任意初始化的事件觸發算法,并精確地收斂到全局最小值點.

我們對局部和全局成本函數作出以下假設:

假設1.對每個i ∈V,局部成本函數fi(x) 是連續可微凸函數.此外,的全局最小值是有界的.

假設2.全局成本函數f(x)=關于全局最小值點x?是mf-(有限)強凸的,即存在常數mf >0,使得,對任意的x∈Rn成立.

假設3.對于每個i ∈V,局部成本函數fi(x) 具有局部Lipschitz 梯度,即對任意緊集D ?Rn,存在常數Mi(D)>0,使得

其中,Mi(D) 稱為函數fi(x) 在緊集D上的Lipschitz常數.

在假設1 的條件下,分布式優化問題(1)的全局最小值點x?可能不唯一.但是,如果假設2 成立,則很容易證明全局最小值點x?是唯一的.與大多數文獻中局部成本函數是強凸的假設相比,這種假設的限制較小.詳細討論,請參見文獻[18,46],假設3 在現有文獻中也被廣泛使用.

3 基于PI 的分布式優化算法

針對問題(1),我們提出兩種基于PI 反饋策略的分布式優化算法,其中xi(t)∈Rn表示第i個節點在時刻t對全局最小值點x?的一個估計,積分項qi(t)∈Rn是用來校正第i個節點由于固定步長所產生的誤差.第一種算法如下:

算法(2)的收斂性如下:

定理 1.假設無向圖是連通的,并且假設1 成立.如果每個智能體i ∈V運行分布式優化算法(2),則有:

1) 每個xi(t),i ∈V,漸近收斂到全局最小值點x?;

2) 如果假設2～ 3 也成立,則每個xi(t),i ∈V,以不小于的速率指數收斂到唯一的全局最小值點x?,其中?2和?3是兩個正常數,并在證明中給出.

證明.見附錄B.

注 1.算法(2)與文獻[27?28]中所提出的分布式優化算法相類似.但是,文獻[27?28]只給出了在凸成本函數下,算法漸近收斂的結果.而定理1 給出了在全局成本函數對最小值點有限強凸的附加條件下,算法指數收斂的結果.針對有向圖為權平衡強連通的情形,當局部成本函數是可微的凸函數并且具有全局Lipschitz 梯度時,文獻[28]中的定理5.4給出了算法漸近收斂的證明.這里我們考慮的是無向連通圖,在全局成本函數對全局最小值點是有限強凸的附加條件下,定理1 給出了算法的指數收斂性.

下面,介紹第二種分布式優化算法:

算法(3)的收斂性如下:

定理 2.假設無向圖是連通的,并且假設1 成立.如果每個智能體i ∈V運行分布式優化算法(3),則有:

1) 每個xi(t),i ∈V,漸近收斂到全局最小值點x?;

2) 如果假設2～ 3 也成立,則每個xi(t),i ∈V,指數收斂到唯一的全局最小值點x?.

證明.該定理的證明與定理1 的證明相類似,這里不再贅述.

注 2.算法(3)與文獻[29]中所提出的算法相類似.但是,文獻[29]考慮的是局部成本函數強凸的情況,而本文中只要求全局成本函數關于全局最小值點是有限強凸的,是較之更一般的情況.

注 3.算法(2)中xi(0)和qi(0) 均可以任意選擇的,而在算法(3)中,雖然xi(0)可以任意選擇,但要求因此算法(2)對初始條件qi(0)是更為魯棒的.然而,與算法(3)相比,式(2b)需要額外通信qj,因此比算法(3)需要更多的通信開銷.

4 基于事件觸發的分布式PI 優化算法

為了避免智能體之間的連續通信和減少通信負擔,將第4 節所提出的分布式PI 算法與事件觸發通信相結合,提出了兩種分布式事件觸發算法并給出其收斂性分析.首先,基于分布式優化算法(2),我們提出第一種事件觸發算法,描述如下:

分布式事件觸發算法設計中的關鍵問題是如何構造觸發機制,以保證提出的算法不存在Zeno 行為,并收斂到全局最小值點.

定理 3.假設無向圖是連通的,并且假設1 成立.如果每個智能體i ∈V運行分布式事件觸發算法(4),并通過如下方式確定其觸發時間序列:

其中,所有ai,bi,ci,di >0均為設計參數,則有:

1) 算法(4)不存在Zeno 行為;xi(t)i ∈V x?

2) 每個,,漸近收斂到全局最小值點 ;

3) 如果假設2～ 3 也成立,則每個xi(t),i ∈V,以不小于的速率指數收斂到唯一的全局最小值點x?,其中?4是正常數,并在證明中給出.

證明.見附錄C.

接下來,基于算法(3),我們提出了第二種事件觸發算法,描述如下所示:

下面的定理給出了與定理3 類似的結果:

定理 4.假設無向圖是連通的,并且假設1 成立.如果每個智能體i ∈V運行分布式事件觸發算法(6),并通過如下方式確定其觸發時間序列:

其中,ai,bi >0 均為設計參數,則有:

1) 算法(6)不存在Zeno 行為;

2) 每個xi(t),i ∈V,漸近收斂到全局最小值點x?;

3) 如果假設2～ 3 也成立,則每個xi(t),i ∈V,指數收斂到唯一的全局最小值點x?.

證明.該定理的證明與定理3 的證明相類似,這里不再贅述.

注 4.基于算法(2)和算法(3),提出了對應的事件觸發算法(4)和算法(6).所提出的事件觸發通信機制,受到文獻[37]中時變觸發機制的啟發.與算法(6)的觸發機制(7)相比,算法(4)的觸發機制(5)更為復雜且需要額外通信開銷,但是算法(4)的初始條件qi(0) 是可以任意取值的,更為魯棒.

注 5.文獻[29]中定理13 要求所有局部成本函數強凸,而定理3 和定理4 只要求全局成本函數有限強凸,并不要求所有的局部成本函數都如此或強凸.此外,我們提出的算法指數收斂到全局最小值點,而文獻[29]中提出的算法只能收斂到全局最小值點的一個鄰域.文獻[44?45] 提出的事件觸發ZGS 算法需要特殊的初始化,而我們提出的算法允許對xi(0) 的任意初始化.

5 仿真實驗

考慮一個包含50 個智能體的大規模網絡,其中局部成本函數fi具體描述如下:

其中,j=1,2,···,5 .函數fi(x),i=6,···,10,36,···,40,是非強凸的函數,而全局成本函數關于點x?有限強凸.所有局部成本函數均可微,且具有局部Lipschitz 梯度.隨機選取一個包含50 個節點的無向連通圖,并針對該網絡拓撲圖以及上述定義的成本函數得到以下兩部分的仿真結果.

不考慮事件觸發時,為了更好地體現算法(2),算法(3)與文獻[29?31]所提算法的區別,我們對這些算法進行了仿真比較.通過圖1 可以看出所有算法均為線性收斂.此外,算法(3)的收斂速度相對較快.

圖1 不同算法中的演化Fig.1 The state evolution of in various algorithms

考慮事件觸發時,對于算法(4),我們隨機選擇觸發機制(5)中的設計參數ai,bi,ci和di.選擇采樣周期為 0.01 s.圖2 展示了智能體 6,16,26,36,46 的狀態演化過程,從中我們可以清楚地看到每個智能體都收斂到全局最小值點x?=?0.01214 .在[0,40 s]時間段內,上述5 個智能體分別被觸發了209,183,161,241,142次.由此可知,事件觸發算法(4)在仿真中針對上述5 個節點避免了大約95.32%的通信開銷.

對于算法(6),我們隨機選擇觸發機制(7)中的設計參數ai和bi.選擇采樣周期為 0.01 s.圖3 展示了智能體 6,16,26,36,46 的狀態演化過程,從中我們可以清楚地看到所有智能體收斂到全局最小值點x?=?0.01214 .在 [0,40 s] 時間段內,上述5 個智能體分別被觸發了 114,121,139,94,182 次.由此可知,事件觸發算法(6)在仿真中針對上述5 個節點避免了大約96.75%的通信.與算法(4)所對應的結果相比,智能體被觸發的次數更少,因此節省了更多的通信和計算量.

圖3 算法(6)中智能體6,16,26,36,46 的狀態演化Fig.3 State evolutions of agents 6,16,26,36,46 of Algorithm (6)

6 結論

本文考慮了一類分布式優化問題,針對無向連通圖,基于比例積分策略提出了兩類分布式優化算法,在局部成本函數為可微凸函數的條件下,證明了所提的分布式優化算法漸近收斂到全局最小值點.當局部成本函數具有局部Lipschitz 梯度,并且全局成本函數對全局最小值點是強凸時,證明了所提算法指數收斂到唯一的全局最小值點.此外,為了避免智能體之間的連續通信和減少通信開銷,提出了兩種基于事件觸發的分布式優化算法.證明了所提出的算法不存在Zeno 行為,并且在相對應條件下保持了與連接通信下分布式優化算法一樣的收斂性.未來的一個方向是設計分布式優化算法動態事件觸發通信機制的條件.

附錄A

下面文獻[46]的引理,在后文中指數收斂的證明中起著重要作用.

引理 1.假設無向圖是連通的.如果令KN=IN?則有,Laplacian 矩陣L是半正定的,KN1N=0,以及

如下引理是對文獻[18]中性質 3.6 的推廣,其中每個局部成本函數梯度局部Lipschitz 的假設放松了原有局部成本函數梯度全局Lipschitz 的假設,在接下來的證明中也很有用.

引理 2.假設無向圖是連通的,以及假設1～ 3 都成立.那么對任意ε>0 以及任意緊的凸集D ?Rn,以及x?∈D,

證明.對任意x ∈DN,對x=u+v進行分解,且u=和v=x?u.易知,vT(1N ?In)=0N.其余證明與文獻[18]中性質 3.6 的證明相同,這里不再贅述.□

附錄B

定理 1 的證明.1) 在這一部分,我們使用Lyapunov 穩定性分析方法.當假設1成立時,每個xi(t),i ∈V,都漸近收斂到全局最小值點x?,其可能是不唯一的.方便起見,記符號x=[x1,···,xN],q=[q1,···,qN],以及?f(x)=[?f1(x1),···,fN(xN)].則算法(2)可以寫為如下緊湊形式:

考慮如下函數:

V1(x,q)沿軌跡(B1)的導數滿足:

2) 在這一部分,我們證明當假設2 和3 成立時,算法的指數收斂性.

我們首先證明對于任意的初始狀態x(0) 和q(0),存在凸緊集C ?Rn,使得x?∈C和xi(t)∈C,?t ≥0,?i ∈V.集合C的具體形式依賴于x(0),q(0) 和x?,將在后文中給出.

由式(B2)和(B3),對任意t ≥0 和i ∈V,可得:

因此,C={x ∈Rn:||x ?x?∥2≤2V1(x(0),q(0))}是我們要尋找的凸緊集.

類似地,V3(x,q) 沿軌跡(B1)的導數滿足:

進而可得,

由于假設1～ 3 成立,由引理2 中式(A2)可得,

考慮如下候選Lyapunov 函數

由(B9)可知,W0(x,q) 沿(B1)的軌跡的導數,滿足如下不等式,

附錄C

1) 在這一部分中,我們通過反證法證明算法(4)不存在Zeno 行為.假設算法(4)存在Zeno 行為,則存在一個智能體i ∈V,使得,其中T0>0 是一個常數.注意到xi(t) 和qi(t) 都是連續的.因此存在常數P1>0 和P2>0,使得∥xi(t)∥≤P1和∥qi(t)∥≤P2對所有i ∈V和所有t ∈[0,T0] 都成立.

根據假設1 可知f(x) 連續可微,另外∥xi(t)∥≤P1,?i ∈V,?t ∈[0,T0].因此,存在一個常數P3>0 使得∥?f(x)∥≤P3,?t ∈[0,T0].

令C1=2LiiP1+2LiiP2+P3以及C2=2LiiP1.那么,由式(4)可得,