劉奕葶 馬銘莙 付 俊

在多智能體網(wǎng)絡(luò)中,分布式優(yōu)化是決策和數(shù)據(jù)處理的重要研究方向,近年來得到廣泛研究[1-3].每個(gè)智能體都有一個(gè)局部目標(biāo)函數(shù),通過各智能體與其鄰居進(jìn)行信息交互,共同協(xié)作實(shí)現(xiàn)由局部目標(biāo)函數(shù)之和構(gòu)成的全局目標(biāo)函數(shù)最小.隨著近年來互聯(lián)網(wǎng)、大數(shù)據(jù)等新興技術(shù)的發(fā)展,資源分配在網(wǎng)絡(luò)系統(tǒng)中得到廣泛的應(yīng)用,如電力系統(tǒng)中的經(jīng)濟(jì)調(diào)度、機(jī)器人研究、智能交通、能源制造、無線網(wǎng)絡(luò)利用率最大化等[4-8],使系統(tǒng)具有更高的功能效率、穩(wěn)定性、安全性和可靠性.

分布式優(yōu)化是通過各智能體間協(xié)調(diào)合作來實(shí)現(xiàn)優(yōu)化任務(wù),每個(gè)智能體只能訪問自己的局部目標(biāo)函數(shù)和局部約束集,與優(yōu)化問題相關(guān)信息分別存儲(chǔ)在各智能體中,這充分保證了信息的隱私安全[2].其次,各智能體與其鄰居節(jié)點(diǎn)進(jìn)行信息交換即可,不必將數(shù)據(jù)信息傳遞到中心節(jié)點(diǎn),更加節(jié)約了通信成本,也避免了集中式算法會(huì)引入的通信單點(diǎn)故障和傳感器故障等,極大地提高了系統(tǒng)的魯棒性,也避免了對(duì)于處理大規(guī)模的復(fù)雜優(yōu)化問題時(shí),集中式算法會(huì)由于智能體之間的通信、計(jì)算等限制變得低效[9].

大多數(shù)的分布式算法是基于無向通信網(wǎng)絡(luò)實(shí)現(xiàn)的,如文獻(xiàn)[10]提出的分布式精確收斂的一階算法是通過前兩次迭代的狀態(tài)和梯度信息來更新節(jié)點(diǎn)的狀態(tài).分布式不精確梯度方法和梯度跟蹤算法中每個(gè)節(jié)點(diǎn)采用相同的步長,變量的更新規(guī)則中并未用到動(dòng)態(tài)一致性算法,最終跟蹤的梯度不是全局平均梯度.之后有研究提出在無向圖網(wǎng)絡(luò)下,改進(jìn)分布式不精確梯度方法和梯度跟蹤技術(shù),使其在不同節(jié)點(diǎn)采用不同步長,加速優(yōu)化算法[11-12].

而許多實(shí)際問題中的通信網(wǎng)絡(luò)往往是有向的,如無線電傳感器網(wǎng)絡(luò)、手機(jī)通訊網(wǎng)絡(luò)等[13].有向圖中算法收斂是一項(xiàng)具有挑戰(zhàn)性的工作,如文獻(xiàn)[12]中所提算法只適用于無向網(wǎng)絡(luò),在有向網(wǎng)絡(luò)下其算法不具備收斂性.文獻(xiàn)[14]考慮在強(qiáng)連通加權(quán)平衡有向圖上智能體的資源分配問題.當(dāng)局部目標(biāo)函數(shù)強(qiáng)凸時(shí),其滿足等式路徑約束和局部凸集的約束條件下,分布式連續(xù)時(shí)間投影算法的輸出狀態(tài)可漸近收斂到資源配置問題的最優(yōu)解.對(duì)局部凸集約束條件進(jìn)行松弛并提出可以在強(qiáng)連通加權(quán)不平衡有向圖上的自適應(yīng)連續(xù)時(shí)間梯度算法,其中局部目標(biāo)函數(shù)及其梯度分別滿足強(qiáng)凸性和Lipachitz 條件,并證明其指數(shù)收斂到問題的最優(yōu)解.文獻(xiàn)[15]結(jié)合Push-Sum 算法的核心思想,提出滿足一致強(qiáng)連通時(shí)變有向圖網(wǎng)絡(luò)下有效收斂的Subgradient-Push 算法.假設(shè)每個(gè)節(jié)點(diǎn)知道其對(duì)應(yīng)的出度信息,在次梯度有界的標(biāo)準(zhǔn)假設(shè)下使每個(gè)節(jié)點(diǎn)收斂并且都能找到最優(yōu)值.

在實(shí)際應(yīng)用中,當(dāng)系統(tǒng)對(duì)實(shí)時(shí)優(yōu)化有較高要求時(shí),通常會(huì)考慮有向網(wǎng)絡(luò)下的分布式連續(xù)時(shí)間算法,其對(duì)系統(tǒng)的穩(wěn)定性及靈活性的高要求可以用來解決資源分配問題[16-19].文獻(xiàn)[20-21]中提出的分布式投影算法分別用于解決無向圖和加權(quán)平衡有向圖的資源分配問題.文獻(xiàn)[20]在滿足線性等式約束和局部可行集約束的前提下,基于差分投影提出的連續(xù)時(shí)間算法,可以不通過初始化對(duì)無向網(wǎng)絡(luò)下的各智能體進(jìn)行決策分配.文獻(xiàn)[21]考慮了滿足局部可行集約束的非光滑代價(jià)函數(shù)在強(qiáng)連通加權(quán)平衡有向網(wǎng)絡(luò)下的分布式資源分配問題.利用微分包含和LaSalle 集值不變性原理,證明了解的唯一性和算法的收斂性.但文獻(xiàn)[20-21]所提的連續(xù)時(shí)間算法對(duì)于分布式資源分配仍存在一定的局限性.文獻(xiàn)[20]的算法對(duì)加權(quán)平衡有向圖的有效性仍需探索;文獻(xiàn)[21]中算法在運(yùn)行前需計(jì)算智能體在切錐上的投影,增加了各智能體之間的交互和計(jì)算時(shí)間.

分布式優(yōu)化問題中最簡單的情況是無約束優(yōu)化[22-23].如文獻(xiàn)[22]通過構(gòu)造李雅普諾夫函數(shù)并進(jìn)行穩(wěn)定性分析,使提出的連續(xù)時(shí)間分布式算法能夠指數(shù)收斂到全局最小值.在無向網(wǎng)絡(luò)下的分布式連續(xù)時(shí)間非光滑凸優(yōu)化問題中[24],只考慮局部可行集約束,通過算法在切錐上的投影,使其在滿足局部可行集的約束條件下使算法收斂.此外,文獻(xiàn)[25]中提出了一種分布式連續(xù)時(shí)間多智能體系統(tǒng),使目標(biāo)函數(shù)在滿足不等式路徑約束、等式路徑約束和局部可行集的約束下算法收斂,找到全局目標(biāo)函數(shù)的最小值.上述研究中大多沒有考慮耦合約束,然而耦合路徑約束出現(xiàn)在許多實(shí)際應(yīng)用中,具有重大研究價(jià)值.

具有耦合約束的分布式優(yōu)化,其中各個(gè)智能體的決策變量的可行域會(huì)受到其他智能體的影響.然而在實(shí)際應(yīng)用中,網(wǎng)絡(luò)拓?fù)鋱D中沒有中心點(diǎn)時(shí),耦合約束并不能夠滿足對(duì)各個(gè)智能體的資源分配[26].在文獻(xiàn)[26]中考慮具有耦合的非線性約束,提出一個(gè)改進(jìn)的拉格朗日函數(shù),引入局部乘子來解耦約束,并使用非光滑罰函數(shù)保證算法的正確性,使其鞍點(diǎn)不僅能得到優(yōu)化問題的最優(yōu)解,其原對(duì)偶次梯度的算法也是完全分布的.文獻(xiàn)[27]研究解決不等式約束的優(yōu)化問題,通過Caratheodory 意義上原始對(duì)偶動(dòng)力學(xué)的解的存在的唯一性和連續(xù)性,建立在原始對(duì)偶動(dòng)力學(xué)下全局漸近收斂的分布式算法.

本文基于文獻(xiàn)[28]中提出的分布式連續(xù)時(shí)間投影算法進(jìn)行延展,通過投影的定義及性質(zhì),結(jié)合線性代數(shù)理論分析,找到了證明算法的平衡解為分布式優(yōu)化問題最優(yōu)解的充分必要條件,并且可以適用于強(qiáng)連通加權(quán)平衡有向通信網(wǎng)絡(luò)拓?fù)鋱D.在滿足耦合不等式約束和局部可行集約束的情況下使非光滑全局目標(biāo)函數(shù)最小,找到分布式優(yōu)化問題的最優(yōu)解.大多數(shù)分布式優(yōu)化問題考慮的是無約束、等式約束或不等式約束[23-25,29-31],與文獻(xiàn)[24]中的局部可行集約束相比,我們考慮的耦合不等式路徑約束更具有通用性,難度更高且計(jì)算更復(fù)雜,適用范圍更廣.本文研究了分布式優(yōu)化在強(qiáng)連通有向通信拓?fù)鋱D下的連續(xù)時(shí)間投影算法,和文獻(xiàn)[12]中無向網(wǎng)絡(luò)下的離散時(shí)間系統(tǒng)相比,可以實(shí)現(xiàn)實(shí)時(shí)優(yōu)化,穩(wěn)定性更高.本文通過Moreau-Yosida 正則化近似函數(shù)解決非光滑目標(biāo)函數(shù)最優(yōu)問題,比文獻(xiàn)[24]和文獻(xiàn)[26]中提出的方法更易于實(shí)現(xiàn).結(jié)合文獻(xiàn)[28]中所提算法找到在強(qiáng)連通加權(quán)平衡網(wǎng)絡(luò)下,滿足耦合不等式路徑約束和局部可行集約束的最優(yōu)解.

本文結(jié)構(gòu)安排如下.第1 節(jié)介紹本文考慮的分布式優(yōu)化問題和預(yù)備知識(shí);第2 節(jié)提出應(yīng)用在強(qiáng)連通有向圖的分布式連續(xù)時(shí)間投影算法,并分析證明算法的平衡解為優(yōu)化問題最優(yōu)解的充分必要條件;第3 節(jié)通過數(shù)值實(shí)驗(yàn)驗(yàn)證理論結(jié)果;第4 節(jié)總結(jié)本文的主要結(jié)論和未來研究方向.

符號(hào)說明:R表示實(shí)數(shù)集,Rm和Rmn分別表示m維列向量集和m×n矩陣空間.Im是m維單位方陣.0m是一組元素為0 的m維列向量,1m是一組元素為1 的m維列向量.‖·‖是歐幾里德范數(shù).TS(x) 是x在集合S上的切錐.Ni={j:(j,i)∈E}是節(jié)點(diǎn)i的鄰居集合.給定一個(gè)矩陣A,r ange(A) 表示矩陣A的像,k er(A) 表示矩陣A的核.λmax(A)表示矩陣A的最大特征值.A ?B表示矩陣A和B之間的Kronecker 積.矩陣A ≥0 (A＞0) 時(shí),A為半正定(正定)矩陣,A∈Rmm.是智能體i的入度,是智能體i的出度.

1 問題描述與預(yù)備知識(shí)

1.1 問題描述

考慮如下分布式優(yōu)化問題[14]

通信網(wǎng)絡(luò)是由M個(gè)智能體組成,x i∈Rm是全局決策變量,Xi∈Rm是各智能體的局部可行集,每個(gè)智能體i∈I={1,···,M}對(duì)應(yīng)一個(gè)局部決策變量其中,X0是各智能體局部可行集的交集.其對(duì)應(yīng)的局部目標(biāo)函數(shù)和局部耦合不等式約束分別是f i(xi):Rm →R和gi(xi):Rm →Rn,各智能體只能訪問自己的局部目標(biāo)函數(shù)fi和不等式約束gi,其中,x=col(x1,x2,···,x M).通過分布式連續(xù)時(shí)間投影算法讓各智能體與鄰居節(jié)點(diǎn)信息交互協(xié)同合作,在滿足耦合不等式約束和局部可行集約束下,使各智能體狀態(tài)收斂到全局最優(yōu)解,全局目標(biāo)函數(shù)值最小.

本文對(duì)目標(biāo)函數(shù)、耦合不等式約束和拓?fù)鋱D等作出以下假設(shè).

假設(shè) 1.fi和gi是局部可行集Xi上的非光滑凸函數(shù),其中Xi是閉凸集且? i∈I.

假設(shè) 2.考慮的信息交換圖G是強(qiáng)連通加權(quán)平衡有向圖.

假設(shè) 3.問題 (1) 至少存在一個(gè)有界的解.

注1.若局部Lipschitz 函數(shù)g是凸函數(shù),則?g(x) 在x處的次微分滿足:?g(x)={s∈Rn:g(y)≥s稱為次梯度.

注2.在假設(shè)1 的條件下,函數(shù)非光滑是指目標(biāo)函數(shù)和約束函數(shù)均為非連續(xù)可微函數(shù).我們通過Moreau-Yosida 近似函數(shù),使非光滑函數(shù)轉(zhuǎn)化為連續(xù)可微函數(shù)[28],即

其中,γ＞0,函數(shù)f γ(x),g γ(x) 分別是非光滑凸函數(shù)f(x),g(x) 的Moreau-Yosida 近似函數(shù).根據(jù)文獻(xiàn)[28]和文獻(xiàn)[32]可知,近似后的函數(shù)f γ(x),g γ(x) 為連續(xù)可微的凸函數(shù),并且滿足關(guān)系式supγ＞0fγ(x)=limγ→0fγ(x)=f(x),supγ＞0gγ(x)=limγ→0gγ(x)=g(x).值得注意的是,f(x),g(x) 是凸函數(shù),那么存在唯一的y使y‖2},其中y稱為f在x處的近似算子.

1.2 預(yù)備知識(shí)

定義2.NS(x) 是x在集合S上的法錐[28]

其中,在集合S上的法錐滿足如下性質(zhì):

其中,NX(y)=col(NX(y1),···,NX(yM)).根據(jù)式(10) 中的等式關(guān)系可得,y i=yj,其中,i,j∈I.因此一定存在yi=x*,其中x*∈Rm,? i∈I.則式(8) 可以寫為

等價(jià)于引理1 中的式 (6).

2 分布式連續(xù)時(shí)間投影算法

2.1 算法設(shè)計(jì)

針對(duì)問題 (1),提出如下分布式投影算法.將非光滑目標(biāo)函數(shù)f(x) 和g(x) 代入Moreau-Yosida 近似函數(shù)中,則分布式投影算法可以寫為

對(duì)比文獻(xiàn)[12]中用于離散時(shí)間系統(tǒng)的DIGing算法,第2.1 節(jié)中的算法不僅用到次梯度來保證算法收斂到最優(yōu)解,并且增加積分反饋項(xiàng)來校正由于局部梯度引起的誤差,最終滿足算法在連續(xù)時(shí)間系統(tǒng)中的強(qiáng)連通加權(quán)平衡有向圖的收斂.

引理 2[28].當(dāng)目標(biāo)函數(shù)f局部有界,并且解的集合為非空凸集時(shí),對(duì)于任意初始點(diǎn)x i(0)∈Xi,則每個(gè)智能體xi始終在其局部可行集Xi內(nèi).

2.2 主要結(jié)果

假設(shè)分布式優(yōu)化算法 (15)～(18) 一致收斂的平衡解為c ol(x*,τ*,μ*,s*),在強(qiáng)連通加權(quán)平衡有向通信網(wǎng)絡(luò)下,證明其平衡解為優(yōu)化問題 (1) 的最優(yōu)解需滿足的充要條件.

定理1.在假設(shè)1～3 成立的條件下,滿足式(19) 和式(20) 時(shí),算法 (15)～(18) 的平衡解col(x*,τ*,μ*,s*)是優(yōu)化問題取得最優(yōu)解的充分必要條件,并且x*∈Rm是問題 (1) 的最優(yōu)解.

下面提出的定理2 是根據(jù)文獻(xiàn)[28]證明算法(15)～(18) 的輸出軌跡x收斂于同一個(gè)平衡解,并結(jié)合定理1 的結(jié)論得到的.即分布式投影算法在強(qiáng)連通加權(quán)平衡有向圖網(wǎng)絡(luò)下,算法漸近收斂到優(yōu)化問題 (1) 的最優(yōu)解.

由凸函數(shù)的性質(zhì)可得如下兩個(gè)不等式關(guān)系:

代入定理2 中的設(shè)定條件可知,上式為半正定矩陣.因此能夠得出J(t)≤J(0),進(jìn)而證明了各參數(shù)x,τ,μ,s的有界性.結(jié)合引理2 可知,當(dāng)目標(biāo)函數(shù)f局部有界時(shí),對(duì)于優(yōu)化問題 (1) 的任意初始點(diǎn)x i(0)∈Xi,每個(gè)智能體xi始終在局部可行集Xi內(nèi).

根據(jù)注 2 中提到的Moreau-Yosida 近似函數(shù)和性質(zhì)可知,對(duì)于優(yōu)化問題 (1) 的任意初始解(x(0),時(shí),有等式關(guān)系τ(0),μ(0),s(0)).當(dāng)函數(shù)f,g是凸函數(shù),在局部可行集上是連續(xù)可微的并且有下界[28],那么分布式投影算法 (15)～(18) 的解一定存在.

當(dāng)t →∞時(shí),各狀態(tài)為PX=x,x=1M ?x′,μ=1M ?μ′,可得,即優(yōu)化問題的所有可行解漸近收斂到平衡解,式 (39) 成立.結(jié)合定理1 證明的算法的平衡解為優(yōu)化問題 (1)的充分必要條件可知,分布式投影算法 (15)～(18)中的決策變量x滿足耦合不等式約束和局部可行集約束的條件下最終會(huì)收斂到問題 (1) 的最優(yōu)解.

3 仿真研究

本節(jié)通過數(shù)值實(shí)驗(yàn)來驗(yàn)證強(qiáng)連通有向通信拓?fù)鋱D下的分布式連續(xù)時(shí)間投影算法的有效性.

考慮由4 個(gè)智能體組成的強(qiáng)連通有向通信拓?fù)鋱D,如圖1 所示.局部代價(jià)函數(shù)為f i(x)=‖x-ωi‖,其中,ωi是各智能體對(duì)應(yīng)的目標(biāo)點(diǎn),即

圖1 加權(quán)平衡有向交互圖Fig.1 Weight-balanced directed interaction graph

局部耦合不等式約束為gi(x)=‖x-ω0‖/4-i/4≤0,i∈{1,2,3,4},其全局耦合不等式約束為g(x)=‖x-ω0‖-5/2≤0,其中,ω0=col(4,4) 是耦合不等式約束的中心點(diǎn)[28].定義各智能體的狀態(tài)初始值為x1=col(2,6),x2=col(3,3),x3=col(5,2),x4=col(1,2),令k=4,c1=1.3,c2=1.2.每個(gè)智能體的局部可行集Xi為

由此可以看出,針對(duì)本文所提的分布式優(yōu)化問題 (1),4 個(gè)智能體在局部可行集約束和耦合不等式約束范圍內(nèi)共同協(xié)作找到距離4 個(gè)目標(biāo)點(diǎn)ωi最近的點(diǎn).如圖2 所示,其中三角形表示各智能體xi局部可行集的交集,圓形表示耦合不等式約束的范圍.從仿真圖中可以看出,對(duì)于滿足局部可行集約束和耦合不等式約束情況下的任意初始值,各智能體最終收斂到分布式優(yōu)化問題的最優(yōu)解.

圖2 狀態(tài) xi 的軌跡圖Fig.2 Trajectories graph of state xi

圖3～5 分別表示變量τ,μ,s的運(yùn)動(dòng)軌跡,從圖中我們可知所有變量是一致收斂的,并且μi總是非負(fù)的,仿真算例驗(yàn)證了理論結(jié)果.本文中的算法是利用各智能體在其局部可行集上進(jìn)行投影,不同于文獻(xiàn)[24]中在切錐上的投影,節(jié)約了智能體間的交互、計(jì)算和時(shí)間成本,使算法更快地達(dá)到收斂.其次,連續(xù)時(shí)間系統(tǒng)更具靈活性和實(shí)時(shí)性,可滿足對(duì)實(shí)時(shí)優(yōu)化精度高的實(shí)際應(yīng)用.

圖3 狀態(tài) τi 的軌跡圖Fig.3 Trajectories graph of state τi

圖4 狀態(tài) μi 的軌跡圖Fig.4 Trajectories graph of state μi

圖5 狀態(tài) si 的軌跡圖Fig.5 Trajectories graph of state si

4 結(jié)束語

本文研究了在強(qiáng)連通加權(quán)平衡的有向通信拓?fù)渚W(wǎng)絡(luò)中,目標(biāo)函數(shù)和約束為凸函數(shù),滿足耦合不等式路徑約束和局部可行集約束的情況下,找到了證明算法的平衡解為分布式優(yōu)化問題最優(yōu)解的充分必要條件,并且所提分布式連續(xù)時(shí)間投影算法漸近收斂到全局最小值點(diǎn).結(jié)合文獻(xiàn)[28]中的分布式連續(xù)時(shí)間投影算法設(shè)計(jì),基于在智能體局部可行集上的投影,通過近似函數(shù)將非光滑的目標(biāo)函數(shù)和約束近似為連續(xù)可微的凸函數(shù),構(gòu)造李雅普諾夫函數(shù)并證明算法收斂到分布式優(yōu)化問題的最優(yōu)解.與加權(quán)平衡有向圖相比,分布式算法在加權(quán)不平衡有向圖的設(shè)計(jì)對(duì)系統(tǒng)性能、資源分配等具有更普遍的意義,其收斂性分析也具有更大的挑戰(zhàn).未來的研究方向集中在將分布式投影算法拓展到加權(quán)不平衡有向圖網(wǎng)絡(luò)下,并考慮放縮強(qiáng)連通的假設(shè)條件至一致聯(lián)合連通時(shí)算法收斂的問題.