多智能体共识算法的粗略数学证明-Toy模板网

这篇具有很好参考价值的文章主要介绍了多智能体共识算法的粗略数学证明。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

这篇文章是对论文《Consensus and Cooperation in Networked Multi-Agent Systems》中定理一的粗略数学证明。

论文中的定理一：

对一个由 n 个智能体以拓扑结构 G 组成的网络，使用以下共识算法：
$\dot{x}_i(t)=\Sigma_{j\in N_i}a_{ij}(x_j(t)-x_i(t)),\ x(0)=z$
假设 G 为强连通有向图，令 L 为 G 的拉普拉斯量，且其左特征向量 $\gamma=(\gamma_1,\cdots,\gamma_n)$ 满足 $\gamma^T L=0$ 。则有：

对所有的初始态 $z$ ，算法可以渐进地达成一个共识；

该算法能够解决 $f(z)=(\gamma^T z)/(\gamma^T \pmb{1})$ 形式的 f-共识问题，其对应的群体决策为 $\alpha=\Sigma_i w_i z_i$ ，其中 $\Sigma_i w_i=1$

如果 G 为强连通有向平衡图，该算法可以渐进地达成均值共识，对应的群体决策为 $\alpha=\frac{1}{n}\Sigma_i x_i(0)$ 。

对 1. 的证明：
- 该算法的紧凑形式为 $\dot{x}=−Lx$ ，则其解为 $x(t)=e^{−tL}x(0)$ ，所以 $x (t)$ 的收敛性可由 $e^{−tL}$ 判定；
- 设 $L$ 的Jordan标准型为 $J$ ，即 $L=PJP^{−1}$ ，则 $diag(f(J_1 ),\cdots,f(J_s))P^{−1}$ ，故有 $e^{−tL}=P diag(e^{−tJ_1},\cdots,e^{−tJ_s})P^{−1}$ ，所以 $x (t)$ 的收敛性可由 $e^{−tJ_i}$ 判定；
- 由于 $e^{−tJ_i}=e^{−t\lambda_i}∗T$ ，其中矩阵 $T$ 的元素为 $t$ 的幂函数，所以 $x (t)$ 的收敛性可由 $e^{−t\lambda_i }$ 判定；
- 根据引理2（ $L$ 的秩为 $n - 1$ ，且所有非零特征值 $\lambda_i$ 均有正实部 ），故 $L$ 的特征值中仅存在一个 0，对应的特征向量为 $\alpha \pmb{1}$ ， $−L(\alpha \pmb{1})=0$ ，又由 $e^{−t\lambda_i }=e^{−t(a_i+jb_i)}=e^{−ta_i} e^{−jtb_i}\to 0$ 可知 $x (t)$ 收敛，即有 $\dot{x}(\infin)=−Lx(\infin)=0$ ，所以 $x(\infin)=\alpha \pmb{1}$ 。
对 2. 的证明：

可以考虑借助不变量 $y=\gamma^T x$ 并考察其初态与终态。
$\gamma=\pmb{1}$ 是 L 的左特征向量的充要条件是 G 为平衡有向图。
对 3. 的证明：略