分布式一致性最优化的梯度算法与收敛分析.pdf_大学文库

工程科学学报.第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 期

根据最优条件（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 ·

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 ·

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 期