分布式一致性最优化的梯度算法与收敛分析

工程科学学报 Chinese Journal of Engineering 分布式一致性最优化的梯度算法与收敛分析 梁舒彭开香 Distributed gradient-based consensus optimization algorithm and convergence analysis LIANG Shu,PENG Kaixiang 引用本文： 梁舒，彭开香.分布式一致性最优化的梯度算法与收敛分析[J].工程科学学报，2020,42(4)：434-440.doi: 10.13374j.issn2095-9389.2019.09.05.005 LIANG Shu,PENG Kaixiang.Distributed gradient-based consensus optimization algorithm and convergence analysis[J].Chinese Journal of Engineering,2020,42(4y:434-440.doi:10.13374.issn2095-9389.2019.09.05.005 在线阅读View online::htps:ldoi.org10.13374.issn2095-9389.2019.09.05.005 您可能感兴趣的其他文章 Articles you may be interested in 纯电动车用18650电池的一致性研究 Consistency study on 18650 cells used in electric vehicles 工程科学学报.2017,391)：107 https::/doi.org10.13374.issn2095-9389.2017.01.014 确定性多变量自校正控制的稳定性、收敛性和鲁棒性 Stability,convergence,and robustness of deterministic multivariable self-tuning control 工程科学学报.2019.41(9外：1215htps:/doi.org10.13374.issn2095-9389.2019.09.014 混沌人工鱼群的鲁棒保性能控制权值矩阵优化方法 A weighting matrix optimization method for robust guaranteed cost control based on chaos artificial fish swarm algorithm 工程科学学报.2018,40(4)：500 https::/1doi.org/10.13374.issn2095-9389.2018.04.014 基于UWB的地下定位算法和拓扑优化 An underground localization algorithm and topology optimization based on ultra-wideband 工程科学学报.2018,40(6：743 https:oi.org10.13374j.issn2095-9389.2018.06.013 基于自适应搜索的免疫粒子群算法 Immune particle swarm optimization algorithm based on the adaptive search strategy 工程科学学报.2017,39(1：125 https:/1doi.org/10.13374.issn2095-9389.2017.01.016

分布式一致性最优化的梯度算法与收敛分析 梁舒 彭开香 Distributed gradient-based consensus optimization algorithm and convergence analysis LIANG Shu, PENG Kaixiang 引用本文: 梁舒, 彭开香. 分布式一致性最优化的梯度算法与收敛分析[J]. 工程科学学报, 2020, 42(4): 434-440. doi: 10.13374/j.issn2095-9389.2019.09.05.005 LIANG Shu, PENG Kaixiang. Distributed gradient-based consensus optimization algorithm and convergence analysis[J]. Chinese Journal of Engineering, 2020, 42(4): 434-440. doi: 10.13374/j.issn2095-9389.2019.09.05.005 在线阅读 View online: https://doi.org/10.13374/j.issn2095-9389.2019.09.05.005 您可能感兴趣的其他文章 Articles you may be interested in 纯电动车用18650电池的一致性研究 Consistency study on 18650 cells used in electric vehicles 工程科学学报. 2017, 39(1): 107 https://doi.org/10.13374/j.issn2095-9389.2017.01.014 确定性多变量自校正控制的稳定性、收敛性和鲁棒性 Stability, convergence, and robustness of deterministic multivariable self-tuning control 工程科学学报. 2019, 41(9): 1215 https://doi.org/10.13374/j.issn2095-9389.2019.09.014 混沌人工鱼群的鲁棒保性能控制权值矩阵优化方法 A weighting matrix optimization method for robust guaranteed cost control based on chaos artificial fish swarm algorithm 工程科学学报. 2018, 40(4): 500 https://doi.org/10.13374/j.issn2095-9389.2018.04.014 基于UWB的地下定位算法和拓扑优化 An underground localization algorithm and topology optimization based on ultra-wideband 工程科学学报. 2018, 40(6): 743 https://doi.org/10.13374/j.issn2095-9389.2018.06.013 基于自适应搜索的免疫粒子群算法 Immune particle swarm optimization algorithm based on the adaptive search strategy 工程科学学报. 2017, 39(1): 125 https://doi.org/10.13374/j.issn2095-9389.2017.01.016

工程科学学报.第42卷.第4期：434-440.2020年4月 Chinese Journal of Engineering,Vol.42,No.4:434-440,April 2020 https://doi.org/10.13374/j.issn2095-9389.2019.09.05.005;http://cje.ustb.edu.cn 分布式一致性最优化的梯度算法与收敛分析 梁舒，彭开香 北京科技大学自动化学院工业过程知识自动化教育部重点实验室，北京100083 ☒通信作者.E-mail:sliang@ustb.edu.cn 摘要研究了多智能体网络中受集合约束的一致性最优化问题，提出了基于原始-对偶梯度的定步长分布式算法.算法中 包括步长在内的参数会影响收敛性，需要先进行收敛分析，再根据收敛条件设置合适的参数.本文首先针对一般的定步长迭 代格式，提出一种基于李雅普诺夫函数的收敛分析范式，它类似于一般微分方程关于李雅普诺夫稳定的分析方法.然后，针 对所考虑的分布式梯度算法，构造了合适的李雅普诺夫函数，并根据收敛条件得到了算法参数设定范围，避免了繁冗复杂的 分析论证.本文提出的理论与方法也为其他类型的分布式算法提供了一个框架性、系统性的论证方法. 关键词分布式优化：原始-对偶：收敛分析：李雅普诺夫函数；一致性 分类号TP27 Distributed gradient-based consensus optimization algorithm and convergence analysis LIANG Shu,PENG Kaixiang Key Laboratory of Knowledge Automation for Industrial Processes of Ministry of Education,School of Automation,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:sliang @ustb.edu.cn ABSTRACT A distributed optimization problem is cooperatively solved by a network of agents,which have significant applications in many science and engineering fields,such as metallurgical engineering.For complex industrial processes with multiple-level characteristics,varying working conditions,and long processes,numerous optimization decision-making micro and macro control problems,such as product quality control,production planning,scheduling,and energy comprehensive deployment,are encountered. The theory and method of distributed optimization are keys to promoting the strategic decision-making of the integration of industrialization and new-generation industrial revolution.Their development enhances the ability to deal with large-scale and complex problems of big data,which have important practical value and economic benefits.In this study,consensus optimization with set constraints in multi-agent networks was explored.A distributed algorithm with a fixed step size was proposed on the basis of a primal- dual gradient scheme.Parameters such as step size affect the convergence of the algorithm.As such,convergence should be analyzed first,and appropriate parameters should be subsequently set in accordance with convergence conditions.Existing works have constructed different Lyapunov functions by exploiting the specific iteration scheme of this algorithm and analyzing convergence.Conversely,a convergence analysis paradigm based on a Lyapunov function was proposed in this study for general fixed step size iteration schemes, which were similar to the analysis method of Lyapunov convergence for general differential equations.A suitable Lyapunov function was constructed for the distributed gradient algorithm,and a parameter setting range was obtained in accordance with the convergence conditions.The proposed method avoids the tedious and complicated analysis of algorithm convergence and parameter assignment.The theory and method presented in this study also provide a framework and systematic demonstration method for other types of distributed algorithms and may be regarded as future directions of distributed optimization. 收稿日期：2019-09-05 基金项目：国家自然科学基金资助项目(61903027,61873024)

分布式一致性最优化的梯度算法与收敛分析 梁    舒苣，彭开香 北京科技大学自动化学院工业过程知识自动化教育部重点实验室，北京 100083 苣通信作者，E-mail：sliang@ustb.edu.cn 摘    要    研究了多智能体网络中受集合约束的一致性最优化问题，提出了基于原始–对偶梯度的定步长分布式算法. 算法中 包括步长在内的参数会影响收敛性，需要先进行收敛分析，再根据收敛条件设置合适的参数. 本文首先针对一般的定步长迭 代格式，提出一种基于李雅普诺夫函数的收敛分析范式，它类似于一般微分方程关于李雅普诺夫稳定的分析方法. 然后，针 对所考虑的分布式梯度算法，构造了合适的李雅普诺夫函数，并根据收敛条件得到了算法参数设定范围，避免了繁冗复杂的 分析论证. 本文提出的理论与方法也为其他类型的分布式算法提供了一个框架性、系统性的论证方法. 关键词    分布式优化；原始–对偶；收敛分析；李雅普诺夫函数；一致性 分类号    TP27 Distributed gradient-based consensus optimization algorithm and convergence analysis LIANG Shu苣 ，PENG Kaixiang Key Laboratory of Knowledge Automation for Industrial Processes of Ministry of Education, School of Automation, University of Science and Technology Beijing, Beijing 100083, China 苣 Corresponding author, E-mail: sliang@ustb.edu.cn ABSTRACT    A distributed optimization problem is cooperatively solved by a network of agents, which have significant applications in many  science  and  engineering  fields,  such  as  metallurgical  engineering.  For  complex  industrial  processes  with  multiple-level characteristics,  varying  working  conditions,  and  long  processes,  numerous  optimization  decision-making  micro  and  macro  control problems,  such  as  product  quality  control,  production  planning,  scheduling,  and  energy  comprehensive  deployment,  are  encountered. The  theory  and  method  of  distributed  optimization  are  keys  to  promoting  the  strategic  decision-making  of  the  integration  of industrialization and new-generation industrial revolution. Their development enhances the ability to deal with large-scale and complex problems  of  big  data,  which  have  important  practical  value  and  economic  benefits.  In  this  study,  consensus  optimization  with  set constraints in multi-agent networks was explored. A distributed algorithm with a fixed step size was proposed on the basis of a primal￾dual gradient scheme. Parameters such as step size affect the convergence of the algorithm. As such, convergence should be analyzed first, and appropriate parameters should be subsequently set in accordance with convergence conditions. Existing works have constructed different  Lyapunov  functions  by  exploiting  the  specific  iteration  scheme  of  this  algorithm  and  analyzing  convergence.  Conversely,  a convergence analysis paradigm based on a Lyapunov function was proposed in this study for general fixed step size iteration schemes, which were similar to the analysis method of Lyapunov convergence for general differential equations. A suitable Lyapunov function was constructed for the distributed gradient algorithm, and a parameter setting range was obtained in accordance with the convergence conditions. The proposed method avoids the tedious and complicated analysis of algorithm convergence and parameter assignment. The theory and method presented in this study also provide a framework and systematic demonstration method for other types of distributed algorithms and may be regarded as future directions of distributed optimization. 收稿日期: 2019−09−05 基金项目: 国家自然科学基金资助项目（61903027，61873024） 工程科学学报，第 42 卷，第 4 期：434−440，2020 年 4 月 Chinese Journal of Engineering, Vol. 42, No. 4: 434−440, April 2020 https://doi.org/10.13374/j.issn2095-9389.2019.09.05.005; http://cje.ustb.edu.cn

梁舒等：分布式一致性最优化的梯度算法与收敛分析 435. KEY WORDS distributed optimization;primal-dual;convergence analysis;Lyapunov function;consensus 分布式优化是多智能体系统控制、网络通信 题，给出定步长分布式原始一对偶梯度算法，并对 和数学规划的赛博空间(Cyberspace)科学，在众多 算法的收敛性进行分析论证.最主要的贡献在于 科学与工程中具有广阔的发展前景-以钢铁行 提出一种基于李雅普诺夫函数的收敛分析范式： 业自动化为例，近年来我国钢铁生产企业普遍建 针对一般的定步长迭代格式，给出基于李雅普诺 立并实施了企业资源计划、生产执行系统、生产 夫函数的收敛条件，类似于一般微分方程关于李 过程系统等多层次的集成自动化系统.对于具有 雅普诺夫稳定的分析方法.这种方法带来的好处 多层级、变工况、长流程等特点的复杂工业过程， 在于将繁冗复杂的收敛性分析工作简化为构造李 其产品质量管控、生产计划与调度、能源综合调 雅普诺夫函数并验证收敛条件.在此基础上，本文 配等微观与宏观调控方面存在大量的优化决策问 将该方法应用到分布式原始-对偶梯度算法中，给 题)分布式优化理论与方法是促进两化融合战略 出算法参数应满足的收敛条件.与已有文献中的 决策和新一代工业革命的关键使能技术，其发展 方法相比，如文献[9]和[101，虽然它们从不同的 将增强人们对付大数据、大规模问题和复杂问题 角度利用算法具体结构设计构造了李雅普诺夫函 的能力，具有重要的实际应用意义并蕴藏着极大 数并辅助收敛分析，但本文提出的方法具有框架 的经济效益 性和系统性，对其他类型分布式优化算法的收敛 分布式优化的一类抽象问题类型是一致性最 分析也具有参考价值 优化，要求所有个体的决策变量最终实现一致性， 下面介绍本文的记号.R和R"分别代表实数空 并且一致点是一个凸优化问题的最优解.Nedic等- 间和n维欧氏空间.记(x,y)为向量x和y的内积， 对该问题进行了较深入地研究，主要针对非光滑 ‖·，和‖·分别代表2-范数和无穷范数 的目标函数，采用分布式次梯度的方法进行求解. 对于N个列向量x1,…,xw,使用col(x1,…,xN)代表 其中，为了确保算法的收敛性，需要采用逐渐衰减 其堆栈而成的列向量.用0m、1n分别表示分量全部 并趋于零的步长.Shi等m针对无约束的光滑最优 为0和分量全部为1的列向量，用In表示Rx中的单 一致性，提出一种定步长并能精确收敛到最优解 位阵.对于矩阵A=[a认a代表该矩阵在第行第 的分布式算法.该算法主要的思想是对所有个体 列的元素.符号⑧表示矩阵的Kronecker乘积 的梯度之和进行跟踪，并利用不精确梯度理论对 1预备知识 算法的收敛性进行分析.基于这种方法，Nedic等阁 改进了这种算法，并利用小增益的技术给出了算 本节的主要目的是罗列后续论述所需的预备 法的指数收敛证明.需要指出，这类算法仅处理无 知识，包括凸集与凸函数，以及图论 约束的分布式一致性最优化问题，目前还不能推 1.1凸集与凸函数 广到有约束的问题.Liu等9和Lei等o利用经典 本段介绍凸集及其投影的相关定义和性质， 约束优化中的原始-对偶梯度方法，给出了分布式 更详细的论述可参考专著[1刀.设2是维欧氏空 原始-对偶梯度算法.这类算法也采用了固定的步 间Rn中的集合，若对任意x,y∈2和0<T<1,均有 长，能够精确收敛到最优解，而且可以处理带有约 tx+(1-ty∈2，则称2为凸集.若一个集合中任意 束的问题.Liang等针对无约束情形下的分布式 点列的极限点仍然属于该集合，则称该集合是闭 原始-对偶梯度算法，基于变分分析中的度量次正 集.定义Pa(z)兰argmineol-xl2为点z∈R"到闭凸 则性，给出算法指数收敛的判据，降低了对目标函 集合2的欧氏距离投影.投影算子具有一个基本 数强凸性的要求.此外，值得指出，有不少学者从 性质：(z-Pa(z),Pa(z)-x)≥0，Yz∈R",Yxe 连续时间微分方程的角度进行了分布式优化算法 本段介绍凸函数的基本概念和性质，更多结 设计，如文献[12-16].总之，关于分布式一致性最 论可参考文献[18.设2cR为凸集，f:2→R为 优化问题已有不少研究，而近年来学者们更加关 一个实函数.如果对任意x,y∈2和0<T<1,均有 注分布式定步长算法，以及对它们收敛性质的分 f(rx+(1-Ty)≤fx)+(1-T)fy),则称f为凸函数 析论证 当f可微时，其梯度记为Vfx).可微凸函数具有一 本文考虑带有约束的分布式一致性最优化问 个基本性质：

KEY WORDS    distributed optimization；primal-dual；convergence analysis；Lyapunov function；consensus 分布式优化是多智能体系统控制、网络通信 和数学规划的赛博空间（Cyberspace）科学，在众多 科学与工程中具有广阔的发展前景[1–2] . 以钢铁行 业自动化为例，近年来我国钢铁生产企业普遍建 立并实施了企业资源计划、生产执行系统、生产 过程系统等多层次的集成自动化系统. 对于具有 多层级、变工况、长流程等特点的复杂工业过程， 其产品质量管控、生产计划与调度、能源综合调 配等微观与宏观调控方面存在大量的优化决策问 题[3] . 分布式优化理论与方法是促进两化融合战略 决策和新一代工业革命的关键使能技术，其发展 将增强人们对付大数据、大规模问题和复杂问题 的能力，具有重要的实际应用意义并蕴藏着极大 的经济效益. 分布式优化的一类抽象问题类型是一致性最 优化，要求所有个体的决策变量最终实现一致性， 并且一致点是一个凸优化问题的最优解. Nedic 等[4−6] 对该问题进行了较深入地研究，主要针对非光滑 的目标函数，采用分布式次梯度的方法进行求解. 其中，为了确保算法的收敛性，需要采用逐渐衰减 并趋于零的步长. Shi 等[7] 针对无约束的光滑最优 一致性，提出一种定步长并能精确收敛到最优解 的分布式算法. 该算法主要的思想是对所有个体 的梯度之和进行跟踪，并利用不精确梯度理论对 算法的收敛性进行分析. 基于这种方法，Nedic 等[8] 改进了这种算法，并利用小增益的技术给出了算 法的指数收敛证明. 需要指出，这类算法仅处理无 约束的分布式一致性最优化问题，目前还不能推 广到有约束的问题. Liu 等[9] 和 Lei 等[10] 利用经典 约束优化中的原始–对偶梯度方法，给出了分布式 原始–对偶梯度算法. 这类算法也采用了固定的步 长，能够精确收敛到最优解，而且可以处理带有约 束的问题. Liang 等[11] 针对无约束情形下的分布式 原始–对偶梯度算法，基于变分分析中的度量次正 则性，给出算法指数收敛的判据，降低了对目标函 数强凸性的要求. 此外，值得指出，有不少学者从 连续时间微分方程的角度进行了分布式优化算法 设计，如文献 [12–16]. 总之，关于分布式一致性最 优化问题已有不少研究，而近年来学者们更加关 注分布式定步长算法，以及对它们收敛性质的分 析论证. 本文考虑带有约束的分布式一致性最优化问 题，给出定步长分布式原始–对偶梯度算法，并对 算法的收敛性进行分析论证. 最主要的贡献在于 提出一种基于李雅普诺夫函数的收敛分析范式： 针对一般的定步长迭代格式，给出基于李雅普诺 夫函数的收敛条件，类似于一般微分方程关于李 雅普诺夫稳定的分析方法. 这种方法带来的好处 在于将繁冗复杂的收敛性分析工作简化为构造李 雅普诺夫函数并验证收敛条件. 在此基础上，本文 将该方法应用到分布式原始–对偶梯度算法中，给 出算法参数应满足的收敛条件. 与已有文献中的 方法相比，如文献 [9] 和 [10]，虽然它们从不同的 角度利用算法具体结构设计构造了李雅普诺夫函 数并辅助收敛分析，但本文提出的方法具有框架 性和系统性，对其他类型分布式优化算法的收敛 分析也具有参考价值. R R n n ⟨x, y⟩ x y · 2 · ∞ N x1,··· , xN col(x1,··· , xN) 0n 1n 0 1 In R n×n A = [ai j] ai j i j ⊗ 下面介绍本文的记号. 和 分别代表实数空 间和 维欧氏空间. 记 为向量 和 的内积 ， 和 分别代表 2-范数和无穷范数. 对于 个列向量 ，使用 代表 其堆栈而成的列向量. 用 、 分别表示分量全部 为 和分量全部为 的列向量，用 表示 中的单 位阵. 对于矩阵 ， 代表该矩阵在第 行第 列的元素. 符号 表示矩阵的 Kronecker 乘积. 1    预备知识 本节的主要目的是罗列后续论述所需的预备 知识，包括凸集与凸函数，以及图论. 1.1    凸集与凸函数 Ω n R n x, y ∈ Ω 0 < τ < 1 τx+(1−τ)y ∈ Ω Ω PΩ(z) ≜ argminx∈Ω∥z− x∥2 z ∈ R n Ω ⟨z− PΩ(z),PΩ(z)− x⟩ ⩾ 0,∀z ∈ R n ,∀x ∈ Ω 本段介绍凸集及其投影的相关定义和性质， 更详细的论述可参考专著 [17]. 设 是 维欧氏空 间 中的集合. 若对任意 和 ，均有 ，则称 为凸集. 若一个集合中任意 点列的极限点仍然属于该集合，则称该集合是闭 集. 定义 为点 到闭凸 集合 的欧氏距离投影. 投影算子具有一个基本 性质： . Ω ⊂ R n f : Ω → R x, y ∈ Ω 0 < τ < 1 f(τx+(1−τ)y) ⩽ τ f(x)+(1−τ)f(y) f f ∇f(x) 本段介绍凸函数的基本概念和性质，更多结 论可参考文献 [18]. 设 为凸集， 为 一个实函数. 如果对任意 和 ，均有 ，则称 为凸函数. 当 可微时，其梯度记为 . 可微凸函数具有一 个基本性质： 梁    舒等： 分布式一致性最优化的梯度算法与收敛分析 · 435 ·

436 工程科学学报，第42卷，第4期 0≤fy)-fx)-y-x,Vfx)》,Yx,y∈2 其中，xcol(x1,…,xw,fx)兰fi(x)+…+fN(xw), 此外，若映射7fx)关于x是k-Lipschitz连续的， eΠg2,o∩g 其中k>0为某个常数，则不论f是否是凸函数，都 在求解问题(1)的过程中，假定每个个体 有下面不等式成立： i∈V的本地目标函数不能被全局共享或者被其他 f0)-f-0-xf》≤5y-呢，xye 个体获取，而个体能够根据本地数据获取目标函 数在给定点的梯度值，但无法获取其他个体目标 1.2图论 函数相关的任何信息 网络节点之间的信息分享关系可以通过图论 下面给出问题(1)的基本假设条件 中的基本概念进行描述.一个图G油节点集合V和 假设1：对于每个iey,fx)是可微凸函数，且 边集8构成，记为G=(V,8).对于具有N个节点的 Vfx)是Kr-Lipschitz连续的，其中Kf>0为某个常 网络，通常记V={L,…,W.边集8cV×V刻画了 数.2是非空的闭凸集合.并且，优化问题(1)至少 节点之间的信息分享关系：若无序节点对（亿，）∈8， 存在一个有限的最优解 那么节点和节点j可以相互通信.如果对于任意 假设2：图G是一个连通图 i,j∈V,都可以从节点出发通过若干条边连接到 上述条件是最基本的，也常见于其他文献中 节点，则称G为连通图.另外，可以通过一些代数 在假设1中，与2的凸性保证问题(1)是一个凸 量对图进行描述，定义图G的加权邻接矩阵 优化问题.的可微性使得个体能够利用本地梯度 A=[a当(，》∈时，a=ai>0,否则a=0.对 信息进行寻优.最优解集非空则确保了问题的适 于任意iey,节点的度定义为d∑a进一步， 定性.此外，假设2中的连通性使多智能体网络实 图的度矩阵定义为D±diag{di,…,dwh,图的Laplace 现整体一致性和最优性成为可能 矩阵定义为LD-A.矩阵L是对称半正定矩阵， 注1：与文献[7]、[8]和[11]相比，本文的分布 且L1N=0m.而且，若图g是连通的，则L仅有一个 式优化的问题模型带有集合约束，所以具有更广 零特征值，其他特征值都为正数.有关图论和代数 的应用范围.文献[4]考虑了集合约束，但仅对相 图论的详细内容可以参考文献[19] 同的约束情形进行了分析，即21=…=2w.而本 2 优化问题与分布式算法 文不需要该限制条件 2.2分布式算法 本节首先描述分布式一致性最优化问题，然 为了能够借助凸优化理论与算法对问题(1) 后给出求解该问题的分布式算法 进行求解，先将一致性等式约束x1=…=xw等价地 2.1问题描述 转化为标准等式约束形式h(x)=0.事实上，可以选 考虑由N个个体组成的多智能体网络，其信息 取h(x)=L⑧Inx,其中L是图G的Laplace矩阵.这是 分享关系图为g=(V,8).对于i∈V,个体i可以控 因为，在假设2的条件下，L⑧Inx=0mw当且仅当 制本地的决策变量x:∈2，其中，2cR"是本地可 x1=…=xN.于是，问题(I)的等价描述为 行集合.多智能体一致性控制问题，是指设计分布 fo,s.tL®Lnr=0nN (2) 式的控制律，使得所有决策变量可以从初态收敛 到某个相同的末态，即渐近满足x1=…=xw.这里 问题(2)是一个标准的约束优化问题，可以定 的分布式，是指仅允许从本地数据和网络邻居个 义一个Lagrange函数 体中获得信息来更新决策变量.进一步，考虑每个 (3) 个体都有一个关于决策变量的目标函数（成本函 kW色+LL®l+号xL®l, 数或效用函数)，记为fx).分布式一致性最优化 其中，l±col(d,…,dw)∈Rmv为Lagrange乘子，B>0 问题，是希望设计分布式算法，使得多智能体网络 为一个常数.通常也把x和分别称为原始变量和 不仅能够实现一致性，还能实现总体目标函数的 对偶变量.在假设1的条件下，最优化问题(2)的 一阶原始-对偶最优条件为 最优性 结合上述多智能体网络背景，分布式一致性 OnN=Pa(x-aVxL(x,A))-x= Pn(x-a(Tfx)+BL⑧lnx+L⑧Ln)-x (4) 最优化问题的数学描述为 0nN=7C(x,)=L⑧Inx fs.L=…=xw∈o (1) 其中，a>0为任意常数

0 ⩽ f(y)− f(x)−⟨y− x,∇f(x)⟩,∀x, y ∈ Ω ∇f(x) x κ κ > 0 f 此外，若映射 关于 是 -Lipschitz 连续的， 其中 为某个常数，则不论 是否是凸函数，都 有下面不等式成立： f(y)− f(x)−⟨y− x,∇f(x)⟩ ⩽ κ 2 ∥y− x∥ 2 2 ,∀x, y ∈ Ω 1.2    图论 G V E G = (V,E) N V = {1,··· ,N} E ⊂ V ×V(i, j) ∈ E i j i, j ∈ V i j G G A = [ai j] (i, j) ∈ E ai j = aji > 0 ai j = 0 i ∈ V i di ≜ ∑N j=1 ai j D ≜ diag{d1,··· , dN} L ≜ D− A L L1N = 0n G L 网络节点之间的信息分享关系可以通过图论 中的基本概念进行描述. 一个图 由节点集合 和 边集 构成，记为 . 对于具有 个节点的 网络，通常记 . 边集 刻画了 节点之间的信息分享关系：若无序节点对 ， 那么节点 和节点 可以相互通信. 如果对于任意 ，都可以从节点 出发通过若干条边连接到 节点 ，则称 为连通图. 另外，可以通过一些代数 量 对 图 进 行 描 述 . 定 义 图 的 加 权 邻 接 矩 阵 ：当 时 ， ，否则 . 对 于任意 ，节点 的度定义为 . 进一步， 图的度矩阵定义为 ，图的 Laplace 矩阵定义为 . 矩阵 是对称半正定矩阵， 且 . 而且，若图 是连通的，则 仅有一个 零特征值，其他特征值都为正数. 有关图论和代数 图论的详细内容可以参考文献 [19]. 2    优化问题与分布式算法 本节首先描述分布式一致性最优化问题，然 后给出求解该问题的分布式算法. 2.1    问题描述 N G = (V,E) i ∈ V i xi ∈ Ωi Ωi ⊂ R n x1 = ··· = xN fi(xi) 考虑由 个个体组成的多智能体网络，其信息 分享关系图为 . 对于 ，个体 可以控 制本地的决策变量 ，其中， 是本地可 行集合. 多智能体一致性控制问题，是指设计分布 式的控制律，使得所有决策变量可以从初态收敛 到某个相同的末态，即渐近满足 . 这里 的分布式，是指仅允许从本地数据和网络邻居个 体中获得信息来更新决策变量. 进一步，考虑每个 个体都有一个关于决策变量的目标函数（成本函 数或效用函数），记为 . 分布式一致性最优化 问题，是希望设计分布式算法，使得多智能体网络 不仅能够实现一致性，还能实现总体目标函数的 最优性. 结合上述多智能体网络背景，分布式一致性 最优化问题的数学描述为 min x∈Ω f(x), s.t. x1 = ··· = xN ∈ Ω0 （1） x ≜ col(x1,··· , xN) f(x) ≜ f1(x1)+···+ fN(xN) Ω ≜ ∏N i=1 Ωi Ω0 ≜ ∩N i=1 Ωi 其 中 ， ， ， ， . i ∈ V i 在求解问题 （ 1）的过程中 ，假定每个个体 的本地目标函数不能被全局共享或者被其他 个体获取，而个体 能够根据本地数据获取目标函 数在给定点的梯度值，但无法获取其他个体目标 函数相关的任何信息. 下面给出问题（1）的基本假设条件. i ∈ V fi(xi) ∇fi(xi) κ f κ f > 0 Ωi 假设 1：对于每个 ， 是可微凸函数，且 是 -Lipschitz 连续的，其中 为某个常 数. 是非空的闭凸集合. 并且，优化问题（1）至少 存在一个有限的最优解. 假设 2：图 G 是一个连通图. fi Ωi fi 上述条件是最基本的，也常见于其他文献中. 在假设 1 中， 与 的凸性保证问题（1）是一个凸 优化问题. 的可微性使得个体能够利用本地梯度 信息进行寻优. 最优解集非空则确保了问题的适 定性. 此外，假设 2 中的连通性使多智能体网络实 现整体一致性和最优性成为可能. Ω1 = ··· = ΩN 注 1：与文献 [7]、[8] 和 [11] 相比，本文的分布 式优化的问题模型带有集合约束，所以具有更广 的应用范围. 文献 [4] 考虑了集合约束，但仅对相 同的约束情形进行了分析，即 . 而本 文不需要该限制条件. 2.2    分布式算法 x1 = ··· = xN h(x) = 0 h(x) = L⊗ In x L G L⊗ In x = 0nN x1 = ··· = xN 为了能够借助凸优化理论与算法对问题（1） 进行求解，先将一致性等式约束 等价地 转化为标准等式约束形式 . 事实上，可以选 取 ，其中 是图 的 Laplace 矩阵. 这是 因为，在假设 2 的条件下， 当且仅当 . 于是，问题 (1) 的等价描述为 min x∈Ω f(x), s.t. L⊗ In x = 0nN （2） 问题（2）是一个标准的约束优化问题，可以定 义一个 Lagrange 函数 L(x,λ) ≜ f(x)+⟨λ, L⊗ In x⟩+ β 2 ⟨x, L⊗ In x⟩ （3） λ ≜ col(λ1,··· ,λN) ∈ R nN β > 0 x λ 其中， 为 Lagrange 乘子， 为一个常数. 通常也把 和 分别称为原始变量和 对偶变量. 在假设 1 的条件下，最优化问题（2）的 一阶原始–对偶最优条件为 0nN = PΩ (x−α∇xL(x,λ))− x = PΩ (x−α(∇f(x)+βL⊗ In x+ L⊗ Inλ))− x 0nN = ∇λL(x,λ) = L⊗ In x （4） 其中， α > 0 为任意常数. · 436 · 工程科学学报，第 42 卷，第 4 期

梁舒等：分布式一致性最优化的梯度算法与收敛分析 437. 根据最优条件(4)，可以设计一个基于原始- V(z,z)≥0，且V(z,z*)=0台z=z; 对偶梯度的迭代算法： 2)对于任意的z°∈乙，V(z,z)关于z是水平强 xilk+1]=Po;(xi[k]- 制的，即对于任意的正数y>0,V的水平集合 N lev≤V{z∈ZIV(z,z)≤yl有界； Vfrk)+B》a(x-xk)+ 3)对于任意的z*∈Z,V(z,z)关于z可微，且映 射VzV(z,z)在zeZ上是kw-Lipschitz连续的，其中 (5) ∑ad[-[ kw>0是一个常数； 4)存在某个常数6>0，使得对于任意的z*∈Z, k+=内+e∑ax-xk 都有(F(z,V:V(z,z)》≥6F(z)服，Yz∈Z,其中F(z)是 (7)中的映射； 其中，常数α和B待定，它们将在收敛分析中根据收 5)选代格式(7)中，步长满足0<<2 敛条件来确定.算法(5)是一个分布式算法.这是因 那么，由算法(7)产生的序列{[收敛到某一 为，个体在更新x:和的过程中，仅利用了本地数 个平衡点，即存在某个z∈Z,满足 据Vfx以、2、x和，以及邻居个体的信息x和A; m内= (8) 将所有个体决策变量和对偶变量罗列起来， 写成更紧凑的形式： 证明：任取z"eZ.因为7zV(z,z*)是w-Lipschitz x[k+1]=Pg (x[k]-aVx C(x[].[k))) 连续的，有 (6) A[k+1]=[k]+aTC(x[k],[k]) V(z[k+1].z)-V([k].")s 由式(6)可见，算法的设计上采用了求解C鞍 ([k+1]-z[k].V:V(z[k].z"))+ 点的梯度下降-梯度上升的方法.其不动点满足一 号k+小-呢=-a(F 阶原始-对偶最优条件(4)，从而确保了算法的正 :Ve.z》+a2yIFa 确性 注2：文献[9-10]提出了类似的分布式原始- 又因为F(z),7zV(z,z)》≥6F(z)服所以 对偶梯度算法.相比之下，本文考虑的算法具有两 vk+1，小e-Ve.e≤-a2i,axyF(≤0 2 个可调参数：a和B.因此，该算法更具灵活性，并且 由此可见，V([,z)是随着k的增大而单调递减 推广了文献中的算法 的，从而V(z[,z)≤V(z[0,z)有界.由于V(z,z)是 3收敛性分析 水平强制的，因此序列{zk有界.不妨设”∈Z是 当k→∞时序列{z[的一个聚点，即存在子列 本节首先对一般的定步长迭代格式，提出基 →o,使得Iimz[k=”.注意到 于李雅普诺夫函数的一种分析范式.在此基础上， 对本文的分布式算法进行分析，给出算法参数的 a2i,∑1Fa6≤即 2 K-◆0o 选择范围 ∑nwe-ak+小.ve0<tm 3.1基于李雅普诺夫函数的一种分析范式 考虑一般的迭代格式 所以，IimF(z[k)=0m:又因为F是连续映射， z[k+1刂=z-aF(z[k),z0]=z0∈ZcRm(7) 所以F(2)=0m.这表明：∈Z 重新选取李雅普诺夫函数V(z,),按照类似的 其中F:Rm→Rm为连续映射，a>0为常步长，集合 证明过程，可以得出{V(z[k,)也是单调递减的序 Z为迭代格式(7)的不变集，即z[k∈乙，Yk≥0.令 列.不仅如此，由于V(,)=0,序列{V(zk,)有 Z{z∈Z乙F(z)=0m为平衡点集合，这里假定Z不 一个收敛到零的子列.从而可以得出序列 为空集 (V(z[,)单调递减并趋于零.再根据V(z,)的正 为了分析论证迭代(7)的收敛性，本文提出一 定性，就得到1imz[内=” 证毕！ 种基于李雅普诺夫函数的分析范式 32分布式一致性最优化梯度算法的收敛分析 定理1：如果存在一个李雅普诺夫函数 考虑分布式一致性最优化梯度算法(6).为了 V:Rm×Rm→R满足： 得收敛条件，采用上小节提出的基于李雅普诺夫 1)对于任意的z∈Z,V(z,z)是正定的，即 函数的分析方法

根据最优条件（4），可以设计一个基于原始– 对偶梯度的迭代算法： xi[k+1] = PΩi (xi[k]− α   ∇fi(xi[k])+β ∑ N j=1 ai j(xi[k]− xj[k]) + ∑ N j=1 ai j(λi[k]−λj[k])     λi[k+1] = λi[k]+α ∑ N j=1 ai j(xi[k]− xj[k]) （5） α β i xi λi ∇fi(xi) Ωi xi λi xj λj 其中，常数 和 待定，它们将在收敛分析中根据收 敛条件来确定. 算法（5）是一个分布式算法. 这是因 为，个体 在更新 和 的过程中，仅利用了本地数 据 、 、 和 ，以及邻居个体的信息 和 . 将所有个体决策变量和对偶变量罗列起来， 写成更紧凑的形式： x[k+1] = PΩ (x[k]−α∇xL(x[k],λ[k])) λ[k+1] = λ[k]+α∇λL(x[k],λ[k]) （6） 由式（6）可见，算法的设计上采用了求解 L 鞍 点的梯度下降–梯度上升的方法. 其不动点满足一 阶原始–对偶最优条件（4），从而确保了算法的正 确性. α β 注 2：文献 [9–10] 提出了类似的分布式原始– 对偶梯度算法. 相比之下，本文考虑的算法具有两 个可调参数： 和 . 因此，该算法更具灵活性，并且 推广了文献中的算法. 3    收敛性分析 本节首先对一般的定步长迭代格式，提出基 于李雅普诺夫函数的一种分析范式. 在此基础上， 对本文的分布式算法进行分析，给出算法参数的 选择范围. 3.1    基于李雅普诺夫函数的一种分析范式 考虑一般的迭代格式 z[k+1] = z[k]−αF(z[k]),z[0] = z0 ∈ Z ⊂ R m （7） F : R m → R m α > 0 Z z[k] ∈ Z,∀k ⩾ 0 Z∗ ≜ {z ∈ Z|F(z) = 0m} Z∗ 其中 为连续映射， 为常步长. 集合 为迭代格式（7）的不变集，即 . 令 为平衡点集合，这里假定 不 为空集. 为了分析论证迭代（7）的收敛性，本文提出一 种基于李雅普诺夫函数的分析范式. V : R m ×R m → R 定 理 1： 如 果 存 在 一 个 李 雅 普 诺 夫 函 数 满足： z ∗ ∈ Z∗ V(z,z ∗ 1）对于任意的 ， ) 是正定的 ，即 V(z,z ∗ ) ⩾ 0 V(z,z ∗ ) = 0 ⇔ z = z ∗ ，且 ； z ∗ ∈ Z∗ V(z,z ∗ ) z γ > 0 V lev⩽γV ≜ {z ∈ Z|V(z,z ∗ ) ⩽ γ} 2）对于任意的 ， 关于 是水平强 制 的 ， 即 对 于 任 意 的 正 数 ， 的 水 平 集 合 有界； z ∗ ∈ Z∗ V(z,z ∗ ) z ∇zV(z,z ∗ ) z ∈ Z κV κV > 0 3）对于任意的 ， 关于 可微，且映 射 在 上是 -Lipschitz 连续的，其中 是一个常数； δ > 0 z ∗ ∈ Z∗ ⟨F(z),∇zV(z,z ∗ )⟩ ⩾ δ∥F(z)∥ 2 2 ,∀z ∈ Z F(z) 4）存在某个常数 ，使得对于任意的 ， 都有 ，其中 是 （7）中的映射； 0 < α < 2δ κV 5）迭代格式（7）中，步长满足 . {z[k]} z˜ ∗ ∈ Z∗ 那么，由算法（7）产生的序列 收敛到某一 个平衡点，即存在某个 ，满足 lim k→∞ z[k] = z˜ ∗ （8） z ∗ ∈ Z∗ ∇zV(z,z ∗ 证明：任取 . 因为 ) 是 κV -Lipschitz 连续的，有 V(z[k+1],z ∗ )−V(z[k],z ∗ ) ⩽ ⟨z[k+1]− z[k],∇zV(z[k],z ∗ )⟩+ κV 2 ∥z[k+1]− z[k]∥ 2 2 = −α⟨F(z[k]), ∇zV(z[k],z ∗ )⟩+α 2 κV 2 ∥F(z[k])∥ 2 2 ⟨F(z),∇zV(z,z ∗ )⟩ ⩾ δ∥F(z)∥ 2 又因为 2 ，所以 V(z[k+1],z ∗ )−V(z[k],z ∗ ) ⩽ − α(2δ−ακV) 2 ∥F(z[k])∥ 2 2 ⩽ 0 V(z[k],z ∗ ) k V(z[k],z ∗ ) ⩽ V(z[0],z ∗ ) V(z,z ∗ ) {z[k]} z˜ ∗ ∈ Z k → ∞ {z[k]} kl → ∞ lim l→∞ z[kl] = z˜ ∗ 由此可见， 是随着 的增大而单调递减 的，从而 有界. 由于 是 水平强制的，因此序列 有界. 不妨设 是 当 时序列 的一个聚点 ，即存在子列 ，使得 . 注意到 α(2δ−ακV) 2 ∑∞ k=0 ∥F(z[k])∥ 2 2 ⩽ lim sup ∑ K→∞ K k=0 V(z[k],z ∗ )−V(z[k+1],z ∗ ) ⩽ V(z[0],z ∗ ) < +∞ lim k→∞ F(z[k]) = 0m F F(z˜ ∗ ) = 0m z˜ ∗ ∈ Z∗ 所以， . 又因为 是连续映射， 所以 . 这表明 . V(z,z˜ ∗ ) {V(z[k],z˜ ∗ )} V(z˜ ∗ ,z˜ ∗ ) = 0 {V(z[k],z˜ ∗ )} {V(z[k],z˜ ∗ )} V(z,z˜ ∗ ) lim k→∞ z[k] = z˜ ∗ 重新选取李雅普诺夫函数 ，按照类似的 证明过程，可以得出 也是单调递减的序 列. 不仅如此，由于 ，序列 有 一 个 收 敛 到 零 的 子 列 . 从 而 可 以 得 出 序 列 单调递减并趋于零. 再根据 的正 定性，就得到 . 证毕！ 3.2    分布式一致性最优化梯度算法的收敛分析 考虑分布式一致性最优化梯度算法（6）. 为了 得收敛条件，采用上小节提出的基于李雅普诺夫 函数的分析方法. 梁    舒等： 分布式一致性最优化的梯度算法与收敛分析 · 437 ·