袁君萍， 李德權(quán)

(安徽理工大學(xué)數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001)

0 引 言

關(guān)于整個(gè)網(wǎng)絡(luò)的凸函數(shù)之和的分布式優(yōu)化問(wèn)題是網(wǎng)絡(luò)化系統(tǒng)數(shù)據(jù)處理的一類重要問(wèn)題，近年來(lái)在連續(xù)時(shí)間多個(gè)體分布式優(yōu)化上已有較多成熟的成果[1～7]。目前，一類重要分布式優(yōu)化問(wèn)題是：關(guān)于整個(gè)網(wǎng)絡(luò)的凸目標(biāo)函數(shù)可以表示為網(wǎng)絡(luò)中所有個(gè)體各自的凸目標(biāo)函數(shù)之和，每個(gè)個(gè)體僅知其自身的凸目標(biāo)函數(shù)，且只能通過(guò)與其鄰居個(gè)體進(jìn)行信息交換協(xié)同地解決該優(yōu)化問(wèn)題。但在許多實(shí)際應(yīng)用中，當(dāng)個(gè)體間進(jìn)行信息交換時(shí)，由于通信信道容量有限，在實(shí)際數(shù)字網(wǎng)絡(luò)中要求個(gè)體之間交換的實(shí)時(shí)數(shù)據(jù)具有無(wú)限精度是難以保證的[8]。因此，研究凸優(yōu)化問(wèn)題的分布式量化優(yōu)化算法具有較強(qiáng)的實(shí)際應(yīng)用價(jià)值。采用了邊拉普拉斯[9～10]，將連邊個(gè)體間的相對(duì)狀態(tài)信息轉(zhuǎn)化為個(gè)體間的邊狀態(tài)信息，進(jìn)而對(duì)邊狀態(tài)信息采取量化[11]。在實(shí)際應(yīng)用中系統(tǒng)往往允許存在一定的誤差,只要系統(tǒng)狀態(tài)能夠控制在一定的范圍內(nèi)即可,沒(méi)有必要漸近收斂于平衡點(diǎn)[12]。根據(jù)魯棒穩(wěn)定條件，給出了具體的系統(tǒng)魯棒性設(shè)計(jì)算法[13]，介紹了各種一致性協(xié)議和不同的收斂性分析方法。

系統(tǒng)的一致有界性控制是指通過(guò)一定的控制策略,將系統(tǒng)狀態(tài)控制在一個(gè)與初始時(shí)刻無(wú)關(guān)的范圍內(nèi)[14]。因此,針對(duì)實(shí)際要求,可以不用實(shí)現(xiàn)將系統(tǒng)狀態(tài)精確控制收斂到某幾個(gè)最優(yōu)點(diǎn)上去,轉(zhuǎn)而設(shè)計(jì)算法使網(wǎng)絡(luò)控制系統(tǒng)一致有界.這樣既滿足實(shí)際要求,又可以使得設(shè)計(jì)方法變得可行。個(gè)體狀態(tài)信息無(wú)約束情況下的邊狀態(tài)信息量化形式，通過(guò)改造合適的Lyapunov函數(shù)并采用了非光滑分析方法來(lái)分析其收斂性；最后證明了該算法是一致有界的。

1 背景知識(shí)

1.1 符 號(hào)

R表示實(shí)數(shù)集，Rn表示n維實(shí)列向量集，Rn×m表示n×m實(shí)矩陣集，In表示n×n單位矩陣，1n表示n×1全1向量，0n表示n×1全0向量，(·)T表示轉(zhuǎn)置。矩陣A的秩、值域、最大特征值及最小非零特征值分別記為rank(A)、range(A)、λmax(A)及λmin(A)，A?B表示矩陣A和B的Kronecker積。此外，‖·‖表示Euclidean范數(shù)，A>0(A≥0)表示矩陣A∈Rn×n是正定的(半正定的)。

1.2 代數(shù)圖論

考慮由N個(gè)節(jié)點(diǎn)構(gòu)成的無(wú)向圖G，點(diǎn)集v={1,2,…,N}，整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)間M的條連邊構(gòu)成邊集ε={(i,j):i,j∈v}?v×v，一條邊代表一個(gè)互異點(diǎn)的點(diǎn)對(duì)，如(i,j)。圖G是連通的當(dāng)且僅當(dāng)任意兩個(gè)互異點(diǎn)間存在一條途徑。文中考慮的圖G是不含環(huán)的。定義ε中的每條邊的一個(gè)端點(diǎn)為正的，另一端點(diǎn)為負(fù)的?，F(xiàn)在考慮ε中的第k條邊，k{1,2,…,M}，這條邊連接的兩個(gè)點(diǎn)是i,j點(diǎn)。Ni表示點(diǎn)i的鄰居點(diǎn)集，Ni={j∈v:(i,j)∈ε}。

圖G的關(guān)聯(lián)矩陣D=[dik]N×M與Laplacian陣L分別定義為

1.3 量化器

篇幅有限，量化器的設(shè)計(jì)詳見(jiàn)[11]。

2 問(wèn)題描述及優(yōu)化算法

2.1 問(wèn)題描述

(1)

其中，每個(gè)個(gè)體只使用自己的局部代價(jià)函數(shù)，自己的狀態(tài)信息xi(t)及從鄰居個(gè)體接受量化相對(duì)狀態(tài)信息Q(xi-xj),j∈Ni。若點(diǎn)i,j由邊l連接，則有

對(duì)所有的l=1,2,…,M,t→∞,zl→0。z(t)=DTx(t)，其中z(t)=[z1,…,zM]T,x(t)=[x1,…,xN]T。

若圖G是連通圖，則顯然有z=0就可以保證所有的個(gè)體狀態(tài)一致。因?yàn)閦=0，則Lx=DDTx=Dz=0。因此，若圖是連通的，z=0就表示了x1=x2=…=xN。

假設(shè)2.1：考慮優(yōu)化問(wèn)題(1)。

1)圖G連通且無(wú)向。2)對(duì)所有的i∈{1,…,N}，fi連續(xù)且凸。3)問(wèn)題(1)至少存在一個(gè)最優(yōu)解。

假設(shè)2.2：在每個(gè)節(jié)點(diǎn)xi∈Rq處對(duì)fi(x)的次梯度gi，都存在li′<∞使得‖gi‖

假設(shè)2.3：在每個(gè)節(jié)點(diǎn)xi∈Rq處對(duì)fi(x)的次梯度gi，都存在l>0滿足‖gi(x)-gi(y)‖≤l‖x-y‖,?x,y∈Rd，即gi滿足Lipschitz條件。

引理2.1： 假定假設(shè)2.1成立。x*∈Rq是問(wèn)題(1)的最優(yōu)解，當(dāng)且僅當(dāng)存在X*=1N?x*∈RNq及λ*∈RNq，使得

0Na∈{p:p=g(X*)+αlλ*,g(X*)∈?F(X*)}

(2a)

dTX*=0Mq*

(2b)

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

考慮優(yōu)化問(wèn)題(1)，其中個(gè)體i的優(yōu)化算法如下：

(3a)

?fi(xi(t))

(3b)

其中，t≥0,i∈{1,…,N},xi(0)∈Rq,λi(0)∈Rq,ai.j是圖G的鄰接矩陣的(i,j)元。

3 收斂性分析

在這部分，將給出算法的收斂性分析。

(4)

其中，

l=L?Iq∈RNq×Nq,d=D?Iq∈RNq×Mq,L是Laplacian陣，D是關(guān)聯(lián)矩陣，0<α<1/λmax(L)。

X*∈RNq,λ*∈RNq是滿足(2)的向量，定義Lyapunov函數(shù)如下

(5)

g(X*)∈?F(X*)，使得g(X*)+αlλ*=0,LFV*(X,λ)是V*的集值李導(dǎo)數(shù)。

引理4.2： 考慮算法(3)，假定假設(shè)2.1、假設(shè)2.2及假設(shè)2.3成立，V*(X,λ)由(5)定義；

(i)V*(X,λ)正定，且當(dāng)且僅當(dāng)(X,λ)=(X*,λ*)時(shí)V*(X,λ)=0；

(ii)a∈LFV*(X,λ)，則存在g(X)∈?F(X)使得

α(2(l′+α)‖lX‖)‖l‖+

‖eTdT(2αl-I)‖) )-

‖X-X*‖(λmax(αl-α2l)‖X-X*‖-

α‖eTdT‖(‖(αl+2I)‖+2l))

證明： (i)由[7]可知結(jié)論成立；(ii)V*(X,λ)關(guān)于X的廣義梯度是

?XV*(X,λ)={p:p=γ(X)+αlX+αlλ+X-

X*-(g(X*)+αlλ*),γ(X)∈?f(X)}

(6)

V*(X,λ)關(guān)于λ的梯度是λV*(X,λ)=

αlX+λ-λ*

(7)

LFV*(X,λ)={a:?v∈κ[F](X,λ),使得a=[pT,(λV*(X,λ))T]v對(duì)所有的p∈?XV*(X,λ)}。

其中，κ[F](X,λ)、?XV*(X,λ)、λV*(X,λ)分別由(4)、(6)、(7)定義。

假設(shè)a∈LFV*(X,λ)。存在g(X)∈?f(X),使得[pT,(λV*(X,λ))T]v=a對(duì)所有的γ(X)∈?f(X)成立，其中

p=γ(X)+αlX+αlλ+X-X*-(g(X*)+

當(dāng)γ(X)=g(X)∈?f(X)時(shí)，則[pT,(λV*(X,λ))T]v=a成立。因此，存在g(X)∈?f(X)使得

a=(g(X)+αlX+αlλ+X-X*-(g(X*)+

αlλ*))T(-αdQ(dTX)-αdQ(dTλ)-g(X))+

(αlX+λ-λ*)TαdQ(dTX)

e為量化誤差，

Q(dTX)=dTX-e,Q(dTλ)=dTλ-e,a=

(g(X)+αlX+αlλ+X-X*-(g(X*)+

αlλ*))T(-αlX-αlλ-g(X)+2αde)+

(αlX+λ-λ*)T(αlX-αde)

為便于后面分析，將a拆分為a1和a2，這里a2為含量化誤差的項(xiàng)：

a=(g(X)+αlX+αlλ+X-X*-(g(X*)+

αlλ*))T(-αlX-αlλ-g(X))+

(αlX+λ-λ*)T

αlX+α(de)T(2g(X))+2αlλ+2(X-X*)-

2g(X*)-2αlλ*-λ+λ*+αlX)=a1+a2

其中：

a1=J1+J2+J3,a2=α(de)T(2g(X)+2αlλ+

2(X-X*)-2g(X*)-2αlλ*-λ+λ*+

αlX)=α(de)T(2(g(X)-g(X*))+

2αl(λ-λ*)+2(X-X*)-(λ+λ*)+αlX)

J2(X,λ)=-(g(X*)+αlλ*)T(-αlX-αl-

g(X)),J3(X,)=(αlX+λ-λ*)TαlX

J1(X,λ)=-(g(X)+αlX+αlλ+X-X*)T(αlX+

αlλ+g(X))=-‖g(X)+αlX+αlλ‖2-

(X-X*)T(αlX+αlλ+g(X))≤

-(‖g(X)+αlX‖2-‖αl‖)2-

(X-X*)T(αlX+αlλ+g(X))=

-‖g(X)+αlX‖2-‖αl(λ-λ*)‖2+

2‖g(X)+αlX‖·‖αl(λ-λ*)‖-

(X-X*)T(αlX+αlλ+g(X))

又因?yàn)?‖g(X)+αlX‖2≤0，所以

J1(X,λ)≤-‖αl(λ-λ*)‖2+2‖g(X)+

αlX‖·‖αl(λ-λ*)‖-

(X-X*)T(αlX+αlλ+g(X))

J2(X,λ)=-(g(X*)+αlλ*)T(X-αlX-αlλ-

g(X)-X)=-(g(X*)+αlλ*)T(X-

αlX-αlλ-g(X)-X*)-(g(X*)+

αlλ*)T(X*-X)

注意到g(X*)∈?F(X*),使得X*-(X*-g(X*)-αlλ*)=0，即-g(X*)-αlλ*=0。

J2(X,λ)≤-(g(X*)+αlλ*)T(X*-X)=

-g(X*)T(X*-X)+α(lλ*)TX

J1(X,λ)+J2(X,λ)≤-‖αl(λ-λ*)‖2+

2‖g(X)+αlX‖·‖αl(λ-λ*)‖-

(X-X*)T(αlX+αlλ+g(X))-

g(X*)T(X*-X)+α(lλ*)TX≤

-‖αl(λ-λ*)‖2+2‖g(X)+

αlX‖·‖αl(λ-λ*)‖-

(X-X*)T(g(X)-g(X*))-αXTlX-

αXTl(λ-λ*)

由假設(shè)F(X)是凸函數(shù)，可得(X-X*)T(g(X)-g(X*))≥0，所以

a1=J1+J2+J3≤-‖αl(λ-λ*)‖2+

2‖g(X)+αlX‖·‖αl(λ-λ*)‖-

αXTlX-αXTl(λ-λ*)+(αlX+λ-λ*)TαlX=

-‖αl(λ-λ*)‖2+2‖g(X)+αlX‖·

‖αl(λ-λ*)‖+XT(α2l2-αl)X=

-‖αl(λ-λ*)‖2+2‖g(X)+αlX‖·

‖αl(λ-λ*)‖+(X-X*)T(α2l2-αl) (X-X*)≤-‖αl(λ-λ*)‖2+2‖g(X)+

αlX‖·‖αl(λ-λ*)‖+

λmax(α2l2-αl) ‖X-X*‖2

αlX‖·‖αl(λ-λ*)‖+

λmax(α2l2-αl)‖X-X*‖2≤

αlX‖·‖l‖·‖λ-λ*‖+

λmax(α2l2-αl)‖X-X*‖2

由假設(shè)2.2次梯度有界，‖g(X)‖≤l′，所以

‖g(X)+αlX‖≤‖g(X)‖+α‖lX‖≤

l′+α‖lX‖

α‖lX‖)·‖l‖·‖λ-λ*‖-

λmax(αl-α2l2)‖X-X*‖2

a2=α(de)T(2(g(X)-g(X*))+

2αl(λ-λ*)+2(X-X*)-(λ+λ*)+

αl(X)=2αeTdT(g(X)-g(X*))+

αeTdT(2αl-I)(λ-λ*)+

αeTdT(αl+2I)(X-X*)≤

2α‖eTdT‖·‖g(X)-g(X*)‖+

α‖eTdT(2αl-I)‖·‖λ-λ*‖+

α‖eTdT(αl+2I)‖·‖X-X*‖

由假設(shè)2.3Lipschitz條件，‖g(X)-g(X*)‖≤l‖X-X*‖,進(jìn)而可得

a2≤2αl‖eTdT‖·‖X-X*‖+

α‖eTdT(2αl-I)‖·‖λ-λ*‖+

α‖eTdT(αl+2I)‖·‖X-X*‖=

α(2l‖eTdT‖+‖eTdT(αl+2I)‖)‖X-

X*‖+α‖eTdT(2αl-I)‖·‖λ-λ*‖

綜上分析，最終得到

λmax(αl-α2l2)‖X-X*‖2+2α(l′+

α‖lX‖)·‖l‖·‖λ-λ*‖+

α‖eTdT(2αl-I)‖·‖λ-λ*‖+

α(2l‖eTdT‖+‖eTdT(αl+2I)‖)‖X-

X*‖=-‖X-X*‖(λmax(αl-α2l2)‖X-

X*‖-α(2l‖eTdT‖+‖eTdT(αl+2I)‖))-

2α(l′+α‖lX‖)·‖l‖-α‖eTdT(2αl-I‖)

4 主要結(jié)論

通過(guò)收斂性分析證明可以得到以下結(jié)論：當(dāng)

λmax(αl-α2l2)‖X-X*‖>α(2l‖eTdT‖+

‖eTdT(αl+2I)‖)

‖l‖+α‖eTdT(2αl-I)‖

同時(shí)成立時(shí)，若a<0則系統(tǒng)會(huì)收斂到一定的范圍內(nèi)；當(dāng)這兩者有一項(xiàng)不成立而造成a≥0或兩項(xiàng)均不成立時(shí)，則個(gè)體狀態(tài)會(huì)在上述收斂范圍內(nèi)震蕩也可能越出收斂范圍，但是越界之后由于a<0，于是便會(huì)重新收斂到該范圍。收斂效果與量化器的設(shè)計(jì)有關(guān)，往往量化誤差越大，則收斂效果越差，收斂上界往往隨著量化誤差上界的減小而減小。在實(shí)際應(yīng)用中，可以根據(jù)實(shí)際需求來(lái)設(shè)計(jì)量化器的最大量化誤差。

5 結(jié) 語(yǔ)

研究了分布式多個(gè)體量化問(wèn)題，用邊laplacian將個(gè)體的狀態(tài)信息轉(zhuǎn)化為個(gè)體間邊的狀態(tài)信息，并對(duì)邊狀態(tài)信息采取量化，收斂性分析中采用了非光滑分析，最終證明了該算法是一致有界的，個(gè)體狀態(tài)會(huì)收斂到一定的范圍內(nèi)。但是仍有很多地方可以進(jìn)一步研究，比如通過(guò)量化器的設(shè)計(jì)讓收斂范圍進(jìn)一步縮小、在不影響收斂速率的基礎(chǔ)上通過(guò)邊laplacian來(lái)簡(jiǎn)化信息交流圖。

[1] Wang J, Elia N. Control approach to distributed optimization[C].Communication, Control, and Computing. 2010:557-561.

[2] Gharesifard B, Cortes J. Distributed Continuous-Time Convex Optimization on Weight-Balanced Digraphs[J]. IEEE Transactions on Automatic Control, 2014, 59(3):781-786.

[3] Shi G, Johansson K H, Hong Y. Reaching an Optimal Consensus: Dynamical Systems That Compute Intersections of Convex Sets[J]. IEEE Transactions on Automatic Control, 2013, 58(3):610-622.

[4] Yi P, Hong Y, Liu F. Distributed gradient algorithm for constrained optimization with application to load sharing in power systems ☆[J]. Systems & Control Letters, 2015, 83(711):45-52.

[5] Kia S S, Cortés J, Martínez S. Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication ☆[J]. Automatica, 2015, 55:254-264.

[6] Liu S, Qiu Z, Xie L. Continuous-time Distributed Convex Optimization with Set Constraints[J]. IFAC Proceedings Volumes, 2014, 47(3):9762-9767.

[7] Zeng X, Yi P, Hong Y. Distributed Continuous-Time Algorithm for Constrained Convex Optimizations via Nonsmooth Analysis Approach[J]. IEEE Transactions on Automatic Control, 2015, PP(99):1-1.

[8] Jiang Z, Liu T. Quantized Nonlinear Control | A Survey[J]. Acta Automatica Sinica, 2013, 39(11): 1820-1830.

[9] Zelazo D, Rahmani A, Sandhu J, et al. Decentralized formation control via the edge Laplacian[J]. 2008, 44(5):783-788.

[10] Zeng Z, Wang X, Zheng Z. Convergence analysis using the edge Laplacian: Robust consensus of nonlinear multi‐agent systems via ISS method[J]. International Journal of Robust & Nonlinear Control, 2016, 26(5):1051-1072.

[11] Zeng Z, Wang X, Zheng Z, et al. Edge Agreement of Multi-agent System with Quantized Measurements via the Directed Edge Laplacian[J]. Iet Control Theory and Applications, 2015, 10(13): 1583-1589.

[12] 徐建軍, 閆麗梅, 趙玉峰. 不確定線性動(dòng)態(tài)控制系統(tǒng)的魯棒性設(shè)計(jì)方法[J]. 佳木斯大學(xué)學(xué)報(bào)(自然科學(xué)版), 2001, 19(4):401-403.

[13] 楊文, 汪小帆, 李翔. 一致性問(wèn)題綜述[C].中國(guó)控制會(huì)議. 2006.

[14] 劉俊豪, 張皓, 陳啟軍. 具有均勻量化器的非線性網(wǎng)絡(luò)控制系統(tǒng)的一致有界性[J]. 控制理論與應(yīng)用, 2012, 29(11):1388-1396.