有向切換網(wǎng)絡(luò)的PUSH—SUM分布式對(duì)偶平均凸優(yōu)化

郭向梅+++張曉倩+++舒良萍+++趙晶晶

摘 要：最近已經(jīng)有大量的基于分布式一致性?xún)?yōu)化應(yīng)用程序的研究。文章在此基礎(chǔ)上描述和證明了一種有向切換網(wǎng)絡(luò)新算法的收斂性我們稱(chēng)此算法為push-sum分布式對(duì)偶平均算法，它結(jié)合最近的一個(gè)優(yōu)化對(duì)偶平均算法[1]構(gòu)成了有push-sum顯著優(yōu)勢(shì)的一致性協(xié)議算法[2]。

關(guān)鍵詞：push-sum；分布式；一致性；收斂

1 引言

文章我們描述和證明一個(gè)為解決凸優(yōu)化可分離函數(shù)組件問(wèn)題的新算法即分布在節(jié)點(diǎn)的一個(gè)網(wǎng)絡(luò)算法及其收斂性。我們稱(chēng)此算法為push-sum分布式對(duì)偶平均（PSDDA）算法。我們的算法是建立在最近發(fā)表的分布式對(duì)偶平均（DDA）算法[1]的基礎(chǔ)上，使用了改進(jìn)的推和共識(shí)協(xié)議[2]。

為了使論文具有獨(dú)立性，我們回顧一些分布式對(duì)偶平均算法必要的背景知識(shí)。假設(shè)我們有一個(gè)強(qiáng)連通網(wǎng)絡(luò)G=（V，E）且|V|=n個(gè)計(jì)算節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的凸函數(shù)hi（x）：Rd→R.我們目標(biāo)是解決下式最小化問(wèn)題

（1）

其中X是一個(gè)凸集。假設(shè)每個(gè)hi（x）都是凸函數(shù)且滿(mǎn)足L-Lipschitz條件的范數(shù)||.||；ie， 。作為一個(gè)推論，對(duì)于任意？坌x∈x和任意的次梯度gi∈？墜hi（x）我們有||gi||*？燮L這里||v||*=sup||u||=1是雙重標(biāo)準(zhǔn)。該算法使用了一個(gè)1--嚴(yán)格相鄰?fù)购瘮?shù)？鬃：Rd→R使的？鬃（x）？叟0且？鬃（0）=0。也選擇非遞增數(shù)列的正的步長(zhǎng)大小為{a（t）}■■和一個(gè)雙隨機(jī)矩陣P結(jié)構(gòu)滿(mǎn)足G在某種意義上，pij>0當(dāng)且僅當(dāng)i=j或者（i，j）∈E分布式對(duì)偶平均算法重復(fù).文獻(xiàn)中的引理4：假設(shè)網(wǎng)絡(luò)序列G（t）是一致性強(qiáng)連通的，則它們滿(mǎn)足以下

幾何收斂速度為

所有i，j=1，...，n且C，？姿∈（0，1）.（2）

2 PUSH-SUM分布式對(duì)偶平均

結(jié)合push-sum平均協(xié)議，我們制定的push-sum分布式雙平均（PSDDA）算法如下：

（3）

（4）

（5）

其中g(shù)i（t）是hi（t）在點(diǎn)x=xi（t）處的梯度，a（t）是表示步長(zhǎng)大小的數(shù)列是非遞增的。觀(guān)察檢索正確的累積梯度的DDA的標(biāo)準(zhǔn)，我們需要分析z變量在每個(gè)節(jié)點(diǎn)適當(dāng)?shù)臋?quán)重。

定理1：PSDDA算法（14）用到了一個(gè)嚴(yán)格凸函數(shù)？追（x）的范數(shù)||.||和二階范數(shù)||.||*使得？追（x*）？燮R2，選擇步長(zhǎng)大小如下

（6）

收斂的每個(gè)節(jié)點(diǎn)j∈V且最優(yōu)值x*∈x在（1）里

（7）

3 定理1的證明

我們首先計(jì)算一個(gè)表達(dá)式的平均 。從（14）迭代遞歸我們得到

（8）

我們用到了一個(gè)事實(shí)即P0=I和P（t：r+1）是列隨機(jī)的。序列

是Z（t）的投影：

（9）

現(xiàn)在我們定義平均步長(zhǎng) 和 .接下來(lái)。使用標(biāo)準(zhǔn)的凸性參數(shù)和（1）中的引理4，對(duì)于 （用于證明參考附錄）

（10）

（11）

（12）

（10）和（14）是同樣有界的。使用到部分結(jié)果到目前為止我們已經(jīng)證明

（13）

完成證明我們因此需要限制每個(gè)網(wǎng)絡(luò)的誤差項(xiàng) 對(duì)

于任意的k。從（13），類(lèi)似于（20）我們獲得一個(gè)表達(dá)式為Zk（t）作為一個(gè)

梯度函數(shù)和從（12），我們看到 ?，F(xiàn)在我們繼續(xù)證明：

（14）

（15）

（16）

下面我們將證明這個(gè)絕對(duì)值是有界的。

（17）

這里？姿∈（0，1），c是有上確界的。因此我們總結(jié)到如下

（18）

（19）

我們使用了幾何總和是有限的公式。現(xiàn)在我們可以回到（13）來(lái)得到

假設(shè)

（20）

最后，如果我們選擇 和減少為A，注意到

我們完成定理1的最后結(jié)果。

4 結(jié)束語(yǔ)

在文章中，我們描述和分析PSDDA算法一個(gè)基于凸優(yōu)化的一致性分布式新算法。作為它的前身[1]不需要添加隨機(jī)共識(shí)協(xié)議，它適用于任何列隨機(jī)協(xié)議。P滿(mǎn)足網(wǎng)絡(luò)結(jié)構(gòu)G且在不需要要知道平穩(wěn)分布的P或在每一個(gè)節(jié)點(diǎn)大小的網(wǎng)絡(luò)無(wú)偏性的收斂到最優(yōu)。

參考文獻(xiàn)

[1]A. G. Dimakis， S. Kar， J. M. Moura， M. G. Rabbat， and A. Scaglione，"Gossip algorithms for distributed signal processing，"[J] Proceedings of the IEEE，2010，98（）57）：1847-1864

[2]B. Gharesifard and J. Cortes， "When does a digraph admit a doubly stochastic adjacency matrix？" in Proceedings of the American Control Conference， Baltimore， Marylan，2010：2440-2445.

[3]S. S. Ram， A. Nedic， and V. V. Veeravalli， "Distributed stochastic subgradient projection algorithms for convex optimization，" Journal of Optimization Theory and Applications， vol. 147， no. 3， pp. 516-545， 2011.

[4] K. I. Tsianos and M. G. Rabbat， "Distributed dual averaging for convex optimization under communication delays，" in American Control Conference （ACC）， 2012.

[5] A. Nedi？c， A. Olshevsky，" Distributed optimization over time-varying directed graphs[J]. arXiv preprint arXiv：1303.2289， 2013.，"2013，1303-2289

摘 要：最近已經(jīng)有大量的基于分布式一致性?xún)?yōu)化應(yīng)用程序的研究。文章在此基礎(chǔ)上描述和證明了一種有向切換網(wǎng)絡(luò)新算法的收斂性我們稱(chēng)此算法為push-sum分布式對(duì)偶平均算法，它結(jié)合最近的一個(gè)優(yōu)化對(duì)偶平均算法[1]構(gòu)成了有push-sum顯著優(yōu)勢(shì)的一致性協(xié)議算法[2]。

關(guān)鍵詞：push-sum；分布式；一致性；收斂

1 引言

文章我們描述和證明一個(gè)為解決凸優(yōu)化可分離函數(shù)組件問(wèn)題的新算法即分布在節(jié)點(diǎn)的一個(gè)網(wǎng)絡(luò)算法及其收斂性。我們稱(chēng)此算法為push-sum分布式對(duì)偶平均（PSDDA）算法。我們的算法是建立在最近發(fā)表的分布式對(duì)偶平均（DDA）算法[1]的基礎(chǔ)上，使用了改進(jìn)的推和共識(shí)協(xié)議[2]。

為了使論文具有獨(dú)立性，我們回顧一些分布式對(duì)偶平均算法必要的背景知識(shí)。假設(shè)我們有一個(gè)強(qiáng)連通網(wǎng)絡(luò)G=（V，E）且|V|=n個(gè)計(jì)算節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的凸函數(shù)hi（x）：Rd→R.我們目標(biāo)是解決下式最小化問(wèn)題

（1）

其中X是一個(gè)凸集。假設(shè)每個(gè)hi（x）都是凸函數(shù)且滿(mǎn)足L-Lipschitz條件的范數(shù)||.||；ie， 。作為一個(gè)推論，對(duì)于任意？坌x∈x和任意的次梯度gi∈？墜hi（x）我們有||gi||*？燮L這里||v||*=sup||u||=1是雙重標(biāo)準(zhǔn)。該算法使用了一個(gè)1--嚴(yán)格相鄰?fù)购瘮?shù)？鬃：Rd→R使的？鬃（x）？叟0且？鬃（0）=0。也選擇非遞增數(shù)列的正的步長(zhǎng)大小為{a（t）}■■和一個(gè)雙隨機(jī)矩陣P結(jié)構(gòu)滿(mǎn)足G在某種意義上，pij>0當(dāng)且僅當(dāng)i=j或者（i，j）∈E分布式對(duì)偶平均算法重復(fù).文獻(xiàn)中的引理4：假設(shè)網(wǎng)絡(luò)序列G（t）是一致性強(qiáng)連通的，則它們滿(mǎn)足以下

幾何收斂速度為

所有i，j=1，...，n且C，？姿∈（0，1）.（2）

2 PUSH-SUM分布式對(duì)偶平均

結(jié)合push-sum平均協(xié)議，我們制定的push-sum分布式雙平均（PSDDA）算法如下：

（3）

（4）

（5）

其中g(shù)i（t）是hi（t）在點(diǎn)x=xi（t）處的梯度，a（t）是表示步長(zhǎng)大小的數(shù)列是非遞增的。觀(guān)察檢索正確的累積梯度的DDA的標(biāo)準(zhǔn)，我們需要分析z變量在每個(gè)節(jié)點(diǎn)適當(dāng)?shù)臋?quán)重。

定理1：PSDDA算法（14）用到了一個(gè)嚴(yán)格凸函數(shù)？追（x）的范數(shù)||.||和二階范數(shù)||.||*使得？追（x*）？燮R2，選擇步長(zhǎng)大小如下

（6）

收斂的每個(gè)節(jié)點(diǎn)j∈V且最優(yōu)值x*∈x在（1）里

（7）

3 定理1的證明

我們首先計(jì)算一個(gè)表達(dá)式的平均 。從（14）迭代遞歸我們得到

（8）

我們用到了一個(gè)事實(shí)即P0=I和P（t：r+1）是列隨機(jī)的。序列

是Z（t）的投影：

（9）

現(xiàn)在我們定義平均步長(zhǎng) 和 .接下來(lái)。使用標(biāo)準(zhǔn)的凸性參數(shù)和（1）中的引理4，對(duì)于 （用于證明參考附錄）

（10）

（11）

（12）

（10）和（14）是同樣有界的。使用到部分結(jié)果到目前為止我們已經(jīng)證明

（13）

完成證明我們因此需要限制每個(gè)網(wǎng)絡(luò)的誤差項(xiàng) 對(duì)

于任意的k。從（13），類(lèi)似于（20）我們獲得一個(gè)表達(dá)式為Zk（t）作為一個(gè)

梯度函數(shù)和從（12），我們看到 ?，F(xiàn)在我們繼續(xù)證明：

（14）

（15）

（16）

下面我們將證明這個(gè)絕對(duì)值是有界的。

（17）

這里？姿∈（0，1），c是有上確界的。因此我們總結(jié)到如下

（18）

（19）

我們使用了幾何總和是有限的公式?，F(xiàn)在我們可以回到（13）來(lái)得到

假設(shè)

（20）

最后，如果我們選擇 和減少為A，注意到

我們完成定理1的最后結(jié)果。

4 結(jié)束語(yǔ)

在文章中，我們描述和分析PSDDA算法一個(gè)基于凸優(yōu)化的一致性分布式新算法。作為它的前身[1]不需要添加隨機(jī)共識(shí)協(xié)議，它適用于任何列隨機(jī)協(xié)議。P滿(mǎn)足網(wǎng)絡(luò)結(jié)構(gòu)G且在不需要要知道平穩(wěn)分布的P或在每一個(gè)節(jié)點(diǎn)大小的網(wǎng)絡(luò)無(wú)偏性的收斂到最優(yōu)。

參考文獻(xiàn)

[1]A. G. Dimakis， S. Kar， J. M. Moura， M. G. Rabbat， and A. Scaglione，"Gossip algorithms for distributed signal processing，"[J] Proceedings of the IEEE，2010，98（）57）：1847-1864

[2]B. Gharesifard and J. Cortes， "When does a digraph admit a doubly stochastic adjacency matrix？" in Proceedings of the American Control Conference， Baltimore， Marylan，2010：2440-2445.

[3]S. S. Ram， A. Nedic， and V. V. Veeravalli， "Distributed stochastic subgradient projection algorithms for convex optimization，" Journal of Optimization Theory and Applications， vol. 147， no. 3， pp. 516-545， 2011.

[4] K. I. Tsianos and M. G. Rabbat， "Distributed dual averaging for convex optimization under communication delays，" in American Control Conference （ACC）， 2012.

[5] A. Nedi？c， A. Olshevsky，" Distributed optimization over time-varying directed graphs[J]. arXiv preprint arXiv：1303.2289， 2013.，"2013，1303-2289

摘 要：最近已經(jīng)有大量的基于分布式一致性?xún)?yōu)化應(yīng)用程序的研究。文章在此基礎(chǔ)上描述和證明了一種有向切換網(wǎng)絡(luò)新算法的收斂性我們稱(chēng)此算法為push-sum分布式對(duì)偶平均算法，它結(jié)合最近的一個(gè)優(yōu)化對(duì)偶平均算法[1]構(gòu)成了有push-sum顯著優(yōu)勢(shì)的一致性協(xié)議算法[2]。

關(guān)鍵詞：push-sum；分布式；一致性；收斂

1 引言

文章我們描述和證明一個(gè)為解決凸優(yōu)化可分離函數(shù)組件問(wèn)題的新算法即分布在節(jié)點(diǎn)的一個(gè)網(wǎng)絡(luò)算法及其收斂性。我們稱(chēng)此算法為push-sum分布式對(duì)偶平均（PSDDA）算法。我們的算法是建立在最近發(fā)表的分布式對(duì)偶平均（DDA）算法[1]的基礎(chǔ)上，使用了改進(jìn)的推和共識(shí)協(xié)議[2]。

為了使論文具有獨(dú)立性，我們回顧一些分布式對(duì)偶平均算法必要的背景知識(shí)。假設(shè)我們有一個(gè)強(qiáng)連通網(wǎng)絡(luò)G=（V，E）且|V|=n個(gè)計(jì)算節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的凸函數(shù)hi（x）：Rd→R.我們目標(biāo)是解決下式最小化問(wèn)題

（1）

其中X是一個(gè)凸集。假設(shè)每個(gè)hi（x）都是凸函數(shù)且滿(mǎn)足L-Lipschitz條件的范數(shù)||.||；ie， 。作為一個(gè)推論，對(duì)于任意？坌x∈x和任意的次梯度gi∈？墜hi（x）我們有||gi||*？燮L這里||v||*=sup||u||=1是雙重標(biāo)準(zhǔn)。該算法使用了一個(gè)1--嚴(yán)格相鄰?fù)购瘮?shù)？鬃：Rd→R使的？鬃（x）？叟0且？鬃（0）=0。也選擇非遞增數(shù)列的正的步長(zhǎng)大小為{a（t）}■■和一個(gè)雙隨機(jī)矩陣P結(jié)構(gòu)滿(mǎn)足G在某種意義上，pij>0當(dāng)且僅當(dāng)i=j或者（i，j）∈E分布式對(duì)偶平均算法重復(fù).文獻(xiàn)中的引理4：假設(shè)網(wǎng)絡(luò)序列G（t）是一致性強(qiáng)連通的，則它們滿(mǎn)足以下

幾何收斂速度為

所有i，j=1，...，n且C，？姿∈（0，1）.（2）

2 PUSH-SUM分布式對(duì)偶平均

結(jié)合push-sum平均協(xié)議，我們制定的push-sum分布式雙平均（PSDDA）算法如下：

（3）

（4）

（5）

其中g(shù)i（t）是hi（t）在點(diǎn)x=xi（t）處的梯度，a（t）是表示步長(zhǎng)大小的數(shù)列是非遞增的。觀(guān)察檢索正確的累積梯度的DDA的標(biāo)準(zhǔn)，我們需要分析z變量在每個(gè)節(jié)點(diǎn)適當(dāng)?shù)臋?quán)重。

定理1：PSDDA算法（14）用到了一個(gè)嚴(yán)格凸函數(shù)？追（x）的范數(shù)||.||和二階范數(shù)||.||*使得？追（x*）？燮R2，選擇步長(zhǎng)大小如下

（6）

收斂的每個(gè)節(jié)點(diǎn)j∈V且最優(yōu)值x*∈x在（1）里

（7）

3 定理1的證明

我們首先計(jì)算一個(gè)表達(dá)式的平均 。從（14）迭代遞歸我們得到

（8）

我們用到了一個(gè)事實(shí)即P0=I和P（t：r+1）是列隨機(jī)的。序列

是Z（t）的投影：

（9）

現(xiàn)在我們定義平均步長(zhǎng) 和 .接下來(lái)。使用標(biāo)準(zhǔn)的凸性參數(shù)和（1）中的引理4，對(duì)于 （用于證明參考附錄）

（10）

（11）

（12）

（10）和（14）是同樣有界的。使用到部分結(jié)果到目前為止我們已經(jīng)證明

（13）

完成證明我們因此需要限制每個(gè)網(wǎng)絡(luò)的誤差項(xiàng) 對(duì)

于任意的k。從（13），類(lèi)似于（20）我們獲得一個(gè)表達(dá)式為Zk（t）作為一個(gè)

梯度函數(shù)和從（12），我們看到 ?，F(xiàn)在我們繼續(xù)證明：

（14）

（15）

（16）

下面我們將證明這個(gè)絕對(duì)值是有界的。

（17）

這里？姿∈（0，1），c是有上確界的。因此我們總結(jié)到如下

（18）

（19）

我們使用了幾何總和是有限的公式?，F(xiàn)在我們可以回到（13）來(lái)得到

假設(shè)

（20）

最后，如果我們選擇 和減少為A，注意到

我們完成定理1的最后結(jié)果。

4 結(jié)束語(yǔ)

在文章中，我們描述和分析PSDDA算法一個(gè)基于凸優(yōu)化的一致性分布式新算法。作為它的前身[1]不需要添加隨機(jī)共識(shí)協(xié)議，它適用于任何列隨機(jī)協(xié)議。P滿(mǎn)足網(wǎng)絡(luò)結(jié)構(gòu)G且在不需要要知道平穩(wěn)分布的P或在每一個(gè)節(jié)點(diǎn)大小的網(wǎng)絡(luò)無(wú)偏性的收斂到最優(yōu)。

參考文獻(xiàn)

[1]A. G. Dimakis， S. Kar， J. M. Moura， M. G. Rabbat， and A. Scaglione，"Gossip algorithms for distributed signal processing，"[J] Proceedings of the IEEE，2010，98（）57）：1847-1864

[2]B. Gharesifard and J. Cortes， "When does a digraph admit a doubly stochastic adjacency matrix？" in Proceedings of the American Control Conference， Baltimore， Marylan，2010：2440-2445.

[3]S. S. Ram， A. Nedic， and V. V. Veeravalli， "Distributed stochastic subgradient projection algorithms for convex optimization，" Journal of Optimization Theory and Applications， vol. 147， no. 3， pp. 516-545， 2011.

[4] K. I. Tsianos and M. G. Rabbat， "Distributed dual averaging for convex optimization under communication delays，" in American Control Conference （ACC）， 2012.

[5] A. Nedi？c， A. Olshevsky，" Distributed optimization over time-varying directed graphs[J]. arXiv preprint arXiv：1303.2289， 2013.，"2013，1303-2289