楊 濤 徐 磊 易新蕾 張圣軍 陳蕊娟 李渝哲

在多智能體系統(tǒng)中,每個(gè)智能體(節(jié)點(diǎn))都具有一個(gè)局部成本函數(shù),分布式優(yōu)化的目標(biāo)是使由局部成本函數(shù)之和所構(gòu)成的全局成本函數(shù)最小.分布式優(yōu)化的研究由來已久,至少可以追溯到[1?2].近年來,由于其在電力系統(tǒng)、機(jī)器學(xué)習(xí)和傳感器網(wǎng)絡(luò)等領(lǐng)域的廣泛應(yīng)用,這一研究重新引起了關(guān)注.研究者設(shè)計(jì)了多種分布式優(yōu)化算法,詳見綜述文章[3?10],大致可分為離散時(shí)間算法和連續(xù)時(shí)間算法.

現(xiàn)有的大多數(shù)離散時(shí)間算法均基于一致性算法和分布式次梯度下降(Distributed gradient descent,DGD)算法[11?15].盡管DGD 算法可以處理非光滑凸函數(shù)的分布式優(yōu)化問題,并在通訊延遲、丟包等多個(gè)方向上進(jìn)行擴(kuò)展以處理更為實(shí)際的情況,但由于使用了衰減步長,因此收斂速度較慢.在步長固定的情況下,雖然DGD 算法收斂速度快,但只能收斂到最小值點(diǎn)的鄰域[16?17].最近的研究集中在利用歷史信息來設(shè)計(jì)具有固定步長的加速算法.具體而言,文獻(xiàn)[18?19]中提出的算法是基于比例積分(Proportional integral,PI)控制策略,文獻(xiàn)[20?25]中提出的算法是基于分布式不精確梯度算法和分布式動態(tài)平均梯度跟蹤技術(shù)[26].現(xiàn)有的連續(xù)時(shí)間算法可以分為兩類:第一類是文獻(xiàn)[27?29]中提出的基于梯度的算法,這類算法本質(zhì)上都是基于PI 控制策略,其中每個(gè)智能體使用一個(gè)輔助狀態(tài)(積分反饋)來校正由不同局部梯度引起的誤差;第二類算法使用二階Hessian 信息,例如文獻(xiàn)[30?32].

為了避免連續(xù)通信和減少通信負(fù)擔(dān),事件觸發(fā)通信和控制的思想最初是針對單個(gè)系統(tǒng)[33?35]提出的.后來這種思想被應(yīng)用到分布式一致性問題[36?42].近年來,研究者提出了基于事件觸發(fā)通信的分布式優(yōu)化算法[29,43?50].文獻(xiàn)[29]提出了一種不存在Zeno行為[51]的事件觸發(fā)算法,即在有限時(shí)間內(nèi)不會觸發(fā)無限多次事件,并針對無向連通圖,在局部成本函數(shù)強(qiáng)凸以及梯度局部Lipschitz 且可微的條件下,證明了算法指數(shù)收斂到最小值點(diǎn)的鄰域.受文獻(xiàn)[30]提出的零梯度和 (Zero-gradient-sum,ZGS)算法的啟發(fā),文獻(xiàn)[44]提出周期性的事件觸發(fā)機(jī)制;文獻(xiàn)[45]則設(shè)計(jì)了基于動態(tài)事件觸發(fā)的ZGS 算法.針對無向連通圖或權(quán)平衡強(qiáng)連通的有向圖,在局部成本函數(shù)強(qiáng)凸且具有局部Lipschitz Hessians 的條件下,證明了算法的指數(shù)收斂性.

本文提出了兩種基于比例積分策略的分布式優(yōu)化算法,并證明了算法的收斂性.在此基礎(chǔ)上,為了減少通信負(fù)擔(dān),我們提出了基于事件觸發(fā)的分布式優(yōu)化算法,并證明了提出的基于事件觸發(fā)的優(yōu)化算法不存在Zeno 行為,且保持了與連續(xù)通信下分布式優(yōu)化算法相同的收斂性.文獻(xiàn)[29]提出的事件觸發(fā)算法只有在局部成本函數(shù)強(qiáng)凸且具有局部Lipschitz梯度的條件下收斂到全局最小值點(diǎn)的一個(gè)鄰域,而我們提出的算法在局部成本函數(shù)可微且凸的條件下,即可精確地指數(shù)收斂到唯一的全局最小值點(diǎn).與文獻(xiàn)[46]中提出的算法相比,我們提出的算法更簡單,因?yàn)樵趫?zhí)行文獻(xiàn)[46]中的算法時(shí)需要一些特殊設(shè)計(jì)的增益參數(shù).與文獻(xiàn)[44?45]中提出的基于二階Hessian 信息的事件觸發(fā)ZGS 算法相比,我們提出的算法是基于一階梯度的,易于實(shí)現(xiàn).此外,ZGS 算法需要特殊的初始化,而我們提出的算法允許任意初始化.

本文其余部分安排如下.第1 節(jié)介紹圖論的基礎(chǔ)知識.第2 節(jié)介紹本文所考慮的分布式優(yōu)化問題.第3 節(jié)提出兩種基于PI 控制策略的分布式優(yōu)化算法,并分析所提算法的收斂性.第4 節(jié)提出基于事件觸發(fā)通信機(jī)制的分布式優(yōu)化算法并分析其收斂性.第5 節(jié)利用數(shù)值仿真驗(yàn)證理論結(jié)果.第6 節(jié)總結(jié)本文的主要結(jié)果并介紹未來的研究方向.

1 基礎(chǔ)概念

在這一部分,我們介紹圖論的一些基本知識[52].考慮一個(gè)包含N個(gè)智能體的無向圖G=(V,E,A),其中V={1,2,···,N}表示智能體的集合,E={(i,j):表示邊的集合,A=[aij]∈RN×N表示加權(quán)鄰接矩陣,其中,當(dāng) (i,j)∈E時(shí),aij >0 ;當(dāng)(i,j)∈/E時(shí),aij=0 .在本文中,我們還假設(shè)圖中沒有自環(huán)邊,即對于所有的i ∈V,aii=0 .智能體i的鄰居集合定義為Ni={j ∈V|aij>0}.在無向圖中從節(jié)點(diǎn)i1到節(jié)點(diǎn)ik的路徑是指存在節(jié)點(diǎn)序列i1,···,ik,使得 (ij,ij+1)∈E,j=1,···,k ?1 .

對于無向加權(quán)圖G,加權(quán)Laplacian 矩陣L=的定義是對于,有Lij=?aij,因此,Laplacian 矩陣的行和為零.如果無向加權(quán)圖G是連通的,則Laplacian 矩陣L有唯一的0 特征值,其對應(yīng)的右特征向量為1,其他所有特征值均大于零.

符號說明:給定一個(gè)矩陣A,AT表示其轉(zhuǎn)置矩陣.對稱矩陣A是半正(負(fù))定的當(dāng)且僅當(dāng)其所有特征值均為非負(fù)(非正)時(shí).給定兩個(gè)對稱矩陣M,N,M ≤N意味著M ?N是半負(fù)定的.記號A ?B表示矩陣A和B之間的Kronecker 積.ρ(·) 代表矩陣的譜半徑,ρ2(·) 表示非負(fù)矩陣的最小正特征值.In表示維數(shù)為n×n的單位矩陣.1n表示n維的列向量,其每個(gè)元素都為1.∥·∥表示向量的歐幾里德范數(shù)或矩陣的誘導(dǎo)2 范數(shù).給定一個(gè)向量[a1,···,aN]T∈RN,diag{a1,···,aN}是第i個(gè)對角線元素為ai的對角矩陣.對于列向量x1,x2,···,xN,那么由其組成的堆棧列向量用 [x1,x2,···,xN] 表示.

2 問題描述

考慮由N個(gè)智能體組成的網(wǎng)絡(luò),每個(gè)智能體都有一個(gè)局部凸函數(shù)fi:Rn →R,i ∈V.所有智能體共同協(xié)作以找到一個(gè)最小值點(diǎn)x?,使全局成本函數(shù)f(x)=最小,即:

智能體之間的通信用無向加權(quán)圖G=(V,E,A)來描述,其中V={1,2,···,N}是智能體的集合,E ?V ×V是邊的集合,A是加權(quán)鄰接矩陣.

如引言部分所述,為了避免智能體之間的連續(xù)通信,研究者設(shè)計(jì)了一些分布式事件觸發(fā)算法.然而,大多數(shù)現(xiàn)有的算法要么需要特殊的初始化,要么只收斂到全局最小值點(diǎn)的一個(gè)鄰域,這些啟發(fā)了本文的研究.更具體地說,我們的目標(biāo)是設(shè)計(jì)任意初始化的事件觸發(fā)算法,并精確地收斂到全局最小值點(diǎn).

我們對局部和全局成本函數(shù)作出以下假設(shè):

假設(shè)1.對每個(gè)i ∈V,局部成本函數(shù)fi(x) 是連續(xù)可微凸函數(shù).此外,的全局最小值是有界的.

假設(shè)2.全局成本函數(shù)f(x)=關(guān)于全局最小值點(diǎn)x?是mf-(有限)強(qiáng)凸的,即存在常數(shù)mf >0,使得,對任意的x∈Rn成立.

假設(shè)3.對于每個(gè)i ∈V,局部成本函數(shù)fi(x) 具有局部Lipschitz 梯度,即對任意緊集D ?Rn,存在常數(shù)Mi(D)>0,使得

其中,Mi(D) 稱為函數(shù)fi(x) 在緊集D上的Lipschitz常數(shù).

在假設(shè)1 的條件下,分布式優(yōu)化問題(1)的全局最小值點(diǎn)x?可能不唯一.但是,如果假設(shè)2 成立,則很容易證明全局最小值點(diǎn)x?是唯一的.與大多數(shù)文獻(xiàn)中局部成本函數(shù)是強(qiáng)凸的假設(shè)相比,這種假設(shè)的限制較小.詳細(xì)討論,請參見文獻(xiàn)[18,46],假設(shè)3 在現(xiàn)有文獻(xiàn)中也被廣泛使用.

3 基于PI 的分布式優(yōu)化算法

針對問題(1),我們提出兩種基于PI 反饋策略的分布式優(yōu)化算法,其中xi(t)∈Rn表示第i個(gè)節(jié)點(diǎn)在時(shí)刻t對全局最小值點(diǎn)x?的一個(gè)估計(jì),積分項(xiàng)qi(t)∈Rn是用來校正第i個(gè)節(jié)點(diǎn)由于固定步長所產(chǎn)生的誤差.第一種算法如下:

算法(2)的收斂性如下:

定理 1.假設(shè)無向圖是連通的,并且假設(shè)1 成立.如果每個(gè)智能體i ∈V運(yùn)行分布式優(yōu)化算法(2),則有:

1) 每個(gè)xi(t),i ∈V,漸近收斂到全局最小值點(diǎn)x?;

2) 如果假設(shè)2～ 3 也成立,則每個(gè)xi(t),i ∈V,以不小于的速率指數(shù)收斂到唯一的全局最小值點(diǎn)x?,其中?2和?3是兩個(gè)正常數(shù),并在證明中給出.

證明.見附錄B.

注 1.算法(2)與文獻(xiàn)[27?28]中所提出的分布式優(yōu)化算法相類似.但是,文獻(xiàn)[27?28]只給出了在凸成本函數(shù)下,算法漸近收斂的結(jié)果.而定理1 給出了在全局成本函數(shù)對最小值點(diǎn)有限強(qiáng)凸的附加條件下,算法指數(shù)收斂的結(jié)果.針對有向圖為權(quán)平衡強(qiáng)連通的情形,當(dāng)局部成本函數(shù)是可微的凸函數(shù)并且具有全局Lipschitz 梯度時(shí),文獻(xiàn)[28]中的定理5.4給出了算法漸近收斂的證明.這里我們考慮的是無向連通圖,在全局成本函數(shù)對全局最小值點(diǎn)是有限強(qiáng)凸的附加條件下,定理1 給出了算法的指數(shù)收斂性.

下面,介紹第二種分布式優(yōu)化算法:

算法(3)的收斂性如下:

定理 2.假設(shè)無向圖是連通的,并且假設(shè)1 成立.如果每個(gè)智能體i ∈V運(yùn)行分布式優(yōu)化算法(3),則有:

1) 每個(gè)xi(t),i ∈V,漸近收斂到全局最小值點(diǎn)x?;

2) 如果假設(shè)2～ 3 也成立,則每個(gè)xi(t),i ∈V,指數(shù)收斂到唯一的全局最小值點(diǎn)x?.

證明.該定理的證明與定理1 的證明相類似,這里不再贅述.

注 2.算法(3)與文獻(xiàn)[29]中所提出的算法相類似.但是,文獻(xiàn)[29]考慮的是局部成本函數(shù)強(qiáng)凸的情況,而本文中只要求全局成本函數(shù)關(guān)于全局最小值點(diǎn)是有限強(qiáng)凸的,是較之更一般的情況.

注 3.算法(2)中xi(0)和qi(0) 均可以任意選擇的,而在算法(3)中,雖然xi(0)可以任意選擇,但要求因此算法(2)對初始條件qi(0)是更為魯棒的.然而,與算法(3)相比,式(2b)需要額外通信qj,因此比算法(3)需要更多的通信開銷.

4 基于事件觸發(fā)的分布式PI 優(yōu)化算法

為了避免智能體之間的連續(xù)通信和減少通信負(fù)擔(dān),將第4 節(jié)所提出的分布式PI 算法與事件觸發(fā)通信相結(jié)合,提出了兩種分布式事件觸發(fā)算法并給出其收斂性分析.首先,基于分布式優(yōu)化算法(2),我們提出第一種事件觸發(fā)算法,描述如下:

分布式事件觸發(fā)算法設(shè)計(jì)中的關(guān)鍵問題是如何構(gòu)造觸發(fā)機(jī)制,以保證提出的算法不存在Zeno 行為,并收斂到全局最小值點(diǎn).

定理 3.假設(shè)無向圖是連通的,并且假設(shè)1 成立.如果每個(gè)智能體i ∈V運(yùn)行分布式事件觸發(fā)算法(4),并通過如下方式確定其觸發(fā)時(shí)間序列:

其中,所有ai,bi,ci,di >0均為設(shè)計(jì)參數(shù),則有:

1) 算法(4)不存在Zeno 行為;xi(t)i ∈V x?

2) 每個(gè),,漸近收斂到全局最小值點(diǎn) ;

3) 如果假設(shè)2～ 3 也成立,則每個(gè)xi(t),i ∈V,以不小于的速率指數(shù)收斂到唯一的全局最小值點(diǎn)x?,其中?4是正常數(shù),并在證明中給出.

證明.見附錄C.

接下來,基于算法(3),我們提出了第二種事件觸發(fā)算法,描述如下所示:

下面的定理給出了與定理3 類似的結(jié)果:

定理 4.假設(shè)無向圖是連通的,并且假設(shè)1 成立.如果每個(gè)智能體i ∈V運(yùn)行分布式事件觸發(fā)算法(6),并通過如下方式確定其觸發(fā)時(shí)間序列:

其中,ai,bi >0 均為設(shè)計(jì)參數(shù),則有:

1) 算法(6)不存在Zeno 行為;

2) 每個(gè)xi(t),i ∈V,漸近收斂到全局最小值點(diǎn)x?;

3) 如果假設(shè)2～ 3 也成立,則每個(gè)xi(t),i ∈V,指數(shù)收斂到唯一的全局最小值點(diǎn)x?.

證明.該定理的證明與定理3 的證明相類似,這里不再贅述.

注 4.基于算法(2)和算法(3),提出了對應(yīng)的事件觸發(fā)算法(4)和算法(6).所提出的事件觸發(fā)通信機(jī)制,受到文獻(xiàn)[37]中時(shí)變觸發(fā)機(jī)制的啟發(fā).與算法(6)的觸發(fā)機(jī)制(7)相比,算法(4)的觸發(fā)機(jī)制(5)更為復(fù)雜且需要額外通信開銷,但是算法(4)的初始條件qi(0) 是可以任意取值的,更為魯棒.

注 5.文獻(xiàn)[29]中定理13 要求所有局部成本函數(shù)強(qiáng)凸,而定理3 和定理4 只要求全局成本函數(shù)有限強(qiáng)凸,并不要求所有的局部成本函數(shù)都如此或強(qiáng)凸.此外,我們提出的算法指數(shù)收斂到全局最小值點(diǎn),而文獻(xiàn)[29]中提出的算法只能收斂到全局最小值點(diǎn)的一個(gè)鄰域.文獻(xiàn)[44?45] 提出的事件觸發(fā)ZGS 算法需要特殊的初始化,而我們提出的算法允許對xi(0) 的任意初始化.

5 仿真實(shí)驗(yàn)

考慮一個(gè)包含50 個(gè)智能體的大規(guī)模網(wǎng)絡(luò),其中局部成本函數(shù)fi具體描述如下:

其中,j=1,2,···,5 .函數(shù)fi(x),i=6,···,10,36,···,40,是非強(qiáng)凸的函數(shù),而全局成本函數(shù)關(guān)于點(diǎn)x?有限強(qiáng)凸.所有局部成本函數(shù)均可微,且具有局部Lipschitz 梯度.隨機(jī)選取一個(gè)包含50 個(gè)節(jié)點(diǎn)的無向連通圖,并針對該網(wǎng)絡(luò)拓?fù)鋱D以及上述定義的成本函數(shù)得到以下兩部分的仿真結(jié)果.

不考慮事件觸發(fā)時(shí),為了更好地體現(xiàn)算法(2),算法(3)與文獻(xiàn)[29?31]所提算法的區(qū)別,我們對這些算法進(jìn)行了仿真比較.通過圖1 可以看出所有算法均為線性收斂.此外,算法(3)的收斂速度相對較快.

圖1 不同算法中的演化Fig.1 The state evolution of in various algorithms

考慮事件觸發(fā)時(shí),對于算法(4),我們隨機(jī)選擇觸發(fā)機(jī)制(5)中的設(shè)計(jì)參數(shù)ai,bi,ci和di.選擇采樣周期為 0.01 s.圖2 展示了智能體 6,16,26,36,46 的狀態(tài)演化過程,從中我們可以清楚地看到每個(gè)智能體都收斂到全局最小值點(diǎn)x?=?0.01214 .在[0,40 s]時(shí)間段內(nèi),上述5 個(gè)智能體分別被觸發(fā)了209,183,161,241,142次.由此可知,事件觸發(fā)算法(4)在仿真中針對上述5 個(gè)節(jié)點(diǎn)避免了大約95.32%的通信開銷.

對于算法(6),我們隨機(jī)選擇觸發(fā)機(jī)制(7)中的設(shè)計(jì)參數(shù)ai和bi.選擇采樣周期為 0.01 s.圖3 展示了智能體 6,16,26,36,46 的狀態(tài)演化過程,從中我們可以清楚地看到所有智能體收斂到全局最小值點(diǎn)x?=?0.01214 .在 [0,40 s] 時(shí)間段內(nèi),上述5 個(gè)智能體分別被觸發(fā)了 114,121,139,94,182 次.由此可知,事件觸發(fā)算法(6)在仿真中針對上述5 個(gè)節(jié)點(diǎn)避免了大約96.75%的通信.與算法(4)所對應(yīng)的結(jié)果相比,智能體被觸發(fā)的次數(shù)更少,因此節(jié)省了更多的通信和計(jì)算量.

圖3 算法(6)中智能體6,16,26,36,46 的狀態(tài)演化Fig.3 State evolutions of agents 6,16,26,36,46 of Algorithm (6)

6 結(jié)論

本文考慮了一類分布式優(yōu)化問題,針對無向連通圖,基于比例積分策略提出了兩類分布式優(yōu)化算法,在局部成本函數(shù)為可微凸函數(shù)的條件下,證明了所提的分布式優(yōu)化算法漸近收斂到全局最小值點(diǎn).當(dāng)局部成本函數(shù)具有局部Lipschitz 梯度,并且全局成本函數(shù)對全局最小值點(diǎn)是強(qiáng)凸時(shí),證明了所提算法指數(shù)收斂到唯一的全局最小值點(diǎn).此外,為了避免智能體之間的連續(xù)通信和減少通信開銷,提出了兩種基于事件觸發(fā)的分布式優(yōu)化算法.證明了所提出的算法不存在Zeno 行為,并且在相對應(yīng)條件下保持了與連接通信下分布式優(yōu)化算法一樣的收斂性.未來的一個(gè)方向是設(shè)計(jì)分布式優(yōu)化算法動態(tài)事件觸發(fā)通信機(jī)制的條件.

附錄A

下面文獻(xiàn)[46]的引理,在后文中指數(shù)收斂的證明中起著重要作用.

引理 1.假設(shè)無向圖是連通的.如果令KN=IN?則有,Laplacian 矩陣L是半正定的,KN1N=0,以及

如下引理是對文獻(xiàn)[18]中性質(zhì) 3.6 的推廣,其中每個(gè)局部成本函數(shù)梯度局部Lipschitz 的假設(shè)放松了原有局部成本函數(shù)梯度全局Lipschitz 的假設(shè),在接下來的證明中也很有用.

引理 2.假設(shè)無向圖是連通的,以及假設(shè)1～ 3 都成立.那么對任意ε>0 以及任意緊的凸集D ?Rn,以及x?∈D,

證明.對任意x ∈DN,對x=u+v進(jìn)行分解,且u=和v=x?u.易知,vT(1N ?In)=0N.其余證明與文獻(xiàn)[18]中性質(zhì) 3.6 的證明相同,這里不再贅述.□

附錄B

定理 1 的證明.1) 在這一部分,我們使用Lyapunov 穩(wěn)定性分析方法.當(dāng)假設(shè)1成立時(shí),每個(gè)xi(t),i ∈V,都漸近收斂到全局最小值點(diǎn)x?,其可能是不唯一的.方便起見,記符號x=[x1,···,xN],q=[q1,···,qN],以及?f(x)=[?f1(x1),···,fN(xN)].則算法(2)可以寫為如下緊湊形式:

考慮如下函數(shù):

V1(x,q)沿軌跡(B1)的導(dǎo)數(shù)滿足:

2) 在這一部分,我們證明當(dāng)假設(shè)2 和3 成立時(shí),算法的指數(shù)收斂性.

我們首先證明對于任意的初始狀態(tài)x(0) 和q(0),存在凸緊集C ?Rn,使得x?∈C和xi(t)∈C,?t ≥0,?i ∈V.集合C的具體形式依賴于x(0),q(0) 和x?,將在后文中給出.

由式(B2)和(B3),對任意t ≥0 和i ∈V,可得:

因此,C={x ∈Rn:||x ?x?∥2≤2V1(x(0),q(0))}是我們要尋找的凸緊集.

類似地,V3(x,q) 沿軌跡(B1)的導(dǎo)數(shù)滿足:

進(jìn)而可得,

由于假設(shè)1～ 3 成立,由引理2 中式(A2)可得,

考慮如下候選Lyapunov 函數(shù)

由(B9)可知,W0(x,q) 沿(B1)的軌跡的導(dǎo)數(shù),滿足如下不等式,

附錄C

1) 在這一部分中,我們通過反證法證明算法(4)不存在Zeno 行為.假設(shè)算法(4)存在Zeno 行為,則存在一個(gè)智能體i ∈V,使得,其中T0>0 是一個(gè)常數(shù).注意到xi(t) 和qi(t) 都是連續(xù)的.因此存在常數(shù)P1>0 和P2>0,使得∥xi(t)∥≤P1和∥qi(t)∥≤P2對所有i ∈V和所有t ∈[0,T0] 都成立.

根據(jù)假設(shè)1 可知f(x) 連續(xù)可微,另外∥xi(t)∥≤P1,?i ∈V,?t ∈[0,T0].因此,存在一個(gè)常數(shù)P3>0 使得∥?f(x)∥≤P3,?t ∈[0,T0].

令C1=2LiiP1+2LiiP2+P3以及C2=2LiiP1.那么,由式(4)可得,

對于給定的觸發(fā)機(jī)制(5),可得?t ≥0,

這與式(C3)相矛盾.因此,事件觸發(fā)算法(4)不存在Zeno行為.

考慮Lyapunov 函數(shù)(B2),可得V1(x,q) 沿軌跡(C6)的導(dǎo)數(shù)滿足:

同時(shí),定義a=max{a1,···,aN,c1,···,cN}>0 .那么由式(5)可得,

由式(B2)可知,

根據(jù)式(C8),(C9)和(C10)可得如下不等式

因此

其中

由式(C10)可得,

根據(jù)式(C7),(C9)和(C12)可得如下不等式

那么,由式(C13)可知,W1(x,q,z) 沿軌跡(C6)的導(dǎo)數(shù)滿足如下不等式,

3) 在這一部分,證明當(dāng)假設(shè)2～ 3 成立時(shí),算法的指數(shù)收斂性.與定理1中2)的證明相類似.

由式(B2),(C14)和(C15),可得對于所有的t ≥0 和i ∈V,有如下不等式成立:

因此,所要尋找的凸緊集為C={x ∈Rn:||x ?x?∥2≤2W1(x(0),q(0),z(0))}.

接下來,由式(B4)可得V2沿軌跡(C6)的導(dǎo)數(shù)滿足

其中,第二個(gè)等式用到了eq的定義,性質(zhì)以及引理1 中(A1)給出的性質(zhì)KNL=L和Cauchy-Schwarz 不等式;第二個(gè)不等式利用引理1 中(A1)給出的性質(zhì)ρ2(L)KN ≤L;最后一個(gè)不等式用到了由假設(shè)3 得到的f(x)具有局部Lipschitz 梯度的事實(shí).

類似地,由(B15)可得V3沿軌跡(C6)的導(dǎo)數(shù)滿足

進(jìn)而可得,

因此,由 ()T[(?f(x)??f())]≥0,式(B8)以及式(C9)和(C16)～ (C17)可得

關(guān)于t ≥0 和所有i ∈V,定義ζi(t)=e?bt和ζ(t)=[ζ1(t),···,ζN(t)].考慮如下候選Lyapunov 函數(shù)

由式(C18)和(C19)可知,W2(x,q,ζ) 沿軌跡(C6)的導(dǎo)數(shù)滿足如下不等式: