權重不平衡有向網絡下的分布式優化算法

夏 俊，倪 偉

(南昌大學數學系，江西 南昌 330031)

分布式優化系統是近幾十年來的一個熱門研究領域，在社會科學和工程等領域已有廣泛的應用，如分布式電源配電網[1]、無線傳感器網絡[2]等。分布式優化主要是通過多智能體和鄰居之間進行信息交流從而實現全局網絡的最優決策，目前在相關方面已取得大量的研究成果。

分布式優化問題的早期工作主要是迭代離散時間算法，比如，Nedic等基于一致機制設計的分布式次梯度投影算法[3]，以及Jakovetic和Xavier基于梯度提出的加速分布式算法[4]。Nedic和Duchi分別提出了分布式梯度下降算法[5]和分布式對偶平均算法[6]，但是在算法[5-6]中使用了遞減步長，其收斂速度會隨著步長的減小而變慢。為了克服遞減步長導致分布式優化算法收斂速度變慢這一問題，Yuan和Matei設計了固定步長的分布式優化算法[7-8]。雖然固定步長要比遞減步長算法的收斂速度快，但文獻[7-8]中提出的算法只能收斂到最優解的某一個鄰域，因此，其不能獲得精確的最優解。為了設計一個固定步長且能精確收斂到最優解的分布式優化算法，我們將梯度跟蹤和比例積分策略[9]相結合，通過設計輔助變量跟蹤梯度的平均值，從而避免了使用遞減步長也使得算法能夠精確收斂到問題的最優解。

目前，大部分分布式優化算法都是針對無向圖網絡提出的，對于有向圖網絡特別是權重不平衡有向網絡獲得的結果相對較少。在無向圖網絡下進行的分布式優化算法包括眾所周知的分布式梯度下降算法[10]，精確的一階算法[11]以及鏡面下降算法[12]。然而當通信網絡是有向圖時，算法[11-12]就不能收斂到優化問題的最優解。為了在有向網絡下也能解決優化問題，Gharesifard和Kai分別提出了基于梯度的分布式優化算法[13]和離散時間的分布式自適應算法[14]，另外，Lee和Ribeiro提出了基于鞍點動力學的分布式算法[15]。但是算法[13-15]都是在權重平衡的有向圖網絡下提出的，事實上，基于權重不平衡有向圖的分布式優化算法在收斂性的分析上與無向圖本質上沒有很大區別，且權重平衡這一條件在一般有向圖下不易達成。因此，將連續時間的分布式優化算法推廣到權重不平衡的有向圖具有重要意義和挑戰。之所以在權重不平衡有向圖網絡下的分布式算法設計比較困難，是因為權重不平衡有向圖對應的拉普拉斯矩陣是非對稱的，而且在算法收斂性分析中不易選擇合適的李雅普諾夫(Lyapunov)函數。于是，Nedic和Olshevsky基于push-sum在有向圖網絡下提出了一個離散時間的分布式優化算法[16]。此外，Li和Ding在權重不平衡有向圖下提出了一個連續時間的分布式自適應優化算法[17]并且證明了其收斂到優化問題的最優解。但不足之處是分布式優化算法[17]直接用到了拉普拉斯矩陣零特征值的左特征向量，若不能提前獲得拉普拉斯矩陣零特征值的左特征向量這一信息，則該算法就無法收斂到問題的最優解。為了解決這一問題，我們通過設計變量對拉普拉斯矩陣零特征值的左特征向量進行跟蹤，從而提出了一種全新的連續時間分布式優化算法。

總而言之，在權重不平衡有向網絡下，我們基于梯度跟蹤[5]和比例積分策略[9]在連續時間下設計了一個固定步長的分布式優化算法。本文所設計算法的收斂速度不受遞減步長影響，而且在通信網絡是權重不平衡有向圖且不能提前知道拉普拉斯矩陣零特征值的左特征向量這一信息的情況下也能解決多智能體系統的優化問題。之后選取適當的Lyapunov函數并結合凸分析理論證明了本文所提出的分布式優化算法能精確收斂到優化問題的最優解。

本文其余部分安排如下。第1節包含符號說明和數學理論，并提出分布式凸優化問題。在第2節中，在權重不平衡有向圖下提出一個連續時間分布式優化算法，并分析其平衡點和收斂性。最后一節給出簡要的總結和未來的工作。

1 預備知識

1.1 符號說明

1.2 代數圖論

1.3 問題描述

我們考慮一個由N個智能體組成的網絡系統，它們之間的通信網絡由權重不平衡有向圖G來描述。對于每個個體i∈…,N}，令fi(x):n→是其局部成本函數，僅個體i和它的鄰居j∈Ni知道fi(x)的信息。網絡上的全局成本函數定義為這個網絡的目標是解決優化問題

(1)

假設1有向圖網絡G是強連通的。

假設2對所有的i=1,2,…N，局部成本函數fi(x)強凸。且對某些li>0，其梯度?fi(·)是li-Lipschitz連續的，即‖?fi(x)-?fi(y)‖≤li‖x-y‖,?x,y∈n。

(2)

其中X=col(x1,x2,…,xN)∈nN，L∈N×N是通信圖G對應的拉普拉斯矩陣。

本文將在權重不平衡有向圖下設計連續時間的分布式優化算法來解決問題(1)，即解決分布式優化問題(2)，在下一節中將給出具體的算法。

2 權重不平衡有向圖下的分布式優化算法

本節首先在權重不平衡有向圖下設計一個連續時間的固定步長分布式優化算法，然后對所設計算法的平衡點和收斂性進行分析。現考慮一組個體I=1,2,…,N在通信網絡是權重不平衡有向圖的情況下解決優化問題(1)，對于i∈I，實施如下分布式算法：

其中a、b是有待確定的正參數，vi∈N是輔助變量，vii是vi的第i個元素，且vi的初值滿足

引理1[17]設L∈N×N是強連通有向圖G對應的拉普拉斯矩陣，則有如下性質成立：

(1) 矩陣L有一個簡單零特征值對應于右特征向量1N。且所有的零特征值都有正實部。

引理2[19]對于系統(3d)，存在ε0>0使得ε0≤vii(t)≤1成立，對任意的i∈{1,2,…,N}和t≥0。

為了方便后續平衡點和收斂性的分析，設=L?In，D=d?In∈nN×nN，其中N×N，將算法(4)寫成緊湊的形式如下：

(4)

其中X=col(x1,…,xN)，Y=col(y1,…,yN)，Z=col(z1,…,zN)∈nN，V=col(v1,…,vN)∈NN，G(X)=col(?f1(x1),…,?fN(xN))∈nN，且N=L?IN。

首先分析分布式優化算法(4)的平衡點，有如下引理。

(5)

(7)

(8)

同樣的在式(8)兩邊同時左乘p?In可得

接下來這個定理分析了分布式優化算法(4)的收斂性，從而證明了該算法能夠在權重不平衡有向網絡下收斂到優化問題(1)的最優解。

定理1若假設1和假設2成立，個體間的通信由權重不平衡有向圖G表示，且L是有向圖G對應的拉普拉斯矩陣。對任意初始值X(0),Y(0),Z(0)∈nN，以及初值V(0)=col(v1(0),…,vN(0))∈NN，其中參數a和b分別滿足如下不等式：

(9)

其中

接下來分析系統

(10)

(11)

則V1關于式(11)的導數為

(12)

由Young不等式，可得如下不等式：

(13)

(14)

由Young不等式和?fi(xi)的Lipschitz連續性，i=1,2,…,N。可得不等式

(15)

同理可得：

(16)

由Young不等式并結合0

(17)

(18)

(19)

(20)

故，當

3 結論

本文主要在權重不平衡有向網絡下用分布式的方法解決了優化問題，通過梯度跟蹤方法與比例積分策略相結合提出了一個連續時間分布式優化算法。通過設計變量對拉普拉斯矩陣零特征值的左特征向量進行跟蹤，將分布式優化算法從無向圖推廣到了權重不平衡有向圖。我們所設計的分布式優化算法是固定步長且沒有直接用到拉普拉斯矩陣零特征值的左特征向量這一信息，并對其收斂性進行了分析，證明了該算法在權重不平衡有向網絡下能精確收斂到優化問題的最優解。在之后的研究中，可以通過跟蹤拉普拉斯矩陣零特征值的左特征向量這一方法將更多的分布式優化算法推廣到權重不平衡有向網絡，還可以與分布式博弈相結合，將其推廣到有向網絡。