權(quán)重平衡有向網(wǎng)絡(luò)下分布式約束優(yōu)化的連續(xù)時間算法設(shè)計

朱亞楠 溫廣輝

0 引言

在過去的幾十年里,多智能體系統(tǒng)的分布式協(xié)調(diào)問題因其在工程、自然、社會科學(xué)等領(lǐng)域的廣泛應(yīng)用，已有大量的研究成果．分布式優(yōu)化作為多智能體系統(tǒng)中的一個重要協(xié)調(diào)問題,其目的是多智能體通過與鄰居之間的相互協(xié)作實現(xiàn)整個網(wǎng)絡(luò)最優(yōu)決策．在分布式優(yōu)化問題的求解方面,早期的工作主要基于迭代格式的離散時間算法．比如,Nedic等將多智能體一致機(jī)制和優(yōu)化方法相結(jié)合,分別設(shè)計了用于求解無約束優(yōu)化和凸交約束優(yōu)化的分布式次梯度算法和分布式次梯度投影算法[1-2]．另外,文獻(xiàn)[3-8]建立了求解等式或不等式約束優(yōu)化的分布式離散時間優(yōu)化算法.

由于連續(xù)時間系統(tǒng)在算法設(shè)計和分析方面的優(yōu)勢,基于連續(xù)時間系統(tǒng)的分布式優(yōu)化算法設(shè)計近年來受到了研究者的廣泛關(guān)注．針對無向網(wǎng)絡(luò)下無約束分布式優(yōu)化問題,文獻(xiàn)[9-10]分別設(shè)計了基于零梯度和一致性和基于牛頓-辛普森一致性的連續(xù)時間算法．文獻(xiàn)[11-12]針對權(quán)重平衡有向網(wǎng)絡(luò)下無約束的情況,從原始對偶的角度出發(fā),分別提出了基于鞍點動力學(xué)和基于負(fù)反饋梯度流的連續(xù)時間算法．為了消除參數(shù)對全局網(wǎng)絡(luò)信息的依賴性,文獻(xiàn)[13]提出了一種自適應(yīng)的連續(xù)時間算法．通過結(jié)合估計左特征向量的一致性協(xié)議和權(quán)重平衡有向網(wǎng)絡(luò)下的連續(xù)時間算法[12],文獻(xiàn)[14]進(jìn)一步給出了權(quán)重非平衡有向網(wǎng)絡(luò)下的連續(xù)時間協(xié)調(diào)算法．相比較無約束的情況,約束優(yōu)化問題在實際中的應(yīng)用更加廣泛[15-20]．考慮到多個局部約束交的情況,文獻(xiàn)[15]設(shè)計了基于二階多智能體系統(tǒng)的分布式優(yōu)化算法．為了避免上述工作中乘子變量的無界性,文獻(xiàn)[16]進(jìn)一步提出了基于原始對偶的連續(xù)時間算法．此外,文獻(xiàn)[17]采用神經(jīng)網(wǎng)絡(luò)動力學(xué)求解局部等式和不等式約束的分布式優(yōu)化問題．最近,文獻(xiàn)[18-20]研究了同時包含局部等式、不等式和閉凸集約束的分布式優(yōu)化問題．對于更多的分布式優(yōu)化算法的工作,讀者可參考一些文獻(xiàn)綜述[21-23].

從上述的工作中可以發(fā)現(xiàn),分布式約束優(yōu)化問題的連續(xù)時間算法設(shè)計主要針對無向網(wǎng)絡(luò)．在有向網(wǎng)絡(luò)下,智能體之間的信息交互往往是不對稱的，這也導(dǎo)致無向網(wǎng)絡(luò)下基于對稱拉普拉斯矩陣的算法通常不再適用有向網(wǎng)絡(luò)的情況．因此,有待進(jìn)一步探討有向網(wǎng)絡(luò)下約束優(yōu)化問題的連續(xù)時間算法設(shè)計．本文考慮一類帶有局部閉凸集約束的分布式優(yōu)化問題,其中網(wǎng)絡(luò)的全局目標(biāo)函數(shù)由智能體的局部目標(biāo)函數(shù)的和構(gòu)成．目的是在權(quán)重平衡有向網(wǎng)絡(luò)下,智能體分布式合作找到該問題的全局最優(yōu)解．對于該問題的研究,文獻(xiàn)[24]給出了基于Fenchel對偶梯度的離散時間算法,該算法的詳細(xì)收斂性分析在文獻(xiàn)[25]中給出．由于獲得Fenchel對偶梯度仍需要求解最優(yōu)化問題,因此很難在迭代中直接使用Fenchel對偶梯度．為此,本文從不精確的Fenchel對偶梯度出發(fā),結(jié)合一致性機(jī)制,提出一類基于奇異攝動系統(tǒng)的分布式連續(xù)時間算法．針對所提出的算法,結(jié)合凸分析和Lyapunov穩(wěn)定性理論,對所提算法進(jìn)行收斂性分析及數(shù)值仿真驗證.

1 預(yù)備知識

本節(jié)給出論文中使用的數(shù)學(xué)符號、代數(shù)圖論及凸分析中的相關(guān)概念和理論預(yù)備知識.

1.1 符號說明

1.2 代數(shù)圖論

1.3 凸分析

根據(jù)投影的定義,可得如下不等式:

(u-PK(u))T(v-PK(u))≤0,?u∈Rn,v∈Rn.

(1)

2 問題描述

考慮一組多智能體求解如下分布式優(yōu)化問題:

(2)

為求解優(yōu)化問題(2),做出如下假設(shè):

假設(shè)1

注1假設(shè)1保證了問題(2)解的存在性和唯一性.

假設(shè)2智能體之間的有向通信網(wǎng)絡(luò)滿足強(qiáng)連通且權(quán)重平衡性.

3 主要結(jié)果

本節(jié)首先將問題(2)轉(zhuǎn)化為等價形式,然后從等價形式的Fenchel對偶問題出發(fā),設(shè)計一類基于奇異攝動系統(tǒng)的分布式連續(xù)時間算法．最后,對所提算法進(jìn)行了詳細(xì)的收斂性分析.

3.1 Fenchel對偶問題

問題(2)等價為

(3)

(4)

其中w=col(w1,w2,…,wN).

等價地,

進(jìn)而,當(dāng)w*是問題(4)的一個最優(yōu)解時,可得

是問題(2)的最優(yōu)解.

(5)

3.2 算法設(shè)計和收斂性分析

(6)

(7)

(8)

證明記col(x*,w*)為系統(tǒng)(7)的一個平衡點,則可得

(9)

(L?In)x*=0Nn.

(10)

注意到

因此,

則在變量y和w下,可重寫系統(tǒng)(7)為

(11)

考慮如下的Lyapunov函數(shù):

則V關(guān)于系統(tǒng)(11)的導(dǎo)數(shù)為

其中

由投影不等式(1),可得不等式:

由f的強(qiáng)凸性,f的Lipschitz連續(xù)性及引理2可分別得:

注意到

根據(jù)引理1中的(Ⅱ)可知成立不等式

λ2‖e‖2-eT(L?In)y+

(12)

(13)

因此,

(14)

再次利用f的強(qiáng)凸性和f的Lipschitz連續(xù)性可得：

結(jié)合f*(w)≥f*(w*),有

(15)

f*(w)-f*(w*)≥(f*(w*))T(w-w*)+

4 數(shù)值仿真

本節(jié)給出一個數(shù)值例子驗證所提算法的有效性．考慮由5個智能體構(gòu)成的通信網(wǎng)絡(luò)如圖1所示．智能體的局部目標(biāo)函數(shù)和局部閉凸集約束給定如下:

f1=(x-1)2+e0.5x,f2=(x-4)2,f3=x2,

f4=x2+e0.1x,f5=x2+e-0.1x,

Ω1=[-1,1],Ω2=[-2,2],Ω3=[0,2],

Ω4=[-5,1],Ω5=[0,3].

在這個優(yōu)化問題中,可以計算出m=2和M=2+0.25e0.5．圖1中的通信網(wǎng)絡(luò)的Laplacian矩陣

5 結(jié)論與展望

為求解權(quán)重平衡有向網(wǎng)絡(luò)下分布式凸交優(yōu)化問題的最優(yōu)解,本文從其等價問題的Fenchel對偶問題出發(fā),將投影方法和一致性機(jī)制相結(jié)合,設(shè)計了基于奇異攝動的分布式連續(xù)時間算法．然后,結(jié)合凸分析方法和Lyapunov穩(wěn)定性理論證明了所提算法的收斂性,并從數(shù)值仿真進(jìn)一步驗證了算法的有效性．本文僅考慮了有向網(wǎng)絡(luò)為權(quán)重平衡的情況．未來將進(jìn)一步探討權(quán)重非平衡網(wǎng)絡(luò)下分布式約束優(yōu)化的連續(xù)時間算法設(shè)計.