基于非光滑分析的凸優(yōu)化問題分布式量化算法①

袁君萍， 李德權

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

0 引 言

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

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

1 背景知識

1.1 符 號

R表示實數(shù)集，Rn表示n維實列向量集，Rn×m表示n×m實矩陣集，In表示n×n單位矩陣，1n表示n×1全1向量，0n表示n×1全0向量，(·)T表示轉置。矩陣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個節(jié)點構成的無向圖G，點集v={1,2,…,N}，整個網(wǎng)絡節(jié)點間M的條連邊構成邊集ε={(i,j):i,j∈v}?v×v，一條邊代表一個互異點的點對，如(i,j)。圖G是連通的當且僅當任意兩個互異點間存在一條途徑。文中考慮的圖G是不含環(huán)的。定義ε中的每條邊的一個端點為正的，另一端點為負的?，F(xiàn)在考慮ε中的第k條邊，k{1,2,…,M}，這條邊連接的兩個點是i,j點。Ni表示點i的鄰居點集，Ni={j∈v:(i,j)∈ε}。

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

1.3 量化器

篇幅有限，量化器的設計詳見[11]。

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

2.1 問題描述

(1)

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

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

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

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

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

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

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

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

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

(2a)

dTX*=0Mq*

(2b)

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

考慮優(yōu)化問題(1)，其中個體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是關聯(lián)矩陣，0<α<1/λmax(L)。

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

(5)

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

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

(i)V*(X,λ)正定，且當且僅當(X,λ)=(X*,λ*)時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]可知結論成立；(ii)V*(X,λ)關于X的廣義梯度是

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

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

(6)

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

αlX+λ-λ*

(7)

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

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

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

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

當γ(X)=g(X)∈?f(X)時，則[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為含量化誤差的項：

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))

又因為-‖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(λ-λ*)

由假設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

由假設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*‖

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

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 主要結論

通過收斂性分析證明可以得到以下結論：當

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

‖eTdT(αl+2I)‖)

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

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

5 結 語

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

[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] 徐建軍, 閆麗梅, 趙玉峰. 不確定線性動態(tài)控制系統(tǒng)的魯棒性設計方法[J]. 佳木斯大學學報(自然科學版), 2001, 19(4):401-403.

[13] 楊文, 汪小帆, 李翔. 一致性問題綜述[C].中國控制會議. 2006.

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