一種基于條件梯度的加速分布式在線學(xué)習(xí)算法

吳慶濤 朱軍龍 葛泉波 張明川

近年來,學(xué)術(shù)界和工業(yè)界對(duì)分布式優(yōu)化產(chǎn)生了濃厚的興趣[1-3].實(shí)際應(yīng)用中的許多經(jīng)典問題本質(zhì)上都是分布式優(yōu)化問題.例如數(shù)據(jù)管理問題[4-5]、資源分配問題[6-7]、目標(biāo)檢測(cè)與跟蹤問題[8-9]、智能電網(wǎng)[10]等.在這些應(yīng)用中,數(shù)據(jù)總量規(guī)模龐大,分散在不同的數(shù)據(jù)中心;節(jié)點(diǎn)計(jì)算能力有限,分散在不同的物理位置.為了提高這些系統(tǒng)的工作效率,均離不開分布式優(yōu)化算法[11-13].

當(dāng)前,多數(shù)分布式優(yōu)化算法的局部代價(jià)函數(shù)是非時(shí)變的.然而,在許多動(dòng)態(tài)變化環(huán)境中,局部代價(jià)函數(shù)可能是時(shí)變的.例如,傳感器網(wǎng)絡(luò)中的估計(jì)問題,由于受干擾和噪聲影響,每個(gè)傳感器的觀察結(jié)果隨時(shí)間變化.因此,動(dòng)態(tài)變化環(huán)境的分布式優(yōu)化須考慮局部代價(jià)函數(shù)的時(shí)變性,即為分布式在線優(yōu)化.在分布式在線優(yōu)化中,智能體僅在每一輪動(dòng)作結(jié)束之后才能獲得其局部代價(jià)函數(shù)值,即智能體無法獲取其未來代價(jià)函數(shù).從這個(gè)意義上說,分布式在線優(yōu)化本質(zhì)上不同于分布式優(yōu)化.

近十年來,機(jī)器學(xué)習(xí)領(lǐng)域主要關(guān)注集中式在線優(yōu)化問題[14],定義了一個(gè)衡量在線優(yōu)化算法性能的“悔函數(shù)”,即算法代價(jià)與事后最佳行為代價(jià)之差[15].受分布式優(yōu)化的啟發(fā),一些學(xué)者開始研究分布式在線優(yōu)化算法[16-21].具體而言,針對(duì)無約束優(yōu)化問題,當(dāng)代價(jià)函數(shù)是凸函數(shù)時(shí),可達(dá)到悔界[16-17];當(dāng)代價(jià)函數(shù)是強(qiáng)凸函數(shù)時(shí),可達(dá)到悔界 O ((logT)2)[18]或悔界 O (logT)[16-17].但在實(shí)際應(yīng)用中,大部分優(yōu)化問題是受約束的[22].因此針對(duì)約束優(yōu)化問題,當(dāng)代價(jià)函數(shù)是凸函數(shù)時(shí),可達(dá)到悔界[19-21];當(dāng)代價(jià)函數(shù)是強(qiáng)凸函數(shù)時(shí),可達(dá)到悔界 O (logT)[21].

隨著各類智能設(shè)備的廣泛使用,許多應(yīng)用中出現(xiàn)了大數(shù)據(jù)集,為了避免在線優(yōu)化算法投影算子造成的大數(shù)據(jù)計(jì)算瓶頸,就需要考慮高維約束優(yōu)化問題[23].為此,針對(duì)高維約束優(yōu)化的無投影算法應(yīng)運(yùn)而生,即Frank-Wolfe 算法[24].在Frank-Wolfe 算法中,使用了一個(gè)線性優(yōu)化步驟替代投影算子.近年來,Frank-Wolfe 算法[25-26]在許多領(lǐng)域廣受關(guān)注.此外,多種Frank-Wolfe 算法的變體[27-31]也相繼提出以解決各種類似問題.但是這些算法都是針對(duì)集中式場(chǎng)景,難以適應(yīng)分布式應(yīng)用.為此,針對(duì)非時(shí)變的代價(jià)函數(shù)提出一種分布式Frank-Wolfe 算法[32].但在實(shí)際中,代價(jià)函數(shù)通常是隨時(shí)間變化的.針對(duì)此問題提出了無投影分布式在線算法[33-34],可以達(dá)到凸局部代價(jià)函數(shù)的悔界 O (T3/4).但這個(gè)悔界劣于分布式在線優(yōu)化算法領(lǐng)域公認(rèn)的悔界

因此,進(jìn)一步優(yōu)化分布式在線學(xué)習(xí)算法的悔界仍然是一個(gè)亟待解決的問題.本文針對(duì)多智能體網(wǎng)絡(luò)中的高維約束優(yōu)化問題,使用Frank-Wolfe 步驟替代投影算子,提出了一種分布式條件梯度在線學(xué)習(xí)算法,主要貢獻(xiàn)如下:

1) 提出了Frank-Wolfe 在線學(xué)習(xí)算法,每個(gè)智能體僅利用自己及從鄰居接收的信息進(jìn)行分布式在線學(xué)習(xí),解決了某些場(chǎng)景無法使用集中式學(xué)習(xí)的應(yīng)用需求.

2) 分析了所提算法的性能.當(dāng)局部代價(jià)函數(shù)為凸時(shí),算法的悔界為;當(dāng)局部代價(jià)函數(shù)為非凸時(shí),算法以速率收斂于平穩(wěn)點(diǎn).是當(dāng)前同類算法能夠達(dá)到的最好性能.

3) 通過仿真實(shí)驗(yàn)驗(yàn)證了所提出算法的性能和理論分析的結(jié)論.

本文其余部分安排如下: 第1 節(jié)給出一些預(yù)備知識(shí);第2 節(jié)對(duì)所研究問題進(jìn)行形式化描述,并提出了一種分布式條件梯度在線學(xué)習(xí)算法;第3 節(jié)給出了一些假設(shè)和主要結(jié)果;第4 節(jié)對(duì)主要結(jié)果進(jìn)行詳細(xì)證明;第5 節(jié)描述了仿真實(shí)驗(yàn)與仿真結(jié)果;最后,對(duì)本文進(jìn)行了總結(jié).

1 符號(hào)及定義

為了方便描述,本節(jié)介紹一些符號(hào)約定和數(shù)學(xué)基礎(chǔ).在本文中,所有向量都是列向量,符號(hào) R 和Rd分別表示實(shí)數(shù)集和d維實(shí)歐幾里得空間;符號(hào)R+和 Z+分別表示正實(shí)數(shù)集和正整數(shù)集;符號(hào)〈·,·〉表示實(shí)歐幾里得空間的內(nèi)積;符號(hào)‖·‖2表示標(biāo)準(zhǔn)歐幾里得范數(shù).設(shè) 1 表示向量中所有元素為1 的列向量;D表示約束集X相對(duì)于標(biāo)準(zhǔn)歐幾里得范數(shù)‖·‖2的直徑,例如D=supx,x′∈X‖x-x′‖2.E [X] 表示隨機(jī)變量X的期望值.設(shè)凸緊集X是 Rd的一個(gè)子集.此外,與函數(shù)f相關(guān)的一些定義表述如下.

定義 1[35].對(duì)于任意的x,y ∈X,α∈[0,1],若有f(αx+(1-α)y)≤αf(x)+(1-α)f(y),則稱函數(shù)f:XR 為凸的.

定義 2[32].對(duì)于任意的x,y ∈X,若有

則稱函數(shù)f:XR 為μ-強(qiáng)凸的,其中μ是一個(gè)非負(fù)常數(shù).

定義 3[32].對(duì)于任意的x,y ∈X,若有

則稱函數(shù)f:XR 為β-光滑,其中β是一個(gè)正常數(shù).另外,式(2)等價(jià)于以下關(guān)系式

定義 4[32].對(duì)于任意的x,y ∈X,若有

則稱函數(shù)f:XR 為L(zhǎng)-Lipchitz,其中L是一個(gè)正常數(shù).

如果函數(shù)f是強(qiáng)凸的并且x*=arg minx∈X f(x),則有

此時(shí),若式(1)中的μ=0,則稱函數(shù)f為凸函數(shù).

2 問題形式化和算法

本文考慮一個(gè)由N個(gè)智能體組成的網(wǎng)絡(luò),表示為圖G(V,E),其中,V={1,···,N}表示智能體的集合,E?V×V表示邊的集合.假設(shè)圖是固定無向圖,符號(hào) (i,j)∈E表示對(duì)于所有的i,j ∈V,智能體j可以直接向智能體i發(fā)送信息.若兩個(gè)智能體可以直接交換信息,則它們是鄰居.Nj表示包括智能體j本身的j的鄰居集合.此外,使用一個(gè)N-by-N鄰接矩陣A表示通信模式,并假設(shè)A為雙隨機(jī)的,定義為A=[aij],i,j=1,···,N.

本文主要研究分布式在線優(yōu)化問題,即每個(gè)智能體的局部代價(jià)函數(shù)隨時(shí)間變化.在每輪時(shí)隙t=1,···,T中,智能體i∈{1,···,N}必須從凸緊集X ?Rd中選擇一個(gè)點(diǎn)xi(t).此時(shí)環(huán)境生成一個(gè)代價(jià)函數(shù):R 作為回報(bào),并且智能體i產(chǎn)生了代價(jià)(xi(t)).這樣,就轉(zhuǎn)化為在一個(gè)時(shí)間范圍T內(nèi)協(xié)作優(yōu)化全局代價(jià)函數(shù)

悔函數(shù)是衡量在線算法性能的重要指標(biāo),定義為[21]

這樣,研究目標(biāo)轉(zhuǎn)化為設(shè)計(jì)一個(gè)能夠解決問題(6)的分布式在線算法,可以在T時(shí)間達(dá)到次線性悔界,即 l im supT→∞R(T)/T=0.

本文借鑒集中式Frank-Wolfe 在線學(xué)習(xí)算法[28],提出了分布式無投影在線學(xué)習(xí)算法.在該算法中,每一個(gè)智能體i∈{1,···,N}線性地組合它自己的估計(jì)值和它從鄰居接收的估計(jì)值,然后計(jì)算一個(gè)能夠替代局部梯度的聚合梯度.最后,每個(gè)智能體i執(zhí)行一個(gè)Frank-Wolfe 步驟更新它的估計(jì)值.在該算法中,每個(gè)智能體只知道自己的局部信息,并只采取局部計(jì)算和局部通信.具體算法描述如算法1 所示.相關(guān)的更新過程見式(8)～(12).

算法1.基于條件梯度的加速分布式在線學(xué)習(xí)算法

算法 1 中,一致性步驟為

聚合步驟為

Frank-Wolfe 步驟為

其中,γ(t)∈(0,1) 是學(xué)習(xí)速率.

3 假設(shè)和主要結(jié)果

本節(jié)首先給出一些算法的假設(shè),然后描述本文的主要結(jié)果.假設(shè)鄰接矩陣A=[aij]∈RN×N滿足以下假設(shè).

假設(shè)1.圖G是強(qiáng)連通圖,對(duì)于任意的i,j ∈{1,···,N},有aii＞0 ;如果 (i,j)∈E,則aij＞0,否則aij=0 .并假設(shè)矩陣A是雙隨機(jī)矩陣,即對(duì)于所有的i,j ∈V,有

假設(shè)1 是為了保證智能體i的信息能直接或間接傳輸至其他智能體.該假設(shè)在分布式優(yōu)化領(lǐng)域中是一個(gè)標(biāo)準(zhǔn)假設(shè)[21,32,36].需要注意ρ(A-(1/N)11T)＜1,其中ρ(·) 是矩陣的譜半徑.因此,?λ ∈(0,1),對(duì)于任意x∈RN,有

同時(shí),從式(14)可以得出

為了分析算法1 的收斂性能,本文分別給出假設(shè)2 和假設(shè)3[28,32].

假設(shè) 2.約束集X是凸緊集,最優(yōu)集X*是非空集.x*∈X*是函數(shù)f的最小值,其中x*是X的內(nèi)部點(diǎn),即η=infx∈?X‖x-x*‖2＞0,其中?X表示約束集X的邊界集.

假設(shè)2 確?？梢杂行У厍蠼庖粋€(gè)線性函數(shù)的最小值.

假設(shè) 3.對(duì)于所有的i∈{1,···,N}和t ∈{1,···,T},局部代價(jià)函數(shù)是β-光滑和L-Lipschitz 的.

在Frank-Wolfe 算法中,假設(shè)3 是一個(gè)標(biāo)準(zhǔn)假設(shè)[28,30,32-34],便于理論分析算法的性能.因此,本文也采用該假設(shè).

定理 1.基于假設(shè)1～3,令步長(zhǎng)γ(t)=2/(t+2),對(duì)于任意的智能體i∈{1,···,N}和t ∈{1,···,T},假設(shè)每個(gè)代價(jià)函數(shù)都是一個(gè)帶正常數(shù)μ的μ-強(qiáng)凸函數(shù).則?t0∈Z+,對(duì)于所有的t≥t*,其中t*定義為

則有

定理1 的證明詳見第4 節(jié).由定理1 可知,Ft((t)) 以速度 O (1/(t+1)) 收斂到Ft(x*(t)),而且收斂速度受網(wǎng)絡(luò)智能體個(gè)數(shù)以及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響.由定理1 可以得到算法1 任意時(shí)刻的界,同時(shí)得到算法1 的悔界如下.

定理 2.基于假設(shè)1 和假設(shè)2,假設(shè)對(duì)于所有的i ∈{1,···,N}和t ∈{1,···,T},每個(gè)代價(jià)函數(shù)是L-Lipchitz 和凸的,并且可能是非光滑的.則對(duì)于任意x*∈X,可以得到

定理2 的證明詳見第4 節(jié).根據(jù)定理2,可以得到強(qiáng)凸條件下的平方根悔界,即算法1 可實(shí)現(xiàn)悔界,其中T是一個(gè)時(shí)間范圍.同時(shí),可以看到悔界由約束集X的直徑D和局部代價(jià)函數(shù)梯度的上界L決定.此外,悔界也受通信網(wǎng)絡(luò)連通性的影響.與文獻(xiàn)[33]和文獻(xiàn)[34]相比,本文使用了梯度追蹤技術(shù)[13]以提高算法的收斂速度.在文獻(xiàn)[33] 和文獻(xiàn)[34]中,它們的悔界都為 O (T3/4),而本文所提算法的悔界為,明顯優(yōu)于以上兩個(gè)工作.具體比較見表1.

表1 不同算法的比較Table 1 Comparison of different algorithms

當(dāng)代價(jià)函數(shù)可能是非凸時(shí),為了分析算法1 的收斂性,引入對(duì)偶間隙的定義為

定理 3.基于假設(shè)1～3,令步長(zhǎng)γ(t)=1/tκ,其中κ∈(0,1).假設(shè)每個(gè)代價(jià)函數(shù)是非凸的,并且時(shí)間范圍T是均等的.則?t0∈Z+,對(duì)于所有的t≥t0和T≥13,當(dāng)κ∈[1/2,1) 時(shí),可以得到

當(dāng)T≥6 且κ∈(0,1/2) 時(shí),可以得到

定理3 的證明詳見第4 節(jié).根據(jù)定理3 可以得出,如果κ∈[1/2,1),算法1 可以在每輪t ∈[T/2+1,T] 得到收斂速率 O (1/T1-κ);如果當(dāng)κ∈(0,1/2),算法1 可以得到收斂速率 O (1/Tκ).此外,當(dāng)設(shè)置κ=1/2 時(shí),算法可以得到最快的收斂速率可以看出,收斂速率受梯度上界L和約束集直徑D的影響.

4 性能分析

本節(jié)分析當(dāng)代價(jià)函數(shù)為凸函數(shù)或潛在非凸函數(shù)時(shí)算法1 的性能,并給出主要結(jié)果的詳細(xì)證明.為了分析算法1 的性能,引入下面3 個(gè)輔助向量,并給出幾個(gè)引理.

引理 1.對(duì)于所有的t=1,···,T,有以下關(guān)系:

引理1 的證明見附錄A.從引理1 可以看出,更新關(guān)系由平均序列(t) 和(t) 決定.下面給出‖zi(t)-(t)‖2的有界性.

引理 2.基于假設(shè)1,對(duì)于某些κ∈(0,1] 使γ(t)=1/tκ,則對(duì)于所有的i=1,···,N和t≥t0,有

引理2 的證明見附錄B.從引理2 可以看出,當(dāng)t趨于無窮大,zi(t) 和(t) 的均方差趨近于零.對(duì)于所有的i∈{1,···,N},下面給出的有界性.

引理 3.基于假設(shè)1,存在κ∈(0,1) 使得γ(t)=1/tκ,則對(duì)于所有的i=1,···,N和t≥t0,有

引理3 的證明見附錄C.從引理3 可以得出,當(dāng)t趨于無窮大時(shí),(t) 和gt(t) 的均方誤差趨近于零.下面利用引理1～3 證明定理 1.

定理 1 證明.為了描述方便,首先定義輔助變量,并將常數(shù)C定義為

其中,θ＞1,C′=2βD2+4DβC1+4DC2.顯然,當(dāng)t=t*時(shí),定理1 成立.然后,假設(shè)對(duì)于某些t≥t*,Δ(t)≤C/(t+1) 成立,其中t*的定義見式(16).從假設(shè)2 可知函數(shù)Ft是β-光滑的,因此根據(jù)引理1中的b),可以得出

其中,第1 個(gè)不等式可由Ft是β-光滑函數(shù)得出,第2 個(gè)不等式依據(jù)引理1 的b)得出,第3 個(gè)不等式根據(jù)X的有界性得到.此外,對(duì)于所有i=1,···,N和v∈X,可以得出

其中,第1 個(gè)不等式可依據(jù)三角形不等式獲得,第2 個(gè)不等式由范數(shù)的凸性和引理3 得出,第3 個(gè)不等式利用函數(shù)的β-光滑性得到,第4 個(gè)不等式根據(jù)引理2 得出.將式(29)和式(30)代入式(28),則對(duì)任意v∈X,有

同時(shí),還可以得到

其中,第1 個(gè)不等式依據(jù)x*(t)=arg minx∈X Ft(x)獲得,最后一個(gè)不等式依據(jù)式(3 1) 和(t)∈arg minv∈X〈v,?Ft((t))〉 得到.此外,根據(jù)Δ(t)=Ft((t))-Ft(x*(t)),可以得出

其中,最后一個(gè)不等式根據(jù)式(32)得出.

另外,假設(shè)Ft是μ-強(qiáng)凸的且x*(t)∈int(X),其中,i nt(X) 表示X的內(nèi)點(diǎn)集.則對(duì)于某些ξ ∈[0,1),x*(t) 為

其中,w(t)∈?X.由于Ft是μ-強(qiáng)凸的,可以得出

其中,第1 個(gè)不等式依據(jù)下式得出

最后一個(gè)不等式根據(jù)η的定義得出.根據(jù)式(35)和式(36),可以得到

為了獲得 Δ (t+1) 的上界,需要得出ft+1((t+1))-ft+1(x*(t+1)) 的上界.由于對(duì)于所有的i ∈{1,···,N}和t∈{1,···,T},每個(gè)代價(jià)函數(shù)都是μ-強(qiáng)凸的,那么根據(jù)Ft的定義,函數(shù)Ft也是μ-強(qiáng)凸的.類似地,假設(shè)3 表明Ft是β-光滑和L-Lipschitz的.由于x*(t)∈arg minx∈X Ft(x),則根據(jù)Ft的強(qiáng)凸性,可以得出

其中,最后一個(gè)不等式根據(jù)歸納假設(shè)得出.這樣,依據(jù)式(39),還可得出

根據(jù)Ft的定義,有

其中,第1 個(gè)不等式由Ft(x*(t))≤Ft(x*(t+1))得出,第2 個(gè)不等式依據(jù)Ft是L-Lipschitz 的獲得,最后一個(gè)不等式根據(jù)X的有界性得到.依據(jù)式(41),得出

其中,最后一個(gè)不等式根據(jù)C≥LD得到.由于‖(t)-x*(t+1)‖2≤D,可以得出

其中,C≥max{324L2/μ,9LD}.此外,還可以得到

其中,最后一個(gè)不等式根據(jù)不等式2/(t+2)≤對(duì)所有的t≥2 都成立得出.因此,根據(jù)式(43)和式(44),得出

其中,最后一個(gè)不等式根據(jù)三角不等式得到.此外,由于ft+1是L-Lipschitz 的,可以得出

將式(38)和式(46)代入式(33),可以得到

其中,最后一個(gè)不等式依據(jù)n≥1 時(shí)成立的不等式得出.根據(jù)C的定義,可得

因此,得出

其中,第2 個(gè)不等式依據(jù)不等式1/(t+1)-1/(t+2)≤1/(t+1)2得出,最后一個(gè)不等式根據(jù)C的定義得到.由于函數(shù)是一個(gè)單調(diào)遞減函數(shù),因此t*定義可由式(16)給出.

由于若θ＞1,則t*值存在.因此,如果t＞t*,則式(50)的右側(cè)是非正的,即

則得到算法1 任意時(shí)刻的界.

定理1 給出了算法1 任意時(shí)刻的界.利用定理1,下面給出定理2 的證明.

定理2 證明.引入一個(gè)輔助函數(shù):

因此,對(duì)任何x*∈X,可得

根據(jù)式(54)和式(56),可得

因此,對(duì)于所有的t≥t*,可以得出

其中,不等式根據(jù)式(55)和以下不等式得出

因此,根據(jù)式(59),可以得到

其中,使用了不等式

依據(jù)ft是凸函數(shù),可以得出

根據(jù)式(60)和式(61),可以得到

最后,本文分析非凸函數(shù)時(shí)算法1 的收斂性能,即分析對(duì)偶間隙的上界,具體結(jié)果如定理3 所述.下面給出定理3 的證明.

定理3 證明.根據(jù)ψ(t) 的定義,即式(19),利用γ(t)=1/tκ式(33)和,可以得到

其中,不等式根據(jù)引理2 和引理3 得出.因此,根據(jù)式(63),可得

另外,根據(jù) Δ (t) 的定義,可得

結(jié)合式(64)和式(65),可以得出

根據(jù)Ft的定義,還可以得到

這樣,根據(jù)式(67),可以得出

其中,第1 個(gè)不等式根據(jù)Ft和ft是L-Lipschitz 得出,第2 個(gè)不等式由D的定義得到,第3 個(gè)和第4 個(gè)不等式依據(jù)獲得.

從t=T/2+1 到t=T對(duì)式(66)求和,可得

由于γ(t)=t-κ,則當(dāng)κ∈[1/2,1),可以得到

由ψ(t)≥0 和γ(t)≥0,還可以得到

因此,對(duì)于所有的T≥6,可得

將式(72)代入式(71),則對(duì)所有的T≥6,有

利用式(74),可得

將式(75) 代入式(69),并除以(1-κ)-1(1-(2/3)1-κ)T1-κ,可得

5 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)考慮一個(gè)數(shù)據(jù)平均分布的多智能體網(wǎng)絡(luò),每個(gè)節(jié)點(diǎn)通過局部通信和局部計(jì)算,與鄰居節(jié)點(diǎn)協(xié)作完成網(wǎng)絡(luò)中的全局任務(wù),使用算法1 解決網(wǎng)絡(luò)系統(tǒng)的多分類問題.

在多分類問題中,每個(gè)局部代價(jià)函數(shù)為

本實(shí)驗(yàn)在aloi 和news20 數(shù)據(jù)集上驗(yàn)證了算法1 的性能.實(shí)驗(yàn)1 考察節(jié)點(diǎn)數(shù)對(duì)算法1 的影響,當(dāng)節(jié)點(diǎn)分別為4、64、128 和256 時(shí)算法1 的性能如圖1所示.從圖1 可以看出,悔界隨著節(jié)點(diǎn)數(shù)量的增加而增加,且在不同節(jié)點(diǎn)數(shù)時(shí)算法1 都是收斂的.實(shí)驗(yàn)2 采用64 個(gè)節(jié)點(diǎn)比較算法1 與D-OCG[33]算法的性能,結(jié)果如圖2 所示.從圖2 可以看出,算法1均比D-OCG 算法具有更快的收斂速率.實(shí)驗(yàn)3 考察不同網(wǎng)絡(luò)拓?fù)鋵?duì)算法1 性能的影響,采用64 個(gè)節(jié)點(diǎn)組成完全圖、隨機(jī)圖和循環(huán)圖三種網(wǎng)絡(luò)拓?fù)?算法1 性能如圖3 所示.從圖3 可以看出,采用完全圖拓?fù)鋾r(shí)算法的收斂速率略快于采用隨機(jī)圖[37]和循環(huán)圖拓?fù)鋾r(shí)算法的收斂速率.

圖1 在news20 和aloi 數(shù)據(jù)集上不同節(jié)點(diǎn)數(shù)下本文算法的性能Fig.1 Performance of the proposed algorithm at different nodes on news20 and aloi datasets

圖2 在news20 和aloi 數(shù)據(jù)集上64 節(jié)點(diǎn)下本文算法和D-OCG 算法的性能比較Fig.2 The performance comparison between the proposed algorithm and the D-OCG algorithm at 64 nodes on news20 and aloi datasets

圖3 本文算法在具有固定64 個(gè)節(jié)點(diǎn)和不同拓?fù)浣Y(jié)構(gòu)的news20 和aloi 數(shù)據(jù)集上的性能Fig.3 Performance of the proposed algorithm on news20 and aloi datasets with fixed 64 nodes and different topologies

6 結(jié)束語

本文研究了多智能體網(wǎng)絡(luò)系統(tǒng)中的分布式在線約束優(yōu)化問題,其中全局代價(jià)函數(shù)是局部代價(jià)函數(shù)之和,且局部代價(jià)函數(shù)是時(shí)變的.為了解決這個(gè)問題,本文提出了一種分布式條件梯度在線學(xué)習(xí)算法,以避免代價(jià)高昂的投影算子.理論分析表明,對(duì)于凸代價(jià)函數(shù),所提算法可以達(dá)到悔界,其中T表示時(shí)間范圍;對(duì)于非凸代價(jià)函數(shù),所提算法以的速率收斂到平穩(wěn)點(diǎn).仿真實(shí)驗(yàn)驗(yàn)證了所提算法的性能和理論分析的結(jié)果.該算法可為多智能體網(wǎng)絡(luò)系統(tǒng)的資源分配、數(shù)據(jù)管理、調(diào)度控制等問題提供參考.

附錄 A 引理1 的證明

證明.1) 關(guān)系 a) 的證明.對(duì)式(9)從i=1,···,N求和,其中t≥1,除以N(t+1) 得到

由于鄰接矩陣A是一個(gè)雙隨機(jī)矩陣,即1TA=1T.由式(A1)可得

其中,最后一個(gè)等式根據(jù)矩陣A由雙隨機(jī)矩陣得出,即 1TA=1T,且

附錄 B 引理2 的證明

證明.根據(jù)范數(shù)的性質(zhì),有

為了證明引理2,只需要證明不等式

下面對(duì)t使用歸納法證明式(B2).可以看出,從t=1 到t=t0,式(B2)成立.假設(shè)對(duì)于某些t≥t0,式(B2)也成立.由于當(dāng)κ∈(0,1],有γ(t)=t-κ,則有xi(t+1)=(1-t-κ)zi(t)+t-κvi(t).因此,根據(jù)引理1 的b),可以得到

的上界.為此,首先有

其中,第1 個(gè)不等式依據(jù)柯西-施瓦茲不等式、約束集X的有界性和不等式得到.第2 個(gè)和第3 個(gè)不等式由歸納假設(shè)得到.因此,根據(jù)式(14),對(duì)于所有的t≥t0,有

其中,第2 個(gè)不等式根據(jù)函數(shù)φ(ν)=(ν/(1+ν))κ是關(guān)于ν的單調(diào)遞增函數(shù)得到.結(jié)合式(14)和式(B5),可以得到

因此,式(B2)成立.

附錄 C 引理3 的證明

證明.首先,利用范數(shù)的性質(zhì),有

為了證明式(25),只需證明式(C2)

下面采用歸納法證明式(C2).可以看出,從t=1 到t=t0,式(C2) 成立.假設(shè)對(duì)于某個(gè)t,式(C 2) 成立.引入一個(gè)輔助變量,將其代入式(9),可以得到

其中,不等式依據(jù)式(9)和式(13)得出.根據(jù)gt(t)的定義,可以得到

其中,第1 個(gè)不等式依據(jù)三角不等式得出,最后一個(gè)不等式根據(jù)式(13) 獲得.另外,‖σ(t+1)-[φt+1(t+1)-φt+1(t)]‖2由式(C7)進(jìn)行計(jì)算

其中,最后一個(gè)不等式依據(jù)φt+1(t+1) 的定義得出.將式(C7)代入式(C6),得到

其中,第1 個(gè)不等式根據(jù)式(4)得到,第2 個(gè)不等式可由歐幾里得范數(shù)的凸性和三角不等式推出,第3個(gè)不等式依據(jù)式(12)和三角不等式獲得,第4 個(gè)不等式從引理1 推出.將式(C9)與(C8)合并,可以得到

其中,最后一個(gè)不等式根據(jù)下面不等式得出

其中,λ∈(0,1).此外,還可以得到

其中,第1 個(gè)不等式根據(jù)歐幾里得范數(shù)的凸性推出,第2 個(gè)不等式依據(jù)三角不等式獲得,第3 個(gè)不等式從式(C9)推出,第4 個(gè)不等式依據(jù)N是一個(gè)正整數(shù)得到.將式(C10)和式(C11)代入式(C4),并使,δ是一個(gè)正常數(shù).則對(duì)于所有的i∈{1,···,N},可以得到

其中,第1 個(gè)不等式依據(jù)三角不等式、柯西-施瓦茲不等式和不等式推出,第2 個(gè)不等式根據(jù)歸納假設(shè)獲得,最后一個(gè)不等式從C2的定義得到.依據(jù)式(14),對(duì)于所有的t≥t0,可以得出

由此,對(duì)式(C12)兩邊取平方根完成歸納.然后,將式(C1) 和式(C2) 結(jié)合,即完成引理3 的證明.