Distributed Push-Sum Dual Averaging for Convex Optimizationover Time-Varying Directed Graphs

多智能体网络往往需要所有智能体相互协作来极小化几个目标函数之和，其中每个智能体仅知道自身目标函数信息，并通过与其它智能体交换信息来协同达到整体最优目标值^[14].本文主要考虑如下分布式约束优化问题^[1]：

其中：智能体i仅知道它自身的目标函数f_i(x)，i=1，…，n；所有的智能体受到公共约束集$X \subset {{\mathbb{R}}^d}$的约束.令X^*为问题(1)的最优解集.

假设考虑的图G(t)=(V，E(t))是有向图，其中V={1，2，…，n}为节点或智能体集合，E(t)⊂V×V为边集合.对于节点i，用N_iⁱⁿ(t) ={j|(j，i)∈E(t)}∪{i}来表示它的内邻居集合；用N_i^out(t)={j|(i，j)∈E(t)}∪{i}来表示它的外邻居集合；用d_i(t)=|N_i^out(t)|来表示它的外度.假设每个智能体i在每个时刻t仅知道它的外度d_i(t)，定义A(t)为通讯权矩阵，其元素为

通常A(t)是时变的列随机矩阵^[14].为了求解问题(1)，提出如下push-sum分布式对偶平均算法，简记为算法PS-DDA：

步0：初始化w_i(0)=1，z_i(0)=0，g_i(0)=0，t=0；

步1：对每个智能体i，i=1，…，n，更新

步2：令t=t+1，转步1.

其中步长序列{a(t)}_t=0^∞是非负单调递减的；g_i(t)是f_i(x)在x=x_i(t)的次梯度；${\mathit{\Pi} }_X^\psi \left( {{\mathit{\pmb{z}}}, a\left( t \right)} \right): = \mathop {\arg \min }\limits_{x \in {\mathit{\pmb{X}}}} \left\{ {\langle {\mathit{\pmb{z}}}, {\mathit{\pmb{x}}}\rangle + \frac{{\psi ({\mathit{\pmb{x}}})}}{{a(t)}}} \right\}$是一个非欧几里得投影算子，这里$\psi :{{\mathbb{R}}^d} \to {\mathbb{R}}$是一个1-强凸函数^[4]，并且满足ψ(x)≥0和ψ(0)=0.

下面将给出算法PS-DDA的收敛性分析.

假设1  (a)有向图序列{G(t)}是B-强连通，即存在一个正整数B使得对于每个k≥0，E_B(k)=$\begin{array}{*{20}{c}} {(k + 1)B - 1}\\ \cup \\ {i = kB} \end{array}$E(i)是强连通的^[11].

(b) 对i=1，…，n，f_i(x)：X→$\mathbb{R}$是凸函数，并且其次梯度g_i(x)是有界的，即对任意x∈X，有‖g_i(x)‖_*≤L，这里g_i(x)∈∂f_i(x)，‖·‖_*是‖·‖的对偶范数.

引理1^[4]  假设步长序列{a(t)}_t=0^∞是非负单调递减的.对于∀x^*∈X^*，有

这里$\hat {\mathit{\pmb{g}}}(t) = \frac{1}{n}\sum\limits_{i = 1}^n {{{\mathit{\pmb{g}}}_i}} (t)$，${\mathit{\pmb{x}}}(t + 1) = {\mathit{{\Pi}}} _X^\psi \left( {\sum\limits_{r = 1}^t {\hat {\mathit{\pmb{g}}}} (r), a(t)} \right)$.

引理2^[4]  对于任意两个向量u，v∈${{\mathbb{R}}^d}$，有‖Π_X^ψ(u，a)－Π_X^ψ(v，a)‖≤a‖u－v‖_*.

引理3^[14]  假设图序列{G(t)}是一致强连通的，则

(a) 存在一个随机向量序列{φ(t)}_t=1^∞，使得对于t≥s≥0，有

其中A(t：s)：=A(t)…A(s)，t≥s≥0，C>0为常数，λ∈(0，1).

(b) 令$\delta = \mathop {\inf }\limits_{t = 0, 1, \cdots } \left( {\begin{array}{*{20}{c}} {\min }\\ {1 \le i \le n} \end{array}{{[A(t) \cdots A(0)1]}_i}} \right)$，有$\delta = \frac{1}{{{n^{nB}}}}$，这里1是一个n维的全1向量.

引进如下记号：${\widehat {\mathit{\pmb{x}}}_i}(T) = \frac{1}{T}\sum\limits_{t = 1}^T {{{\mathit{\pmb{x}}}_i}} (t)$，$\bar {\mathit{\pmb{z}}}(t) = \frac{1}{n}\sum\limits_{i = 1}^n {{{\mathit{\pmb{z}}}_i}} (t)$，${\mathit{\pmb{y}}}(t) = {\mathit{\Pi}} _X^\psi (\bar {\mathit{\pmb{z}}}(t)$，a(t－1))，$\hat {\mathit{\pmb{y}}}\left( t \right) = \frac{1}{T}\sum\limits_{t = 1}^T {\mathit{\pmb{y}}} (t)$.为了得到算法PS-DDA的收敛性，首先证明如下一个重要引理.

引理4  假设1成立，序列{z_i(t)}_t=1^∞是由算法PS-DDA产生的.对于所有t≥1，则有

这里$\frac{1}{{{n^{nB}}}}$≤δ < 1，0 < λ≤${\left( {1 - \frac{1}{{{n^{nB}}}}} \right)^{\frac{1}{B}}}$.

证  由式(2)递推可得

由式(3)递推可得

进一步，由以上关系可得

综合以上结果，并注意到z_i(0)=0，于是，对于t≥0有

由文献[14]的推论2知，[A(t－1：0)]_il≤$\begin{array}{*{20}{l}} {\;\;{\rm{max}}}\\ {1 \le l \le n} \end{array}$[A(t－1：0)]_il，i=1，2，…，n，进而由(6)式可得

根据引理3有

证毕.

下面将陈述本文的主要结果.

定理1  假设1成立，步长序列{a(t)}_t=0^∞是非负单调递减的.对任意T≥1和x^*∈X^*，有

证  由F(x)的凸性和假设1(b)可得

考虑式(6)中的第二项，并结合引理1可得

再由Cauchy不等式和引理2可得

现在估计式(6)中第三项

综合式(7)，(8)和(9)，则有

最后利用引理4，即可证得定理1的结论.证毕

定理2  假设定理1的条件成立.令ψ(x^*)≤R²，选择步长a(t)=$\frac{p}{{\sqrt t }}$(t≥1)，这里的p是一个正常数.对任意T≥1和x^*∈X^*，有

证  利用定理1的结果和ψ(x^*)≤R²，则有

注意到a(t)=$\frac{p}{{\sqrt t }}$(t≥1)，有$\sum\limits_{t = 1}^T {\frac{1}{{\sqrt t }}} \le 2\;\;{\sqrt T }$.根据以上结果，结论得证.

注  定理2的前两项给出了优化误差项，最后一项给出了网络误差项，这里的λ刻画了网络的连通性，δ刻画了网络的平衡性.同时，定理2表明

它刻画了F(${{\hat {\mathit{\pmb{x}}}}_j}$(T))收敛到最优值F(x^*)的速率是O($\frac{1}{{\sqrt T }}$)，其中常数依赖于参数λ和δ.

考虑一个l₁回归问题^[6]：给出n个点对(a_i，b_i)∈${{\mathbb{R}}^d}$×$\mathbb{R}$，需要估计未知参数x∈${{\mathbb{R}}^d}$，使得a_i^Tx≈b_i，即求解下述优化问题：

显然F(x)是凸的，其次梯度是有界的，上界为L=max_i‖a_i‖.

对i=1，…，n，假设点对(a_i，b_i)是随机产生的，且服从标准正态分布.取步长a(t)=$\frac{{0.1}}{{\sqrt t }}$，D=10.考虑最大误差$\max {\rm{ error }} = \begin{array}{*{20}{c}} {\max }\\ {i \in V} \end{array}\left[ {F\left( {{{\hat {\mathit{\pmb{x}}}}_i}(T)} \right) - F\left( {{{\mathit{\pmb{x}}}^*}} \right)} \right]$.

图 1(a)，(b)描述了节点个数Node=100，维数分别为Dim=2和Dim=4的最大误差的收敛曲线.从图 1(a)和(b)可以看出，算法是收敛的.对比图 1(a)和(b)知，随着问题维数增加，其收敛误差也随之增大.

将本文PS-DDA算法与文献[11]中的分布式push-sum次梯度(PS-SG)算法进行对比. 图 2(a)，(b)分别描述了节点个数Node=200和Node=400，维数为Dim=2的最大误差值的收敛曲线.通过对比发现，算法PS-DDA的收敛精度均略优于算法PS-SG.