基于概率量化的分布式無梯度優(yōu)化算法研究

李德權(quán)，陳 平

（安徽理工大學(xué)理學(xué)院，安徽 淮南232001）

0 引言

近年來，隨著網(wǎng)絡(luò)通訊和計(jì)算機(jī)科學(xué)的飛速發(fā)展，人們迎來了大數(shù)據(jù)、云計(jì)算的時(shí)代，這導(dǎo)致以往的集總式優(yōu)化理論已無法適應(yīng)現(xiàn)在的大規(guī)模大數(shù)據(jù)優(yōu)化問題［1］。目前，分布式優(yōu)化理論研究的一類優(yōu)化問題是：關(guān)于整個(gè)網(wǎng)絡(luò)的優(yōu)化問題可以分解成網(wǎng)絡(luò)中各個(gè)個(gè)體目標(biāo)函數(shù)之和，每個(gè)個(gè)體僅知道其自身目標(biāo)函數(shù)并通過與其鄰居個(gè)體進(jìn)行信息交互，從而使整個(gè)網(wǎng)絡(luò)優(yōu)化問題最優(yōu)且每個(gè)個(gè)體狀態(tài)均在最優(yōu)解處達(dá)到一致。由于不需要考慮網(wǎng)絡(luò)全局信息及其魯棒性［2］，因此分布式優(yōu)化理論最近引起學(xué)者們的廣泛關(guān)注。分布式優(yōu)化理論主要依賴個(gè)體間的局部合作協(xié)調(diào)從而實(shí)現(xiàn)優(yōu)化任務(wù)［3］。文獻(xiàn)［4］首先提出了基于多個(gè)體一致性的分布式優(yōu)化問題。

目前，大多數(shù)分布式優(yōu)化問題通常是在假定每個(gè)個(gè)體目標(biāo)函數(shù)具有梯度或次梯度的前提下進(jìn)行研究的。但并非所有目標(biāo)函數(shù)（次）梯度均存在或有時(shí)（次）梯度需要花費(fèi)大量復(fù)雜而繁瑣的計(jì)算，因而有學(xué)者提出了分布式無梯度優(yōu)化算法［5］。如文獻(xiàn)［6］討論了隨機(jī)無梯度的最小值問題，文獻(xiàn)［7］討論了基于push-sum算法的分布式無梯度優(yōu)化問題，文獻(xiàn)［8］討論了時(shí)變網(wǎng)絡(luò)中的分布式隨機(jī)無梯度優(yōu)化問題等等。

此外，隨著通信技術(shù)的發(fā)展，數(shù)字通信正逐步取代模擬通信而被廣泛應(yīng)用到各個(gè)領(lǐng)域，例如多個(gè)體網(wǎng)絡(luò)的一致性、分布式估計(jì)等。由于網(wǎng)絡(luò)帶寬有限，數(shù)字通信技術(shù)一般通過量化編碼將模擬信息轉(zhuǎn)化為數(shù)字信息，然后經(jīng)由數(shù)字信號(hào)通道進(jìn)行通訊［9］。信息量化大致可以分為概率量化和確定性量化。概率量化相對(duì)于確定性量化具有量化誤差的期望為零的優(yōu)點(diǎn)。但由于隨機(jī)因素的引入，網(wǎng)絡(luò)中個(gè)體僅能達(dá)到概率意義下的收斂［1］。文獻(xiàn)［10］首次在切換網(wǎng)絡(luò)拓?fù)湎掠懻摿舜_定性量化對(duì)分布式次梯度優(yōu)化算法的影響。文獻(xiàn)［11］則研究了概率量化下分布式算法的平均一致性問題。在文獻(xiàn)［11］的基礎(chǔ)上，文獻(xiàn)［12］進(jìn)一步討論了概率量化對(duì)分布式次梯度優(yōu)化算法的影響。

文獻(xiàn)［13］主要研究隨機(jī)投影下分布式優(yōu)化算法，并應(yīng)用次梯度算法探究其最優(yōu)解的收斂情況，而本文在隨機(jī)投影無梯度優(yōu)化算法的基礎(chǔ)上，考慮概率量化對(duì)多個(gè)體網(wǎng)絡(luò)分布式優(yōu)化算法的收斂性及最優(yōu)解的影響。

1 問題描述

1．1 基礎(chǔ)知識(shí)

1．1．1 代數(shù)圖論

若將網(wǎng)絡(luò)中每個(gè)個(gè)體看作是一個(gè)節(jié)點(diǎn)，則多個(gè)體網(wǎng)絡(luò)中個(gè)體間的信息通信可以建模成有向圖G＝（v，ε），其中v＝｛v1，v2，…，vM｝，M 為個(gè)體數(shù)目，邊集ε＝v×v用來表示個(gè)體間的信息交流過程。若第j個(gè)個(gè)體是第i個(gè)個(gè)體的鄰居，則有序數(shù)對(duì)｛j，i｝∈ε，第i個(gè)個(gè)體的鄰居節(jié)點(diǎn)的集合記為Ni＝｛j∈v｜（j，i）∈ε｝。

從上述引理可以看出概率均勻量化是無偏差的，但是確定性量化不滿足該性質(zhì)，因而概率均勻量化更適合在平均一致性算法中應(yīng)用。

1．2 問題的提出

本文考慮的是具有M個(gè)個(gè)體的網(wǎng)絡(luò)系統(tǒng)中的分布式優(yōu)化問題。由于分布式優(yōu)化所研究的是所有局部目標(biāo)函數(shù)和最小值的問題，因此本文考慮下面這個(gè)問題［14］，即：

2 分布式無梯度優(yōu)化的量化算法

2．1 高斯近似函數(shù)

由于本文所要考慮的是一般的目標(biāo)函數(shù)，其不一定有次梯度，或次梯度求解過程太繁瑣，所以本文根據(jù)參考文獻(xiàn)［6］引入高斯近似函數(shù)將目標(biāo)函數(shù)fi（x）變?yōu)槠涓咚菇坪瘮?shù)：

2．2 量化算法

2．3 相關(guān)引理

引理3［6］?i∈V，L 是函數(shù)fi（x）的 Lipschitz約束，則有：

2．4 相關(guān)性質(zhì)

本文將用到的系數(shù)矩陣A是雙隨機(jī)矩陣，即滿足下列性質(zhì)［12］：

1）對(duì)于?（i，j）?ε或i≠j有Aij＝0；

2）A 是對(duì)稱矩陣即A＝AT且Avec（1）＝vec（1）；

3）ρ（A-（vec（1）vec（1）T）／m）＜1．

其中，vec（1）＝（1，1，…，1）T∈Rm；ρ為矩陣的譜半徑。

3 主要結(jié)果

定理1 若高斯無梯度預(yù)測(cè)gi（t）滿足引理1且系數(shù)矩陣A滿足性質(zhì)3），根據(jù)算法（2），對(duì)于每個(gè)個(gè)體i，則有

將以上2個(gè)式子相減并同時(shí)取范數(shù)，并根據(jù)高斯無梯度預(yù)測(cè)gi（t）的有界性得到：

將等式右邊第2項(xiàng)展開并根據(jù)應(yīng)用引理1可知

4 結(jié)語(yǔ)

本文研究了固定拓?fù)湎露鄠€(gè)體網(wǎng)絡(luò)的目標(biāo)函數(shù)可以分解成網(wǎng)絡(luò)中每個(gè)個(gè)體自己知曉的目標(biāo)函數(shù)之和，且個(gè)體間通過交互量化信息尋求最優(yōu)解的問題。研究表明，當(dāng)概率量化精度足夠高且步長(zhǎng)足夠小時(shí)，則所求的解就越接近最優(yōu)解。

［1］袁德明．多智能體系統(tǒng)的分布式一致與優(yōu)化［D］．南京：南京理工大學(xué)，2012．

［2］Wang Na，Li Dequan，Yin Zhixiang．Broadcast Gossip Algorithm with Quantization．Proceedings of the 9thInternational Conference on Fuzzy Systems and Knowledge Discovery，2012：2157-2161．

［3］洪奕光，張艷瓊．分布式優(yōu)化：算法設(shè)計(jì)和收斂性分析［J］．控制理論與應(yīng)用，2014，31（7）．DOI：10．7641／CTA．2014．40 012．

［4］A．Nedic，A．Ozdaglar．Distributed Sub-gradient Methods for Multi-agent Optimization［J］．IEEE Transactions on Automatic Control，2009，54（1）：48-61．

［5］Yu．Nesterov．Random Gradient-free Minimization Functions［J］．CORE Discussion Paper 2011／1．2011．

［6］Y．Nesterov．Random Gradient-free Minimization of Convex Functions［J］．Dept．Center Oper．Res．Econ．，Univ．Catholique de Louvain，Louvain，Belgium，Tech．Rep．，2011／1．

［7］Deming Yuan，Shengyuan Xu，and Jun wei Lu．Gradientfree Method for Distributed Multi-agent Optimization Via push-sum Algorithms［J］．International Journal of Robust and Nonlinear Control，2015，25（10）：1569-1580．

［8］Deming Yuan and DanielW．C．Ho，Randomized Gradient-Free Method for Multi-agent Optimization over Time-Varying Networks［J］．Senior Member，IEEE，2014．

［9］孟誠(chéng)．二階多智能體系統(tǒng)一致性研究［M］．控制理論與控制工程，2012．

［10］Nedic A，Olshevsky A．Ozdaglar A，et al．Distributed Subgradient Methods and Quantization Effect［A］．Proceedings of IEEE CDC ［C］，Mexico：IEEE，2008：4177-4184．

［11］Aysal T，Coates M，Rabbat M．Distributed Average Consensus Using Dithered Quantization ［J］．IEEE Transactions on Signal Processing，2008，56（10）：4905-4918．

［12］袁德明，徐盛元，趙環(huán)宇，等．分布式多自主體優(yōu)化問題中的概率量化影響研究［J］．南京理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，35（2）．

［13］Soomin Lee and Angelia Nedic′．Distributed Random Projection Algorithm for Convex Optimization［J］．Selected Topics in Signal Processing，IEEE．2013，7（2）：221-229．

［14］李婧．基于量化共識(shí)的分布式Gossip算法研究［M］．哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2013．

［15］Xiao L，Boyd S．Fast Linear Iterations for Distributed Averaging［J］．Sys and Contr Letters，2004，53（1）：65-78．