【学术报告】东北大学副教授石重霄：多智能体网络下的分布式优化算法研究

在研究多智能体网络下的分布式优化时，首先需要了解其研究对象——多智能体网络。多智能体网络是从实际网络系统中抽象出来的一类网络模型，可以定义为由一组智能体及其之间的通信连接构成的网络系统。典型的例子包括实际工程中的无线传感器网络、由多个机器人组成的系统，以及智能电网等。只要这些节点之间存在通信连接，就可以被视为一个网络系统。

多智能是指每个智能体具备一定的计算、感知、观测和通信能力，如图1所示。例如，在无线传感器网络中，每个传感器节点具备观测能力，能够获取目标的方位信息、距离信息，或者测量周围环境的温度等。

图1 多智能体网络

另一方面，如果在传感器节点上集成计算单元和通信模块，那么这些节点就进一步具备了计算和通信能力。在这种情况下，传感器节点就可以视为一个智能体。例如，一个机器人可以通过其配备的摄像头或雷达来观测和感知周围环境，然后将图像数据传回自身的CPU进行处理，最终形成决策结果，从而使机器人也具备了智能体的特征。

在多智能体网络中，“多”意味着多个智能体协同工作，以完成单个智能体难以完成的任务。多智能体网络的研究重点是探讨如何通过多个智能体的协作，来实现复杂任务。例如，在传感器网络中，测量目标位置通常需要多个传感器的协作。GPS定位技术中，它需要多个卫星对目标进行测距或测方位，通过整合这些数据来计算目标位置。通过这种协同工作，多个智能体能够完成单个智能体无法独立完成的复杂任务，从而体现出多智能体网络的优势和研究价值。

在由多个机器人进行目标追逐时，它们通常会形成包围动作，这是单一智能体无法完成的任务，体现了协同的必要性。同样，许多大型演出中常见的无人机编队表演，也需要多个无人机协作来形成各种图案，这也是单一无人机无法独立完成的任务。

在实际的多智能体网络中执行协同任务时，通常会遇到诸多优化问题。以无线传感器网络对目标定位为例，如图2所示，每个传感器节点需要利用自身的观测数据，并通过网络间的数据传递进行数据整合，最终求解一个全局二次优化问题以确定目标位置。在这里，每个节点都有自己的子目标函数。最终，所有节点需要通过优化这些子目标函数来求解出决策变量的最优点，即目标的真实位置。研究多智能体网络下的分布式优化，不仅有助于理解和解决单一智能体无法完成的复杂任务，还能提升协同任务的效率和准确性。

图2 多智能体网络协同任务

在电力网络的经济调度中，我们最终的目标是寻求成本最低的解决方案，这个最低成本可以通过优化问题来计算。传统的优化方法通常是集中式的，特点是需要一个中心节点来融合所有智能体的信息，计算出一个最优解，然后将其传回给智能体应用。然而，这种集中式计算模式存在一些限制，如必须有一个中心节点、计算效率低、灵活性差等。

为了弥补这些不足，我们提出了分布式优化方法。分布式优化无需中心节点，每个智能体仅需利用自身的智能决策，并通过与邻接节点的通信交流，实现对整体目标的优化，这类方法具有计算效率高、灵活性强等优点。

考虑由n个智能体组成的网络，其任务是协同优化如下的全局优化问题。每个节点都拥有一个私有的目标函数，该函数信息仅为相应的智能体所知，其他智能体无法获知。分布式优化的任务是，每个智能体需要利用自身子函数的信息，结合某些优化算法的运行，再通过分布式网络通信，最终求取全局优化问题的最优解。

分布式优化的研究可以分为两个主要方向：一是分布式网络环境，二是优化算法。分布式优化研究的爆发始于2009年，当时link发表了一篇重要文章，提出了最经典的基于梯度下降法的分布式优化算法。在2015年，专家学者通过改进分布式梯度下降法，提出了一种精确的一阶算法。这种算法在梯度法基础上添加了积分项，实现了快速且精确的收敛。

另一方面，从网络环境的角度出发，也有针对时变网络、有效网络、随机网络等网络结构进行优化算法的设计与分析。通过这种双重视角的研究，分布式优化在理论和应用上都取得了显著的进展。分布式优化方法不仅要设计高效的优化算法，还需考虑实际网络环境中的各种不确定性和复杂性，从而在多智能体网络中实现有效的全局优化。

尽管在分布式优化研究方面已有许多优秀成果，但仍存在一些关键问题需要解决。首先，从优化算法的角度出发，主要难点在于如何降低算法收敛性分析的复杂性以及如何提高算法的收敛速度。另一方面，从网络环境的角度来看，大部分研究成果是在安全或理想环境下进行的，而我们关注的是如何在非理想或对抗环境下保证算法的可靠性。针对这些问题，我们研究了在简化收敛性分析、提高收敛速度，并设计出在面对网络延迟、数据丢失和恶意攻击等情况下仍能保持高性能和可靠性的鲁棒分布式优化算法。

（一）如何降低算法收敛性分析的复杂性？

首先，我们研究了如何降低算法收敛性分析的复杂性，研究框架基于增广拉格朗日乘子法的分布式优化问题展开。考虑由n个智能体组成的无线网络，这些智能体的任务是协同优化一个全局性能指标。每个智能体拥有一个私有的目标函数，该函数仅由智能体所知，其他智能体无法获知，如图3所示。假设每个子函数都是强凸的，在这个假设下，设计的算法可以实现线性收敛。每个智能体拥有统一的决策变量，我们最终想要求出的最优解。针对这一问题，现有许多有效的方法可以进行求解，主要分为三类：利用一阶梯度信息设计分布式优化算法、利用二阶Hessian矩阵信息设计分布式优化算法，以及利用零阶目标函数信息设计分布式优化算法。大多数研究利用一阶梯度信息设计算法，而这种设计又分为最经典的梯度下降法和增广拉格朗日乘子法。

图3 问题描述

基于增广拉格朗日乘子法的分布式优化算法可以分为两大类：首先是X convex算法，它在经典梯度法基础上添加乘子更新的积分项，实质上是增广拉格朗日乘子法的一种形式；其次是DRM算法，全称为分布式线性化交替方向乘子法，通过信息化处理和分布式更新实现，同样属于增广拉格朗日乘子法的分布式优化算法。作为非数学专业背景的研究者，我发现研究这些算法最具挑战性的部分在于分析其收敛性和速度，这涉及复杂的数学推导和证明过程，尤其是算法中涉及多类网络相关参数的收敛性分析。 

在分布式优化算法的收敛性分析中，复杂的网络参数增加了推导和理解的难度，尤其是在看到一个推导结果后忘记了上文推导过程时，常常会产生对算法收敛性的疑问。我思考能否在不改变收敛性结果的情况下，提供更简单的收敛性分析方法或降低分析复杂性。尽管这项工作不直接改进算法设计，但有助于更直观地理解分布式优化算法的运行模式。

在分布式优化算法的收敛性分析中，设计思路对分析过程产生重大影响。首先，我们考虑原始的优化问题，所有智能体的决策变量都是相同的。为了优化这个问题，我们将每个智能体的局部决策变量替换到各自的目标函数中，并确保这些局部变量相等，从而等价化两个优化问题。

接下来，我们需要设计算法来处理带有约束的优化问题。简化约束的一种方法是引入关于拉普拉斯矩阵的分解技术，构建一个简单的一致性约束。图4中W和E是拉普拉斯矩阵的部分，涵盖了与拉普拉斯矩阵相关的信息。与现有算法相比，这种约束的构造较为复杂，因为它包含了更多的矩阵信息，如X中的邻接矩阵及其诱导的相关矩阵，以及DLM中的有项入设矩阵、无项入设矩阵和辅助决策变量。

图4 拉普拉斯矩阵分解技术

因此，可以看出，这些约束的构造相对来说较为复杂，我们可能需要在收敛性分析中进行进一步简化处理。接下来的任务是基于增广拉格朗日乘子法设计算法来解决带有约束的优化问题。首先构造一个增广拉格朗日函数，该函数在x方向上是凸的，在方向上是线性的，形成了一个马鞍形状的优化形式。

我们的目标是解决带有约束的优化问题，并最终将其转化为寻找拉格朗日函数的鞍点，即鞍点搜索算法，如图5所示。在进一步的收敛性分析中，我们只需证明算法估计变量与最优解之间的差距趋于0即可，这涉及算法的迭代关系。

图5 收敛性分析

通过拉普拉斯矩阵的分解，我们整合了多种网络相关参数，使得收敛性分析只需使用拉普拉斯矩阵的一类参数，其中包括最小非零特征值。

通过比较我们提出的算法收敛性分析过程与现有结果，我们有效地简化了分析过程，并且得出了与已有结果相符的结论：在固定步长满足一定条件时，算法生成的估计值以线性速度收敛到优化问题的最优解。

（二）如何提高算法的收敛速度？

接下来我们将进一步研究如何提升算法的收敛速度，研究框架基于一类分布式假设检验的设定展开。假设检验是统计学中的重要概念和方法，在各个领域都有广泛的应用，例如对模型参数进行估计、方差和均值的推断等。考虑一个通信链路，数据传输可能会遇到中断和丢包，我们需要推断中断的概率，这也涉及到假设检验的任务。

在多智能体网络中，假设检验的具体问题描述如下：考虑由N个智能体组成的时变网络，即节点之间的连接结构随时间变化，不一定始终保持连接，但整体上需要满足联合连通性条件。

进一步，在每个采样时刻，每个智能体收集到一个观测数据，这些数据可以表示为方差或者中断标签，例如，中断可以表示为0，没有中断表示为1，这些观测数据服从一个未知的概率分布。

图6是进行优化问题的等价转化，使用KL散度进行转换。KL散度是衡量两个概率分布之间差异的度量，其值大于等于0，数值越小表示两个分布之间差异越小。

在假设检验问题中，可以描述f₁与似然函数之间的差异性，并通过最小化一个核函数的数值来确定属于最优假设集中的假设。所有智能体共同解决这个全局优化问题，本质上是一个分布式优化问题。已有的研究在这方面设计了有效的算法，例如，2017年Link提出的非贝叶斯学习算法就是一个例子，该算法结合了贝叶斯更新规则和分布式网络通信。

图6 分布式优化

在该算法中，我关注的不仅是任务的完成，还包括算法的收敛速度和学习效率问题。已有研究证明，非最优假设的置信度以指数速度收敛。虽然收敛速度已经很快，但我们是否还有提升的空间，或者是否可以通过微调算法来进一步提高收敛速度，这是我们当前工作的重点。

我们的切入点是从观测数据角度出发的。在传统的非贝叶斯学习算法中，每一步的更新仅使用当前时刻的观测数据。在日常学习中，历史经验对于学习新知识具有指导意义，这也是学习迁移理论的一部分，涉及教育学中的相关问题。直观上来看，历史观测数据也应当对学习过程有所帮助。因此，我们思考在第k+1步时，将前k步的历史数据x₁到x_k引入算法中，是否能够提高算法的学习效率和收敛速度，这是我们设计的思路。

基于这一思路，我们设计了两类新的分布式优化算法，分别引入了历史数据的二重累积和三重累积，如图7所示。通过收敛性分析得出结论，更多重的历史数据累积会加快优化算法的收敛速度。仿真结果验证了这一结论，绿色虚线和蓝色实线分别表示二重和三重累积所对应的收敛速度，可以看到，累积的历史数据越多，算法的收敛速度越快。在图中，线性收敛表示没有引入历史数据的算法。纵坐标取对数，使得指数收敛的情况下呈现线性趋势，我们实现了超线性收敛。

图7 利用数据累积技术提高算法的收敛速度

历史数据累积技术的优点显而易见，但它也存在一些缺点。通过理论分析，我们得出结论，累积的历史数据越多，算法的展开性能越差，内存负担也越重。

展开性能指的是在每个k步时达到目标速度的概率。随着历史数据累积的增加，这一概率会降低，即展开性能变差。另一方面，内存负担的增加很容易理解，因为引入更多历史数据会增加内存使用量。因此，在利用这项技术提升算法收敛速度时，需要进行权衡。

（三）如何保证算法的可靠性？

先前从优化算法的角度探讨了收敛性及其速度相关的问题。现在我们转而从网络环境的角度出发，研究如何在对抗环境中确保算法的可扩展性。

在多智能体网络中，协同定位是一个关键问题，对于执行多种协同任务至关重要，如目标追逐和编队。定位的研究具有重要意义。过去的研究已将协同定位问题转化为一类分布式优化问题来解决。图8中包含N个静态智能体的网络，将其视为节点。每个节点可以分为两类：已知位置的主节点和待测位置的待定节点，用蓝色和橙色表示。

图8 基于方位的协同定位

节点i到节点j的方位由定位向量bⁱ_j描述。若i与j之间有边缘连接，则它们可以相互测量到对方的方位信息，并进行通信。方位测量信息由单位向量mⁱ_j表示。

基于上述网络模型与测量模型，我们提出了定位网络的概念，由四元组组成：主节点位置向量、待定节点集合、定位向量集合和方位测量信息集合。在通过设计有效的分布式算法，给定主节点位置信息和节点之间的方位信息，使得待定节点能够解算出其真实位置p_i。为此，我们将问题转化为求解非线性方程组的形式，并证明了当该方程组存在唯一解时，可以等价地将其转化为优化问题进行求解。

通过求解目标函数的梯度，可以得到一个分布式优化算法，每个节点仅利用其邻居的位置估计进行更新。研究表明，当优化问题的解是唯一且最优值为0时，算法生成的估计变量最终会收敛到节点的真实位置，从而完成定位任务。这里需要强调，解的唯一性和最优值为0的条件称为可定位条件。

针对已有结果，我们注意到在方位测量信息等于真实方位的情况下对算法和问题进行了研究。我们的目标是考虑当某些方位测量信息不准确时，尤其是在对抗环境中的情况。例如，在战场或存在黑客的环境中，可能会有对方篡改节点的测量数据，使方位测量信息不准确，从而导致定位结果错误。

如图9所示，假设节点P₃和P₄是待定节点，它们的方位信息当前是平的。如果这些方位测量信息被篡改成一个不正确的值，那么节点P₃的位置估计就会出现错误。

图9 对抗环境下定位算法的可靠性

我们的任务是在存在恶意或篡改的测量信息的情况下，仍然能够保证上述定位算法的可靠性。因此，我们首先提出了一个对抗模型，即考虑某些方位测量信息可能被篡改或是恶意的情况。这些恶意测量信息对应的边称为恶意边，其数量受到一个上限的限制，且严格小于总边数。

当面对对抗环境时，确保分布式定位算法的可靠性需要解决两个主要任务。首先，我们需要有效地搜索网络中的恶意测量信息，这些信息可能被恶意篡改以导致定位错误。我们采用逐步排除边的方法进行搜索，每次移除s条边并验证它们是否包含恶意信息。搜索的核心条件是确保在移除任意s条边后，定位网络仍能保持可定位，这是判断恶意信息存在的充分条件。

其次，一旦发现网络中的恶意测量信息，需要隔离这些信息以保护分布式定位算法的准确性和可靠性。为了确保全局一致性和信息同步，节点按照统一的搜索顺序运行分布式定位算法。这个搜索顺序结合了字典排序和网络泛洪算法，每个节点在每次搜索中都执行分布式定位算法，以验证最优化问题的解是否为0。这种方法不仅能有效搜索并隔离恶意测量信息，还能确保定位算法在对抗环境中的可靠性和稳定性。

在每次搜索中，运行分布式定位算法，其迭代次数受限于预设的最大迭代次数，这个值与阈值相关联，共同影响算法的停止条件。在达到预设的迭代次数后，算法返回一个位置估计值，并将其代入目标函数中进行评估，判断其是否小于预设的阈值。这里的阈值被定义为严格大于目标函数最优值的数值。根据目标函数值与阈值之间的差距，如果大于阈值，则表明搜索未成功，即去掉s条边后仍未包含所有恶意边；如果小于阈值，则表明搜索成功，此时的估计值可以视为目标位置的良好估计。

通过数学证明，我们得出了估计误差的界限，其与预设的阈值相关。该误差界限还与一个特定的矩阵相关，该矩阵代表在去掉s条边和所有恶意边后形成的子网络的方位拉普拉斯矩阵。这个矩阵的特性保证了误差界限的可靠性，与恶意测量信息无关。

最终，我们通过仿真验证了算法的有效性。在仿真中，我们设定了边47和59为恶意边，并且第577次搜索成功地包含了这两条边。设定的阈值为0.05，运行结果表明，在第577次搜索中，目标函数值显著低于阈值，证明了搜索的成功性。在此次搜索中，算法展现了良好的收敛性，如图10中蓝线所示，目标函数值逐渐趋近于0，并在1500多次迭代后以非常小的误差跳出循环。

图10 分布式定位算法的可靠性

在每次科研工作中，我们需要以解决新问题为初心。写作论文时，要明确所研究的科学问题是否具有重要性和新颖性。这不仅是审稿人关注的重点，也是科研工作的核心。在确立了新问题之后，选择合适的技术和方法去解决是至关重要的。大部分情况下，新问题会催生新技术和新方法的提出，这些技术和方法的有效性需要在理论和实验层面加以论证和验证。在论文的撰写过程中，确保论述新技术和方法的正确性，并通过实验数据验证其有效性，是至关重要的一步。

一篇优秀的论文不仅需要提出新问题和新方法，还需要对现有结果进行深入比较和理论分析。与现有研究成果的比较可以突显出新方法和技术的重要性和优势。此外，对理论性结果进行细致的分析和解释，能够帮助读者和审稿人更好地理解研究成果的价值和创新之处。在实验数据方面，充足的支持性数据能够进一步强化论文的完整性和说服力。

最近在审稿过程中，我发现一些论文虽然提出了新问题或新技术，但在对结果的比较和理论分析上显得不够完整，这可能会影响读者的理解和接受。因此，为了确保科研成果的有效传播和认可，我们在撰写论文时应该注重这些方面的完整性和深度分析。

写出一篇优秀的科研成果不仅需要提出新问题和采用新技术进行解决，还需要充分的实验数据支持。这些要素是确保论文完整性和说服力的关键。然而，一篇文章不可能完全包含所有要素，因为不同的研究问题可能会侧重于不同的方面。文章的质量和影响力往往取决于其中包含了多少关键点和独特之处。在科研道路上，理解和实践这些原则并没有捷径可循。

 “即使是千里马，也不能一蹴而就。”这句话深刻体现了在科研道路上持续努力和不懈追求的重要性。多年来，这句话一直激励着我，希望它也能为大家带来一些启发和思考。

个人简介

石重霄

东北大学副教授

石重霄，东北大学副教授，博士生导师。主要研究方向有多无人系统协同控制、优化与决策，信息物理系统安全性等，目前在相关领域发表SCI论文21篇，其中18篇以第一作者身份发表，包括在控制领域顶级期刊Automatica与IEEE Transactions on Automatic Control发表论文3篇（其中一篇以长文形式发表），以及在其他IEEE会刊发表论文5篇；入选2021年度中国博士后创新人才支持计划、沈阳市领军人才；主持国家自然科学基金青年项目、辽宁省自然科学基金面上资助计划项目、中国博士后科学基金面上项目等；获2023年度中国自动化学会优秀博士学位论文奖、2022年度辽宁省优秀博士学位论文奖。

*本报告版权属原作者所有，任何媒体、网站或个人未经授权不得转载、链接、转贴或以其他方式复制发布/发表。