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