多个体切换网络中带有时延通信的分布式次梯度优化算法

doi:10.11896/j.issn.1002-137X.2019.07.012

计算机科学 ›› 2019, Vol. 46 ›› Issue (7): 81-85.doi: 10.11896/j.issn.1002-137X.2019.07.012

多个体切换网络中带有时延通信的分布式次梯度优化算法

王俊雅,李甲地,李德权

(安徽理工大学数学与大数据学院安徽淮南232000)

收稿日期:2018-05-09 出版日期:2019-07-15 发布日期:2019-07-15
作者简介:王俊雅(1994-),女,硕士生,主要研究方向为分布式优化、统计机器学习,E-mail:784836893@qq.com;李甲地(1991-),男,硕士生,主要研究方向为分布式优化理论与应用;李德权(1973-),男,教授,主要研究方向为分布式优化、统计机器学习,E-mail:leeqdcpp@126.com(通信作者)。
基金资助:
国家自然科学基金项目(11701007)资助

Distributed Subgradient Optimization Algorithm with Communication Delays for Multi-agent Switched Networks

WANG Jun-ya,LI Jia-di,LI De-quan

(School of Mathematics and Big Data,Anhui University of Science and Technology,Huainan,Anhui 232000,China)

Received:2018-05-09 Online:2019-07-15 Published:2019-07-15

摘要/Abstract

摘要： 在一般的非平衡有向切换网络中,网络中的个体间可能存在通信时延现象。针对该情况,文中提出了多个体切换网络中带有时延通信的分布式次梯度优化算法。在该算法中,通过对通信网络进行扩维,将存在通信时延的无约束凸优化问题转化为无时延的无约束凸优化问题进行解决。利用非二次李雅普诺夫函数法证明了只要非平衡有向切换网络是周期强连通的以及通信时延有上界,那么基于时延通信的分布式次梯度优化算法就是收敛的。由于集中考虑了网络拓扑与通信时延,该算法更贴合实际情况。最后通过仿真实验验证了算法的有效性。

关键词: 次梯度方法, 非二次李雅普诺夫函数, 切换网络, 随机矩阵, 通信时延

Abstract: In the general non-balanced directional switching network,there may be communication delays among agents in networks.In light of this,this paper proposed a distributed subgradient optimization algorithm with communication delays for multi-agent switched networks.In this method,the unconstrained convex optimization problem with communication delays is converted into the unconstrained convex optimization problem without communication delays by augmenting delay nodes in communication network.The convergence of the multi-agent distributed subgradient optimization algorithm with communication delays is proved by using the non-quadratic Lyapunov function method,as long as the non-balanced directional switching network is periodical strong connectivity and the communication delays are upper bounded.Because the network topology conditions and communication delay are both intensively considered,this algorithm is more general and practical.Finally,a simulation example was given to demonstrate the effectiveness of the proposed algorithm.

Key words: Communication delays, Non-quadratic Lyapunov function, Stochastic matrix, Subgradient method, Switched networks

中图分类号:

TP301

王俊雅,李甲地,李德权. 多个体切换网络中带有时延通信的分布式次梯度优化算法[J]. 计算机科学, 2019, 46(7): 81-85. https://doi.org/10.11896/j.issn.1002-137X.2019.07.012

WANG Jun-ya,LI Jia-di,LI De-quan. Distributed Subgradient Optimization Algorithm with Communication Delays for Multi-agent Switched Networks[J]. Computer Science, 2019, 46(7): 81-85. https://doi.org/10.11896/j.issn.1002-137X.2019.07.012

参考文献

[1]NEDIC A,OZDAGLAR A.Distributed subgradient methods for Multi-Agent optimization [J].IEEE Transactions on Automatic Control,2009,54(1):48-61.
[2]LEE S,NEDIC A.Distributed random projection algorithm for convex optimization [J].IEEE Journal of Selected Topics in Signal Processing,2013,7 (2):221-229.
[3]LIU S,QIU Z,XIE L.Convergence rate analysis of distributed optimization with projected subgradient algorithm [J].Automatica A Journal of Ifac the International Federation of Automatic Control,2017,83:162-169.
[4]LI J D,LI D Q.Distributed Subgradient Optimization Algorithm for Multi-agent Switched Networks[J].Computer Science,2018,45(1):229-232.(in Chinese)
李甲地,李德权,切换网络分布式次梯度优化算法[J].计算机科学,2018,45(1):229-232.
[5]XI C G,KHAN U A.Distributed Subgradient Projection Algorithm Over Directed Graphs [J].IEEE Transactions on Automatic Control,2017,62(8):3986-3992.
[6]MAKJDOUMI A,OZDAGLAR A.Graph balancing for distri- buted subgradient methods over directed graphs[C]∥Procee-dings of the 2016 IEEE Conference on Decision and Control.IEEE,2016:1364-1371.
[7]NEDIC A,OLSHEVSKY A.Distributed optimization over time-varying directed graphs [J].IEEE Transactions on Automatic Control,2014,60(3):601-615.
[8]ZHANG D D.On quantized consensus multi-agent networks under communication delays [J].Journal of Heifei University of Technology,2015,38(7):923-928.(in Chinese)
张丹丹.具有通信时延的多个体网络量化一致性分析[J].合肥工业大学学报,2015,38(7):923-928.
[9]LI J,CHEN G,WU Z.et al.Distributed subgradient method for multi-agent optimization with quantized communication [J].Mathematical Methods in the Applied Sciences,2017,40(4):1201-1213.
[10]TSIANOS K I,RABBAT M G,et al.Distributed Consensus and Optimization under Communication Delays[C]∥Proceedings of the 2011 Annual Allerton Conference under Communication,Control,and Computing.IEEE Press,2011:974-982.
[11]YANG S F,LIU Q S,WANG J.Distributed Optimization Based on a Multi agent System in the Presence of Communication Delays[J].IEEE Transactions on Systems Man & Cybernetics Systems,2017,47(5):717-728.
[12]LIU J,LI D Q,YIN Z X.Distributed subgradient method for multi-agent optimization with communication delays [J].Journal of Heifei University of Technology,2013,36(5):559-565.(in Chinese)
刘军,李德权,殷志祥.具有通信时延的多个体分布式次梯度优化算法[J].合肥工业大学学报,2013,36(5):559-565.
[13]TSITSIKLIS J N.Problems in decentralized decision making and computation [D].Cambridge:Massachusetts Institute of Technology,1984:1-134.
[14]TSITSIKLIS J N.ATHANS M.Convergence and asymptotic agreement in distributed decision problems [J].IEEE Transactions on Automatic Control,1983,29(1):692-701.
[15]ZHU M H,MARTINEZ S.Discrete-time dynamic average consensus [J].Automatica,2014,50(12):3131-3138.
[16]SUNDARAM S,GHARESI B.Distributed Optimization Under Adversarial Nodes [J].IEEE Transactions on Automatic Control,2016,PP(99):1.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

多个体切换网络中带有时延通信的分布式次梯度优化算法

Distributed Subgradient Optimization Algorithm with Communication Delays for Multi-agent Switched Networks

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

Metrics

本文评价

推荐阅读 0

[1]	刘鹏, 叶宾. 基于随机矩阵理论的高维数据线性判别分析方法 Linear Discriminant Analysis of High-dimensional Data Using Random Matrix Theory 计算机科学, 2019, 46(6A): 423-426.
[2]	李甲地,李德权. 切换网络分布式次梯度优化算法 Distributed Subgradient Optimization Algorithm for Multi-agent Switched Networks 计算机科学, 2018, 45(1): 228-232. https://doi.org/10.11896/j.issn.1002-137X.2018.01.040
[3]	王海鹏,黄天彪,任崇帅,姚五一. 多通道延时遥交互研究综述 Survey of Multimodal Delay Tele-interaction 计算机科学, 2017, 44(Z6): 1-6. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.001
[4]	魏雅娟,范九伦,任方. 基于混沌和小波变换的音频加密算法 Audio Encryption Algorithm Based on Chaos and Wavelet Transform 计算机科学, 2017, 44(12): 94-99. https://doi.org/10.11896/j.issn.1002-137X.2017.12.019