周小清

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

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

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

1 問題描述

(1)

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

2 提出的算法

(2)

(3)

(4)

(5)

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

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

并且

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

(6)

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

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

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

首先，以下引理成立。

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

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

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

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

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

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

3 主要結(jié)論

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

3.1 主要引理

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

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

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

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

=…

(7)

由式(3)，遞推可得：

由zi(0)=0，有：

(8)

(9)

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

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

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

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

引理6[6]：對于任意的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é) 語

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