時(shí)滯多智能體網(wǎng)絡(luò)中的Push-Sum分布式對(duì)偶平均算法研究

周小清

(重慶師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院， 重慶 401331)

在基于局部信息交互的資源配置和傳感器網(wǎng)絡(luò)之間的信息交換中都涉及復(fù)雜多個(gè)體系統(tǒng)。復(fù)雜的多個(gè)體系統(tǒng)中，每個(gè)個(gè)體有一個(gè)目標(biāo)函數(shù)，整個(gè)網(wǎng)絡(luò)系統(tǒng)的目標(biāo)函數(shù)可表示成每個(gè)個(gè)體的目標(biāo)函數(shù)之和。解決這類優(yōu)化問題主要有3類算法，即原始算法[1]、對(duì)偶算法[2]和原始對(duì)偶算法[3]。解決實(shí)際問題時(shí)，個(gè)體的信息交流會(huì)出現(xiàn)滯后的現(xiàn)象。信息從個(gè)體出發(fā)后，需要經(jīng)過相對(duì)較長的時(shí)間才能到達(dá)接受的個(gè)體，就是所消耗的時(shí)間比正常時(shí)間長，這樣的信息延遲被稱為狀態(tài)的延遲[4,5]。此外，還有一種信息延遲現(xiàn)象，被稱為梯度信息延遲[6]，即每個(gè)個(gè)體接收的梯度信息不是當(dāng)前的梯度信息，而是延遲后的梯度信息。網(wǎng)絡(luò)系統(tǒng)的信息交流出現(xiàn)信息延遲現(xiàn)象，會(huì)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)造成一定的影響。本次研究，主要針對(duì)梯度信息延遲現(xiàn)象，討論多智能體網(wǎng)絡(luò)中的分布式凸優(yōu)化問題。

文獻(xiàn)[7]研究有向通訊網(wǎng)絡(luò)中時(shí)間不變的分布式優(yōu)化問題，提出了Push-Sum對(duì)偶平均次梯度算法，對(duì)應(yīng)的通訊矩陣是列隨機(jī)的，但沒有考慮次梯度出現(xiàn)時(shí)延的情況。文獻(xiàn)[8]研究時(shí)變有向網(wǎng)絡(luò)下的分布式優(yōu)化問題，給出了次梯度推進(jìn)算法的收斂性分析，但僅考慮了無約束優(yōu)化的情況。文獻(xiàn)[6]研究時(shí)間不變的無向通訊網(wǎng)絡(luò)的分布式優(yōu)化問題，考慮了次梯度信息會(huì)出現(xiàn)延遲的情況，但沒有涉及Push-Sum協(xié)議，并且要求通訊矩陣是雙隨機(jī)的。對(duì)通訊矩陣的雙隨機(jī)要求，意味著個(gè)體進(jìn)行信息通訊時(shí)的網(wǎng)絡(luò)必須是平衡的。受到這些文獻(xiàn)的啟發(fā)，筆者提出了一種Push-Sum分布式對(duì)偶平均優(yōu)化算法。該算法引入了Push-Sum協(xié)議，對(duì)應(yīng)的通訊矩陣是列隨機(jī)的，而不必是雙隨機(jī)的；在信息傳遞的過程中，每個(gè)個(gè)體接收的是過時(shí)的梯度，而不是當(dāng)前的梯度；盡管有時(shí)延的狀態(tài)，運(yùn)用時(shí)滯的Push-Sum對(duì)偶平均次梯度算法，仍然能使得目標(biāo)函數(shù)漸近地達(dá)到最優(yōu)。同時(shí)，分析了延遲對(duì)收斂速度的影響。

1 問題描述

(1)

式(1)中：X為約束集，X?Rd，為Rd維空間；fi(x)為凸函數(shù)，fi(x)：X→R，并且對(duì)于范數(shù)‖·‖是 Lipschitz連續(xù)，即 |fi(x)-fi(y)|≤L‖x-y‖,?x,y∈X。對(duì)于任何x∈X和任何次梯度gi(x)≤?fi(x)，有 ‖gi‖*≤L，其中‖·‖*為‖·‖對(duì)偶范數(shù)，定義為 ‖v‖*=sup‖u‖=1〈u,v〉。

2 提出的算法

(2)

(3)

(4)

(5)

其中，gi(t-τ)為次梯度，是fi(xi(t-τ))在x=xi(t-τ)的次梯度，τ是表示常數(shù)延遲的正整數(shù)。對(duì)于所有的i，初始化：wi(0)=1，zi(0)=0，gi(0)=0。投影算子定義為：

為了敘述方便，引入以下記號(hào)及相關(guān)定義和假設(shè)。

并且

由矩陣A的列隨機(jī)性，可得：

(6)

定義1[9]：給定一個(gè)緊的凸函數(shù)ψ(·):Rd→R，定義一個(gè)Bregman散度。相應(yīng)的定義為：

Dψ(x,y)=ψ(x)-ψ(y)-〈▽?duì)?y),x-y〉

假設(shè)1[3]：(1)圖序列{G(t)}是B-強(qiáng)連通的；(2)每個(gè)函數(shù)fi是凸的，i>0。

首先，以下引理成立。

引理2[8]：令x+minmize〈z,x〉+Aψ(x)，對(duì)于?x∈X，有：

〈z,x〉+Aψ(x)≥〈z,x+〉+Aψ(x+)+ADψ(x,x+)

引理3[8]：令圖序列{G(t)}是一致強(qiáng)連通的。采用記號(hào)A(t:s)，即A(t:s)A(t)…A(s)，t≥s≥0。則

(a) 存在一個(gè)隨機(jī)向量序列{φ(t)}，即φ(t)∈Rn，且t≥s,A(t:s)-φ(t)1′呈幾何級(jí)數(shù)退化。對(duì)于所有的i和j(i=1，2，3，…，n；j=1，2，3，…，n)，有：

|[A(t:s)]ij-φi(t)|≤Cλt-s

其中，對(duì)?i,j有t≥s≥0，C為常數(shù)，C>0，λ∈(0，1)。

3 主要結(jié)論

首先，針對(duì)個(gè)體之間造成的不平衡的現(xiàn)象，證明了各個(gè)個(gè)體之間有一個(gè)上界；然后，為了簡化證明，將引理5和引理6作為時(shí)滯的Push-Sum對(duì)偶平均次梯度算法的2個(gè)獨(dú)立性質(zhì)，從證明中分離出來；最后，對(duì)時(shí)滯的Push-Sum對(duì)偶平均次梯度算法的收斂性進(jìn)行了分析。

3.1 主要引理

為了得到時(shí)滯的Push-Sum對(duì)偶平均次梯度算法的收斂性，先證明一個(gè)重要引理。

引理4：考慮序列{zi(t)}。假設(shè)圖序列{G(t)}是一致強(qiáng)連通，則對(duì)于所有t，t≥1，有：

其中，δ>0，λ∈(0，1)，滿足δ≥1

【證明】 由式(2)，遞推可得：

=…

(7)

由式(3)，遞推可得：

由zi(0)=0，有：

(8)

(9)

因此，在t≥0時(shí)，結(jié)合式(7)(8)(9)，并且在式中加上一個(gè)φ(t-1)，再減去一個(gè)φ(t-1)，據(jù)引理3，可得：

由范數(shù)滿足三角不等式，則有：

據(jù)引理3的δ的定義，且τ是一個(gè)正整數(shù)，λ∈(0，1)，即有：

引理5[6]：對(duì)于任意的x*，x*∈X，有

引理6[6]：對(duì)于任意的x*，x*∈X，有

【證明】 由引理6，可得

(10)

根據(jù)xi(t)的迭代式和范數(shù)的性質(zhì)，且

則有

[a(t-s-1)-a(t-s)]ψ(x*)

(11)

將式(11)代入式(10)，并利用 (A+B+C+D)2≤4(A2+B2+C2+D2)，可以得出

(12)

結(jié)合引理4的結(jié)果和步長的非負(fù)單調(diào)遞減性，經(jīng)過計(jì)算，將式(12)化簡可得：

3.2 算法的收斂性分析

【證明】 由f(x)的凸性，可得

(13)

首先，估計(jì)式(13)的前2項(xiàng)。因?yàn)間i(t)是fi在xi(t)的次梯度，gi(t)∈?fi[xi(t)]，根據(jù)fi的凸性和Lipschitz連續(xù)性，有

(14)

根據(jù)ei(t)=gi(t)-gi(t-τ-1) 的定義，則有

〈gi(t),xi(t)-x*〉 =〈gi(t-τ-1),xi(t)-x*〉+〈ei(t),xi(t)-x*〉

=〈gi(t-τ-1),h(t)-x*〉+〈gi(t-τ-1),xi(t)-h(t)〉+

〈ei(t),xi(t)-x*〉

〈ei(t),xi(t)-x*〉

(15)

其次，估計(jì)式(13)的最后一項(xiàng)。根據(jù)fi的Lipschitz連續(xù)性，有

(16)

將式(14)(15)(16)代入式(13)，并結(jié)合引理4、引理5、引理6，則有

4 結(jié) 語

研究提出了時(shí)滯的Push-Sum分布式對(duì)偶平均算法。運(yùn)用此算法，各個(gè)節(jié)點(diǎn)的變量最終會(huì)收斂到最優(yōu)點(diǎn)的附近。時(shí)滯的Push-Sum分布式對(duì)偶平均算法，在信息接收過程中接收的是過時(shí)的梯度，而不是當(dāng)前的梯度。通過建立時(shí)滯的梯度信息，證明盡管有時(shí)滯的狀態(tài)，本次提出的算法仍然能使目標(biāo)函數(shù)漸近地達(dá)到最優(yōu)，它保持了網(wǎng)絡(luò)拓?fù)涞男阅軆?yōu)勢(shì)。針對(duì)延遲對(duì)收斂速度的影響問題，通過利用Bregman散度，說明了延遲在收斂中的作用，且速度是O[(τ+1)2由此可知，由延遲引起的優(yōu)化誤差是二階的，當(dāng)延遲固定時(shí)，隨著T的增加，收斂速度逐漸趨于0。