高 娟,劉新為

(1.河北工業(yè)大學(xué)人工智能與數(shù)據(jù)科學(xué)學(xué)院,天津 300401;2.河北工業(yè)大學(xué)數(shù)學(xué)研究院,天津 300401)

1 引言

隨著大數(shù)據(jù)時代的到來和多智能體系統(tǒng)協(xié)調(diào)技術(shù)的發(fā)展,分布式優(yōu)化受到了學(xué)術(shù)界和工業(yè)界越來越多的關(guān)注,現(xiàn)已被廣泛應(yīng)用于分布式機(jī)器學(xué)習(xí)[1]、編隊控制[2]、多智能體目標(biāo)搜索[3]、無線網(wǎng)絡(luò)[4]和協(xié)調(diào)控制[5]等領(lǐng)域.這些實際問題通常被建模為最小化網(wǎng)絡(luò)上多個局部損失函數(shù)的平均值.網(wǎng)絡(luò)中智能體之間的通信通常可以抽象為一個圖.由于實際中許多網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是復(fù)雜的且不是雙向的,如基于廣播的通信協(xié)議[6],所以基于有向圖的分布式優(yōu)化問題受到了眾多學(xué)者的關(guān)注和青睞[7–8].本文主要關(guān)注基于有向圖的分布式優(yōu)化問題以及求解這類問題的優(yōu)化算法.

分布式梯度下降(distributed gradient descent,DG D)算法[9–10]已經(jīng)成為求解多智能體網(wǎng)絡(luò)優(yōu)化問題最流行的方法之一.當(dāng)采用衰減步長時,DGD方法可以次線性收斂到最優(yōu)解,但是收斂速度較慢;當(dāng)使用固定步長時,DGD方法可以達(dá)到線性收斂速度,但是只能收斂到最優(yōu)解的鄰域內(nèi).近年來,該算法得到了顯著的改進(jìn)并發(fā)展了許多變形,可參考文獻(xiàn)[11–18].例如,Shi等[11]通過利用兩次連續(xù)的DGD迭代的差構(gòu)造了精確的一階算法(exact first-order algorithm,EXTR A).當(dāng)使用固定步長時,該算法可以線性收斂到精確解.然而,該算法要求權(quán)重矩陣是對稱雙隨機(jī)矩陣.進(jìn)一步,Xu 等[12]首次將基于動態(tài)平均一致性[19]的梯度跟蹤技巧與DGD方法相結(jié)合提出了分布式梯度跟蹤方法.該算法中每個智能體使用不一致固定步長,并且權(quán)重矩陣可以是非對稱雙隨機(jī)矩陣.當(dāng)目標(biāo)函數(shù)是光滑和強(qiáng)凸函數(shù)時,Nedi?等[13]和Qu等[14]證明了該算法線性地收斂到最優(yōu)解.另外,Berahas等[15]結(jié)合了多次一致步技巧和DGD算法,提出了改進(jìn)的DGD方法.當(dāng)多次一致步數(shù)隨著迭代次數(shù)增加時,該方法在采用固定步長的情況下可以精確線性地收斂到最優(yōu)解.最近,Li和Lin[16]進(jìn)一步研究了EXTRA方法并對其進(jìn)行了復(fù)雜性分析.同時,Li和Lin[16]也將Catalyst加速技巧應(yīng)用到EXTRA中提出了加速的EXTRA算法,并分析了該算法的通信和計算復(fù)雜性.Qu和Li[17]提出了加速的分布式Nesterov梯度跟蹤算法,并且分析了該算法的線性收斂性質(zhì).Li等[18]提出了兩種基于懲罰方法的分布式加速梯度算法.

上述文獻(xiàn)中的算法僅適用于基于無向圖的分布式優(yōu)化問題,這些算法要求構(gòu)造雙隨機(jī)權(quán)重矩陣.然而對于基于有向圖的分布式優(yōu)化問題,網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可能是非平衡的,因此構(gòu)造雙隨機(jī)權(quán)重矩陣是件不切實際的事情.于是,Nedi?和Olshevsky[20–21]將Push-sum技巧[22]與DGD方法結(jié)合提出了求解有向網(wǎng)絡(luò)優(yōu)化問題的分布式梯度推力(gradient-push,GP)算法.該方法采用了列隨機(jī)權(quán)重矩陣并且利用Push-sum方法學(xué)習(xí)該矩陣的特征向量來消除有向圖的非平衡性.然而在GP方法中,由局部梯度引起的誤差,學(xué)習(xí)特征向量所需要的迭代以及衰減步長都可能惡化算法的性能表現(xiàn).

為了消除由局部梯度引起的誤差,許多學(xué)者提出了改進(jìn)的方法,如參考文獻(xiàn)[23–28].結(jié)合EXTRA和GP算法,Zeng等[23]和Xi等[24]提出了快速的分布式算法,并證明了其線性收斂性質(zhì).然而該分布式算法的步長范圍比較嚴(yán)格,即步長的最大下界嚴(yán)格大于0.文獻(xiàn)[25–28]提出了基于梯度跟蹤的方法.對于光滑和強(qiáng)凸函數(shù)來說,與GP算法的次線性收斂不同,這些方法[25–28]被證明可以線性地收斂到最優(yōu)解.例如,Xi等[25]提出了加速的基于有向圖的分布式優(yōu)化方法(accelerated distributed directed optimization,ADD-O PT).ADD-OPT算法結(jié)合了列隨機(jī)權(quán)重矩陣,Push-su m技巧和梯度跟蹤策略,并放寬了對步長的限制.另一些算法(參見文獻(xiàn)[27–28])則使用了行隨機(jī)權(quán)重矩陣,Push-sum技巧和梯度跟蹤策略.其中Xin等[28]提出基于不一致固定步長的快速行隨機(jī)優(yōu)化算法(fast row-st ochastic optimization with uncoordinated step sizes,FR OST).上述所有的基于有向圖的方法都需要專門的迭代來學(xué)習(xí)行或列隨機(jī)矩陣的特征向量,這導(dǎo)致此類算法需要額外的計算和通信.最近,通過同時地使用行隨機(jī)和列隨機(jī)權(quán)重矩陣,Xin和Khan[29]提出了AB算法(文獻(xiàn)[30]也研究了該算法).該算法的一個顯著特點是它避免了由特征向量估計引起的計算與通信.當(dāng)目標(biāo)函數(shù)是光滑和強(qiáng)凸函數(shù)時,Xin和Khan[29]證明了AB算法的線性收斂性質(zhì).進(jìn)一步,Xin和Khan[31]將AB和Heavy-ball動量加速技巧相結(jié)合,提出了分布式Heavy-ball動量加速算法,并證明了該算法對于光滑強(qiáng)凸函數(shù)可達(dá)到線性收斂速度.Gao等[32]提出了帶有參數(shù)的分布式動量方法,并證明了其線性收斂性質(zhì).該方法是分布式Heavy-ball動量加速算法的一種推廣.Li等[33]提出了Nesterov和Heavy-ball雙動量加速的分布式異步優(yōu)化算法,并分析了其收斂性質(zhì).

眾所周知,梯度類算法中步長的選取對算法的表現(xiàn)起著重要作用.上面提到的算法[9–18,20–21,23–33]涉及兩類步長: 一類是一致或者不一致固定步長,在實驗中它們被手動調(diào)試使得算法達(dá)到最佳表現(xiàn);另一類是衰減步長,當(dāng)?shù)c靠近最優(yōu)解時,它使得算法收斂速度很慢.這些分布式梯度類方法[9–18,20–21,23–33]沒有考慮如何充分利用局部信息為每個智能體選擇合適的步長,以此改善算法的數(shù)值表現(xiàn).最近,Gao等[34]將Barzilai-Borwein(BB)方法[35]引入基于無向圖的分布式優(yōu)化中,提出了帶有BB步長的分布式梯度方法并證明了該方法具有幾何收斂速度.進(jìn)一步,結(jié)合行隨機(jī)權(quán)重矩陣和Push-sum技巧,Hu等[36]將該方法推廣到有向圖上,提出了ADBB(accelerated distributed BB)算法.此外,這兩篇文獻(xiàn)中提出的分布式BB方法都需要結(jié)合多次一致步內(nèi)循環(huán)技術(shù),這大大地增加了智能體之間的通信成本.

受以自適應(yīng)截斷循環(huán)方式生成的BB步長[37]改善梯度法表現(xiàn)的啟發(fā),本文給出該BB步長的分布式形式,然后將其引入到AB算法中,從而提出了一種求解基于強(qiáng)連通有向圖的優(yōu)化問題的分布式Barzilai-Borwein梯度跟蹤方法,簡稱AB-BB.該方法中每個智能體利用其局部梯度信息自動地計算步長.與現(xiàn)有的分布式BB方法[34,36]相比,AB-BB方法不需要使用多次一致步內(nèi)循環(huán)技巧.所以,該方法在保證不增加每次迭代的計算和通信成本的基礎(chǔ)上通過采用分布式的BB步長策略提高了AB算法的性能.與只采用行隨機(jī)或列隨機(jī)權(quán)重矩陣的分布式梯度算法[25–28,36]相比,AB-BB算法避免了估計特征向量,從而降低了計算和通信成本.本文在與AB算法相同的假設(shè)下,證明了AB-BB算法可以線性地收斂到最優(yōu)解.最后,本文對所提出的AB-BB算法進(jìn)行了數(shù)值仿真.仿真結(jié)果表明了本文所提出的算法的有效性.

本文其余部分結(jié)構(gòu)安排為:第2節(jié)描述了所求解的優(yōu)化問題;第3節(jié)提出了新算法;第4節(jié)給出了新算法的收斂性結(jié)果;第5節(jié)為仿真實驗;第6節(jié)為本文結(jié)論.

記智能體i在第k次迭代時的變量為∈Rp.用1n代表元素全為1的n維列向量,In表示n×n階的單位矩陣,X ?Y定義為矩陣X和Y的克羅內(nèi)克積,ρ(X)表示方陣X的譜半徑,diag{x}代表以向量x的元素生成的對角矩陣.給定矩陣S ∈Rn×n,S∞表示為它的無限次冪(如果它存在),即.對于一個本原行隨機(jī)矩陣A ∈Rn×n,它的特征值為1的左特征向量和右特征向量分別記為πr和1n,且滿足1n=1.相應(yīng)地,對于一個本原列隨機(jī)矩陣B ∈Rn×n,它的特征值為1的左特征向量和右特征向量分別記為1n和πc,且滿足πc=1.由Perron-Frobenius定理[38]有A∞=1n和B∞=πc.符號‖·‖表示為向量或矩陣的歐氏范數(shù).

2 問題描述

考慮由n個智能體組成的有向網(wǎng)絡(luò),網(wǎng)絡(luò)中智能體之間的信息通信通過有向圖G=(V,E)來刻畫.其中V={1,2,···,n}是所有智能體(節(jié)點)構(gòu)成的集合,E是有向邊集且代表智能體之間的通信鏈路.記={j ∈V|(j,i)∈E}為智能體i的入鄰居集合,即該集合中的每個智能體可以將信息發(fā)送給智能體i.相應(yīng)地,記={j ∈V|(i,j)∈E}為智能體i的出鄰居集合,即該集合中的每個智能體可以接收智能體i發(fā)送的信息.注意,在這里包含智能體i本身.所有智能體協(xié)同地求解下列分布式優(yōu)化問題:

其中:x ∈Rp是全局決策變量;局部損失函數(shù)fi:Rp→R是連續(xù)可微的,且僅被智能體i所知.本文對目標(biāo)函數(shù)和通信圖作出以下標(biāo)準(zhǔn)假設(shè).

假設(shè)1對于每個i∈V,它的目標(biāo)函數(shù)fi是Li光滑的,即對?x,y ∈Rp,存在常數(shù)Li>0,使得

假設(shè)2對于每個i ∈V,它的目標(biāo)函數(shù)fi是μi強(qiáng)凸的,即對?x,y ∈Rp,存在常數(shù)μi>0,使得

假設(shè)3通信圖G是強(qiáng)連通的.

3 算法

本節(jié)首先介紹了分布式的Barzilai-Borwein步長,然后將其引入到AB算法中并提出了AB-BB算法.

3.1 分布式的Barzilai-Borwein步長

本小節(jié)首先回顧原始的Barzilai-Borwein方法.求解問題(1)的原始的BB方法[39]的迭代格式為

文獻(xiàn)[37,40–41]中的數(shù)值仿真表明,BB方法以交替或自適應(yīng)的方式使用長BB步長和一些短BB步長,比原始的BB方法[39]的性能要好得多.所以,本文考慮以自適應(yīng)截斷循環(huán)方式生成的BB步長[37].顯然,直接將該BB步長應(yīng)用到分布式優(yōu)化中是一件不切實際的事情.因為它需要計算全局梯度?f(xk).因此,本文給出該BB步長的分布式形式.

對于每個智能體i,定義

本文給出的分布式BB步長有下列形式:

其中h>0是間隔參數(shù),k≥1是迭代次數(shù),

3.2 Barzilai-Borwein梯度跟蹤方法

4 收斂性分析

本節(jié)證明了AB-BB算法具有R-線性收斂速度.

以下引理給出了分布式BB步長的取值范圍.

引理1設(shè)假設(shè)1–2成立.對所有的k≥1和i∈V,AB-BB算法中的BB步長滿足

下面兩個引理對收斂性證明有著重要作用,可參考文獻(xiàn)[29].

引理2考慮增廣的權(quán)重矩陣A和B.對于0<σA<1和0<σB<1,存在向量范數(shù)‖·‖A和‖·‖B,對?a ∈Rnp,有

其中σA=A-A∞A,σB=B-B∞B,以及·A和·B分別是與上述兩個向量范數(shù)相容的矩陣范數(shù).

根據(jù)有限維線性空間中任意兩種向量的等價性,存在正數(shù)r,l,t,u使得

類似于AB算法的收斂性證明思路,本文也考慮下列3個量:

1)一致誤差,‖xk+1-A∞xk+1‖A;

2)最優(yōu)間隙,‖A∞xk+1-1n ?x?‖;

3)梯度跟蹤誤差,‖zk+1-B∞zk+1‖B.

本文首先建立了關(guān)于上述3個量的一個線性不等式,然后結(jié)合該線性不等式和引理1的結(jié)果證明了AB-BB算法具有R-線性收斂速度.

為了證明AB-BB算法的線性收斂性質(zhì),本文首先需要給出跟蹤梯度的上界.

引理4[29]對所有的k≥0,有

其中vk ∈R3和Gc ∈R3×3有下列定義:

上述矩陣中的常數(shù)ai,i=1,2,3,4,5和di,i=1,2由下列式子計算得到:a1=σAl‖Inp-A∞‖,a2=(πc)n,a3=‖A∞‖,a4=r‖A-Inp‖,a5=‖A‖,d1=L‖B∞‖,d2=uLσB‖Inp-B∞‖.

證首先,給出一致誤差‖xk+1-A∞xk+1‖A的上界.注意到A∞A=A∞.由引理2和式(6a)可知

結(jié)合引理4可得

其次,給出最優(yōu)間隙‖A∞xk+1-1n ?x?‖的上界.由式(6a)有

考慮式(11)的右邊第1項,令

其中第1個等式利用了引理3.

考慮θ1.利用文獻(xiàn)[14]中的引理10,可知如果0<,則

結(jié)合式(11)–(14),可得到

最后,給出梯度跟蹤誤差‖zk+1-B∞zk+1‖B的上界.根據(jù)B∞B=B∞,引理2、假設(shè)1和式(6b),得

考慮式(16)的右邊第2項.由AA∞=A∞可知,AA∞-A∞是零矩陣.又由式(6a)有

將式(17)代入式(16)并使用引理4,可得

結(jié)合式(10),式(15)和式(18)即可得證.以下定理給出了AB-BB算法的主要收斂性結(jié)果.

定理1設(shè)假設(shè)1–3成立.令Ψ=rd1ψ1+d1ψ2+tψ3.定義

證根據(jù)文獻(xiàn)[38]中的推論8.1.29,本文推導(dǎo)保障參數(shù)c的范圍和正向量ψ=[ψ1ψ2ψ3]T的值使得Gcψ<ψ.上式可等價地寫為

其中Ψ=rd1ψ1+d1ψ2+tψ3.由于式(21)的右邊項必須為正,則有

注1定理1表明,當(dāng)保障參數(shù)c滿足某個下界時,所提出的AB-BB算法可以線性地收斂到問題(1)的最優(yōu)解.由定理1可知,最大步長滿足,其中πr和πc是元素和為1的正向量.當(dāng)智能體的個數(shù)n比較大時,πc的值相當(dāng)小.因此,參數(shù)c的值不必取為n,并且可以是更小的.從這一點來看,本文所提出的BB步長比ADBB算法中使用的BB步長更加靈活,甚至可能更大.當(dāng)然,參數(shù)c的取值還依賴于一些其他信息,例如范數(shù)等價常數(shù)和收縮系數(shù),這些信息通常是無法獲取的.因此,在實際中,c的上界是不可計算的,本文通過手動調(diào)整c的值使得算法達(dá)到滿意的表現(xiàn).

注2本文所提出的算法和AB算法在理論上都保證了線性收斂性質(zhì),但是它們的收斂速度并不能顯式表達(dá).因此無法在理論上明確比較本文的算法與已有算法的收斂速度的快慢.與使用固定步長的AB算法相比,本文所提出的算法的亮點在于每個智能體利用其局部迭代點信息和梯度信息自動地計算其步長.本文通過仿真實驗驗證了所提出的算法極大地改善了AB算法的數(shù)值表現(xiàn).

5 數(shù)值仿真

本節(jié)通過測試實際數(shù)據(jù)集上的分布式邏輯回歸問題來驗證所提出的AB-BB算法的有效性,并且將其性能與其他算法進(jìn)行對比.問題模型有下列形式:

圖1 不同的參數(shù)c對AB-BB算法的影響Fig.1 Comparison of AB-BB with different parameter c

為了研究初始步長對算法的影響,基于a9a數(shù)據(jù)集,圖2對比了AB-BB算法在取不同的初始步長時的結(jié)果.從圖2中可以看出,AB-BB算法的性能對初始步長的選取并不敏感.

圖2 不同的初始步長對AB-BB算法的影響Fig.2 Comparison of AB-BB with different initial step sizes

為了觀察間隔參數(shù)h對算法的影響,基于a9a數(shù)據(jù)集,本文針對h=1,2,3,5,8,10對AB-BB算法進(jìn)行了測試.當(dāng)h=1時,AB-BB算法中的BB步長退化為BB1步長.從圖3可以看出,與h=1相比,當(dāng)h=2,3,5,8,10時,AB-BB算法的表現(xiàn)更好,這也說明了算法往往比采用單個BB1步長效果好.

圖3 不同的間隔參數(shù)h對AB-BB算法的影響Fig.3 Comparison of AB-BB with different parameter h

為了進(jìn)一步說明所提出的算法的有效性,基于a9a和w8a數(shù)據(jù)集,本文將AB-BB算法與GP[21],ADD-OP T[25],FROST[28],AB[29]和ADBB[36]算法作了比較.

需要注意的是ADD-OPT和FROST每次迭代都有3次信息通信,而GP,AB和AB-BB每次迭代只有2次信息通信.為了公平起見,對于ADBB算法,取多次一致步內(nèi)循環(huán)迭代次數(shù)為1,這樣ADBB每次迭代有3次信息通信.對于a9a和w8a數(shù)據(jù)集,AB-BB算法分別選取初始步長=1.5,i ∈V和=2.4,i ∈V,其他算法通過多次手動調(diào)試得到最優(yōu)的步長.圖4和圖5在2個數(shù)據(jù)集上對比了所有算法的迭代次數(shù)、通信次數(shù)和運(yùn)行時間.平均殘差與迭代次數(shù)的關(guān)系圖直觀地反映了算法的收斂速度.從圖4(a)和圖5(a)可以看出,本文所提出的算法實現(xiàn)了線性收斂速度,并且比采用固定步長的分布式算法的收斂速度更快.由圖4和圖5可以看出,本文所提出的AB-BB算法在迭代次數(shù),通信次數(shù)和時間方面都比使用固定步長的算法的表現(xiàn)好很多;與現(xiàn)有的BB方法相比ADBB在迭代次數(shù)方面有相似的數(shù)值表現(xiàn),但是在通信次數(shù)和時間方面,本文算法的表現(xiàn)比ADBB算法更好些.這是因為本文算法不需要特征向量學(xué)習(xí)所需的計算和通信成本.

圖4 AB-BB算法與其他算法在a9a上的對比Fig.4 Comparison of AB-BB and other methods on a9a

圖5 AB-BB算法與其他算法在w8a上的對比Fig.5 Comparison of AB-BB and other methods on w8a

進(jìn)一步,本文對算法進(jìn)行了定量分析.基于數(shù)據(jù)集a9a和w8a,本文對比了所提出的算法與其他算法在平均殘差的精度達(dá)到10-12時所需迭代次數(shù),通信次數(shù)和運(yùn)行時間.表1給出了所有算法的實驗對比數(shù)據(jù),其中“–”表示未統(tǒng)計數(shù)據(jù).GP算法是次線性收斂,收斂速度較慢,耗時太長,所以本文沒有給出關(guān)于GP算法的相關(guān)數(shù)據(jù).從表1中可以觀察到,當(dāng)平均殘差達(dá)到某個精度時,與其他算法相比,本文所提出的算法需要最少的迭代次數(shù),通信次數(shù)和運(yùn)行時間.這反映了本文所提出的算法比其他算法更加具有優(yōu)勢.

表1 不同算法的實驗數(shù)據(jù)結(jié)果Table 1 Experimental data of different algorithms

6 結(jié)論

本文提出了一種求解基于強(qiáng)連通有向圖的優(yōu)化問題的分布式Barzilai-Borwein梯度跟蹤方法.該方法是在同時使用行和列隨機(jī)矩陣的AB算法的基礎(chǔ)上加入分布式的BB步長得到的方法.本文所提出的方法中每個智能體利用局部梯度信息自動地計算步長,使得算法在不增加計算和通信成本的情況下獲得更好的數(shù)值表現(xiàn).當(dāng)目標(biāo)函數(shù)是光滑和強(qiáng)凸函數(shù)時,本文證明了該算法可以線性地收斂到最優(yōu)解.仿真實驗表明,本文算法比使用最優(yōu)固定步長的AB算法的表現(xiàn)好很多,并且優(yōu)于一些常用的分布式梯度算法.