• 写在前面
• 无向图的情况
• 有向图的情况

写在前面

分布式一致算法(Distributed Consensus Algorithm)可以用来设计分布式估计器/观测器，在控制中应用广泛。本文主要关注的是有限时间收敛且参考信号时变的情况，即有限时间(finite-time)分布式一致跟踪(Consensus Tracking)算法。

无向图的情况

第一个算法是最常见的有限时间速度估计器，如下所示：

$\dot \zeta_i=-\beta\operatorname{sgn}\left(\sum_{j\in\mathcal N_i}a_{ij}(\zeta_i-\zeta_j)+b_i(\zeta_i-\zeta_d)\right)。$

其中$\beta>\|\dot \zeta_d\|_\infty$。该算法直接将标准分布式一致跟踪算法的速度项去掉，然后加上了符号函数。

令$e_\zeta=\zeta-1_n\otimes \zeta_d$。误差动力学为

$\dot e_\zeta=-\beta\operatorname{sgn}(Le_\zeta+Be_\zeta)-1_n\otimes \dot \zeta_d$

令$H=L+B$，其中$B=\operatorname{diag}(b_1,\cdots,b_n)$。如果$b_i=1$即为leader，可以获得参考信号；否则为follower，无法获得参考信号。

假设图是一个连通无向图，容易得到$H$是一个对称正定矩阵，证明可以参考定理1。

定理1（Ren 2005^[1]）：如果有向图存在一个有向生成树，则$H$所有特征根拥有正实部。即$H$是一个非奇异的M-矩阵，且主对角占优。

参考Mehdifar 2019^[2]，设计李雅普诺夫函数

$V=\frac{1}{2}e_\zeta^THe_\zeta$

求导得

$\begin{aligned} \dot V&=e_\zeta^TH(-\beta\operatorname{sgn}(He_\zeta)-1_n\otimes \dot \zeta_d)\\ &\leq -\beta\|He_\zeta\|_1+\|\dot \zeta_d\|_\infty\|He_\zeta\|_1\\ &=-(\beta-\|\dot \zeta_d\|_\infty)\|He_\zeta\|_1\\ &\leq -(\beta-\|\dot \zeta_d\|_\infty)\lambda_2\|e_\zeta\|\\ &\leq -(\beta-\|\dot \zeta_d\|_\infty)\sqrt{\frac{2\lambda_2^2}{\lambda_n}}V^{\frac{1}{2}} \end{aligned}$

由$\frac{\dot V}{\sqrt{V}}\leq -c$积分，可以得到$2\sqrt{V(t)}\leq 2\sqrt{V(0)}-ct$，即有限时间收敛，其中$c=(\beta-\|\dot \zeta_d\|_\infty)\sqrt{\frac{2\lambda_2^2}{\lambda_n}}>0$。

定理 2（Long 2010^[3]， Lemma 3）：假设$V(t)$可微且

$\frac{dV(t)}{dt}\leq -cV(t)^\alpha$

其中$c>0$且$0<\alpha<1$。则$V(t)$有限时间收敛于0，且收敛时间为$T\leq \frac{V(0)^{1-\alpha}}{c(1-\alpha)}$。

由定理2可知，收敛时间为$t\leq T=\frac{2}{c}V(0)^{1/2}$。

有向图的情况

假设图是一个有向图，有以leader为根的有向生成树。

定理3（Li 2015^[4]，Lemma 4）：存在正对角矩阵$G$使得$GH+H^TG>0$成立。矩阵$G$可以由$\operatorname{diag}(q_1,\cdots,q_n)$给出，其中$q=[q_1,\cdots,q_n]^T=(H^T)^{-1}1_n$。

证明：（第一句）直接取$L$的左特征向量即可。第二句也给出了范例。

（第二句）因为$H$非奇异，所以$(L^T)^T$存在且非负，没有0行，故$q>0$。由于$H$主对角占优，即$H1_n=0$，左乘$G$相当于行元素同时放大缩小，故有$GH1_n>0$。又注意到$H^TG1_n=H^Tq=1_n$，相加得到$(GH+H^TG)1_n>0$，所以$GH+H^TG$严格主对角占优，即所有特征根为正，再加上对称性，得到正定性。

对于$x\in\mathbb R^d$，定义$\operatorname{sig}^{\mu}(x)=[|x_1|^\mu\operatorname{sgn}(x_1),\cdots,|x_d|^\mu\operatorname{sgn}(x_d)]^T$。设计第二个算法

$\begin{aligned} \dot \zeta_i&=-\alpha\operatorname{sig}^\mu(\delta_i)-\alpha\operatorname{sig}^{\frac{1}{\mu}}(\delta_i)-\beta\operatorname{sgn}(\delta_i)\\ \delta_i&=\sum_{j\in\mathcal N_i}a_{ij}(\zeta_i-\zeta_j)+b_i(\zeta_i-\zeta_d) \end{aligned}$

其中$0<\mu<1$，$\beta>\|\dot \zeta_d\|_\infty$。可以看出该算法是在第一个算法基础上增加了两个sig函数。

令$e_\zeta=\zeta-1_n\otimes \zeta_d$，则$\delta=He_\zeta$。由定理1可知，在有向图中，$H$不一定对称，但仍然是满秩的。因此只需证明$\delta$有限时间收敛于0。

$\dot \delta=H\dot e_\zeta=-\alpha H\operatorname{sig}^\mu(\delta)-\alpha H\operatorname{sig}^{\frac{1}{\mu}}(\delta)-\beta H\operatorname{sgn}(\delta)-H (1_n\otimes \dot \zeta_d)$

定义$\|x\|_\gamma=(\sum_{i=1}^d |x_i|^\gamma)^{1/\gamma}$。参考Ning 2020^[5]，设计李雅普诺夫函数

$V=\sum_{i=1}^{n}q_i(\frac{\alpha}{\mu+1}|\delta_i|_{\mu+1}^{\mu+1}+\frac{\alpha\mu}{\mu+1}|\delta_i|_{\frac{1}{\mu}+1}^{\frac{1}{\mu}+1})$

求导得

$\begin{aligned} \dot V&=\sum_{i=1}^n\alpha q_i(\operatorname{sig}^\mu(\delta_i)+\operatorname{sig}^{\frac{1}{\mu}}(\delta_i))\dot \delta_i\\ &=-\alpha^2(\operatorname{sig}^\mu(\delta)+\operatorname{sig}^{\frac{1}{\mu}}(\delta))GH(\operatorname{sig}^\mu(\delta)+\operatorname{sig}^{\frac{1}{\mu}}(\delta))\\ &\quad-\alpha(\operatorname{sig}^\mu(\delta)+\operatorname{sig}^{\frac{1}{\mu}}(\delta))GH(\beta\operatorname{sgn}(\delta)+1_n\otimes \dot \zeta_d)\\ \end{aligned}$

注意到，第二个等式第二项中$GH=GL+GB$，对于$GL$这一部分，可以看出$GL$是有向平衡图的拉普拉斯矩阵，我们有$GL(1_n\otimes \zeta_d)=0$，且

$\operatorname{sig}^\mu(\delta)GL\operatorname{sgn}(\delta)=\sum_{i=1}^n\operatorname{sgn}(\delta_i)\sum_{j\in\mathcal N_i}|\delta_i|^\mu q_ia_{ij}(\operatorname{sgn}(\delta_i)-\operatorname{sgn}(\delta_j))$

分类讨论，若$\delta_i,\delta_j$同号（或$\delta_i=0$），则$\operatorname{sgn}(\delta_i)-\operatorname{sgn}(\delta_j)=0$（或$\operatorname{sgn}(\delta_i)=0$）；

若$\delta_i,\delta_j$异号（或$\delta_j=0$），则$\operatorname{sgn}(\delta_i)-\operatorname{sgn}(\delta_j)=2\operatorname{sgn}(\delta_i)$（或$\operatorname{sgn}(\delta_i)$），

故$\operatorname{sgn}(\delta_i)|\delta_i|^\mu q_ia_{ij}(\operatorname{sgn}(\delta_i)-\operatorname{sgn}(\delta_j))=2|\delta_i|^\mu q_ia_{ij}\geq 0$（或$|\delta_i|^\mu q_ia_{ij}\geq 0$）。

综上所述，对于$GL$的这部分，恒大于等于0。

令$g=\alpha(\operatorname{sig}^\mu(\delta)+\operatorname{sig}^{\frac{1}{\mu}}(\delta))$。对于$GB$这一部分，有

$gGB(\beta\operatorname{sgn}(g)+1_n\otimes \dot \zeta_d)\geq (\beta-\|\zeta_d\|_\infty)\sum_{i\in\mathcal V_l}q_ib_i|g_i|\geq 0$

因此，当$\beta>\|\dot \zeta_d\|_\infty$时，有

$\begin{aligned} \dot V&\leq -\alpha^2(\operatorname{sig}^\mu(\delta)+\operatorname{sig}^{\frac{1}{\mu}}(\delta))GH(\operatorname{sig}^\mu(\delta)+\operatorname{sig}^{\frac{1}{\mu}}(\delta))\\ &\leq -\lambda_{\min}(M)\alpha^2\|\operatorname{sig}^\mu(\delta)+\operatorname{sig}^{\frac{1}{\mu}}(\delta)\|^2 \end{aligned}$

其中$M=\frac{1}{2}(GH+H^TG)$。

定理4（Wang 2019^[6], Theorem 1）：对任意向量$x\in\mathbb R^d$，以及$0<\mu_1<1<\mu_2$，给定$X_1=\|x\|_{\mu_1+1}^{\mu_1+1}+\|x\|_{\mu_2+1}^{\mu_2+1}$和$X_2=\|\operatorname{sig}^{\mu_1}(x)+\operatorname{sig}^{\mu_2}(x)\|$。则以下不等式成立：

$X_1^{\frac{\mu_1+\mu_2}{\mu_2+1}}\leq X_2^2,\quad (2d)^{\frac{1-\mu_2}{1+\mu_2}}X_1^{\frac{2\mu_2}{\mu_2+1}}\leq X_2^2。$

由李雅普诺夫函数定义得到，

$\begin{aligned} V&\leq \frac{\alpha\|q\|_\infty}{1+\mu}(\|\delta\|_{\mu+1}^{\mu+1}+\|\delta\|_{\frac{1}{\mu}+1}^{\frac{1}{\mu}+1})\\ \dot V&\leq -\lambda_{\min}(M)\alpha^2(\|\delta\|_{2\mu}^{2\mu}+2\|\delta\|_{\mu+\frac{1}{\mu}}^{\mu+\frac{1}{\mu}}+\|\delta\|_{\frac{2}{\mu}}^{\frac{2}{\mu}}) \end{aligned}$

由定理4，容易证明

$\dot V\leq -\frac{c_2}{2}((\frac{V}{c_1})^{\frac{\mu^2+1}{\mu+1}}+(2nd)^{\frac{\mu-1}{\mu+1}}(\frac{V}{c_1})^{\frac{2}{\mu+1}})$

其中$c_1=\frac{\alpha\|q\|_\infty}{1+\mu}$，$c_2=\lambda_{\min}(M)\alpha^2$。

定理5（Polyakov 2012^[7]）：考虑如下ODE

$\dot x(t)=g(x(t),t),\quad x(0)=x_0,$

其中$x\in\mathbb R^d$，$g:R^d\to R^d$是非线性函数。假设存在连续正定函数$V(x):R^d\to R$和一些标量$a,b>0$，$\mu>0$以及$0<\nu<1$使得$\dot V(x)+aV^\mu(x)+bV^\nu(x)\leq 0$，$x\in\mathbb R^d\backslash\{0\}$。那么，该ODE的原点是全局固定时间稳定(globally fixed-time stable)，且稳定时间$T$满足

$T\leq 1/a(1-\mu)+1/b(1-\nu)。$

由于$\frac{\mu^2+1}{\mu+1}<1<\frac{2}{\mu+1}$，由定理5，可以得到$V$有限时间收敛到0，收敛时间为

$t\leq T=\frac{1}{\frac{c_2}{2}(1-\frac{\mu^2+1}{\mu+1})}+\frac{1}{(2nd)^{\frac{\mu-1}{\mu+1}}(\frac{2}{\mu+1}-1)}=\frac{(2+c_2\mu(2nd)^\frac{1-\mu}{1+\mu})(1+\mu)}{c_2\mu(1-\mu)}$