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 期