基于有向圖的分布式連續時間非光滑耦合約束凸優化分析

劉奕葶 馬銘莙 付 俊

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

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

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

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

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

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

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

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

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

符號說明:R表示實數集,Rm和Rmn分別表示m維列向量集和m×n矩陣空間.Im是m維單位方陣.0m是一組元素為0 的m維列向量,1m是一組元素為1 的m維列向量.‖·‖是歐幾里德范數.TS(x) 是x在集合S上的切錐.Ni={j:(j,i)∈E}是節點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 問題描述

考慮如下分布式優化問題[14]

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

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

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

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

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

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

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

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

1.2 預備知識

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

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

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

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

2 分布式連續時間投影算法

2.1 算法設計

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

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

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

2.2 主要結果

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

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

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

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

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

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

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

3 仿真研究

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

考慮由4 個智能體組成的強連通有向通信拓撲圖,如圖1 所示.局部代價函數為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].定義各智能體的狀態初始值為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為

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

圖2 狀態 xi 的軌跡圖Fig.2 Trajectories graph of state xi

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

圖3 狀態 τi 的軌跡圖Fig.3 Trajectories graph of state τi

圖4 狀態 μi 的軌跡圖Fig.4 Trajectories graph of state μi

圖5 狀態 si 的軌跡圖Fig.5 Trajectories graph of state si

4 結束語

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