工程科学学报 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 primaldual 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)中，步长满足00为常步长，集合 证明过程，可以得出{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 ·
438 工程科学学报，第42卷，第4期 令zcol(x,).定义Z为原始-对偶最优解集 并且 合，即所有满足等式(4)的点z°=col(x,)的集合 (z-z,G(z)-Gz)》=x-x,7fx)-Vfx)》+ 在迭代格式(6)中，{x[始终保持在集合Ω中，因 B(x,L⑧lnx)≥B(x,L⑧lnx) (18) 此Z兰2×RN是一个不变集.可以将(6)重新写成 与此同时，通过简单计算得到NCx,)= 类似(7)的标准迭代格式 IL⑧lnx呢，且 [k+1]=z[k]-aF(z[k]),z[0]ZoEZ (9) IZox,L⑧lnx)≥lL⑧1nxl,Vx ERIN(19) 其中， 结合式(16)~(19)，得到 Fa)e-Pz-aG(e ,G(z± Vx L(x,A) (10) a -7C(x,) Fe.:Vzz》≥e-Pze-aGe+ (20) 根据最优条件，映射G(z)满足 (z-z∴，G(z》≥0，z∈Z,z'∈Z (11) (品-如o1.6 接下来，构造李雅普诺夫函数 至此，可以给出分布式算法(5)的收敛分析结果 V(z,z)=a(C(x,)-x*,)- 定理2：在假设1和假设2的条件下，如果分 1 (12) 布式算法(5)的步长a和常数B满足 r-x,xLx',r》+5k-z呢 1 00(21) Ex,)-x,')-(x-x,VrCx',)》≥0.于是， 那么算法产生的迭代序列收敛到某个原始- V(z,z)≥a((x,)-x,X)》+ 对偶最优解 k-ci呢≥-alLk-i6 (13) 证明：因为已经给出了定理1所述的基于李雅普 2 诺夫函数的分析范式，所以这里仅需考虑式(12) 而且，V(z,z)是关于z的可微函数，可以通过计算得到 构造的V(z,z),并验证其满足各项条件 VxCx,)lVxCx',) 首先根据(13)，若0i+5
z ≜ col(x,λ) Z∗ z ∗ = col(x∗ ,λ ∗ ) {x[k]} Ω Z ≜ Ω ×R nN 令 . 定义 为原始–对偶最优解集 合，即所有满足等式 (4) 的点 的集合. 在迭代格式 (6) 中 ， 始终保持在集合 中，因 此 是一个不变集. 可以将（6）重新写成 类似（7）的标准迭代格式 z[k+1] = z[k]−αF(z[k]),z[0] = z0 ∈ Z （9） 其中， F(z) ≜ z− PZ (z−αG(z)) α , G(z) ≜ [ ∇xL(x,λ) −∇λL(x,λ) ] （10） 根据最优条件，映射 G(z) 满足 ⟨ z− z ∗ ,G(z ∗ ) ⟩ ⩾ 0,∀z ∈ Z,∀z ∗ ∈ Z∗ （11） 接下来，构造李雅普诺夫函数 V(z,z ∗ ) = α(L(x,λ)− L(x ∗ ,λ ∗ )− ⟨x− x ∗ ,∇xL(x ∗ ,λ ∗ )⟩)+ 1 2 ∥z− z ∗ ∥ 2 2 （12） L(x,λ ∗ ) x L(x,λ ∗ )− L(x ∗ ,λ ∗ )−⟨x− x ∗ ,∇xL(x ∗ ,λ ∗ )⟩ ⩾ 0 由 于 是 关 于 的 凸 函 数 ， 所 以 . 于是， V(z,z ∗ ) ⩾ α(L(x,λ)− L(x,λ ∗ ))+ 1 2 ∥z− z ∗ ∥ 2 2 ⩾ 1−α∥L∥∞ 2 ∥z− z ∗ ∥ 2 2 （13） V(z,z ∗ 而且， ) 是关于 z 的可微函数，可以通过计算得到 ∇zV(z,z ∗ )=α ([ ∇xL(x,λ) ∇λL(x,λ) ] − [ ∇xL(x ∗ ,λ ∗ ) −∇λL(x ∗ ,λ ∗ ) ])+z−z ∗ = α [ ∇f(x)− ∇f(x ∗ )+βL⊗ In x+ L⊗ In(λ−λ ∗ ) L⊗ In x ] +z−z ∗ （14） ∇zV(z,z ∗ 容易证明， ) 是关于 z 的κV -Lipschitz 连续映 射，其中 κV = α(κ f +β∥L∥∞ +∥L∥∞)+1 （15） ⟨F(z),∇zV(z,z ∗ )⟩ ⩾ δ∥F(z)∥ 2 2 ∀z ∈ Z δ 下 面 验 证 不 等 式 ， ，并确定常数 . 通过计算， ⟨F(z),∇zV(z,z ∗ )⟩ = 1 α ⟨ z− PZ (z−αG(z)), α ([ ∇xL(x,λ) ∇λL(x,λ) ] − [ ∇xL(x ∗ ,λ ∗ ) −∇λL(x ∗ ,λ ∗ ) ])+ z− z ∗ ⟩ = 1 α ⟨ z− PZ (z−αG(z)),αG(z)−αG(z ∗ )+ z− z ∗ ⟩ −2α∥∇λL(x,λ)∥ 2 2 （16） 根据投影算子的基本性质和不等式 (11)，容易 证明 1 α ⟨ z− PZ (z−αG(z)),αG(z)−αG(z ∗ )+ z− z ∗ ⟩ ⩾ 1 α z− PZ (z−αG(z)) 2 2 +⟨z− z ∗ ,G(z)−G(z ∗ )⟩ （17） 并且 ⟨z− z ∗ ,G(z)−G(z ∗ )⟩ = ⟨x− x ∗ ,∇f(x)− ∇f(x ∗ )⟩+ β⟨x, L⊗ In x⟩ ⩾ β⟨x, L⊗ In x⟩ （18） ∥∇λL(x,λ)∥ 2 2 = ∥L⊗ In x∥ 2 2 与此同时 ，通过简单计算得到 ，且 ∥L∥∞ ⟨x, L⊗ In x⟩ ⩾ ∥L⊗ In x∥ 2 2 ,∀x ∈ R nN （19） 结合式（16）～（19），得到 ⟨F(z),∇zV(z,z ∗ )⟩⩾ 1 α z− PZ (z−αG(z)) 2 2 + ( β ∥L∥∞ −2α ) ∥L⊗ In x∥ 2 2 （20） 至此，可以给出分布式算法（5）的收敛分析结果. 定理 2：在假设 1 和假设 2 的条件下，如果分 布式算法（5）的步长 α 和常数 β 满足 00 （21） 那么算法产生的迭代序列收敛到某个原始– 对偶最优解. V(z,z ∗ ) 证明：因为已经给出了定理 1 所述的基于李雅普 诺夫函数的分析范式，所以这里仅需考虑式（12） 构造的 ，并验证其满足各项条件. 0 i+5 · 438 · 工程科学学报，第 42 卷，第 4 期
梁舒等：分布式一致性最优化的梯度算法与收敛分析 439. 个体之间的信息分享关系如图1所示 20 18 8 6 图1信息分享关系图 Fig.1 Information sharing graph 0 容易验证20=∩%，2=[-5，-1山，而问题的最优 50100150200250300350400450500 Iteration number,k 解为 图4李雅普诺夫函数的更新轨迹 xi=…=x5=-1 (23) Fig.4 Trajectory of the Lyapunov function 通过分析和计算得 5结论 5 =3IlLll =6 (24) 对分布式一致性最优化问题进行了研究，设 因此，根据式(21)，选择B=0.9,得到参数α的 计了具有两个可调参数的分布式原始-对偶梯度 选择范围是0<a<0.075.在数值实验中，选择 算法，并论证了算法的收敛性.针对一般的定步长 α=0.07，得到的实验结果如图2~4所示.可以看 迭代格式，提出一种基于李雅普诺夫函数的分析 出，由于选择了合适的步长等参数，算法仅迭代 范式，具有普适性和一般性，在收敛分析方面具有 300次后就已经收敛到最优解.这些实验结果验证 框架性和系统性.提出的方法运用在论文所考虑 了本文提出的分布式算法及其收敛分析方法的正 的分布式梯度算法上，得到了算法收敛条件，确定 确性和有效性 出算法参数的选择范围，证实了方法的有效性.给 出的数值实验结果也验证了该方法的有效性.接 Agent 1 Agent 2 下来的工作将包括对其他类型的分布式优化算法 Agent 3 Agent 4 进行设计和分析，如带有耦合等式或不等式约束 Agent s 0 的分布式资源分配问题等 参考文献 [1]Yang T,Yi X L,Wu J F,et al.A survey of distributed optimization.Ann Rev Control,2019,47:278 050100150200250300350400450500 [2]Yi P,Hong Y G.Distributed cooperative optimization and its Iteration number,k applications.Sci Sin Math,2016,46(10):1547 图2决策变量的更新轨迹 (衣鹏，洪奕光.分布式合作优化及其应用.中国科学：数学， Fig.2 Trajectories of decision variables 2016,46(10):1547) [3]Peng K X,Zhang C F,Ma L,et al.System-levels-based Agent I Agent 2 holographic fault diagnosis for complex industrial processes. Agent 3 C1ESCJ,2019,70(2):590 Agent 4 Agent 5 (彭开香，张传放，马亮，等.面向系统层级的复杂工业过程全息 故障诊断.化工学报，2019.70(2)：590) [4]Nedic A,Ozdaglar A,Parrilo P A.Constrained consensus and optimization in multi-agent networks.IEEE Trans Autom Control. 2010,55(4):922 [5]Nedic A,Olshevsky A.Distributed optimization over time-varying 50100150200250300350400450500 directed graphs.IEEE Trans Autom Control,2015,60(3):601 Iteration number,k [6]Nedic A,Olshevsky A.Stochastic gradient-push for strongly 图3对偶变量的更新轨迹 convex functions on time-varying directed graphs.IEEE Trans Fig.3 Trajectories of dual variables Autom Control.2016.61(12):3936
个体之间的信息分享关系如图 1 所示. Ω0 = ∩N 容易验证 i=1 Ωi = [−5,−1] ，而问题的最优 解为 x ∗ 1 = ··· = x ∗ 5 = −1 （23） 通过分析和计算得 κ f = 5 3 , ∥L∥∞ = 6 （24） β = 0.9 α 0 < α < 0.075 α = 0.07 因此，根据式（21），选择 ，得到参数 的 选择范围是 . 在数值实验中 ，选择 ，得到的实验结果如图 2～4 所示. 可以看 出，由于选择了合适的步长等参数，算法仅迭代 300 次后就已经收敛到最优解. 这些实验结果验证 了本文提出的分布式算法及其收敛分析方法的正 确性和有效性. 5 结论 对分布式一致性最优化问题进行了研究，设 计了具有两个可调参数的分布式原始–对偶梯度 算法，并论证了算法的收敛性. 针对一般的定步长 迭代格式，提出一种基于李雅普诺夫函数的分析 范式，具有普适性和一般性，在收敛分析方面具有 框架性和系统性. 提出的方法运用在论文所考虑 的分布式梯度算法上，得到了算法收敛条件，确定 出算法参数的选择范围，证实了方法的有效性. 给 出的数值实验结果也验证了该方法的有效性. 接 下来的工作将包括对其他类型的分布式优化算法 进行设计和分析，如带有耦合等式或不等式约束 的分布式资源分配问题等. 参 考 文 献 Yang T, Yi X L, Wu J F, et al. A survey of distributed optimization. Ann Rev Control, 2019, 47: 278 [1] Yi P, Hong Y G. Distributed cooperative optimization and its applications. Sci Sin Math, 2016, 46（10）: 1547 （衣鹏, 洪奕光. 分布式合作优化及其应用. 中国科学: 数学, 2016, 46（10）：1547） [2] Peng K X, Zhang C F, Ma L, et al. System-levels-based holographic fault diagnosis for complex industrial processes. CIESC J, 2019, 70（2）: 590 （彭开香, 张传放, 马亮, 等. 面向系统层级的复杂工业过程全息 故障诊断. 化工学报, 2019, 70（2）：590） [3] Nedic A, Ozdaglar A, Parrilo P A. Constrained consensus and optimization in multi-agent networks. IEEE Trans Autom Control, 2010, 55（4）: 922 [4] Nedic A, Olshevsky A. Distributed optimization over time-varying directed graphs. IEEE Trans Autom Control, 2015, 60（3）: 601 [5] Nedic A, Olshevsky A. Stochastic gradient-push for strongly convex functions on time-varying directed graphs. IEEE Trans Autom Control, 2016, 61（12）: 3936 [6] 1 2 3 5 4 图 1 信息分享关系图 Fig.1 Information sharing graph 0 50 100 150 200 Iteration number, k 250 300 350 400 450 500 −4 −3 −2 −1 0 1 2 3 Agent 1 Agent 2 Agent 3 Agent 4 Agent 5 Primal variable, x[k] 图 2 决策变量的更新轨迹 Fig.2 Trajectories of decision variables 0 50 100 150 200 Iteration number, k 250 300 350 400 450 500 −3 −2 −1 0 1 2 3 Agent 1 Agent 2 Agent 3 Agent 4 Agent 5 Dual variable, λ[k] 图 3 对偶变量的更新轨迹 Fig.3 Trajectories of dual variables 0 50 100 150 200 Iteration number, k 250 300 350 400 450 500 0 6 4 2 8 10 12 14 18 16 20 Lyapunov function, V[k] 图 4 李雅普诺夫函数的更新轨迹 Fig.4 Trajectory of the Lyapunov function 梁 舒等： 分布式一致性最优化的梯度算法与收敛分析 · 439 ·
440 工程科学学报，第42卷.第4期 [7]Shi W.Ling Q,Wu G.et al.Extra:An exact first-order algorithm for constrained convex optimizations via nonsmooth analysis for decentralized consensus optimization.SIAM J Optim,2015, approach.IEEE Trans Autom Control,2017,62(10):5227 25(2):944 [14]Yang S F,Liu Q S,Wang J.A multi-agent system with a [8]Nedic A.Olshevsky A,Shi W.Achieving geometric convergence proportional-integral protocol for distributed constrained for distributed optimization over time-varying graphs.SLAM/ optimization.IEEE Trans Autom Control,2017,62(7):3461 0pmim,2017,27(4):2597 [15]Deng Z H,Liang S,Hong Y G.Distributed continuous-time [9]Liu QS,Yang S F,Hong Y G.Constrained consensus algorithms algorithms for resource allocation problems over weight-balanced with fixed step size for distributed convex optimization over multi- digraphs.IEEE Trans Cybern,2018,48(11):3116 agent networks.IEEE Trans Autom Control,2017,62(8):4259 [16]Liang S.Zeng X L.Hong Y G.Distributed nonsmooth [10]Lei JL,Chen H F,Fang H T.Primal-dual algorithm for distributed optimization with coupled inequality constraints via modified constrained optimization.Syst Conrol Len,016,9:110 Lagrangian function.IEEE Trans Autom Control,2018,63(6): [11]Liang S,Wang L Y,Yin G.Exponential convergence of 1753 distributed primal-dual convex optimization algorithm without [17]Hiriart-Urruty J B,Lemarechal C.Comvex Analysis and strong convexity.Automatica,2019,105:298 Minimization Algorithms I:Fundamentals.Springer Science& [12]Gharesifard B,Cortes J.Distributed continuous-time convex Business Media,2013 optimization on weight-balanced digraphs.IEEE Trans Autom [18]Nesterov Y.Lectures on Convex Optimization.Springer,2018 Control,.2014,59(3):781 [19]Godsil C,Royle G F.Algebraic Graph Theory.Springer Science [13]Zeng X L,Yi P,Hong Y G.Distributed continuous-time algorithm Business Media,2013
Shi W, Ling Q, Wu G, et al. Extra: An exact first-order algorithm for decentralized consensus optimization. SIAM J Optim, 2015, 25（2）: 944 [7] Nedic A, Olshevsky A, Shi W. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM J Optim, 2017, 27（4）: 2597 [8] Liu Q S, Yang S F, Hong Y G. Constrained consensus algorithms with fixed step size for distributed convex optimization over multiagent networks. IEEE Trans Autom Control, 2017, 62（8）: 4259 [9] Lei J L, Chen H F, Fang H T. Primal-dual algorithm for distributed constrained optimization. Syst Control Lett, 2016, 96: 110 [10] Liang S, Wang L Y, Yin G. Exponential convergence of distributed primal-dual convex optimization algorithm without strong convexity. Automatica, 2019, 105: 298 [11] Gharesifard B, Cortes J. Distributed continuous-time convex optimization on weight-balanced digraphs. IEEE Trans Autom Control, 2014, 59（3）: 781 [12] [13] Zeng X L, Yi P, Hong Y G. Distributed continuous-time algorithm for constrained convex optimizations via nonsmooth analysis approach. IEEE Trans Autom Control, 2017, 62（10）: 5227 Yang S F, Liu Q S, Wang J. A multi-agent system with a proportional-integral protocol for distributed constrained optimization. IEEE Trans Autom Control, 2017, 62（7）: 3461 [14] Deng Z H, Liang S, Hong Y G. Distributed continuous-time algorithms for resource allocation problems over weight-balanced digraphs. IEEE Trans Cybern, 2018, 48（11）: 3116 [15] Liang S, Zeng X L, Hong Y G. Distributed nonsmooth optimization with coupled inequality constraints via modified Lagrangian function. IEEE Trans Autom Control, 2018, 63（6）: 1753 [16] Hiriart-Urruty J B, Lemaréchal C. Convex Analysis and Minimization Algorithms I: Fundamentals. Springer Science & Business Media, 2013 [17] [18] Nesterov Y. Lectures on Convex Optimization. Springer, 2018 Godsil C, Royle G F. Algebraic Graph Theory. Springer Science & Business Media, 2013 [19] · 440 · 工程科学学报，第 42 卷，第 4 期
