有向切換網絡的PUSH—SUM分布式對偶平均凸優化

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

摘 要：最近已經有大量的基于分布式一致性優化應用程序的研究。文章在此基礎上描述和證明了一種有向切換網絡新算法的收斂性我們稱此算法為push-sum分布式對偶平均算法，它結合最近的一個優化對偶平均算法[1]構成了有push-sum顯著優勢的一致性協議算法[2]。

關鍵詞：push-sum；分布式；一致性；收斂

1 引言

文章我們描述和證明一個為解決凸優化可分離函數組件問題的新算法即分布在節點的一個網絡算法及其收斂性。我們稱此算法為push-sum分布式對偶平均（PSDDA）算法。我們的算法是建立在最近發表的分布式對偶平均（DDA）算法[1]的基礎上，使用了改進的推和共識協議[2]。

為了使論文具有獨立性，我們回顧一些分布式對偶平均算法必要的背景知識。假設我們有一個強連通網絡G=（V，E）且|V|=n個計算節點。每個節點對應的凸函數hi（x）：Rd→R.我們目標是解決下式最小化問題

（1）

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

幾何收斂速度為

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

2 PUSH-SUM分布式對偶平均

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

（3）

（4）

（5）

其中gi（t）是hi（t）在點x=xi（t）處的梯度，a（t）是表示步長大小的數列是非遞增的。觀察檢索正確的累積梯度的DDA的標準，我們需要分析z變量在每個節點適當的權重。

定理1：PSDDA算法（14）用到了一個嚴格凸函數？追（x）的范數||.||和二階范數||.||*使得？追（x*）？燮R2，選擇步長大小如下

（6）

收斂的每個節點j∈V且最優值x*∈x在（1）里

（7）

3 定理1的證明

我們首先計算一個表達式的平均 。從（14）迭代遞歸我們得到

（8）

我們用到了一個事實即P0=I和P（t：r+1）是列隨機的。序列

是Z（t）的投影：

（9）

現在我們定義平均步長 和 .接下來。使用標準的凸性參數和（1）中的引理4，對于 （用于證明參考附錄）

（10）

（11）

（12）

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

（13）

完成證明我們因此需要限制每個網絡的誤差項 對

于任意的k。從（13），類似于（20）我們獲得一個表達式為Zk（t）作為一個

梯度函數和從（12），我們看到 。現在我們繼續證明：

（14）

（15）

（16）

下面我們將證明這個絕對值是有界的。

（17）

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

（18）

（19）

我們使用了幾何總和是有限的公式?，F在我們可以回到（13）來得到

假設

（20）

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

我們完成定理1的最后結果。

4 結束語

在文章中，我們描述和分析PSDDA算法一個基于凸優化的一致性分布式新算法。作為它的前身[1]不需要添加隨機共識協議，它適用于任何列隨機協議。P滿足網絡結構G且在不需要要知道平穩分布的P或在每一個節點大小的網絡無偏性的收斂到最優。

參考文獻

[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

摘 要：最近已經有大量的基于分布式一致性優化應用程序的研究。文章在此基礎上描述和證明了一種有向切換網絡新算法的收斂性我們稱此算法為push-sum分布式對偶平均算法，它結合最近的一個優化對偶平均算法[1]構成了有push-sum顯著優勢的一致性協議算法[2]。

關鍵詞：push-sum；分布式；一致性；收斂

1 引言

文章我們描述和證明一個為解決凸優化可分離函數組件問題的新算法即分布在節點的一個網絡算法及其收斂性。我們稱此算法為push-sum分布式對偶平均（PSDDA）算法。我們的算法是建立在最近發表的分布式對偶平均（DDA）算法[1]的基礎上，使用了改進的推和共識協議[2]。

為了使論文具有獨立性，我們回顧一些分布式對偶平均算法必要的背景知識。假設我們有一個強連通網絡G=（V，E）且|V|=n個計算節點。每個節點對應的凸函數hi（x）：Rd→R.我們目標是解決下式最小化問題

（1）

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

幾何收斂速度為

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

2 PUSH-SUM分布式對偶平均

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

（3）

（4）

（5）

其中gi（t）是hi（t）在點x=xi（t）處的梯度，a（t）是表示步長大小的數列是非遞增的。觀察檢索正確的累積梯度的DDA的標準，我們需要分析z變量在每個節點適當的權重。

定理1：PSDDA算法（14）用到了一個嚴格凸函數？追（x）的范數||.||和二階范數||.||*使得？追（x*）？燮R2，選擇步長大小如下

（6）

收斂的每個節點j∈V且最優值x*∈x在（1）里

（7）

3 定理1的證明

我們首先計算一個表達式的平均 。從（14）迭代遞歸我們得到

（8）

我們用到了一個事實即P0=I和P（t：r+1）是列隨機的。序列

是Z（t）的投影：

（9）

現在我們定義平均步長 和 .接下來。使用標準的凸性參數和（1）中的引理4，對于 （用于證明參考附錄）

（10）

（11）

（12）

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

（13）

完成證明我們因此需要限制每個網絡的誤差項 對

于任意的k。從（13），類似于（20）我們獲得一個表達式為Zk（t）作為一個

梯度函數和從（12），我們看到 。現在我們繼續證明：

（14）

（15）

（16）

下面我們將證明這個絕對值是有界的。

（17）

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

（18）

（19）

我們使用了幾何總和是有限的公式。現在我們可以回到（13）來得到

假設

（20）

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

我們完成定理1的最后結果。

4 結束語

在文章中，我們描述和分析PSDDA算法一個基于凸優化的一致性分布式新算法。作為它的前身[1]不需要添加隨機共識協議，它適用于任何列隨機協議。P滿足網絡結構G且在不需要要知道平穩分布的P或在每一個節點大小的網絡無偏性的收斂到最優。

參考文獻

[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

摘 要：最近已經有大量的基于分布式一致性優化應用程序的研究。文章在此基礎上描述和證明了一種有向切換網絡新算法的收斂性我們稱此算法為push-sum分布式對偶平均算法，它結合最近的一個優化對偶平均算法[1]構成了有push-sum顯著優勢的一致性協議算法[2]。

關鍵詞：push-sum；分布式；一致性；收斂

1 引言

文章我們描述和證明一個為解決凸優化可分離函數組件問題的新算法即分布在節點的一個網絡算法及其收斂性。我們稱此算法為push-sum分布式對偶平均（PSDDA）算法。我們的算法是建立在最近發表的分布式對偶平均（DDA）算法[1]的基礎上，使用了改進的推和共識協議[2]。

為了使論文具有獨立性，我們回顧一些分布式對偶平均算法必要的背景知識。假設我們有一個強連通網絡G=（V，E）且|V|=n個計算節點。每個節點對應的凸函數hi（x）：Rd→R.我們目標是解決下式最小化問題

（1）

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

幾何收斂速度為

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

2 PUSH-SUM分布式對偶平均

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

（3）

（4）

（5）

其中gi（t）是hi（t）在點x=xi（t）處的梯度，a（t）是表示步長大小的數列是非遞增的。觀察檢索正確的累積梯度的DDA的標準，我們需要分析z變量在每個節點適當的權重。

定理1：PSDDA算法（14）用到了一個嚴格凸函數？追（x）的范數||.||和二階范數||.||*使得？追（x*）？燮R2，選擇步長大小如下

（6）

收斂的每個節點j∈V且最優值x*∈x在（1）里

（7）

3 定理1的證明

我們首先計算一個表達式的平均 。從（14）迭代遞歸我們得到

（8）

我們用到了一個事實即P0=I和P（t：r+1）是列隨機的。序列

是Z（t）的投影：

（9）

現在我們定義平均步長 和 .接下來。使用標準的凸性參數和（1）中的引理4，對于 （用于證明參考附錄）

（10）

（11）

（12）

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

（13）

完成證明我們因此需要限制每個網絡的誤差項 對

于任意的k。從（13），類似于（20）我們獲得一個表達式為Zk（t）作為一個

梯度函數和從（12），我們看到 ?，F在我們繼續證明：

（14）

（15）

（16）

下面我們將證明這個絕對值是有界的。

（17）

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

（18）

（19）

我們使用了幾何總和是有限的公式。現在我們可以回到（13）來得到

假設

（20）

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

我們完成定理1的最后結果。

4 結束語

在文章中，我們描述和分析PSDDA算法一個基于凸優化的一致性分布式新算法。作為它的前身[1]不需要添加隨機共識協議，它適用于任何列隨機協議。P滿足網絡結構G且在不需要要知道平穩分布的P或在每一個節點大小的網絡無偏性的收斂到最優。

參考文獻

[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