分布式有限时间重球法

doi:10.7523/j.ucas.2020.0009

中国科学院大学学报 ›› 2022, Vol. 39 ›› Issue (1): 127-133.DOI: 10.7523/j.ucas.2020.0009

• 电子信息与计算机科学 • 上一篇

分布式有限时间重球法

曲志海, 陆疌

上海科技大学信息科学与技术学院, 上海 201210;中国科学院上海微系统与信息技术研究所, 上海 200050;中国科学院大学, 北京 100049

收稿日期:2020-01-06 修回日期:2020-02-26 发布日期:2021-05-31
通讯作者: 陆疌
基金资助:
国家自然科学基金（61603254）资助

Distributed finite-time-consensus-based heavy-ball algorithm

QU Zhihai, LU Jie

School of Information Science and Technology, ShanghaiTech University, Shanghai 201210, China;Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences, Shanghai 200050, China;University of Chinese Academy of Sciences, Beijing 100049, China

Received:2020-01-06 Revised:2020-02-26 Published:2021-05-31

摘要/Abstract

摘要： 结合有限时间共识算法及一阶加速算法重球法提出分布式有限时间重球法。本算法的优点为可以保证所有节点在每个周期都达到共识，同时达到与集中式重球法相同阶数的收敛速率。通过数值仿真将该算法与其他分布式优化算法应用于机器学习问题上，展现了该算法的优良性能。

关键词: 分布式优化, 算法设计, 有限时间共识算法, 重球法

Abstract: Based on the finite-time-consensus algorithm and the heavy-ball algorithm which is a first order accelerate algorithm, a distributed optimization algorithm is proposed. The algorithm can achieve consensus after every periodic updates. The non-ergodic convergence rate is at the same order of the centralized heavy-ball algorithm. In addition, the numerical examples compare our algorithm with other state-of-art distributed optimization algorithms on machine learning problems and show the competitive performance.

Key words: distributed optimization, algorithm design, finite-time-consensus algorithm, heavy-ball algorithm

中图分类号:

TN99

曲志海, 陆疌. 分布式有限时间重球法[J]. 中国科学院大学学报, 2022, 39(1): 127-133.

QU Zhihai, LU Jie. Distributed finite-time-consensus-based heavy-ball algorithm[J]. Journal of University of Chinese Academy of Sciences, 2022, 39(1): 127-133.

参考文献

[1] Beck A, Nedić A, Ozdaglar A, et al. An O(1/k) gradient method for network resource allocation problems[J]. IEEE Transactions on Control of Network Systems, 2014, 1(1):64-73.
[2] Rabbat M, Nowak R. Distributed optimization in sensor networks[C]//Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks 2004. April 26-27, 2004. Berkeley, California, USA. New York:Association for Computing Machinery, 2004:20-27.
[3] Shamma J S. Cooperative control of distributed multi-agent systems[M]. New York:John Wiley & Sons, Ltd, 2007.
[4] Wai H T, Yang Z, Wang Z, et al. Multi-agent reinforcement learning via double averaging primal-dual optimization[C]//Bengio S, Wallach H, Larochelle, et al. Advances in Neural Information Processing Systems 31:New York:Curran Associates, 2018:9649-9660.
[5] Nedic A, Ozdaglar A. Distributed subgradient methods for multi-agent optimization[J]. IEEE Transactions on Automatic Control, 2009, 54(1):48-61.
[6] Shi W, Ling Q, Wu G, et al. EXTRA:an exact first-order algorithm for decentralized consensus optimization[J]. SIAM Journal on Optimization, 2015, 25(2):944-966.
[7] Nedić A, Olshevsky A, Shi W. Achieving geometric convergence for distributed optimization over time-varying graphs[J]. SIAM Journal on Optimization, 2017, 27(4):2597-2633.
[8] Sundaram S, Hadjicostis C N. Finite-time distributed consensus in graphs with time-invariant topologies[C]//2007 American Control Conference, July 9-13, 2007, New York NY, USA. IEEE, 2007:711-716.
[9] Mai V S, Abed E H. Local prediction for enhanced convergence of distributed optimization algorithms[J]. IEEE Transactions on Control of Network Systems, 2018, 5(4):1962-1975.
[10] Qu Z H, Wu X Y, Lu J. Finite-time-consensus-based methods for distributed optimization[C]//2019 Chinese Control Conference (CCC). July 27-30, 2019, Guangzhou, China. IEEE, 2019:5764-5769.
[11] Xiao L, Boyd S. Fast linear iterations for distributed averaging[J]. Systems & Control Letters, 2004, 53(1):65-78.
[12] Horn R A, Johnson C R. Matrix analysis[M]. 2nd ed. Cambridge:Cambridge University Press, 1985, 191-200.
[13] Sundaram S, Hadjicostis C N. Distributed function calculation and consensus using linear iterative strategies[J]. IEEE Journal on Selected Areas in Communications, 2008, 26(4):650-660.
[14] Ghadimi E, Feyzmahdavian H R, Johansson M. Global convergence of the heavy-ball method for convex optimization[C]//2015 European Control Conference (ECC). July 15-17, 2015, Linz, Austria. IEEE, 2015:310-315.
[15] Sun T, Yin P H, Li D S, et al. Non-ergodic convergence analysis of heavy-ball algorithms[C]//Proceedings of the AAAI Conference on Artificial Intelligence. AAAI, 2019, 33(1):5033-5040.
[16] Murphy K P. Machine learning:a probabilistic perspective[M]. Cambridge, Massachusetts:MIT press, 2012:290-295.
[17] Löfberg J. YALMIP:a toolbox for modeling and optimization in MATLAB[C]//2004 IEEE International Conference on Robotics and Automation (IEEE Cat. No.04CH37508). September 2-42004, Taipei, Taiwan, China. IEEE, 2004:284-289.
[18] Bajović D, Jakovetić D, Krejić N, et al. Newton-like method with diagonal correction for distributed optimization[J]. SIAM Journal on Optimization, 2017, 27(2):1171-1203.
[19] Mokhtari A, Ling Q, Ribeiro A. Network Newton distributed optimization methods[J]. IEEE Transactions on Signal Processing, 2017, 65(1):146-161.

分布式有限时间重球法

Distributed finite-time-consensus-based heavy-ball algorithm

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价

访问统计

联系我们