朱小梅

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

引言

分布式優(yōu)化理論及應(yīng)用是目前系統(tǒng)和控制科學(xué)的重要研究方向之一，在分布式網(wǎng)絡(luò)中，節(jié)點(diǎn)之間通過相互協(xié)調(diào)合作，可以有效解決如智能電網(wǎng)、傳感器網(wǎng)絡(luò)等大規(guī)?，F(xiàn)實(shí)問題，并能提高數(shù)據(jù)傳遞效率，增強(qiáng)網(wǎng)絡(luò)魯棒性［1-2］。但在實(shí)際應(yīng)用中，分布式網(wǎng)絡(luò)一般都運(yùn)行在動態(tài)環(huán)境下，分布式優(yōu)化算法不能實(shí)時處理網(wǎng)絡(luò)數(shù)據(jù)流，而在線學(xué)習(xí)能夠根據(jù)數(shù)據(jù)的變化動態(tài)地調(diào)整模型［3-4］，進(jìn)而更高效地完成對大量實(shí)時數(shù)據(jù)的處理，并且分布式在線優(yōu)化算法已經(jīng)在機(jī)器學(xué)習(xí)、在線推薦系統(tǒng)和資源分配等方面有著重要的應(yīng)用價值。

分布式優(yōu)化算法已成為有效求解大規(guī)模優(yōu)化問題的熱點(diǎn)算法之一?，F(xiàn)有的分布式優(yōu)化算法主要分為三類：第一類是文獻(xiàn)［5］最早提出的一種分布式次梯度算法來求解無約束的分布式優(yōu)化問題，第二類是文獻(xiàn)［6］提出的一種分布式對偶平均算法，給出算法的收斂性，并得出了收斂率依賴于網(wǎng)絡(luò)規(guī)模和拓?fù)浣Y(jié)構(gòu)的結(jié)論，第三類是文獻(xiàn)［7］基于拉格朗日對偶方法提出的分布式原始對偶算法來求解一類帶約束的優(yōu)化問題。雖然文獻(xiàn)［6］提出的分布式對偶平均算法已經(jīng)成為可以解決大規(guī)模問題的熱點(diǎn)算法，但由于環(huán)境的不確定性以及目標(biāo)函數(shù)具有時變性和不確定性，導(dǎo)致分布式優(yōu)化算法并不能對網(wǎng)絡(luò)中產(chǎn)生的大量分布式數(shù)據(jù)流進(jìn)行實(shí)時處理，這造成網(wǎng)絡(luò)資源和時間的浪費(fèi)。針對上面的情形，一種有效的解決方法是在線學(xué)習(xí)，因?yàn)樵诰€學(xué)習(xí)可以利用時變的目標(biāo)函數(shù)來表示多個體網(wǎng)絡(luò)系統(tǒng)的不確定性，同時還可以方便地對網(wǎng)絡(luò)節(jié)點(diǎn)的動態(tài)數(shù)據(jù)流進(jìn)行實(shí)時處理。最近，對于成本和網(wǎng)絡(luò)結(jié)構(gòu)不確定的凸優(yōu)化問題，文獻(xiàn)［8］提出了分布式加權(quán)對偶平均算法。李德權(quán)等人提出的一種快速的分布式在線對偶平均算法，即通過對底層網(wǎng)絡(luò)依次添邊，提高了分布式在線優(yōu)化算法的收斂速率［9］。為更好的解決多智能體的在線優(yōu)化問題，文獻(xiàn)［10］設(shè)計(jì)了Nesterov對偶平均算法的兩個去中心化的隨機(jī)變體，即SODA-C和SODA-PS。文獻(xiàn)［11］考慮了正則化隨機(jī)學(xué)習(xí)和在線優(yōu)化問題，開發(fā)了一種正則化的對偶平均算法，可以在在線環(huán)境中更有效的利用正則化結(jié)構(gòu)。這充分說明分布式在線對偶平均方法可以有效的解決分布式在線優(yōu)化問題。

現(xiàn)有的分布式在線對偶平均算法都是基于目標(biāo)函數(shù)的梯度可以有效計(jì)算的情況，但在現(xiàn)實(shí)生活中，梯度信息一般獲取困難。由此看來，現(xiàn)有的分布式在線對偶平均算法面臨著一個梯度計(jì)算瓶頸。因此，設(shè)計(jì)出一種無梯度計(jì)算方法是十分有價值的。受文獻(xiàn)［12］的啟發(fā)，本文提出了一種基于Bandit反饋的分布式在線對偶平均算法。不同于分布式在線對偶平均算法，本文提出的算法只需要計(jì)算損失函數(shù)的值，即主要是利用損失函數(shù)在一些隨機(jī)點(diǎn)的函數(shù)值信息去逼近損失函數(shù)原來的梯度信息，從而避免了直接計(jì)算損失函數(shù)的梯度。

1 準(zhǔn)備工作

1.1圖論

設(shè)G=（v，ε）表示一個無向圖，其中v=｛1，2，…，n｝表示由n個節(jié)點(diǎn)構(gòu)成的集合，ε?v×v表示相鄰節(jié)點(diǎn)構(gòu)成的邊集，邊（i，j）∈ε表示節(jié)點(diǎn)i可以從節(jié)點(diǎn)j接收數(shù)據(jù)信息。并記Ni=｛j|（i，j）∈ε｝表示節(jié)點(diǎn)i所有鄰居構(gòu)成的集合。非負(fù)矩陣A為圖G=（v，ε）的權(quán)重矩陣，滿足［A］ij＞0，當(dāng)且僅當(dāng) （i，j）∈ ε，否則［A］ij=0。

假設(shè)1［2］設(shè)圖G=（v，ε）是連通的，非負(fù)矩陣A∈Rn×n為圖G=（v，ε）的權(quán)重矩陣，設(shè)權(quán)重矩陣是雙隨機(jī)的，即

1.2 Bandit反饋

在已有的分布式在線對偶平均算法的研究中，節(jié)點(diǎn)之間都是通過梯度信息進(jìn)行通信反饋的，但在實(shí)際應(yīng)用場景中，更一般的情況是不能夠直接得到梯度信息的，所以本文提出了一種新的梯度信息反饋的改進(jìn)方法，即Bandit反饋，該方法只顯示當(dāng)前時刻的損失函數(shù)的值，而不是顯示整個函數(shù)的值。在Bandit設(shè)置中，節(jié)點(diǎn)只能訪問一些點(diǎn)上的代價函數(shù)上的值并且不知道函數(shù)的梯度。由于大多數(shù)優(yōu)化算法需要相關(guān)函數(shù)的梯度，因此，下面給出根據(jù)函數(shù)在有限點(diǎn)上的函數(shù)值來估計(jì)梯度的一些結(jié)果。

給定一個函數(shù)fi，t（x）：Rm→R，對?x∈（1-ξ）χ，χ?Rm及某個很小的數(shù)δ＞0，定義fi，t（x）的一個光滑化近似函數(shù)，如下［8］

為梯度估計(jì)，其中u是滿足均勻分布的隨機(jī)向量。

引理 1［13］（I）即使fi，t（x）不可微，均勻光滑化函數(shù)^f i，t（x）在 （1-ξ）χ是可微的，對 ?x∈ （1-ξ）χ有

（II）若fi，t（x）在 χ上是凸的，則^fi，t（x）在 （1-ξ）χ上也是凸的，且對 ?x∈ （1-ξ）χ，fi，t（x）≤^fi，t（x）。

（III）若fi，t（x）在 χ上是 L-Lipschitz連續(xù)的，則）在 （1-ξ）χ上也是 L-Lipschitz連續(xù)的，且對 ?x∈ （1-ξ）χ有）≤Lδ。

（IV）若fi，t（x）在 χ上是 L-Lipschitz連續(xù)的，則對?x∈ （1-ξ）χ有mL。

2 問題與算法

2.1問題

考慮圖G=（v，ε）上的分布式在線凸優(yōu)化問題，如下

本文的最終目標(biāo)是得到一系列的決策點(diǎn)｛xi，t｝使得對于每一個節(jié)點(diǎn)i∈v與最佳的固定決策點(diǎn)x*的Regret界［14］。

假設(shè)2（I）對任意的i∈v和任意的t∈｛1，2，…，T｝，fi，t（x）在 χ是 L-Lipschitz連續(xù)的，即對任意的x∈ χ和y∈ χ都有）-fi，t（y）Lx-y。

（II）存在正常數(shù)r和R使得rB?χ?RB，其中B=｛x∈x≤1｝。

由假設(shè) 2知，fi，t（·）的次梯度 ▽fi，t（·）在上是一致有界的，即 ▽fi，t≤L。

2.2 基于Bandit反饋的分布式在線對偶平均算法

算法1DODA-B算法

1.輸入：最大迭代輪數(shù)T，步長αt，收縮系數(shù)ξ，光滑化參數(shù)δ和近端函數(shù)ψ（·）；

2.初始化：xi，1∈ （1-ξ）χ，?i∈v，zi，1=0；

3.fort=1，2，…，Tdo

4.fori=1，2，…，ndo

5.觀測fi，t（·），由式（2）計(jì)算梯度估計(jì)^gi，t；

8.輸出：xi，t+1；

9.end for

10.end for

注記：（I）算法1給出了所提算法的偽代碼，每個節(jié)點(diǎn)i都有如下兩個局部序列：局部原始決策變量序列｛xi，t｝?χ，局部對偶變量序列 ｛zi，t｝?（1-ξ）χ，通過算法1的步6和步7更新。

（II）算法1中的步7中的 Πψ（1-ξ）χ（·）是在 （1-ξ）χ上的正則投影，這個投影可以表示為

其中ψ（x）是一個近端函數(shù)。

3 收斂性分析

這部分提出一個帶兩點(diǎn)梯度估計(jì)的在線分布式對偶平均算法來解決所考慮的優(yōu)化問題，然后給出Regret界。下面主要陳述對算法1的主要結(jié)果。下面的定理描述基于一些特別選擇的步長，壓縮系數(shù)和光滑化參數(shù)等等。首先給出幾個重要的引理：

引理2［13］對任意的常數(shù)k∈ ［0，1），且s≤T∈R+，有

引理3［15］設(shè)假設(shè)1成立，則存在常數(shù) λ∈ （0，1）及C＞0，對 ?i，j∈v，?t≥1有

引理4設(shè)假設(shè)1-2成立，對任意的i∈v和t∈R+，｛zi，t｝是由算法 1產(chǎn)生的序列，則

再對式（10）兩邊取對偶范數(shù)可得

第二個不等式由引理1的（IV）和引理3得到。

引理5設(shè)假設(shè)1-2成立，｛xi，t｝是由算法1產(chǎn)生的序列，則對任意的i∈v，x*∈（1-ξ）χ有

證明根據(jù)fi，t（x）的L-Lipschitz連續(xù)性，對x*∈（1-ξ）χ和由 φ（t）=，αt）定義的序列 ｛φ（t）｝，有

將（13）式右邊最后一個等式的第一項(xiàng)重新寫為

根據(jù)引理1的（III）可知

從而在式（19）兩邊對t=1，2，…，T求和得

于是將式（23）代入式（18）可得

由式（17）和式（24）可得

于是將式（26）代入式（13）可得

將引理4代入上式即可得結(jié)論，式（12）得證。

定理1設(shè)假設(shè)1-2成立，對任意的T∈ R+，｛x｝是由算法 1產(chǎn)生的序列，取 α=，δ，ξ=i，tt，ψ（x）≤D2，有

從而結(jié)論得以證明。

注記：定理1的結(jié)果表明，算法1的收斂速度是O（Tmax｛k，1-k｝），當(dāng)k=時，算法1的收斂速度與已往的分布式在線對偶平均算法的收斂速度同階。通過對比，本文所提出的算法1只需要計(jì)算損失函數(shù)的函數(shù)值，避免了花費(fèi)較大的梯度計(jì)算，從而節(jié)省了計(jì)算成本，并且算法適用范圍更加廣泛。

4 數(shù)值模擬計(jì)算

在本節(jié)中，考慮一個分布式在線傳感器問題，對于每個節(jié)點(diǎn)i∈v都有自己的測量方程qi，t=Uix+ei，t，其中qi，t∈Rn，Ui∈Rn×m是測量數(shù)據(jù)，x∈Rm是未知的，ei，t∈Rn是未知的噪音，問題最終的目標(biāo)在于估計(jì)x，使用所提出的DODA-B算法去解決如下問題［16］

考慮一個節(jié)點(diǎn)n的隨機(jī)網(wǎng)絡(luò)，對于任意的節(jié)點(diǎn)i∈v。假設(shè) χ=Rm，實(shí)矩陣Ui∈ Rn×m且qi，t∈ Rn在（0，2）中產(chǎn)生，設(shè)ui，t是在歐式單位球S上隨機(jī)產(chǎn)生，且服從均勻分布。取T=500，R=5，，λ=0.5，步長α=。取光滑參數(shù)δ，壓縮系數(shù)ξ=?？紤]平t均Regret界，將本文的DODA-B算法與現(xiàn)有的DODA算法進(jìn)行對比。

圖1和圖2表示節(jié)點(diǎn)總數(shù)n分別為50和100的平均Regret界的演化圖。根據(jù)定理1的理論結(jié)果分析，可以從圖1觀察到，當(dāng)?shù)鷷r間T達(dá)到100時，兩種算法的平均Regret界均會收斂到0，并且DODA-B算法的收斂率和DODA算法收斂率同階，因?yàn)樗鼈儍H相差一個由函數(shù)值信息近似梯度信息產(chǎn)生的光滑化誤差項(xiàng)。另外，從圖2可以觀察到，當(dāng)節(jié)點(diǎn)n=100時，也可以得到同樣的結(jié)果。

圖1 DODA-B與DODA算法平均化Regret界的比較（n=50）

圖2 DODA-B與DODA算法平均化Regret界的比較（n=100）

5 結(jié)論

針對分布式在線優(yōu)化中一類損失函數(shù)梯度難以獲取的問題，通過Bandit設(shè)置，本文提出了一種基于Bandit反饋的分布式在線對偶平均（DODA-B）算法，將DODA算法改進(jìn)成無梯度的DODA-B算法。理論分析表明，DODA-B算法具有O(Tmax{k，1-k})的Regret界。數(shù)值模擬計(jì)算結(jié)果進(jìn)一步表明兩種算法的收斂率同階，并且DODA-B算法僅僅用到計(jì)算量較小的函數(shù)值信息，這要比DODA算法更節(jié)約成本。未來可以將所提的DODA-B算法推廣到有向網(wǎng)絡(luò)中，或推廣到時變網(wǎng)絡(luò)中。