梁舒等：分布式一致性最优化的梯度算法与收敛分析 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 ·