上接有向图上的多智能体同步（上）

图论代数

广义代数连通性

定义1 对于具有拉普拉斯矩阵 L 的强连通网络，广义代数连通性定义为$$a(L)=\underset{\begin{array}{c}{x}^{\mathrm{T}}\xi =0,x\ne 0\end{array}}{\min }\frac{x^{\mathrm{T}}\hat{L}x}{x^{\mathrm{T}}\Xi x}$$其中，$\hat{L}=\frac{1}{2}(\Xi L+L^{\mathrm{T}}\Xi )$，$\Xi =\mathrm{diag}({\xi }_1,\dots ,{\xi }_n)$，$\xi =({\xi }_1,{\xi }_2,\dots ,{\xi }_n{)}^{\mathrm{T}}>0$，且满足 ${\xi }^{\mathrm{T}}L=0$，${\sum }_{i=1}^n{\xi }_i=1$。注意，若 $\Xi =\eta I_N$（$\eta$ 为常数，$I_n$ 为 $n$ 阶单位矩阵）且网络是无向的，则 $a(L)={\lambda }_2(L)$（即无向网络的第二小拉普拉斯特征值，传统代数连通性）。
引理 4：假设矩阵 $\hat{L}$ 是对称的、不可约的，且满足 ${\sum }_{j=1}^N{\hat{L}}_{ij}=0$（行和为 0），同时 ${\hat{L}}_{ij}\ge 0$（$i\ne j$，$i,j=1,2,\dots ,n$）。令$$\hat{a}(\hat{L})=\underset{\begin{array}{c}{x}^{\mathrm{T}}\xi =0,x\ne 0\end{array}}{\min }\frac{x^{\mathrm{T}}\hat{L}x}{x^{\mathrm{T}}x}$$则有 ${\lambda }_2(\hat{L})\ge \hat{a}(\hat{L})\ge 0$。此外，$\hat{a}(\hat{L})=0$ 当且仅当 $\xi$ 与 $\hat{L}$ 对应于特征值 0 的左特征向量正交；并且，若 $\xi$ 是 $\hat{L}$ 对应于特征值 0 的左特征向量，则 $\hat{a}(\hat{L})={\lambda }_2(\hat{L})$。

证明 由于 $\hat{L}$ 对称且行和为零，其最小特征值为 ${\lambda }_1(\hat{L})=0$，对应的特征向量为 $1_n$。由 Courant–Fischer 极小极大原理，第二小特征值可表示为
$${\lambda }_2(\hat{L})=\underset{\begin{array}{c}x\ne 0\\ x^{\top }{1}_N=0\end{array}}{\min }\frac{x^{\top }\hat{L}x}{x^{\top }x}.$$
注意到约束条件 $x^{\top }\xi =0$ 定义了一个超平面，而 $x^{\top }{1}_n=0$ 定义了另一个超平面。一般情况下，这两个超平面不同，因此在更受限的集合 { x ∣ x ⊤ ξ = 0 , x ≠ 0 } \{x \mid x^\top \xi = 0, x \neq 0\} {x∣x⊤ξ=0,x=0} 上取最小值，所得结果不会小于在 { x ∣ x ⊤ 1 N = 0 , x ≠ 0 } \{x \mid x^\top \mathbf{1}_N = 0, x \neq 0\} {x∣x⊤1N​=0,x=0} 上的最小值。故有
$${\lambda }_2(\hat{L})\ge \hat{a}(\hat{L})\ge 0.$$

进一步，若 $\xi$ 与 $1_n$ 正交（即 ${\xi }^{\top }{1}_n=0$），则存在非零向量 $x$ 同时满足 $x^{\top }\xi =0$ 和 x ∈ s p a n { 1 n } x \in \mathrm{span}\{\mathbf{1}_n\} x∈span{1n​}，此时 $x^{\top }\hat{L}x=0$，从而 $\hat{a}(\hat{L})=0$。反之，若 $\hat{a}(\hat{L})=0$，则存在非零 $x$ 满足 $x^{\top }\xi =0$ 且 $x^{\top }\hat{L}x=0$，即 $x$ 属于 $\hat{L}$ 的零空间，故 $x\propto 1_N$，从而 ${\xi }^{\top }{1}_N=0$。

特别地，若 $\xi =1_n/n$（即 $\xi$ 是 $\hat{L}$ 对应于零特征值的归一化左特征向量），则约束 $x^{\top }\xi =0$ 等价于 $x^{\top }{1}_n=0$，此时极小化问题与 ${\lambda }_2(\hat{L})$ 的定义完全一致，故 $\hat{a}(\hat{L})={\lambda }_2(\hat{L})$。 $\square$

引理 5 若 Laplacian 矩阵 $L$ 不可约（即对应的有向图强连通），则广义代数连通度 $a(L)>0$。

证明 当 $L$ 不可约时，存在正向量 $\xi =({\xi }_1,\dots ,{\xi }_n{)}^{\top }>0$ 满足 ${\xi }^{\top }L=0$ 且 ${\xi }^{\top }{1}_n=1$。定义对角矩阵 $\Xi =\mathrm{diag}({\xi }_1,\dots ,{\xi }_N)$，并令
$$\hat{L}=\frac{1}{2}(\Xi L+L^{\top }\Xi ).$$
易见 $\hat{L}$ 为对称矩阵，且满足 $\hat{L}{1}_n=0$，即其行和与列和均为零。此外，由于 $L$ 不可约且 $\xi >0$，可证 $\hat{L}$ 亦不可约（否则将导致 $L$ 可约，矛盾）。

根据定义1，广义代数连通度为
$$a(L)=\underset{\begin{array}{c}{x}^{\top }\xi =0\\ x\ne 0\end{array}}{\min }\frac{x^{\top }\hat{L}x}{x^{\top }\Xi x}.$$
注意到 $\Xi$ 正定，故对任意非零 $x$ 满足 $x^{\top }\xi =0$，分母 $x^{\top }\Xi x>0$。又因 $\hat{L}$ 对称半正定且零空间为 s p a n { 1 N } \mathrm{span}\{\mathbf{1}_N\} span{1N​}，而约束 $x^{\top }\xi =0$ 与 $1_n$ 不正交（因 ${\xi }^{\top }{1}_n=1\ne 0$），故在该约束下 $x\notin \ker (\hat{L})$，从而 $x^{\top }\hat{L}x>0$。

进一步，利用引理4中的辅助量 $\hat{a}(\hat{L})={\min }_{x^{\top }\xi =0,x\ne 0}\frac{x^{\top }\hat{L}x}{x^{\top }x}$，可得
$$a(L)=\underset{x^{\top }\xi =0,x\ne 0}{\min }\frac{x^{\top }\hat{L}x}{x^{\top }\Xi x}\ge \frac{1}{{\max }_i{\xi }_i}\underset{x^{\top }\xi =0,x\ne 0}{\min }\frac{x^{\top }\hat{L}x}{x^{\top }x}=\frac{\hat{a}(\hat{L})}{{\max }_i{\xi }_i}.$$
由于 $\hat{L}$ 不可约且 ${\xi }^{\top }{1}_N=1\ne 0$，由引理6知 $\hat{a}(\hat{L})>0$，故 $a(L)>0$。 $\square$

多智能体同步

在多智能体协同控制中，一致性（consensus）是最基本且核心的问题之一：每个智能体仅能获取局部邻居信息，却希望全局状态最终趋于一致。例如，一群无人机，彼此只能“单向”接收邻居的位置信息（比如 A 能看到 B，但 B 看不到 A），它们还能不能最终排成整齐队形？答案是肯定的，只要通信图是“强连通”的，就能同步。

模型

考虑 $N$ 个智能体，每个状态为 $x_i(t)\in \mathbb{R}$，遵循如下规则：
$${\dot{x}}_i(t)=\sum _{j=1}^N{a}_{ij}(x_j(t)-x_i(t)),$$
其中 $a_{ij}\ge 0$ 表示智能体 $i$ 对 $j$ 的“信任权重”。若 $a_{ij}>0$，说明存在一条从 $j$ 指向 $i$ 的有向边（$i$ 能接收 $j$ 的信息）。

这个模型的物理意义非常直观：每个智能体把自己的状态向邻居的加权平均靠拢。它是一阶共识（first-order consensus）的标准形式，也是更复杂编队、协同控制的基础。

令 Laplacian 矩阵 $L=D-A$（$D$ 为出度对角阵），系统可写为：
$$\dot{x}=-Lx.$$

同步的定义

我们说系统达成同步（consensus），若
$$\underset{t\to \infty }{\lim }|x_i(t)-x_j(t)|=0,\forall i,j.$$

在无向图中，极限是算术平均 $\frac{1}{N}\sum x_i(0)$。但在有向图中，由于信息流不对称，极限是一个加权平均：
$$\bar{x}={\xi }^{\top }x(0),$$
其中 $\xi >0$ 是 $L$ 的左零特征向量，满足 ${\xi }^{\top }L=0$ 且 ${\xi }^{\top }{1}_N=1$。这个 ${\xi }_i$ 可理解为智能体 $i$ 在网络中的“影响力权重”——越能被他人间接影响，权重越高。

结论与证明

定理一 当通信图是强连通（strongly connected）时，即任意两个节点间都存在有向路径，则系统是指数同步的。

证明 注意上一节的定义1，广义代数连通度：
$$a(L)=\underset{\begin{array}{c}{x}^{\top }\xi =0\\ x\ne 0\end{array}}{\min }\frac{x^{\top }\hat{L}x}{x^{\top }\Xi x}。$$
同时，引理5证明，只要图强连通，就有 $a(L)>0$。 此时，定义误差 $\hat{x}=x-1_N\bar{x}$，则 ${\xi }^{\top }\hat{x}=0$，且 $\dot{\hat{x}}=-L\hat{x}$。构造 Lyapunov 函数：
$$V(t)={\hat{x}}^{\top }\Xi \hat{x}\ge 0,$$
其导数为：
$$\dot{V}=-2{\hat{x}}^{\top }\hat{L}\hat{x}\le -2a(L){\hat{x}}^{\top }\Xi \hat{x}=-2a(L)V(t).$$

于是 $V(t)\le V(0)e^{-2a(L)t}\to 0$，即指数同步！

注 当图无向时，$L$ 对称，$\xi =\frac{1}{N}{1}_N$，$\Xi =\frac{1}{N}I$，$\hat{L}=L$，此时
$$a(L)={\lambda }_2(L),$$
完全退化为经典结果。

潜在应用

这项关于有向图同步的理论，可以直接回应了现实世界中大量非对称通信场景的控制需求。 同步与否，不取决于通信是否“双向”，而取决于信息能否“遍历全网”。我们可以将模型用在例如无人机编队、机器人控制、网络传输以及网络算法的收敛和鲁棒性上。其实也有点像团队协作，每个人做好自己的局部沟通，整个团队就会实现全局目标。

PS：可以用在信息传播上，如果大家都转发和点赞文章，就能促进大家的共同进步！