分布式一致性最優(yōu)化的梯度算法與收斂分析

梁 舒，彭開香

北京科技大學(xué)自動(dòng)化學(xué)院工業(yè)過程知識自動(dòng)化教育部重點(diǎn)實(shí)驗(yàn)室，北京 100083

分布式優(yōu)化是多智能體系統(tǒng)控制、網(wǎng)絡(luò)通信和數(shù)學(xué)規(guī)劃的賽博空間（Cyberspace）科學(xué)，在眾多科學(xué)與工程中具有廣闊的發(fā)展前景[1-2]. 以鋼鐵行業(yè)自動(dòng)化為例，近年來我國鋼鐵生產(chǎn)企業(yè)普遍建立并實(shí)施了企業(yè)資源計(jì)劃、生產(chǎn)執(zhí)行系統(tǒng)、生產(chǎn)過程系統(tǒng)等多層次的集成自動(dòng)化系統(tǒng). 對于具有多層級、變工況、長流程等特點(diǎn)的復(fù)雜工業(yè)過程，其產(chǎn)品質(zhì)量管控、生產(chǎn)計(jì)劃與調(diào)度、能源綜合調(diào)配等微觀與宏觀調(diào)控方面存在大量的優(yōu)化決策問題[3]. 分布式優(yōu)化理論與方法是促進(jìn)兩化融合戰(zhàn)略決策和新一代工業(yè)革命的關(guān)鍵使能技術(shù)，其發(fā)展將增強(qiáng)人們對付大數(shù)據(jù)、大規(guī)模問題和復(fù)雜問題的能力，具有重要的實(shí)際應(yīng)用意義并蘊(yùn)藏著極大的經(jīng)濟(jì)效益.

分布式優(yōu)化的一類抽象問題類型是一致性最優(yōu)化，要求所有個(gè)體的決策變量最終實(shí)現(xiàn)一致性，并且一致點(diǎn)是一個(gè)凸優(yōu)化問題的最優(yōu)解. Nedic等[4?6]對該問題進(jìn)行了較深入地研究，主要針對非光滑的目標(biāo)函數(shù)，采用分布式次梯度的方法進(jìn)行求解.其中，為了確保算法的收斂性，需要采用逐漸衰減并趨于零的步長. Shi等[7]針對無約束的光滑最優(yōu)一致性，提出一種定步長并能精確收斂到最優(yōu)解的分布式算法. 該算法主要的思想是對所有個(gè)體的梯度之和進(jìn)行跟蹤，并利用不精確梯度理論對算法的收斂性進(jìn)行分析. 基于這種方法，Nedic等[8]改進(jìn)了這種算法，并利用小增益的技術(shù)給出了算法的指數(shù)收斂證明. 需要指出，這類算法僅處理無約束的分布式一致性最優(yōu)化問題，目前還不能推廣到有約束的問題. Liu等[9]和Lei等[10]利用經(jīng)典約束優(yōu)化中的原始-對偶梯度方法，給出了分布式原始-對偶梯度算法. 這類算法也采用了固定的步長，能夠精確收斂到最優(yōu)解，而且可以處理帶有約束的問題. Liang等[11]針對無約束情形下的分布式原始-對偶梯度算法，基于變分分析中的度量次正則性，給出算法指數(shù)收斂的判據(jù)，降低了對目標(biāo)函數(shù)強(qiáng)凸性的要求. 此外，值得指出，有不少學(xué)者從連續(xù)時(shí)間微分方程的角度進(jìn)行了分布式優(yōu)化算法設(shè)計(jì)，如文獻(xiàn)[12-16]. 總之，關(guān)于分布式一致性最優(yōu)化問題已有不少研究，而近年來學(xué)者們更加關(guān)注分布式定步長算法，以及對它們收斂性質(zhì)的分析論證.

本文考慮帶有約束的分布式一致性最優(yōu)化問題，給出定步長分布式原始-對偶梯度算法，并對算法的收斂性進(jìn)行分析論證. 最主要的貢獻(xiàn)在于提出一種基于李雅普諾夫函數(shù)的收斂分析范式：針對一般的定步長迭代格式，給出基于李雅普諾夫函數(shù)的收斂條件，類似于一般微分方程關(guān)于李雅普諾夫穩(wěn)定的分析方法. 這種方法帶來的好處在于將繁冗復(fù)雜的收斂性分析工作簡化為構(gòu)造李雅普諾夫函數(shù)并驗(yàn)證收斂條件. 在此基礎(chǔ)上，本文將該方法應(yīng)用到分布式原始-對偶梯度算法中，給出算法參數(shù)應(yīng)滿足的收斂條件. 與已有文獻(xiàn)中的方法相比，如文獻(xiàn)[9]和[10]，雖然它們從不同的角度利用算法具體結(jié)構(gòu)設(shè)計(jì)構(gòu)造了李雅普諾夫函數(shù)并輔助收斂分析，但本文提出的方法具有框架性和系統(tǒng)性，對其他類型分布式優(yōu)化算法的收斂分析也具有參考價(jià)值.

下面介紹本文的記號. R 和Rn分別代表實(shí)數(shù)空間和n維 歐氏空間. 記〈x,y〉為向量x和y的內(nèi)積，分別代表2-范數(shù)和無窮范數(shù).對于N個(gè)列向量x1,···,xN，使用col(x1,···,xN)代表其堆棧而成的列向量. 用0n、1n分別表示分量全部為0和分量全部為1的列向量，用In表 示Rn×n中的單位陣. 對于矩陣A=[aij]，aij代表該矩陣在第i行第j列的元素. 符號?表示矩陣的Kronecker乘積.

1 預(yù)備知識

本節(jié)的主要目的是羅列后續(xù)論述所需的預(yù)備知識，包括凸集與凸函數(shù)，以及圖論.

1.1 凸集與凸函數(shù)

本段介紹凸集及其投影的相關(guān)定義和性質(zhì)，更詳細(xì)的論述可參考專著[17]. 設(shè)?是n維歐氏空間Rn中的集合. 若對任意x,y∈?和0<τ<1，均有τx+(1?τ)y∈?，則稱?為凸集. 若一個(gè)集合中任意點(diǎn)列的極限點(diǎn)仍然屬于該集合，則稱該集合是閉集. 定義為點(diǎn)z∈Rn到閉凸集合?的歐氏距離投影. 投影算子具有一個(gè)基本性質(zhì)：〈z?P?(z),P?(z)?x〉≥0,?z∈Rn,?x∈?.

本段介紹凸函數(shù)的基本概念和性質(zhì)，更多結(jié)論可參考文獻(xiàn)[18]. 設(shè)??Rn為凸集，f:?→R為一個(gè)實(shí)函數(shù). 如果對任意x,y∈?和0<τ<1，均有f(τx+(1?τ)y)≤τf(x)+(1?τ)f(y)，則稱f為凸函數(shù).當(dāng)f可微時(shí)，其梯度記為?f(x). 可微凸函數(shù)具有一個(gè)基本性質(zhì)：

此外，若映射?f(x)關(guān)于x是κ-Lipschitz連續(xù)的，其中κ>0為某個(gè)常數(shù)，則不論f是否是凸函數(shù)，都有下面不等式成立：

1.2 圖論

網(wǎng)絡(luò)節(jié)點(diǎn)之間的信息分享關(guān)系可以通過圖論中的基本概念進(jìn)行描述. 一個(gè)圖G由 節(jié)點(diǎn)集合V和邊集E 構(gòu)成，記為G=(V,E). 對于具有N個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，通常記V={1,···,N}. 邊集E?V×V刻畫了節(jié)點(diǎn)之間的信息分享關(guān)系：若無序節(jié)點(diǎn)對(i,j)∈E，那么節(jié)點(diǎn)i和節(jié)點(diǎn)j可以相互通信. 如果對于任意i,j∈V，都可以從節(jié)點(diǎn)i出發(fā)通過若干條邊連接到節(jié)點(diǎn)j，則稱G為連通圖. 另外，可以通過一些代數(shù)量對圖進(jìn)行描述. 定義圖G的加權(quán)鄰接矩陣A=[aij]：當(dāng)(i,j)∈E 時(shí)，aij=aji>0，否則aij=0. 對于任意i∈V，節(jié)點(diǎn)i的度定義為進(jìn)一步，圖的度矩陣定義為，圖的Laplace矩陣定義為矩陣L是對稱半正定矩陣，且L1N=0n. 而且，若圖G是 連通的，則L僅有一個(gè)零特征值，其他特征值都為正數(shù). 有關(guān)圖論和代數(shù)圖論的詳細(xì)內(nèi)容可以參考文獻(xiàn)[19].

2 優(yōu)化問題與分布式算法

本節(jié)首先描述分布式一致性最優(yōu)化問題，然后給出求解該問題的分布式算法.

2.1 問題描述

考慮由N個(gè)個(gè)體組成的多智能體網(wǎng)絡(luò)，其信息分享關(guān)系圖為G=(V,E). 對于i∈V，個(gè)體i可以控制本地的決策變量xi∈?i，其中，?i?Rn是本地可行集合. 多智能體一致性控制問題，是指設(shè)計(jì)分布式的控制律，使得所有決策變量可以從初態(tài)收斂到某個(gè)相同的末態(tài)，即漸近滿足x1=···=xN. 這里的分布式，是指僅允許從本地?cái)?shù)據(jù)和網(wǎng)絡(luò)鄰居個(gè)體中獲得信息來更新決策變量. 進(jìn)一步，考慮每個(gè)個(gè)體都有一個(gè)關(guān)于決策變量的目標(biāo)函數(shù)（成本函數(shù)或效用函數(shù)），記為fi(xi). 分布式一致性最優(yōu)化問題，是希望設(shè)計(jì)分布式算法，使得多智能體網(wǎng)絡(luò)不僅能夠?qū)崿F(xiàn)一致性，還能實(shí)現(xiàn)總體目標(biāo)函數(shù)的最優(yōu)性.

結(jié)合上述多智能體網(wǎng)絡(luò)背景，分布式一致性最優(yōu)化問題的數(shù)學(xué)描述為

在求解問題（1）的過程中，假定每個(gè)個(gè)體i∈V的本地目標(biāo)函數(shù)不能被全局共享或者被其他個(gè)體獲取，而個(gè)體i能夠根據(jù)本地?cái)?shù)據(jù)獲取目標(biāo)函數(shù)在給定點(diǎn)的梯度值，但無法獲取其他個(gè)體目標(biāo)函數(shù)相關(guān)的任何信息.

下面給出問題（1）的基本假設(shè)條件.

假設(shè)1：對于每個(gè)i∈V，fi(xi)是可微凸函數(shù)，且?fi(xi)是κf-Lipschitz連續(xù)的，其中κf>0為某個(gè)常數(shù). ?i是非空的閉凸集合. 并且，優(yōu)化問題（1）至少存在一個(gè)有限的最優(yōu)解.

假設(shè)2：圖G是 一個(gè)連通圖.

上述條件是最基本的，也常見于其他文獻(xiàn)中.在假設(shè)1中，fi與?i的凸性保證問題（1）是一個(gè)凸優(yōu)化問題.fi的可微性使得個(gè)體能夠利用本地梯度信息進(jìn)行尋優(yōu). 最優(yōu)解集非空則確保了問題的適定性. 此外，假設(shè)2中的連通性使多智能體網(wǎng)絡(luò)實(shí)現(xiàn)整體一致性和最優(yōu)性成為可能.

注1：與文獻(xiàn)[7]、[8]和[11]相比，本文的分布式優(yōu)化的問題模型帶有集合約束，所以具有更廣的應(yīng)用范圍. 文獻(xiàn)[4]考慮了集合約束，但僅對相同的約束情形進(jìn)行了分析，即?1=···=?N. 而本文不需要該限制條件.

2.2 分布式算法

為了能夠借助凸優(yōu)化理論與算法對問題（1）進(jìn)行求解，先將一致性等式約束x1=···=xN等價(jià)地轉(zhuǎn)化為標(biāo)準(zhǔn)等式約束形式h(x)=0. 事實(shí)上，可以選取h(x)=L?Inx，其中L是圖G的Laplace矩陣. 這是因?yàn)?，在假設(shè)2的條件下，L?Inx=0nN當(dāng)且僅當(dāng)x1=···=xN. 于是，問題(1)的等價(jià)描述為

問題（2）是一個(gè)標(biāo)準(zhǔn)的約束優(yōu)化問題，可以定義一個(gè)Lagrange函數(shù)

其中，λ?col(λ1,···,λN)∈RnN為Lagrange乘子，β>0為一個(gè)常數(shù). 通常也把x和λ分別稱為原始變量和對偶變量. 在假設(shè)1的條件下，最優(yōu)化問題（2）的一階原始-對偶最優(yōu)條件為

其中，α>0為任意常數(shù).

根據(jù)最優(yōu)條件（4），可以設(shè)計(jì)一個(gè)基于原始-對偶梯度的迭代算法：

其中，常數(shù)α和β待定，它們將在收斂分析中根據(jù)收斂條件來確定. 算法（5）是一個(gè)分布式算法. 這是因?yàn)?，個(gè)體i在更新xi和λi的過程中，僅利用了本地?cái)?shù)據(jù)?fi(xi)、?i、xi和λi，以及鄰居個(gè)體的信息xj和λj.

將所有個(gè)體決策變量和對偶變量羅列起來，寫成更緊湊的形式：

由式（6）可見，算法的設(shè)計(jì)上采用了求解L鞍點(diǎn)的梯度下降-梯度上升的方法. 其不動(dòng)點(diǎn)滿足一階原始-對偶最優(yōu)條件（4），從而確保了算法的正確性.

注2：文獻(xiàn)[9-10]提出了類似的分布式原始-對偶梯度算法. 相比之下，本文考慮的算法具有兩個(gè)可調(diào)參數(shù)：α和β. 因此，該算法更具靈活性，并且推廣了文獻(xiàn)中的算法.

3 收斂性分析

本節(jié)首先對一般的定步長迭代格式，提出基于李雅普諾夫函數(shù)的一種分析范式. 在此基礎(chǔ)上，對本文的分布式算法進(jìn)行分析，給出算法參數(shù)的選擇范圍.

3.1 基于李雅普諾夫函數(shù)的一種分析范式

考慮一般的迭代格式

其中F:Rm→Rm為連續(xù)映射，α>0為常步長. 集合Z 為迭代格式（7）的不變集，即z[k]∈Z,?k≥0. 令為平衡點(diǎn)集合，這里假定Z?不為空集.

為了分析論證迭代（7）的收斂性，本文提出一種基于李雅普諾夫函數(shù)的分析范式.

定理1：如果存在一個(gè)李雅普諾夫函數(shù)V:Rm×Rm→R滿足：

1）對于任意的z?∈Z?，V(z,z?)是正定的，即V(z,z?)≥0，且V(z,z?)=0?z=z?；

2）對于任意的z?∈Z?，V(z,z?)關(guān)于z是水平強(qiáng)制的，即對于任意的正數(shù)γ>0，V的水平集合有界；

3）對于任意的z?∈Z?，V(z,z?)關(guān)于z可微，且映射?zV(z,z?)在z∈Z上 是κV-Lipschitz連續(xù)的，其中κV>0是一個(gè)常數(shù)；

4）存在某個(gè)常數(shù)δ>0，使得對于任意的z?∈Z?，都有，其中F(z)是（7）中的映射；

那么，由算法（7）產(chǎn)生的序列{z[k]}收斂到某一個(gè)平衡點(diǎn)，即存在某個(gè)滿足

證明：任取z?∈Z?. 因?yàn)?zV(z,z?)是κV-Lipschitz連續(xù)的，有

3.2 分布式一致性最優(yōu)化梯度算法的收斂分析

考慮分布式一致性最優(yōu)化梯度算法（6）. 為了得收斂條件，采用上小節(jié)提出的基于李雅普諾夫函數(shù)的分析方法.

其中，

根據(jù)最優(yōu)條件，映射G(z)滿足

接下來，構(gòu)造李雅普諾夫函數(shù)

由于L(x,λ?)是關(guān)于x的凸函數(shù)，所以L(x,λ?)?L(x?,λ?)?〈x?x?,?xL(x?,λ?)〉≥0. 于是，

而且，V(z,z?)是關(guān)于z的可微函數(shù)，可以通過計(jì)算得到

容易證明，?zV(z,z?)是關(guān)于z的κV-Lipschitz連續(xù)映射，其中

根據(jù)投影算子的基本性質(zhì)和不等式(11)，容易證明

并且

結(jié)合式（16）～（19），得到

至此，可以給出分布式算法（5）的收斂分析結(jié)果.

定理2：在假設(shè)1和假設(shè)2的條件下，如果分布式算法（5）的步長α和常數(shù)β滿足

那么算法產(chǎn)生的迭代序列收斂到某個(gè)原始-對偶最優(yōu)解.

證明：因?yàn)橐呀?jīng)給出了定理1所述的基于李雅普諾夫函數(shù)的分析范式，所以這里僅需考慮式（12）構(gòu)造的V(z,z?)，并驗(yàn)證其滿足各項(xiàng)條件.

首先根據(jù)（13），若0<α<1/‖L‖∞，則V(z,z?)是正定的，也是水平強(qiáng)制的，即滿足范式條件中的1）和2）. 然后，由（15）可知，V(z,z?)滿足條件3）. 再次，根據(jù)式（20），如果β≥2α‖L‖∞，則

即V(z,z?)滿足條件4），且δ=α. 將范式條件5）及其他關(guān)于α和β的條件列在一起，得到

整理后即可得到式（21）中的參數(shù)條件.

證畢！

4 數(shù)值實(shí)驗(yàn)

本節(jié)給出一個(gè)數(shù)值算例來驗(yàn)證算法的有效性.

考慮優(yōu)化問題（2），其中N=5，決策變量xi∈R，?i=[i?10,i?2]，i∈{1,2,3,4,5}. 每個(gè)個(gè)體的本地目標(biāo)函數(shù)為

個(gè)體之間的信息分享關(guān)系如圖1所示.

圖 1 信息分享關(guān)系圖Fig.1 Information sharing graph

通過分析和計(jì)算得

因此，根據(jù)式（21），選擇β=0.9，得到參數(shù)α的選擇范圍是0<α<0.075. 在數(shù)值實(shí)驗(yàn)中，選擇α=0.07，得到的實(shí)驗(yàn)結(jié)果如圖2～4所示. 可以看出，由于選擇了合適的步長等參數(shù)，算法僅迭代300次后就已經(jīng)收斂到最優(yōu)解. 這些實(shí)驗(yàn)結(jié)果驗(yàn)證了本文提出的分布式算法及其收斂分析方法的正確性和有效性.

圖 2 決策變量的更新軌跡Fig.2 Trajectories of decision variables

圖 3 對偶變量的更新軌跡Fig.3 Trajectories of dual variables

圖 4 李雅普諾夫函數(shù)的更新軌跡Fig.4 Trajectory of the Lyapunov function

5 結(jié)論

對分布式一致性最優(yōu)化問題進(jìn)行了研究，設(shè)計(jì)了具有兩個(gè)可調(diào)參數(shù)的分布式原始-對偶梯度算法，并論證了算法的收斂性. 針對一般的定步長迭代格式，提出一種基于李雅普諾夫函數(shù)的分析范式，具有普適性和一般性，在收斂分析方面具有框架性和系統(tǒng)性. 提出的方法運(yùn)用在論文所考慮的分布式梯度算法上，得到了算法收斂條件，確定出算法參數(shù)的選擇范圍，證實(shí)了方法的有效性. 給出的數(shù)值實(shí)驗(yàn)結(jié)果也驗(yàn)證了該方法的有效性. 接下來的工作將包括對其他類型的分布式優(yōu)化算法進(jìn)行設(shè)計(jì)和分析，如帶有耦合等式或不等式約束的分布式資源分配問題等.