On the convergence of exact distributed generalisation and acceleration algorithm for convex optimisation

Abstract

In this paper, we study distributed multiagent optimisation over undirected graphs. The optimisation problem is to minimise a global objective function, which is composed of the sum of a set of local objective functions. Recent researches on this problem have made significant progress by using primal-dual methods. However, the inner link among different algorithms is unclear. This paper shows that some state-of-the-art algorithms differ in that they incorporate the slightly different last dual gradient terms based on the augmented Lagrangian analysis. Then, we propose a distributed Nesterov accelerated optimisation algorithm, where a doubly stochastic matrix is allowed to use, and nonidentical local step-sizes are employed. We analyse the convergence of the proposed algorithm by using the generalised small gain theorem under the assumption that each local objective function is strongly convex and has Lipschitz continuous gradient. We prove that the sequence generated by the proposed algorithm linearly converge to an optimal solution if the largest step-size is positive and less than an explicitly estimated upper bound, and the largest momentum parameter is nonnegative and less than an upper bound determined by the largest step-size. Simulation results further illustrate the efficacy of the proposed algorithm.

Keywords:

• Distributed optimisation
• Nesterov method
• acceleration
• nonidentical step-sizes
• small gain theorem
• linear convergence rate

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

The work described in this paper is supported in part by the National Natural Science Foundation of China [grant number 61773321], in part by the Innovation Support Program for Chongqing Overseas Returnees [grant number cx2019005], and in part by the Fundamental Research Funds for the Central Universities [grant number XDJK2019AC001].

Notes on contributors

Huqiang Cheng

Huqiang Cheng received the B.E. degree in internet of things engineering from Chongqing Three Gorges University, Chongqing, China, in 2018. He is currently pursuing his M.S. degree in signal and information processing from Southwest University, Chongqing, China. His research interests include multi-agent systems, machine learning, and distributed optimization.

Huaqing Li

Huaqing Li (Senior Member, IEEE) received the B.S. degree in Information and Computing Science from Chongqing University of Posts and Telecommunications, in 2009, and the Ph.D. degree in Computer Science and Technology from Chongqing University in 2013.

He is currently a Professor with the College of Electronic and Information Engineering, Southwest University, Chongqing, China. He was a Postdoctoral Researcher at School of Electrical and Information Engineering, The University of Sydney from Sept. 2014 to Sept. 2015, and at School of Electrical and Electronic Engineering, Nanyang Technological University from Nov. 2015 to Nov. 2016.

Prof. Li has authored or coauthored about 30 refereed international journal papers, and is a reviewer of several journals. He serves as a Regional Editor for Neural Computing and Applications and an Editorial Board Member for IEEE Access. His main research interests include nonlinear dynamics and control, multi-agent systems, and distributed optimization.

Zheng Wang

Zheng Wang received the B.E. degree in electronic information science and technology from the University of Jinan, China, in 2015, and the M.E. degree in electronics and communication engineering from Southwest University, China, in 2018. His research interests include multi-agent systems and distributed optimization.