權(quán)重不平衡有向網(wǎng)絡(luò)下的分布式優(yōu)化算法

夏 俊，倪 偉

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

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

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

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

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

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

1 預(yù)備知識(shí)

1.1 符號(hào)說(shuō)明

1.2 代數(shù)圖論

1.3 問(wèn)題描述

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

(1)

假設(shè)1有向圖網(wǎng)絡(luò)G是強(qiáng)連通的。

假設(shè)2對(duì)所有的i=1,2,…N，局部成本函數(shù)fi(x)強(qiáng)凸。且對(duì)某些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對(duì)應(yīng)的拉普拉斯矩陣。

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

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

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

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

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

(1) 矩陣L有一個(gè)簡(jiǎn)單零特征值對(duì)應(yīng)于右特征向量1N。且所有的零特征值都有正實(shí)部。

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

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

(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)的平衡點(diǎn)，有如下引理。

(5)

(7)

(8)

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

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

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

(9)

其中

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

(10)

(11)

則V1關(guān)于式(11)的導(dǎo)數(shù)為

(12)

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

(13)

(14)

由Young不等式和?fi(xi)的Lipschitz連續(xù)性，i=1,2,…,N?？傻貌坏仁?/p>

(15)

同理可得：

(16)

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

(17)

(18)

(19)

(20)

故，當(dāng)

3 結(jié)論

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