-
分布式优化理论及应用已经成为当前系统和控制科学的重要研究方向之一.在优化理论研究过程中,算法的设计、收敛性分析和复杂性分析是研究的关键点[1].目前已有许多国内外学者研究了分布式优化的理论和算法[2-6].基于次梯度信息,现有的分布式优化算法大致可分为3类:primal分布式算法、dual分布式算法和primal-dual分布式算法.文献[3]最早提出了一种分布式次梯度算法来求解无约束的分布式优化问题,并给出了收敛性分析.随后,文献[4]在固定无向通讯网络中提出了分布式对偶平均次梯度算法,并给出了算法的收敛性分析,得到了收敛率依赖于网络规模和拓扑结构的结论.文献[5]基于Lagrangian对偶方法提出了primal-dual分布式次梯度算法来求解一类带有等式或不等式约束的分布式凸优化问题.目前分布式方法已广泛应用于各个领域[7-12].
现有的分布式算法大多是基于无向通讯网络设计的,而许多实际问题的通讯网络往往是有向的,比如无线传感器网络、手机通讯网络等[13].而在无向网络中,分布式算法的设计往往需要一个很强的条件,即要求通讯权矩阵是双随机的,这样的要求对于有向通讯网络来说通常是不能满足的[14].最近,文献[13]通过引入push-sum协同机制,首次考虑了时间不变的有向通讯网络(假设其通讯权矩阵仅是列随机的)下的分布式优化问题,提出了push-sum对偶平均次梯度算法,给出了算法的收敛性分析,但他们考虑的通讯网络是时间不变的.随后,文献[14]考虑了时变有向网络下的分布式优化问题,并得到了算法的收敛率,但作者仅考虑了无约束的分布式优化问题.于是,在时变有向网络情形下,对带约束的分布式问题的研究就显得尤为必要.
受文献[13-14]的启发,本文提出了在时变有向网络下的push-sum分布式对偶平均次梯度算法,分析了算法的收敛性,并得到了算法的收敛率为O(
$\frac{1}{{\sqrt T }}$ ).数值结果验证了所提出算法的有效性.本文将文献[13]中的时间不变的有向网络推广到了时变的有向网络中,且能用于求解带约束的分布式优化问题.
全文HTML
-
假设考虑的图G(t)=(V,E(t))是有向图,其中V={1,2,…,n}为节点或智能体集合,E(t)⊂V×V为边集合.对于节点i,用Niin(t) ={j|(j,i)∈E(t)}∪{i}来表示它的内邻居集合;用Niout(t)={j|(i,j)∈E(t)}∪{i}来表示它的外邻居集合;用di(t)=|Niout(t)|来表示它的外度.假设每个智能体i在每个时刻t仅知道它的外度di(t),定义A(t)为通讯权矩阵,其元素为
通常A(t)是时变的列随机矩阵[14].为了求解问题(1),提出如下push-sum分布式对偶平均算法,简记为算法PS-DDA:
步0:初始化wi(0)=1,zi(0)=0,gi(0)=0,t=0;
步1:对每个智能体i,i=1,…,n,更新
步2:令t=t+1,转步1.
其中步长序列{a(t)}t=0∞是非负单调递减的;gi(t)是fi(x)在x=xi(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,EB(k)=
$\begin{array}{*{20}{c}} {(k + 1)B - 1}\\ \cup \\ {i = kB} \end{array}$ E(i)是强连通的[11].(b) 对i=1,…,n,fi(x):X→
$\mathbb{R}$ 是凸函数,并且其次梯度gi(x)是有界的,即对任意x∈X,有‖gi(x)‖*≤L,这里gi(x)∈∂fi(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成立,序列{zi(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)递推可得
进一步,由以上关系可得
综合以上结果,并注意到zi(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*)≤R2,选择步长a(t)=
$\frac{p}{{\sqrt t }}$ (t≥1),这里的p是一个正常数.对任意T≥1和x*∈X*,有证 利用定理1的结果和ψ(x*)≤R2,则有
注意到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 }}$ ),其中常数依赖于参数λ和δ.
-
考虑一个l1回归问题[6]:给出n个点对(ai,bi)∈
${{\mathbb{R}}^d}$ ×$\mathbb{R}$ ,需要估计未知参数x∈${{\mathbb{R}}^d}$ ,使得aiTx≈bi,即求解下述优化问题:显然F(x)是凸的,其次梯度是有界的,上界为L=maxi‖ai‖.
对i=1,…,n,假设点对(ai,bi)是随机产生的,且服从标准正态分布.取步长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.