夏 俊，倪 偉

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

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

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

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

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

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

1 預備知識

1.1 符號說明

1.2 代數(shù)圖論

1.3 問題描述

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

(1)

假設1有向圖網(wǎng)絡G是強連通的。

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

(2)

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

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

2 權重不平衡有向圖下的分布式優(yōu)化算法

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

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

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

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

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

為了方便后續(xù)平衡點和收斂性的分析，設=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。

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

(5)

(7)

(8)

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

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

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

(9)

其中

接下來分析系統(tǒng)

(10)

(11)

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

(12)

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

(13)

(14)

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

(15)

同理可得：

(16)

由Young不等式并結(jié)合0

(17)

(18)

(19)

(20)

故，當

3 結(jié)論

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