论文部分内容阅读
摘要：针对多个体网络中个体信息交互常会出现数据丢包及个体目标函数次梯度难以计算或不存在的问题，提出数据丢包情形下分布式无梯度Push-sum算法，该算法要求网络的权矩阵为列随机而无需是双随机。通过增加虚拟节点进行系统扩维，从而建立一个有限的非均匀的马尔可夫链，并结合遍历性系数的结论证明了所提算法的收敛性。研究表明：收敛误差值与高斯近似函数的光滑参数、目标函数的Lipschitz常数成正比，从而有效解决了数据丢包及个体目标函数次梯度不存在或难以计算的分布式优化问题。
关键词：多个体网络；push-sum算法；无梯度；数据丢包
中图分类号： TP13 文献标志码：A文章编号：1672-1098（2017）03-0023-08
Abstract：The problem of distributed optimization in unbalanced networks with data packet-dropping communication among the agents is investigated in this paper.Due to the fact that data packet-dropping may occur when agents communicate with each other in the multi-agent network and the subgradient of each agent’s local objective function is computationally infeasible or does not exist，this paper proposes a distributed Push-sum gradient-free optimization algorithm under the condition of data packet-dropping， which requires that the weight matrix associated with the multi-agent network be column stochastic but not necessarily doubly stochastic. By adding virtual nodes for system expansion， a finite inhomogenous Markov chain was obtained， and the convergence of the proposed method to an approximate solution was testified by combining results of ergodic coefficients，. It is shown that the error level of the convergence is proportional to the smoothing parameters of Gaussian approximation function and the Lipschitz constant of the objective function， so it can effectively solve the distributed optimization problem of data packet-dropping when the subgradient of each agent’s local objective function is computationally infeasible or does not exist.
Key words：multi-agent network； push-sum algorithm； gradient-free； data packet-dropping
近年来，伴随着网络、通信、计算机技术等的快速发展，多个体网络的分布式优化问题研究受到广泛关注。多个体网络是由一群具有感知、处理和通信能力的个体或子系统通过信息交流耦合成的网络化系统。一类典型的网络优化问题要求网络中个体通过信息传递协同解决关于整个网络目标函数的优化問题，其中每个个体仅知其自身的目标函数。这类网络优化问题解法通常分为集中式和分布式两类。集中式要求多个体网络中，存在一个个体作为中心个体，其他个体感知的信息必须传递给中心个体，再由中心个体反馈给其他个体来完成网络优化问题。而分布式则仅要求网络中的每个个体只需与其邻居个体交换信息。两者相比，针对复杂大规模网络计算问题，集中式求解耗时耗财且实用性较差；而分布式求解则较为灵活且在复杂环境下具有极强的鲁棒性。因此分布式优化近年来发展迅速且在众多领域均有广泛应用，如信号处理[1]、电网[2]、大规模机械学习中的回归与分类[3]等实际问题都可以归类为多个体网络分布式优化问题。由于分布式优化要求网络中个体交互信息达成一致协同解决网络优化问题，因此分布式优化方法主要是由标准次梯度算法和一致性算法构成。文献[4]介绍了标准次梯度算法，文献[5]给出约束一致性算法。基于文献[4-5]提出了分布式原始对偶优化算法[6]和分布式对偶优化平均算法[7]。在此基础上进而研究了分布式push-sum对偶平均优化算法[8]。
上述文献是在假设任意时刻下个体间都可以及时进行信息交流。而文献[9-12]中，信息会因为通信链不可靠导致信息不能及时发送到接受端，即出现数据丢包的情况。因此数据丢包情形下的一致性算法及应用引起了学者的关注。文献[9]考虑通讯网络图是无向图时，一条通信链出现数据丢包时直接影响两方向的通讯，但是个体能及时发现且进行补救。文献[10]则考虑通讯网络是有向的，并提出两种补救方法来解决数据丢包问题，但节点达成一致性的值不一定是平均值。而文献[11]先通过设计校正迭代算法，每个节点再基于迭代计算修改状态中的错误，进而重发信息作为一种减少数据丢包的有害影响。文献[12]提出一种算法，该算法中个体通过建立一个有限的非均匀的马尔可夫链解决了有向网络中的数据丢包问题。 上述算法[9-13]都是在假设个体目标函数次梯度存在的前提下研究数据丢包。而个体目标函数的次梯度通常不存在或难以计算[14-16]，解决这一问题的一种有效方法就是采用无梯度法[17-19]。文献[17]研究隨机无梯度算法的收敛性并说明了收敛速度与高斯近似函数的光滑参数、lipschitz常数有关。文献[18]针对时变网络拓扑情形，采用无梯度Push-sum算法来解决整个网络的优化问题并证明了算法的收敛性且收敛速度为O（LnTT）。文献[19]研究了时延情形下的分布式随机无梯度优化算法，只要个体间的通信时延有上界，提出的优化算法依然收敛。
为了解决通信中的数据丢包和个体目标函数非凸或非光滑问题，本文在文献[12]的基础上提出一种鲁棒的分布式无梯度Push-sum算法，该算法可以有效地应付通信中的数据丢包，并无需计算个体目标函数的次梯度。由于数据丢包，通信网络所对应的权矩阵是列随机矩阵而无需是双随机矩阵。进而通过建立有限非均匀的马尔可夫链，并结合遍历性系数的相关结论证明算法的收敛性。
多个体网络信息通信通常可建模成有向图G（k）=（V，E（k）），其中V={1，2，…，n}表示网络中个体的集合；n为个体的数目；E（k）={（i，j）|i，j∈V}表示个体间的有向边集，dk∈Rn×n是权矩阵且非负，若（i，j）∈E（k）表示个体i发送信息给个体j则对应的边权[Dk]ij≥0，否则[Dk]ij=0；（i，i）表示个体i给自己发送信息。Nini （k）={j|（j，i）∈E（k）}，Nouti （k）={j|（i，j）∈E（k）}分别表示个体i的输入邻居集和输出邻居集（i∈Nini 且i∈Nouti），di（k）=|Nouti （k）|表示i的出度。令Rn为一个n维向量空间，E（x）表示向量的期望，f（x）代表函数f（x）在x处的梯度。
3.1网络模型
文献[12]考虑存在通信数据丢包且目标函数次梯度存在的分布式优化问题，而本文则讨论个体目标函数次梯度难以计算或不存在及存在数据丢包的分布式优化问题。因此，文献[12]算法将对本文研究不再适用。为此本文提出数据丢包情形下分布式无梯度Push-sum算法。假定有向图序列{G（k）}∞k=0 满足下列假设。
3.2DPSGF法
本文提出数据丢包情形下分布式无梯度Push-sum算法（DPSGF法），除了考虑xi（k），zi（k），wi（k）外还需考虑出现数据丢包时发送端和接受端的权梯度和权。当k≥0时，σi（k）和i（k）分别表示个体i已发送信息的权梯度和权；ρji（k）和ji（k）分别表示个体i已接受信息的权梯度和权。它们的初始值全为0。
式中：β=1maxDii∈V，γ=1-β2nB，B≥1，Di是i的出度。由定理1可以看出在T+1时刻所有个体状态平均值的函数值近似收敛到最优值，即所有个体状态达成一致（s1=s2=…=sn=s*∈S*），同时表明误差值limT→∞E[f（i（T+1））]-E[f（s*）]与高斯近似函数的光滑参数ui、lipschitz常数有关，即无梯度代替次梯度导致的惩罚项。5 结论与已有算法相比，该算法不仅可以有效地应付时变非平衡网络通信中的数据丢包，而且无需计算个体目标函数的次梯度，从而有效克服了个体目标函数的次梯度不存在或难以计算的问题。
参考文献：
[1] OLSHEVSKY A.Efficient Information Aggregation Strategies for Distributed Control and Signal Processing[J].Mathematics，2010，56：345-356.
[2] RAM S S， VEERAVALLI V V， NEDIC A. Distributed Non-Autonomous Power C-ontrol through Distributed Convex Optimization[C]//IEEE. International Conference on Computer Communications. Pacific Grove：IEEE Xplore， 2009：3 001-3 005.
[3] D P BERTSEKAS，博塞卡斯. convex optimization algorithms[M].北京：清华大学出版社， 2016：33-79.
[4] NEDIC A，OZDAGLAR A.Distributed Subgradient Methods for Multi-Agent Opti-mization[J]. IEEE Transactions on Automatic Control， 2009， 54（1）：48-61.
[5] NEDIC A，OZDAGLAR A， PARRILO P A. Constrained Consensus and Optimizati-on in Multi-Agent Networks[J]. IEEE Transactions on Automatic Control， 2010，55 （4）：922-938. [6] YUAN D， XU S， ZHAO H. Distributed Primal—Dual Subgradient Method for Multia-gent Optimization via Consensus Algorithms[J]. IEEE Transactions on Systems Man and Cybernetics Part B，2011，41（6）：1 715-1 724.
[7] DUCHI J C， AGARWAL A， WAINWRIGHT M J. Dual Averaging for Distributed Optimization： Convergence Analysis and Network Scaling[J]. IEEE Transactions on Automatic Control， 2011， 57（3）：592-606.
[8] TSIANOS K I， LAWLOR S， RABBAT M G. Push-Sum Distributed Dual Averaging for convex optimization[C]//IEEE Conference on Decision and Control. Singapore： IEEE， 2012：5 453-5 458.
[9] PATTERSON S， BAMIEH B， El ABBADI A. Distributed average consensus with s-tochastic communication failures[C]//IEEE Conference on Decision and Control. Singapore： IEEE， 2008：4 215-4 220.
[10] FAGNANI F， ZAMPIERI S. Average Consensus with Packet Drop Communication [J]. Siam Journal on Control and Optimization， 2009， 48（1）：102-133.
[11] CHEN Y， TRON R， TERZIS A， et al. Corrective consensus： Converging to the exa-ct average[C]//IEEE Conference on Decision and Control. Singapore： IEEE， 2010：1 221-1 228.
[12] VAIDYA N H， HADJICOSTIS C N， DOMINGUEZ-GARCI A D. Robust average consensus over packet dropping links： Analysis via coefficients of ergodicity[C]//IEEE Conference on Decision and Control. Singapore： IEEE， 2012：2 761-2 766.
[13] VAIDYA N H， HADJICOSTIS C N， DOMINGUEZ-GARCIA A D. Robust avera-ge consensus over packet dropping links： Analysis via coefficients of ergodicity[C]//IEEE Conference on Decision and Control. Singapore： IEEE， 2012：2 761-2 766.
[14] YU N. Random gradient-free minimization of convex functions[J]. Foundations of Computational Mathematics， 2011（1）：1-40.
[15] ORBAN， DOMINIQUE. Introduction to Derivative-Free Optimization[J]. Siam Re-view， 2011（2）：395-396.
[16] LI J， WU C， WU Z， et al. Gradient-free method for nonsmooth distributed optimiz-ation[J]. Journal of Global Optimization， 2014， 61（2）：325-340.
[17] YUAN D， HO D W. Randomized gradient-free method for multiagent optimization over time-varying networks[J]. IEEE Transactions on Neural Networks and Leanin-g Systems， 2015， 26（6）：1 342-1 347.
[18] YUAN D， XU S， LU J. Gradient-free method for distributed multi-agent optimizati-on via push-sum algorithms[J]. International Journal of Robust and Nonlinear Con-trol， 2015， 25（10）：1 569-1 580.
[19] 任芳芳， 李德權. 时延情形下的分布式随机无梯度优化算法[J]. 安徽理工大学学报（自然科学版）， 2016， 36（1）：34-39.
（责任编辑：李 丽，编辑：丁 寒）
关键词：多个体网络；push-sum算法；无梯度；数据丢包
中图分类号： TP13 文献标志码：A文章编号：1672-1098（2017）03-0023-08
Abstract：The problem of distributed optimization in unbalanced networks with data packet-dropping communication among the agents is investigated in this paper.Due to the fact that data packet-dropping may occur when agents communicate with each other in the multi-agent network and the subgradient of each agent’s local objective function is computationally infeasible or does not exist，this paper proposes a distributed Push-sum gradient-free optimization algorithm under the condition of data packet-dropping， which requires that the weight matrix associated with the multi-agent network be column stochastic but not necessarily doubly stochastic. By adding virtual nodes for system expansion， a finite inhomogenous Markov chain was obtained， and the convergence of the proposed method to an approximate solution was testified by combining results of ergodic coefficients，. It is shown that the error level of the convergence is proportional to the smoothing parameters of Gaussian approximation function and the Lipschitz constant of the objective function， so it can effectively solve the distributed optimization problem of data packet-dropping when the subgradient of each agent’s local objective function is computationally infeasible or does not exist.
Key words：multi-agent network； push-sum algorithm； gradient-free； data packet-dropping
近年来，伴随着网络、通信、计算机技术等的快速发展，多个体网络的分布式优化问题研究受到广泛关注。多个体网络是由一群具有感知、处理和通信能力的个体或子系统通过信息交流耦合成的网络化系统。一类典型的网络优化问题要求网络中个体通过信息传递协同解决关于整个网络目标函数的优化問题，其中每个个体仅知其自身的目标函数。这类网络优化问题解法通常分为集中式和分布式两类。集中式要求多个体网络中，存在一个个体作为中心个体，其他个体感知的信息必须传递给中心个体，再由中心个体反馈给其他个体来完成网络优化问题。而分布式则仅要求网络中的每个个体只需与其邻居个体交换信息。两者相比，针对复杂大规模网络计算问题，集中式求解耗时耗财且实用性较差；而分布式求解则较为灵活且在复杂环境下具有极强的鲁棒性。因此分布式优化近年来发展迅速且在众多领域均有广泛应用，如信号处理[1]、电网[2]、大规模机械学习中的回归与分类[3]等实际问题都可以归类为多个体网络分布式优化问题。由于分布式优化要求网络中个体交互信息达成一致协同解决网络优化问题，因此分布式优化方法主要是由标准次梯度算法和一致性算法构成。文献[4]介绍了标准次梯度算法，文献[5]给出约束一致性算法。基于文献[4-5]提出了分布式原始对偶优化算法[6]和分布式对偶优化平均算法[7]。在此基础上进而研究了分布式push-sum对偶平均优化算法[8]。
上述文献是在假设任意时刻下个体间都可以及时进行信息交流。而文献[9-12]中，信息会因为通信链不可靠导致信息不能及时发送到接受端，即出现数据丢包的情况。因此数据丢包情形下的一致性算法及应用引起了学者的关注。文献[9]考虑通讯网络图是无向图时，一条通信链出现数据丢包时直接影响两方向的通讯，但是个体能及时发现且进行补救。文献[10]则考虑通讯网络是有向的，并提出两种补救方法来解决数据丢包问题，但节点达成一致性的值不一定是平均值。而文献[11]先通过设计校正迭代算法，每个节点再基于迭代计算修改状态中的错误，进而重发信息作为一种减少数据丢包的有害影响。文献[12]提出一种算法，该算法中个体通过建立一个有限的非均匀的马尔可夫链解决了有向网络中的数据丢包问题。 上述算法[9-13]都是在假设个体目标函数次梯度存在的前提下研究数据丢包。而个体目标函数的次梯度通常不存在或难以计算[14-16]，解决这一问题的一种有效方法就是采用无梯度法[17-19]。文献[17]研究隨机无梯度算法的收敛性并说明了收敛速度与高斯近似函数的光滑参数、lipschitz常数有关。文献[18]针对时变网络拓扑情形，采用无梯度Push-sum算法来解决整个网络的优化问题并证明了算法的收敛性且收敛速度为O（LnTT）。文献[19]研究了时延情形下的分布式随机无梯度优化算法，只要个体间的通信时延有上界，提出的优化算法依然收敛。
为了解决通信中的数据丢包和个体目标函数非凸或非光滑问题，本文在文献[12]的基础上提出一种鲁棒的分布式无梯度Push-sum算法，该算法可以有效地应付通信中的数据丢包，并无需计算个体目标函数的次梯度。由于数据丢包，通信网络所对应的权矩阵是列随机矩阵而无需是双随机矩阵。进而通过建立有限非均匀的马尔可夫链，并结合遍历性系数的相关结论证明算法的收敛性。
1符号说明
多个体网络信息通信通常可建模成有向图G（k）=（V，E（k）），其中V={1，2，…，n}表示网络中个体的集合；n为个体的数目；E（k）={（i，j）|i，j∈V}表示个体间的有向边集，dk∈Rn×n是权矩阵且非负，若（i，j）∈E（k）表示个体i发送信息给个体j则对应的边权[Dk]ij≥0，否则[Dk]ij=0；（i，i）表示个体i给自己发送信息。Nini （k）={j|（j，i）∈E（k）}，Nouti （k）={j|（i，j）∈E（k）}分别表示个体i的输入邻居集和输出邻居集（i∈Nini 且i∈Nouti），di（k）=|Nouti （k）|表示i的出度。令Rn为一个n维向量空间，E（x）表示向量的期望，f（x）代表函数f（x）在x处的梯度。
2问题描述
3算法介绍
3.1网络模型
文献[12]考虑存在通信数据丢包且目标函数次梯度存在的分布式优化问题，而本文则讨论个体目标函数次梯度难以计算或不存在及存在数据丢包的分布式优化问题。因此，文献[12]算法将对本文研究不再适用。为此本文提出数据丢包情形下分布式无梯度Push-sum算法。假定有向图序列{G（k）}∞k=0 满足下列假设。
3.2DPSGF法
本文提出数据丢包情形下分布式无梯度Push-sum算法（DPSGF法），除了考虑xi（k），zi（k），wi（k）外还需考虑出现数据丢包时发送端和接受端的权梯度和权。当k≥0时，σi（k）和i（k）分别表示个体i已发送信息的权梯度和权；ρji（k）和ji（k）分别表示个体i已接受信息的权梯度和权。它们的初始值全为0。
式中：β=1maxDii∈V，γ=1-β2nB，B≥1，Di是i的出度。由定理1可以看出在T+1时刻所有个体状态平均值的函数值近似收敛到最优值，即所有个体状态达成一致（s1=s2=…=sn=s*∈S*），同时表明误差值limT→∞E[f（i（T+1））]-E[f（s*）]与高斯近似函数的光滑参数ui、lipschitz常数有关，即无梯度代替次梯度导致的惩罚项。5 结论与已有算法相比，该算法不仅可以有效地应付时变非平衡网络通信中的数据丢包，而且无需计算个体目标函数的次梯度，从而有效克服了个体目标函数的次梯度不存在或难以计算的问题。
参考文献：
[1] OLSHEVSKY A.Efficient Information Aggregation Strategies for Distributed Control and Signal Processing[J].Mathematics，2010，56：345-356.
[2] RAM S S， VEERAVALLI V V， NEDIC A. Distributed Non-Autonomous Power C-ontrol through Distributed Convex Optimization[C]//IEEE. International Conference on Computer Communications. Pacific Grove：IEEE Xplore， 2009：3 001-3 005.
[3] D P BERTSEKAS，博塞卡斯. convex optimization algorithms[M].北京：清华大学出版社， 2016：33-79.
[4] NEDIC A，OZDAGLAR A.Distributed Subgradient Methods for Multi-Agent Opti-mization[J]. IEEE Transactions on Automatic Control， 2009， 54（1）：48-61.
[5] NEDIC A，OZDAGLAR A， PARRILO P A. Constrained Consensus and Optimizati-on in Multi-Agent Networks[J]. IEEE Transactions on Automatic Control， 2010，55 （4）：922-938. [6] YUAN D， XU S， ZHAO H. Distributed Primal—Dual Subgradient Method for Multia-gent Optimization via Consensus Algorithms[J]. IEEE Transactions on Systems Man and Cybernetics Part B，2011，41（6）：1 715-1 724.
[7] DUCHI J C， AGARWAL A， WAINWRIGHT M J. Dual Averaging for Distributed Optimization： Convergence Analysis and Network Scaling[J]. IEEE Transactions on Automatic Control， 2011， 57（3）：592-606.
[8] TSIANOS K I， LAWLOR S， RABBAT M G. Push-Sum Distributed Dual Averaging for convex optimization[C]//IEEE Conference on Decision and Control. Singapore： IEEE， 2012：5 453-5 458.
[9] PATTERSON S， BAMIEH B， El ABBADI A. Distributed average consensus with s-tochastic communication failures[C]//IEEE Conference on Decision and Control. Singapore： IEEE， 2008：4 215-4 220.
[10] FAGNANI F， ZAMPIERI S. Average Consensus with Packet Drop Communication [J]. Siam Journal on Control and Optimization， 2009， 48（1）：102-133.
[11] CHEN Y， TRON R， TERZIS A， et al. Corrective consensus： Converging to the exa-ct average[C]//IEEE Conference on Decision and Control. Singapore： IEEE， 2010：1 221-1 228.
[12] VAIDYA N H， HADJICOSTIS C N， DOMINGUEZ-GARCI A D. Robust average consensus over packet dropping links： Analysis via coefficients of ergodicity[C]//IEEE Conference on Decision and Control. Singapore： IEEE， 2012：2 761-2 766.
[13] VAIDYA N H， HADJICOSTIS C N， DOMINGUEZ-GARCIA A D. Robust avera-ge consensus over packet dropping links： Analysis via coefficients of ergodicity[C]//IEEE Conference on Decision and Control. Singapore： IEEE， 2012：2 761-2 766.
[14] YU N. Random gradient-free minimization of convex functions[J]. Foundations of Computational Mathematics， 2011（1）：1-40.
[15] ORBAN， DOMINIQUE. Introduction to Derivative-Free Optimization[J]. Siam Re-view， 2011（2）：395-396.
[16] LI J， WU C， WU Z， et al. Gradient-free method for nonsmooth distributed optimiz-ation[J]. Journal of Global Optimization， 2014， 61（2）：325-340.
[17] YUAN D， HO D W. Randomized gradient-free method for multiagent optimization over time-varying networks[J]. IEEE Transactions on Neural Networks and Leanin-g Systems， 2015， 26（6）：1 342-1 347.
[18] YUAN D， XU S， LU J. Gradient-free method for distributed multi-agent optimizati-on via push-sum algorithms[J]. International Journal of Robust and Nonlinear Con-trol， 2015， 25（10）：1 569-1 580.
[19] 任芳芳， 李德權. 时延情形下的分布式随机无梯度优化算法[J]. 安徽理工大学学报（自然科学版）， 2016， 36（1）：34-39.
（责任编辑：李 丽，编辑：丁 寒）