在多智能体系统中, 每个智能体(节点)都具有一个局部成本函数, 分布式优化的目标是使由局部成本函数之和所构成的全局成本函数最小. 分布式优化的研究由来已久, 至少可以追溯到^[1-2]. 近年来, 由于其在电力系统、机器学习和传感器网络等领域的广泛应用, 这一研究重新引起了关注. 研究者设计了多种分布式优化算法, 详见综述文章^[3-10], 大致可分为离散时间算法和连续时间算法.

现有的大多数离散时间算法均基于一致性算法和分布式次梯度下降(Distributed gradient descent, DGD)算法^[11-15]. 尽管DGD算法可以处理非光滑凸函数的分布式优化问题, 并在通讯延迟、丢包等多个方向上进行扩展以处理更为实际的情况, 但由于使用了衰减步长, 因此收敛速度较慢. 在步长固定的情况下, 虽然DGD算法收敛速度快, 但只能收敛到最小值点的邻域^[16-17]. 最近的研究集中在利用历史信息来设计具有固定步长的加速算法. 具体而言, 文献[18-19]中提出的算法是基于比例积分(Proportional integral, PI)控制策略, 文献[20-25]中提出的算法是基于分布式不精确梯度算法和分布式动态平均梯度跟踪技术^[26]. 现有的连续时间算法可以分为两类: 第一类是文献[27-29]中提出的基于梯度的算法, 这类算法本质上都是基于PI控制策略, 其中每个智能体使用一个辅助状态(积分反馈)来校正由不同局部梯度引起的误差; 第二类算法使用二阶Hessian信息, 例如文献[30-32].

为了避免连续通信和减少通信负担, 事件触发通信和控制的思想最初是针对单个系统^[33-35]提出的. 后来这种思想被应用到分布式一致性问题^[36-42]. 近年来, 研究者提出了基于事件触发通信的分布式优化算法^{[29, 43-50]}. 文献[29]提出了一种不存在Zeno行为^[51]的事件触发算法, 即在有限时间内不会触发无限多次事件, 并针对无向连通图, 在局部成本函数强凸以及梯度局部Lipschitz且可微的条件下, 证明了算法指数收敛到最小值点的邻域. 受文献[30]提出的零梯度和 (Zero-gradient-sum, ZGS)算法的启发, 文献[44]提出周期性的事件触发机制; 文献[45]则设计了基于动态事件触发的ZGS算法. 针对无向连通图或权平衡强连通的有向图, 在局部成本函数强凸且具有局部Lipschitz Hessians的条件下, 证明了算法的指数收敛性.

本文提出了两种基于比例积分策略的分布式优化算法, 并证明了算法的收敛性. 在此基础上, 为了减少通信负担, 我们提出了基于事件触发的分布式优化算法, 并证明了提出的基于事件触发的优化算法不存在Zeno行为, 且保持了与连续通信下分布式优化算法相同的收敛性. 文献[29]提出的事件触发算法只有在局部成本函数强凸且具有局部Lipschitz梯度的条件下收敛到全局最小值点的一个邻域, 而我们提出的算法在局部成本函数可微且凸的条件下, 即可精确地指数收敛到唯一的全局最小值点. 与文献[46]中提出的算法相比, 我们提出的算法更简单, 因为在执行文献[46]中的算法时需要一些特殊设计的增益参数. 与文献[44-45]中提出的基于二阶Hessian信息的事件触发ZGS算法相比, 我们提出的算法是基于一阶梯度的, 易于实现. 此外, ZGS算法需要特殊的初始化, 而我们提出的算法允许任意初始化.

本文其余部分安排如下. 第1节介绍图论的基础知识. 第2节介绍本文所考虑的分布式优化问题. 第3节提出两种基于PI控制策略的分布式优化算法, 并分析所提算法的收敛性. 第4节提出基于事件触发通信机制的分布式优化算法并分析其收敛性. 第5节利用数值仿真验证理论结果. 第6节总结本文的主要结果并介绍未来的研究方向.

1.   基础概念

在这一部分, 我们介绍图论的一些基本知识^[52]. 考虑一个包含$ N $个智能体的无向图$ {\cal G} = ({\cal V},{\cal E},{\cal A}) $, 其中${\cal V} = \{1,2, \cdots,N\}$表示智能体的集合, ${\cal E} = \{(i,j): $$ i,j \in {\cal V}, i\neq j\}$表示边的集合, ${\cal A} = [a_{ij}] \in {\bf R}^{N\times N}$表示加权邻接矩阵, 其中, 当$ (i,j) \in {\cal E} $时, $ a_{ij}> 0 $; 当$ (i,j) \notin {\cal E} $时, $ a_{ij} = 0 $. 在本文中, 我们还假设图中没有自环边, 即对于所有的$ i\in {\cal V} $, $ a_{ii} = 0 $. 智能体$ i $的邻居集合定义为$ {\cal N}_i = \{j \in {\cal V}| a_{ij}>0\} $. 在无向图中从节点$ i_{1} $到节点$ i_{k} $的路径是指存在节点序列$i_1, \cdots, i_k$, 使得$ (i_j,i_{j+1}) \in {\cal E} $, $j = 1, \cdots, k-1$.

对于无向加权图$ {\cal G} $, 加权Laplacian矩阵$L = $$ [L_{ij}] \in {\bf R}^{N\times N}$的定义是$ L_{ii} = \sum\nolimits_{j = 1}^{N}a_{ij} $, 对于$ i\neq j $, 有$ L_{ij} = -a_{ij} $, 因此, Laplacian矩阵的行和为零. 如果无向加权图$ {\cal G} $是连通的, 则Laplacian矩阵$ L $有唯一的0特征值, 其对应的右特征向量为1, 其他所有特征值均大于零.

符号说明: 给定一个矩阵$ A $, $A^{\rm T}$表示其转置矩阵. 对称矩阵$ A $是半正(负)定的当且仅当其所有特征值均为非负(非正)时. 给定两个对称矩阵$ M $, $ N $, $ M \leq N $意味着$ M-N $是半负定的. 记号$ A\otimes B $表示矩阵$ A $和$ B $之间的Kronecker积. $ \rho(\cdot) $代表矩阵的谱半径, $ \rho_{2}(\cdot) $表示非负矩阵的最小正特征值. $ I_{n} $表示维数为$ n\times n $的单位矩阵. $ 1_n $表示$ n $维的列向量, 其每个元素都为1. $ \|\cdot\| $表示向量的欧几里德范数或矩阵的诱导2范数. 给定一个向量$[a_1, \cdots, a_N]^{\rm T}\in $$ {\bf R}^N$, ${\rm{diag}}\{a_1, \cdots ,a_N\}$是第$ i $个对角线元素为$ a_i $的对角矩阵. 对于列向量$x_1, x_2, \cdots, x_N$, 那么由其组成的堆栈列向量用$[x_1, x_2, \cdots, x_N]$表示.

2.   问题描述

考虑由$ N $个智能体组成的网络, 每个智能体都有一个局部凸函数$f_{i}: {\bf R}^{n} \to {\bf R}$, $ i\in{\cal V} $. 所有智能体共同协作以找到一个最小值点$ x^{\ast} $, 使全局成本函数$ f(x) = \sum\nolimits_{i = 1}^{N}f_{i}(x) $最小, 即:

智能体之间的通信用无向加权图$ {\cal G} = ({\cal V}, {\cal E}, {\cal A}) $来描述, 其中${\cal V} = \{1,2,\cdots,N\}$是智能体的集合, $ {\cal E}\subseteq {\cal V}\times {\cal V} $是边的集合, $ {\cal A} $是加权邻接矩阵.

如引言部分所述, 为了避免智能体之间的连续通信, 研究者设计了一些分布式事件触发算法. 然而, 大多数现有的算法要么需要特殊的初始化, 要么只收敛到全局最小值点的一个邻域, 这些启发了本文的研究. 更具体地说, 我们的目标是设计任意初始化的事件触发算法, 并精确地收敛到全局最小值点.

我们对局部和全局成本函数作出以下假设:

假设 1. 对每个$ i\in{\cal V} $, 局部成本函数$ f_{i}(x) $是连续可微凸函数. 此外, $ \sum\nolimits_{i = 1}^{N}f_{i}(x) $的全局最小值是有界的.

假设 2. 全局成本函数$ f(x) = \sum\nolimits_{i = 1}^{N}f_{i}(x) $关于全局最小值点$ x^{\ast} $是$ m_f $-(有限)强凸的, 即存在常数$ m_f>0 $, 使得$\sum\nolimits_{i = 1}^N (\nabla f_i(x)-\nabla f_i(x^*))^{\rm T}(x-x^*) \ge $$ m_f\|x-x^*\|^2$, 对任意的$x \in {\bf R}^n$成立.

假设 3. 对于每个$ i\in{\cal V} $, 局部成本函数$ f_{i}(x)$具有局部Lipschitz梯度, 即对任意紧集$D \subseteq {\bf R}^{n}$, 存在常数$ M_{i}(D)>0 $, 使得

其中, $ M_{i}(D) $称为函数$ f_{i}(x)$在紧集$ D $上的Lipschitz常数.

在假设1的条件下, 分布式优化问题(1)的全局最小值点$ x^{\ast}$可能不唯一. 但是, 如果假设2成立, 则很容易证明全局最小值点$ x^{\ast}$是唯一的. 与大多数文献中局部成本函数是强凸的假设相比, 这种假设的限制较小. 详细讨论, 请参见文献[18, 46], 假设3在现有文献中也被广泛使用.

3.   基于PI的分布式优化算法

针对问题(1), 我们提出两种基于PI反馈策略的分布式优化算法, 其中$x_{i}(t)\in {\bf R}^{n}$表示第$ i $个节点在时刻$ t $对全局最小值点$ x^{*} $的一个估计, 积分项$q_{i}(t) \in {\bf R}^{n}$是用来校正第$ i $个节点由于固定步长所产生的误差. 第一种算法如下:

算法(2)的收敛性如下:

定理 1. 假设无向图是连通的, 并且假设1成立. 如果每个智能体$ i\in {\cal V} $运行分布式优化算法(2), 则有:

1) 每个$ x_i(t) $, $ \; i \in {\cal V} $, 渐近收敛到全局最小值点$ x^* $;

2) 如果假设2 ~ 3也成立, 则每个$ x_i(t) $, $ i \in {\cal V} $, 以不小于$\dfrac{\epsilon_2}{\epsilon_3}$的速率指数收敛到唯一的全局最小值点$ x^{\ast} $, 其中$ {\epsilon_2}$和$ {\epsilon_3}$是两个正常数, 并在证明中给出.

证明. 见附录B.

注 1. 算法(2)与文献[27-28]中所提出的分布式优化算法相类似. 但是, 文献[27-28]只给出了在凸成本函数下, 算法渐近收敛的结果. 而定理1给出了在全局成本函数对最小值点有限强凸的附加条件下, 算法指数收敛的结果. 针对有向图为权平衡强连通的情形, 当局部成本函数是可微的凸函数并且具有全局Lipschitz梯度时, 文献[28]中的定理5.4给出了算法渐近收敛的证明. 这里我们考虑的是无向连通图, 在全局成本函数对全局最小值点是有限强凸的附加条件下, 定理1给出了算法的指数收敛性.

下面, 介绍第二种分布式优化算法:

算法(3)的收敛性如下:

定理 2. 假设无向图是连通的, 并且假设1成立. 如果每个智能体$ i\in {\cal V}$运行分布式优化算法(3), 则有:

1) 每个$ x_i(t) $, $ i \in {\cal V}$, 渐近收敛到全局最小值点$ x^{\ast} $;

2) 如果假设2 ~ 3也成立, 则每个$ x_{i}(t)$, $ i \in {\cal V}$, 指数收敛到唯一的全局最小值点$ x^{\ast} $.

证明. 该定理的证明与定理1 的证明相类似, 这里不再赘述.

注 2. 算法(3)与文献[29]中所提出的算法相类似. 但是, 文献[29]考虑的是局部成本函数强凸的情况, 而本文中只要求全局成本函数关于全局最小值点是有限强凸的, 是较之更一般的情况.

注 3. 算法(2)中$ x_i(0) $和$ q_i(0) $均可以任意选择的, 而在算法(3)中, 虽然$ x_i(0)$可以任意选择, 但要求$ \sum\nolimits_{i = 1}^{N}q_i(0) = 0 $, 因此算法(2)对初始条件$ q_i(0)$是更为鲁棒的. 然而, 与算法(3)相比, 式(2b)需要额外通信$ q_j $, 因此比算法(3)需要更多的通信开销.

4.   基于事件触发的分布式PI优化算法

为了避免智能体之间的连续通信和减少通信负担, 将第4节所提出的分布式PI算法与事件触发通信相结合, 提出了两种分布式事件触发算法并给出其收敛性分析. 首先, 基于分布式优化算法(2), 我们提出第一种事件触发算法, 描述如下:

其中, $ \{ t_k^j \}_{k = 1}^{\infty},\forall j\in {\cal V} $是待定的触发时间序列, 并且$ t^j_{k_j(t)} = \max \{ t_k^j: t_k^j \leq t \} $.

分布式事件触发算法设计中的关键问题是如何构造触发机制, 以保证提出的算法不存在Zeno行为, 并收敛到全局最小值点.

定理 3. 假设无向图是连通的, 并且假设1成立. 如果每个智能体$ i \in {\cal V}$运行分布式事件触发算法(4), 并通过如下方式确定其触发时间序列:

其中, 所有$ a_i, b_i, c_i, d_i>0$均为设计参数, 则有:

1) 算法(4)不存在Zeno行为;

2) 每个$ x_{i}(t) $, $ i\in {\cal V}$, 渐近收敛到全局最小值点$ x^{\ast} $;

3) 如果假设2 ~ 3也成立, 则每个$ x_{i}(t) $, $ i\in {\cal V}$, 以不小于$\dfrac{\epsilon_2}{\epsilon_4}$的速率指数收敛到唯一的全局最小值点$ x^{\ast} $, 其中$ {\epsilon_4}$是正常数, 并在证明中给出.

证明. 见附录C.

接下来, 基于算法(3), 我们提出了第二种事件触发算法, 描述如下所示:

下面的定理给出了与定理3类似的结果:

定理 4. 假设无向图是连通的, 并且假设1成立. 如果每个智能体$ i\in {\cal V}$运行分布式事件触发算法(6), 并通过如下方式确定其触发时间序列:

其中, $ a_i$, $ b_i>0$均为设计参数, 则有:

1) 算法(6)不存在Zeno行为;

2) 每个$ x_{i}(t) $, $ i\in {\cal V}$, 渐近收敛到全局最小值点$ x^{\ast} $;

3) 如果假设2 ~ 3也成立, 则每个$ x_{i}(t) $, $i\in {\cal V},$ 指数收敛到唯一的全局最小值点$ x^{\ast}. $

证明. 该定理的证明与定理3的证明相类似, 这里不再赘述.

注 4. 基于算法(2)和算法(3), 提出了对应的事件触发算法(4)和算法(6). 所提出的事件触发通信机制, 受到文献[37]中时变触发机制的启发. 与算法(6)的触发机制(7)相比, 算法(4)的触发机制(5)更为复杂且需要额外通信开销, 但是算法(4)的初始条件$ q_{i}(0) $是可以任意取值的, 更为鲁棒.

注 5. 文献[29]中定理13要求所有局部成本函数强凸, 而定理3和定理4只要求全局成本函数有限强凸, 并不要求所有的局部成本函数都如此或强凸. 此外, 我们提出的算法指数收敛到全局最小值点, 而文献[29]中提出的算法只能收敛到全局最小值点的一个邻域. 文献[44-45]提出的事件触发ZGS算法需要特殊的初始化, 而我们提出的算法允许对$ x_i(0) $的任意初始化.

5.   仿真实验

考虑一个包含50个智能体的大规模网络, 其中局部成本函数$ f_i$具体描述如下:

其中, $j = 1,2,\cdots,5$. 函数$ f_{i}(x) $, $i = 6,\cdots, 10$, $36,\cdots, $$ 40,$是非强凸的函数, 而全局成本函数$ \sum\nolimits_{i = 1}^{50}f_{i}(x) $关于点$ x^{*} $有限强凸. 所有局部成本函数均可微, 且具有局部Lipschitz梯度. 随机选取一个包含50个节点的无向连通图, 并针对该网络拓扑图以及上述定义的成本函数得到以下两部分的仿真结果.

不考虑事件触发时, 为了更好地体现算法(2), 算法(3)与文献[29-31]所提算法的区别, 我们对这些算法进行了仿真比较. 通过图1可以看出所有算法均为线性收敛. 此外, 算法(3)的收敛速度相对较快.

图 1  不同算法中$\sum\nolimits_{i = 1}^{50}\|x_{i}(t)-x^{*}\|^{2}$的演化

Fig. 1  The state evolution of $\sum\nolimits_{i = 1}^{50}\|x_{i}(t)-x^{*}\|^{2}$ in various algorithms

下载: 全尺寸图片 幻灯片

考虑事件触发时, 对于算法(4), 我们随机选择触发机制(5)中的设计参数$ a_i $, $ b_i $, $ c_i$和$ d_i $. 选择采样周期为 0.01 s. 图2展示了智能体 6, 16, 26, 36, 46 的状态演化过程, 从中我们可以清楚地看到每个智能体都收敛到全局最小值点$ x^{*} = -0.01214 $. 在$ [0, 40\; {\rm{s}}]$时间段内, 上述5个智能体分别被触发了$ 209, $$ \ 183, \ 161, \ 241, \ 142 $次. 由此可知, 事件触发算法(4)在仿真中针对上述5个节点避免了大约95.32%的通信开销.

图 2  算法(4)中智能体6, 16, 26, 36, 46的状态演化

Fig. 2  State evolutions of agents 6, 16, 26, 36, 46 of Algorithm (4)

下载: 全尺寸图片 幻灯片

对于算法(6), 我们随机选择触发机制(7)中的设计参数$ a_i$和$ b_i $. 选择采样周期为 0.01 s. 图3展示了智能体 6, 16, 26, 36, 46 的状态演化过程, 从中我们可以清楚地看到所有智能体收敛到全局最小值点$ x^{*} = -0.01214 $. 在$ [0, 40\; {\rm{s}}]$时间段内, 上述5个智能体分别被触发了$ 114, \ 121, \ 139, \ 94, \ 182 $次. 由此可知, 事件触发算法(6)在仿真中针对上述5个节点避免了大约96.75%的通信. 与算法(4)所对应的结果相比, 智能体被触发的次数更少, 因此节省了更多的通信和计算量.

图 3  算法(6)中智能体6, 16, 26, 36, 46的状态演化

Fig. 3  State evolutions of agents 6, 16, 26, 36, 46 of Algorithm (6)

下载: 全尺寸图片 幻灯片

6.   结论

本文考虑了一类分布式优化问题, 针对无向连通图, 基于比例积分策略提出了两类分布式优化算法, 在局部成本函数为可微凸函数的条件下, 证明了所提的分布式优化算法渐近收敛到全局最小值点. 当局部成本函数具有局部Lipschitz梯度, 并且全局成本函数对全局最小值点是强凸时, 证明了所提算法指数收敛到唯一的全局最小值点. 此外, 为了避免智能体之间的连续通信和减少通信开销, 提出了两种基于事件触发的分布式优化算法. 证明了所提出的算法不存在Zeno行为, 并且在相对应条件下保持了与连接通信下分布式优化算法一样的收敛性. 未来的一个方向是设计分布式优化算法动态事件触发通信机制的条件.

附录A

下面文献[46]的引理, 在后文中指数收敛的证明中起着重要作用.

引理 1. 假设无向图是连通的. 如果令$K_N = I_N- $$ \frac{1}{N}{\bf 1}_N{\bf 1}^{\rm T}_N$. 则有, Laplacian矩阵$ L$是半正定的, $ K_N{\bf 1}_N = 0 $, 以及

如下引理是对文献[18]中性质 3.6的推广, 其中每个局部成本函数梯度局部Lipschitz的假设放松了原有局部成本函数梯度全局Lipschitz的假设, 在接下来的证明中也很有用.

引理 2. 假设无向图是连通的, 以及假设1 ~ 3都成立. 那么对任意$ \varepsilon>0$以及任意紧的凸集$D\subseteq {\bf R}^n$, 以及$ x^*\in D $,

其中, ${\boldsymbol{x}} = [x_1,\cdots,x_N] ,$ $f({\boldsymbol{x}}) = \sum\nolimits_{i = 1}^N f_i(x_i)$, $\bar{{\boldsymbol{x}}} = {\bf 1}_N \otimes x^*$, $m(\varepsilon) = $$ \min\Big\{m_f-2 M(D) \iota,\frac{\varepsilon \rho_2(L)\iota^2}{ 1+\iota^2}\Big\},$ $M(D) = \max_{i\in{\cal V}}\{M_i(D)\} ,$ 以及$ \iota\in(0,\frac{m_f}{2M(D)}) $.

证明. 对任意$ {\boldsymbol{x}}\in D^{N} $, 对$ {\boldsymbol{x}} = {\boldsymbol{u}}+{\boldsymbol{v}}$进行分解, 且${\boldsymbol{u}} = $$ {\bf 1}_N \otimes u_0$, $u_0 = \frac{1}{N}\sum\nolimits_{i = 1}^Nx_i\in D$和${\boldsymbol{v}} = {\boldsymbol{x}}-{\boldsymbol{u}}$. 易知, ${\boldsymbol{v}}^{\rm T}({\bf 1}_N \otimes I_n) = $$ {\bf 0}_N$. 其余证明与文献[18]中性质 3.6 的证明相同, 这里不再赘述. □

附录B

定理 1的证明. 1) 在这一部分, 我们使用Lyapunov稳定性分析方法. 当假设1成立时, 每个$ x_i(t) $, $ i \in {\cal V}$, 都渐近收敛到全局最小值点$ x^* $, 其可能是不唯一的. 方便起见, 记符号${\boldsymbol{{x}}} = [{x}_1,\cdots,{x}_N]$, ${\boldsymbol{{q}}} = [{q}_1,\cdots,{q}_N]$, 以及$\nabla f({\boldsymbol{x}}) = [\nabla f_1(x_1), \cdots, $$ f_N(x_N)]$. 则算法(2)可以写为如下紧凑形式:

考虑如下函数:

其中, $ \bar{{\boldsymbol{x}}} = {\boldsymbol{1}}_N\otimes x^* $, $ \bar{{\boldsymbol{q}}} $满足$ (L \otimes I_n) \bar{{\boldsymbol{q}}} = -\nabla f(\bar{{\boldsymbol{x}}})$(根据文献[28] 中命题 3.2可知$ \bar{{\boldsymbol{q}}}$存在).

$ V_1({\boldsymbol{x}},{\boldsymbol{q}})$沿轨迹(B1)的导数满足:

其中, 用到了$ (L \otimes I_n) \bar{{\boldsymbol{q}}} = -\nabla {\boldsymbol{f}}(\bar{{\boldsymbol{x}}})$和${\bar{\boldsymbol{x}}}^{\rm T}(L \otimes I_n) = 0$. 由式(B3)可得, $ V_1({\boldsymbol{x}},{\boldsymbol{q}})$径向无界, 从而由LaSalle＇s不变集原理^[53]可知, $ {\boldsymbol{x}}(t)$ 渐近收敛于 $\{{\boldsymbol{1}}_N\otimes x^1 \in {\bf R}^{nN}:\; \sum\nolimits_{i = 1}^n(x^1-x^*)\times $$ (\nabla f_i(x^1)-\nabla f_i(x^*)) = 0\}$因为$ \sum\nolimits_{i = 1}^n\nabla f_i(x^*) = 0 $, 因此可知$\sum\nolimits_{i = 1}^n(x^1-x^*)(\nabla f_i(x^1)-\nabla f_i(x^*)) = 0$等价于$\sum\nolimits_{i = 1}^n \nabla f_i(x^1) = $$ 0$, 即$ x^1$是全局最小值点. 因此, $ {\boldsymbol{x}}(t)$渐近收敛于$ {\bf 1}_N \otimes x^* $, 即每个$ x_i(t) $, $ i \in {\cal V}$, 渐近收敛于$ x^* $.

2) 在这一部分, 我们证明当假设2和3成立时, 算法的指数收敛性.

我们首先证明对于任意的初始状态$ {\boldsymbol{x}}(0)$和$ {\boldsymbol{q}}(0) $, 存在凸紧集${\cal C}\subseteq {\bf R}^n$, 使得$ x^*\in{\cal C}$和$ x_i(t)\in{\cal C},\; \forall t\ge0,\; \forall i\in{\cal V} $. 集合$ {\cal C}$的具体形式依赖于$ {\boldsymbol{x}}(0) $, $ {\boldsymbol{q}}(0)$和$ x^* $, 将在后文中给出.

由式(B2)和(B3), 对任意$ t\ge0$和$ i\in{\cal V} $, 可得:

因此, ${\cal C} = \{x\in {\bf R}^n:\; ||x-x^*\|^2\le 2V_1({\boldsymbol{x}}(0),{\boldsymbol{q}}(0))\}$ 是我们要寻找的凸紧集.

接下来, 考虑如下函数:

其中, $\epsilon_1 = \frac{2(M({\cal C}))^2}{m_1\rho_2(L)},$ $m_1 = \min\Big\{m_f-2 M({\cal C}) \iota,\frac{\rho_2(L)\iota^2}{ 2(1+\iota^2)}\Big\} ,$ $M({\cal C}) = $$ \max\nolimits_{i\in{\cal V}}\{M_i({\cal C})\}$, 以及$\iota\in(0,\frac{m_f}{2M({\cal C})}) .$

$ V_2({\boldsymbol{x}},{\boldsymbol{q}})$沿轨迹(B1)的导数满足:

其中, 第二个等式用到了性质$ (L \otimes I_n) \bar{{\boldsymbol{q}}} = -\nabla {\boldsymbol{f}}(\bar{{\boldsymbol{x}}}) $, 以及引理1中(A1)给出的性质$ K_N L = L$和Cauchy-Schwarz不等式; 第二个不等式利用引理1中(A1)给出的性质$\rho_2(L) K_N\le $$ L$; 最后一个不等式用到了由假设3得到的$ f({\boldsymbol{x}})$具有局部Lipschitz梯度的性质.

类似地, $ V_3({\boldsymbol{x}},{\boldsymbol{q}})$沿轨迹(B1)的导数满足:

进而可得,

由于假设1 ~ 3成立, 由引理2中式(A2)可得,

因此, 由$({\boldsymbol{x}}-\bar{{\boldsymbol{x}}})^{\rm T}[(\nabla{f}({\boldsymbol{x}})-\nabla {f}({\bar{\boldsymbol{x}}}))]\ge0$, $ \epsilon_1 = \frac{2(M({\cal C}))^2}{m_1\rho_2(L)} $, 由式(B6) ~ (B8)可得

考虑如下候选Lyapunov函数

由(B9)可知, $ W_0({\boldsymbol{x}},{\boldsymbol{q}})$沿(B1)的轨迹的导数, 满足如下不等式,

其中, $ \epsilon_2 = \min\{\frac{\rho_2(L)}{4},\epsilon_1m_1,1\}>0 $.

令$ \epsilon_3 = \frac{\epsilon_1+3}{2} $, 可得,

从而, 由式(B11)和式(B12)可得 $\dot{W}_0({\boldsymbol{x}},{\boldsymbol{q}}) \leq $$ -\frac{\epsilon_2}{\epsilon_3}W_0({\boldsymbol{x}},{\boldsymbol{q}})$. 因此, $W_0({\boldsymbol{x}}(t),{\boldsymbol{q}}(t))\le W_0({\boldsymbol{x}}(0),{\boldsymbol{q}}(0)){\rm e}^{-\frac{\epsilon_2}{\epsilon_3}t}$. 由$\|{\boldsymbol{x}}-\bar{{\boldsymbol{x}}}\|^2\le $$ \frac{2}{\epsilon_1}W_0({\boldsymbol{x}},{\boldsymbol{q}})$. 从而可知, $ x_i(t)$以不小于$ \frac{\epsilon_2}{2\epsilon_3}>0$的速度指数收敛到全局唯一最小值点$ x^* $.

附录C

定理 3的证明. 我们首先给出一些必要的符号说明. 假定$t^j_1 = 0, \; \forall j\in{\cal V}$. 简便起见, 我们分别定义$\hat{x}_j(t) = x_j(t^j_{k_j(t)})$, $ \hat{q}_j(t) = q_j(t^j_{k_j(t)}) $, $ e^{x}_j(t) = \hat{x}_j(t)-x_j(t) $, $ e^{q}_j(t) = \hat{q}_j(t)-q_j(t) $, ${\boldsymbol{x}}(t) = [x_1(t),\cdots,x_N(t)]^{\rm T}$, 以及${\boldsymbol{q}}(t) = [q_1(t),\cdots,q_N(t)]^{\rm T}$.

1) 在这一部分中, 我们通过反证法证明算法(4)不存在Zeno行为. 假设算法(4)存在Zeno行为, 则存在一个智能体$ i \in {\cal V} $, 使得$ \lim\nolimits_{k\rightarrow \infty}t_{k}^i = T_0 $, 其中$ T_0 > 0$是一个常数. 注意到$ x_i(t)$和$ q_i(t)$都是连续的. 因此存在常数$ P_1>0$和$ P_2>0 $, 使得$ \| x_i(t)\|\leq P_1$和$ \| q_i(t)\|\leq P_2$对所有$ i \in {\cal V}$和所有$ t \in [0, T_0]$都成立.

根据假设1可知$ f({\boldsymbol{x}})$连续可微, 另外$\| x_i(t)\|\leq P_1, \; \forall i \in $$ {\cal V},\; \forall t \in [0, T_0]$. 因此, 存在一个常数$ P_3>0$使得$\| \nabla f({\boldsymbol{x}}) \| \leq $$ P_3,\; \forall t \in [0, T_0]$.

令$ C_1 = 2L_{ii}P_1+2L_{ii}P_2+P_3$以及$ C_2 = 2L_{ii}P_1 $. 那么, 由式(4)可得,

记$a_0 = \min\{a_1,\cdots,a_N\},$ $b_0 = \max\{b_1,\cdots,b_N\},$ $c_0 = \min $$ \{c_1,\cdots, c_N\}$, $d_0 = \max\{d_1,\cdots,d_N\}$, 以及$\epsilon_0 = \min\Big\{\frac{a_0e^{-b_0 T_0}}{2C_1},\, $$ \frac{c_0e^{-d_0 T_0}}{2C_2}\Big\} > 0$. 根据极限的性质可知, 存在正整数$ N(\epsilon_0) $, 使得,

对于给定的触发机制(5), 可得$ \; \forall t\ge0 $,

因为对于任何触发时间$ t_k^i $, 都有$ \hat{x}_i(t^i_k) = x_i(t_k^i) $. 因此由式(C1) ~ (C2)可得如下使得式(C4)成立的充分条件,

假设我们已经确定了智能体$ i$的第$ N(\epsilon)$次触发时间, 记为$ t^i_{N(\epsilon_0)} $. 记$ t^i_{N(\epsilon_0)+1} $和$ \tilde t^i_{N(\epsilon_0)+1} $分别为由式(5)和(C5)所确定的下一次触发时间. 则有, $ t^i_{N(\epsilon_0)+1}\geq \tilde {t}^i_{N(\epsilon_0)+1}$以及

其中, 不等号的成立用到了$ t^i_{N(\epsilon_0)}\le T_0 $. 从而可得,

这与式(C3)相矛盾. 因此, 事件触发算法(4)不存在Zeno行为.

2) 在这一部分, 与定理1中1)部分的证明相类似. 我们使用Lyapunov稳定性分析证明, 当假设1成立时, 每个$ x_i(t) $, $ i \in {\cal V}$都渐近收敛到全局最小值点$ x^* $. 方便起见, 记符号${\boldsymbol{\hat{x}}} = [\hat{x}_1,\cdots,\hat{x}_N]$, ${\boldsymbol{\hat{q}}} = [\hat{q}_1,\cdots,\hat{q}_N]$, ${\boldsymbol{e}}^{x} = [e^{x}_1,\cdots, e^{x}_N]$以及${\boldsymbol{e}}^{q} = [e^{q}_1,\cdots, e^{q}_N]$. 则算法(4)可以写成如下紧凑形式:

考虑Lyapunov函数(B2), 可得$ V_1({\boldsymbol{x}},{\boldsymbol{q}})$沿轨迹(C6)的导数满足:

其中, 第一个不等式由$ {\boldsymbol{e}}^x = {\boldsymbol{\hat{x}}}-{\boldsymbol{x}}$和$ {\boldsymbol{e}}^q = {\boldsymbol{\hat{q}}}-{\boldsymbol{q}}$得到; 根据$ (L \otimes I_n) \bar{{\boldsymbol{q}}} = -\nabla {\boldsymbol{f}}(\bar{{\boldsymbol{x}}})$可得第二个不等式; 最后一个不等式由${\bar{\boldsymbol{x}}}^{\rm T}(L \otimes I_n) = 0$, Young＇s不等式, Cauchy-Schwarz不等式诱导的不等式, 以及$b = \min\{b_1,\cdots,b_N,d_1,\cdots,d_N\} > 0$得到.

同时, 定义$a = \max \{a_1,\cdots, a_N,c_1,\cdots,c_N\} > 0$. 那么由式(5)可得,

由式(B2)可知,

根据式(C8), (C9)和(C10)可得如下不等式

因此

其中

由式(C10)可得,

根据式(C7), (C9)和(C12)可得如下不等式

其中, $ \gamma_2 = a(2a+\sqrt{\frac{2 \gamma_1}{N}})\rho(L) $.

关于$ t \geq 0$和所有的$ i\in{\cal V}$定义$z_i(t) = {\rm e}^{-\frac{b}{4}t}$, 记${\boldsymbol{z}}(t) = $$ [z_1(t),\cdots,z_N(t)]$. 考虑如下候选Lyapunov函数:

那么, 由式(C13)可知, $ W_1({\boldsymbol{x}},{\boldsymbol{q}},{\boldsymbol{z}})$沿轨迹(C6)的导数满足如下不等式,

因此,$ W_1({\boldsymbol{x}},{\boldsymbol{q}},{\boldsymbol{z}})$径向无界. 由LaSalle＇s不变集原理^[53]可知, $ {\boldsymbol{x}}(t)$渐近收敛于$\{{\boldsymbol{1}}_N\otimes x^1 \in {\bf R}^{nN}:\; \sum\nolimits_{i = 1}^n(x^1-x^*) $$ (\nabla f_i(x^1)-\nabla f_i(x^*)) = 0\}$. 因为$ \sum\nolimits_{i = 1}^n\nabla f_i(x^*) = 0 $, 从而可知$\sum\nolimits_{i = 1}^n(x^1-x^*)(\nabla f_i(x^1)-\nabla f_i(x^*)) = 0$等价于$\sum\nolimits_{i = 1}^n \nabla f_i(x^1)= $$ 0$, 即$ x^1$是全局最小值点. 因此, $ {\boldsymbol{x}}(t)$渐近收敛于$ {\bf 1}_N \otimes x^* $, 即每个$ x_i(t) $, $ i \in {\cal V}$, 渐近收敛于$ x^* $.

3) 在这一部分, 证明当假设2 ~ 3成立时, 算法的指数收敛性. 与定理1中2)的证明相类似.

由式(B2), (C14)和(C15), 可得对于所有的$ t\ge0$和$ i\in{\cal V} $, 有如下不等式成立:

因此, 所要寻找的凸紧集为${\cal C} = \{x\in {\bf R}^n:\; ||x-x^*\|^2\le $$ 2W_1({\boldsymbol{x}}(0),{\boldsymbol{q}}(0),{\boldsymbol{z}}(0))\}$.

接下来, 由式(B4)可得$ V_2$沿轨迹(C6)的导数满足

其中, 第二个等式用到了$ {\boldsymbol{e}}^q$的定义, 性质$(L \otimes I_n) \bar{{\boldsymbol{q}}} = -\nabla {\boldsymbol{f}}(\bar{{\boldsymbol{x}}})$, 以及引理1中(A1)给出的性质$ K_N L = L$和Cauchy-Schwarz不等式; 第二个不等式利用引理1中(A1)给出的性质$ \rho_2(L) K_N\le L $; 最后一个不等式用到了由假设3得到的$ f({\boldsymbol{x}})$具有局部Lipschitz梯度的事实.

类似地, 由(B15)可得$ V_3$沿轨迹(C6)的导数满足

进而可得,

因此, 由$({\boldsymbol{x}}-\bar{{\boldsymbol{x}}})^{\rm T}[(\nabla{f}({\boldsymbol{x}})-\nabla {f}({\bar{\boldsymbol{x}}}))]\ge0$, $\epsilon_1= \frac{2(M({\cal C}))^2}{m_1\rho_2(L)}$, 式(B8)以及式(C9)和(C16) ~ (C17)可得

其中$ \gamma_3 = a^2\rho(L)[1+\epsilon_1+(1+\epsilon_1)^2(1+\frac{1}{\epsilon_1})] $.

关于$ t \geq 0$和所有 $ i \in {\cal V} $, 定义 $\zeta_i(t) = {\rm e}^{-b t}$ 和 ${\boldsymbol{\zeta}}(t) = $$ [\zeta_1(t),\cdots,\zeta_N(t)]$. 考虑如下候选Lyapunov函数

由式(C18)和(C19)可知, $ W_2({\boldsymbol{x}},{\boldsymbol{q}},{\boldsymbol{\zeta}})$沿轨迹(C6)的导数满足如下不等式:

令$ \epsilon_4 = \max\{\frac{\epsilon_1+3}{2},\frac{1}{b}\} $, 则有:

那么, 由式(C20)和(C21)可得, $\dot{W}_2({\boldsymbol{x}},{\boldsymbol{q}},{\boldsymbol{\zeta}}) \leq -\frac{\epsilon_2}{\epsilon_4}W_2 ({\boldsymbol{x}}, $$ {\boldsymbol{q}},{\boldsymbol{\zeta}})$. 因此, $W_2({\boldsymbol{x}}(t),{\boldsymbol{q}}(t),{\boldsymbol{\zeta}}(t))\le W_2({\boldsymbol{x}}(0), {\boldsymbol{q}}(0),{\boldsymbol{\zeta}}(0)){\rm e}^{-\frac{\epsilon_2}{\epsilon_4}t}$. 由$ \|{\boldsymbol{x}}-\bar{{\boldsymbol{x}}}\|^2\le \frac{2}{\epsilon_1}W_2({\boldsymbol{x}},{\boldsymbol{q}},{\boldsymbol{\zeta}}) $可知, $ x_i(t)$以不小于$ \frac{\epsilon_2}{2\epsilon_4}>0$的速度指数收敛到全局唯一最小值点$ x^* $.