基于有向圖的分布式連續(xù)時間非光滑耦合約束凸優(yōu)化分析

劉奕葶 馬銘莙 付 俊

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

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

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

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

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

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

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

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

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

符號說明:R表示實數(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é)點i的鄰居集合.給定一個矩陣A,r ange(A) 表示矩陣A的像,k er(A) 表示矩陣A的核.λmax(A)表示矩陣A的最大特征值.A ?B表示矩陣A和B之間的Kronecker 積.矩陣A ≥0 (A＞0) 時,A為半正定(正定)矩陣,A∈Rmm.是智能體i的入度,是智能體i的出度.

1 問題描述與預備知識

1.1 問題描述

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

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

本文對目標函數(shù)、耦合不等式約束和拓撲圖等作出以下假設.

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

假設 2.考慮的信息交換圖G是強連通加權平衡有向圖.

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

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

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

其中,γ＞0,函數(shù)f γ(x),g γ(x) 分別是非光滑凸函數(shù)f(x),g(x) 的Moreau-Yosida 近似函數(shù).根據(jù)文獻[28]和文獻[32]可知,近似后的函數(shù)f γ(x),g γ(x) 為連續(xù)可微的凸函數(shù),并且滿足關系式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 預備知識

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

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

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

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

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

2.1 算法設計

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

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

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

2.2 主要結果

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

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

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

由凸函數(shù)的性質可得如下兩個不等式關系:

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

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

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

3 仿真研究

本節(jié)通過數(shù)值實驗來驗證強連通有向通信拓撲圖下的分布式連續(xù)時間投影算法的有效性.

考慮由4 個智能體組成的強連通有向通信拓撲圖,如圖1 所示.局部代價函數(shù)為f i(x)=‖x-ωi‖,其中,ωi是各智能體對應的目標點,即

圖1 加權平衡有向交互圖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) 是耦合不等式約束的中心點[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.每個智能體的局部可行集Xi為

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

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

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

圖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 結束語

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