基于非光滑分析的凸优化问题分布式量化算法①

袁君萍， 李德权

(安徽理工大学数学与大数据学院，安徽 淮南 232001)

0 引 言

关于整个网络的凸函数之和的分布式优化问题是网络化系统数据处理的一类重要问题，近年来在连续时间多个体分布式优化上已有较多成熟的成果[1～7]。目前，一类重要分布式优化问题是：关于整个网络的凸目标函数可以表示为网络中所有个体各自的凸目标函数之和，每个个体仅知其自身的凸目标函数，且只能通过与其邻居个体进行信息交换协同地解决该优化问题。但在许多实际应用中，当个体间进行信息交换时，由于通信信道容量有限，在实际数字网络中要求个体之间交换的实时数据具有无限精度是难以保证的[8]。因此，研究凸优化问题的分布式量化优化算法具有较强的实际应用价值。采用了边拉普拉斯[9～10]，将连边个体间的相对状态信息转化为个体间的边状态信息，进而对边状态信息采取量化[11]。在实际应用中系统往往允许存在一定的误差,只要系统状态能够控制在一定的范围内即可,没有必要渐近收敛于平衡点[12]。根据鲁棒稳定条件，给出了具体的系统鲁棒性设计算法[13]，介绍了各种一致性协议和不同的收敛性分析方法。

系统的一致有界性控制是指通过一定的控制策略,将系统状态控制在一个与初始时刻无关的范围内[14]。因此,针对实际要求,可以不用实现将系统状态精确控制收敛到某几个最优点上去,转而设计算法使网络控制系统一致有界.这样既满足实际要求,又可以使得设计方法变得可行。个体状态信息无约束情况下的边状态信息量化形式，通过改造合适的Lyapunov函数并采用了非光滑分析方法来分析其收敛性；最后证明了该算法是一致有界的。

1 背景知识

1.1 符 号

R表示实数集，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范数，A>0(A≥0)表示矩阵A∈Rn×n是正定的(半正定的)。

1.2 代数图论

考虑由N个节点构成的无向图G，点集v={1,2,…,N}，整个网络节点间M的条连边构成边集ε={(i,j):i,j∈v}⊂v×v，一条边代表一个互异点的点对，如(i,j)。图G是连通的当且仅当任意两个互异点间存在一条途径。文中考虑的图G是不含环的。定义ε中的每条边的一个端点为正的，另一端点为负的。现在考虑ε中的第k条边，k{1,2,…,M}，这条边连接的两个点是i,j点。Ni表示点i的邻居点集，Ni={j∈v:(i,j)∈ε}。

图G的关联矩阵D=[dik]N×M与Laplacian阵L分别定义为

1.3 量化器

篇幅有限，量化器的设计详见[11]。

2 问题描述及优化算法

2.1 问题描述

(1)

其中，每个个体只使用自己的局部代价函数，自己的状态信息xi(t)及从邻居个体接受量化相对状态信息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就可以保证所有的个体状态一致。因为z=0，则Lx=DDTx=Dz=0。因此，若图是连通的，z=0就表示了x1=x2=…=xN。

假设2.1：考虑优化问题(1)。

1)图G连通且无向。2)对所有的i∈{1,…,N}，fi连续且凸。3)问题(1)至少存在一个最优解。

假设2.2：在每个节点xi∈Rq处对fi(x)的次梯度gi，都存在li′<∞使得‖gi‖

假设2.3：在每个节点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)的最优解，当且仅当存在X*=1N⊗x*∈RNq及λ*∈RNq，使得

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

(2a)

dTX*=0Mq*

(2b)

2.2 分布式连续时间投影算法

考虑优化问题(1)，其中个体i的优化算法如下：

(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是关联矩阵，0<α<1/λmax(L)。

X*∈RNq,λ*∈RNq是满足(2)的向量，定义Lyapunov函数如下

(5)

g(X*)∈∂F(X*)，使得g(X*)+αlλ*=0,LFV*(X,λ)是V*的集值李导数。

引理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)是凸函数，可得(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则系统会收敛到一定的范围内；当这两者有一项不成立而造成a≥0或两项均不成立时，则个体状态会在上述收敛范围内震荡也可能越出收敛范围，但是越界之后由于a<0，于是便会重新收敛到该范围。收敛效果与量化器的设计有关，往往量化误差越大，则收敛效果越差，收敛上界往往随着量化误差上界的减小而减小。在实际应用中，可以根据实际需求来设计量化器的最大量化误差。

5 结 语

研究了分布式多个体量化问题，用边laplacian将个体的状态信息转化为个体间边的状态信息，并对边状态信息采取量化，收敛性分析中采用了非光滑分析，最终证明了该算法是一致有界的，个体状态会收敛到一定的范围内。但是仍有很多地方可以进一步研究，比如通过量化器的设计让收敛范围进一步缩小、在不影响收敛速率的基础上通过边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] 徐建军, 闫丽梅, 赵玉峰. 不确定线性动态控制系统的鲁棒性设计方法[J]. 佳木斯大学学报(自然科学版), 2001, 19(4):401-403.

[13] 杨文, 汪小帆, 李翔. 一致性问题综述[C].中国控制会议. 2006.

[14] 刘俊豪, 张皓, 陈启军. 具有均匀量化器的非线性网络控制系统的一致有界性[J]. 控制理论与应用, 2012, 29(11):1388-1396.