logo

SCIENCE CHINA Technological Sciences, Volume 63 , Issue 9 : 1647-1655(2020) https://doi.org/10.1007/s11431-020-1596-8

Distributed accelerated optimization algorithms: Insights from an ODE

More info
  • ReceivedMar 18, 2020
  • AcceptedApr 10, 2020
  • PublishedJun 19, 2020

Abstract

In this paper, we consider the distributed optimization problem, where the goal is to minimize the global objective function formed by a sum of agents' local smooth and strongly convex objective functions, over undirected connected graphs.Several distributed accelerated algorithms have been proposed for solving such a problem in the existing literature.In this paper, we provide insights for understanding these existing distributed algorithms from an ordinary differential equation (ODE) point of view.More specifically, we first derive an equivalent second-order ODE, which is the exact limit of these existing algorithms by taking the small step-size.Moreover, focusing on the quadratic objective functions, we show that the solution of the resulting ODE exponentially converges to the unique global optimal solution.The theoretical results are validated and illustrated by numerical simulations.


Acknowledgment

This work was supported by the National Natural Science Foundation of China (Grant Nos. 91748112, 61991403, 61991404, and 61991400).


References

[1] Tsitsiklis J N. Problems in decentralized decision making and computation Dissertation for Doctoral Degree. Cambridge: Massachusetts Institute of Technology, 1984. Google Scholar

[2] Tsitsiklis J, Bertsekas D, Athans M. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE Trans Automat Contr, 1986, 31: 803-812 CrossRef Google Scholar

[3] Xiao L, Boyd S. Optimal Scaling of a Gradient Method for Distributed Resource Allocation. J Optim Theor Appl, 2006, 129: 469-488 CrossRef Google Scholar

[4] Molzahn D K, Dorfler F, Sandberg H. A Survey of Distributed Optimization and Control Algorithms for Electric Power Systems. IEEE Trans Smart Grid, 2017, 8: 2941-2962 CrossRef Google Scholar

[5] Boyd S, Parikh N, Chu E. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. FNT Machine Learning, 2010, 3: 1-122 CrossRef Google Scholar

[6] Rabbat M, Nowak R. Distributed optimization in sensor networks. In:. Google Scholar

[7] Ren W, Beard R W, Atkins E M. Information consensus in multivehicle cooperative control. IEEE Control Syst, 2007, 27: 71-82 CrossRef Google Scholar

[8] Olfati-Saber R, Fax J A, Murray R M. Consensus and Cooperation in Networked Multi-Agent Systems. Proc IEEE, 2007, 95: 215-233 CrossRef Google Scholar

[9] Yuan Y, Stan G B, Shi L. Decentralised minimum-time consensus. Automatica, 2013, 49: 1227-1235 CrossRef Google Scholar

[10] Gao W, Jiang Z P, Lewis F L. Leader-to-Formation Stability of Multiagent Systems: An Adaptive Optimal Control Approach. IEEE Trans Automat Contr, 2018, 63: 3581-3587 CrossRef Google Scholar

[11] Nedic A, Ozdaglar A. Distributed Subgradient Methods for Multi-Agent Optimization. IEEE Trans Automat Contr, 2009, 54: 48-61 CrossRef Google Scholar

[12] Nedic A, Olshevsky A. Distributed Optimization Over Time-Varying Directed Graphs. IEEE Trans Automat Contr, 2015, 60: 601-615 CrossRef Google Scholar

[13] Hong Y G, Zhang Y Q. Distributed optimization: Algorithm design and convergence analysis (in Chinese). Contl Theor Appl 2014, 31: 850--857. Google Scholar

[14] Yi P, Hong Y G. Distributed cooperative optimization and its applications (in Chinese). Sci Sin Math 2016, 46: 1547--1564. Google Scholar

[15] Long Y S, Liu S, Xie L H. Distributed constrained stochastic optimal consensus (in Chinese). Sci Sin Math 2016, 46: 1487--1498. Google Scholar

[16] Nedi? A, Liu J. Distributed Optimization for Control. Annu Rev Control Robot Auton Syst, 2018, 1: 77-103 CrossRef Google Scholar

[17] Yang T, Yi X, Wu J. A survey of distributed optimization. Annu Rev Control, 2019, 47: 278-305 CrossRef Google Scholar

[18] Xie P, You K Y, Hong Y G, et al. A survey of distributed convex optimization algorithms over networks (in Chinese). Contl Theor Appl 2018, 35: 918--927. Google Scholar

[19] Yang T, Chai T Y. Research status and prospects of distributed collaborative optimization (in Chinese). Sci Sin Tech in press. Google Scholar

[20] Matei I, Baras J S. Performance Evaluation of the Consensus-Based Distributed Subgradient Method Under Random Communication Topologies. IEEE J Sel Top Signal Process, 2011, 5: 754-771 CrossRef ADS Google Scholar

[21] Yuan K, Ling Q, Yin W. On the Convergence of Decentralized Gradient Descent. SIAM J Optim, 2016, 26: 1835-1854 CrossRef Google Scholar

[22] Shi W, Ling Q, Wu G. EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization. SIAM J Optim, 2015, 25: 944-966 CrossRef Google Scholar

[23] Qu G, Li N. Harnessing Smoothness to Accelerate Distributed Optimization. IEEE Trans Control Netw Syst, 2018, 5: 1245-1260 CrossRef Google Scholar

[24] Nedi? A, Olshevsky A, Shi W. Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs. SIAM J Optim, 2017, 27: 2597-2633 CrossRef Google Scholar

[25] Xu J, Zhu S, Soh Y C. Convergence of Asynchronous Distributed Gradient Methods Over Stochastic Networks. IEEE Trans Automat Contr, 2018, 63: 434-448 CrossRef Google Scholar

[26] Jakovetic D. A Unification and Generalization of Exact Distributed First-Order Methods. IEEE Trans Signal Inf Process over Networks, 2019, 5: 31-46 CrossRef Google Scholar

[27] Yang T, George J, Qin J. Distributed least squares solver for network linear equations. Automatica, 2020, 113: 108798 CrossRef Google Scholar

[28] Yuan Y, Tang X, Zhou W. Data driven discovery of cyber physical systems. Nat Commun, 2019, 10: 4894 CrossRef PubMed ADS arXiv Google Scholar

[29] Wang J, Elia N. Control approach to distributed optimization. In: Proceedings of the 48th Annual Allerton Conference on Communication, Control, and Computing. Allerton, 2010. 557--561. Google Scholar

[30] Gharesifard B, Cortes J. Distributed Continuous-Time Convex Optimization on Weight-Balanced Digraphs. IEEE Trans Automat Contr, 2014, 59: 781-786 CrossRef Google Scholar

[31] Xie Y, Lin Z. Global optimal consensus for multi-agent systems with bounded controls. Syst Control Lett, 2017, 102: 104-111 CrossRef Google Scholar

[32] Kia S S, Cortés J, Martínez S. Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication. Automatica, 2015, 55: 254-264 CrossRef Google Scholar

[33] Lu J, Tang C Y. Zero-Gradient-Sum Algorithms for Distributed Convex Optimization: The Continuous-Time Case. IEEE Trans Automat Contr, 2012, 57: 2348-2354 CrossRef Google Scholar

[34] Chen W, Ren W. Event-triggered zero-gradient-sum distributed consensus optimization over directed networks. Automatica, 2016, 65: 90-97 CrossRef Google Scholar

[35] Mokhtari A, Ling Q, Ribeiro A. Network Newton Distributed Optimization Methods. IEEE Trans Signal Process, 2017, 65: 146-161 CrossRef ADS Google Scholar

[36] Varagnolo D, Zanella F, Cenedese A. Newton-Raphson Consensus for Distributed Convex Optimization. IEEE Trans Automat Contr, 2016, 61: 994-1009 CrossRef Google Scholar

[37] Su W J, Boyd S, Candès E J. A differential equation for modeling Nesterov's accelerated gradient method: theory and insights. J Mach Learn Res, 2016, 17: 1--43. Google Scholar

[38] Brown A A, Bartholomew-Biggs M C. Some effective methods for unconstrained optimization based on the solution of systems of ordinary differential equations. J Optim Theor Appl, 1989, 62: 211-224 CrossRef Google Scholar

[39] Nesterov Y E. Introductory Lectures on Convex Optimization: A Basic Course. New York: Springer, 2004. 87. Google Scholar

[40] Wibisono A, Wilson A C, Jordan M I. A variational perspective on accelerated methods in optimization.. Proc Natl Acad Sci USA, 2016, 113: E7351-E7358 CrossRef PubMed Google Scholar

[41] Shi B, Du S, Su W J, et al. Acceleration via symplectic discretization of high-resolution differential equations. In: Proceedings of the 33th International Conference on Neural Information Processing Systems. 2019. 5745--5753. Google Scholar

[42] Zhang J Z, Uribe C A, Mokhtari A, et al. Achieving acceleration in distributed optimization via direct discretization of the Heavy-Ball ODE In: Proceedings of the American Control Conference. IEEE, 2019. 3408--3413. Google Scholar

Copyright 2020  CHINA SCIENCE PUBLISHING & MEDIA LTD.  中国科技出版传媒股份有限公司  版权所有

京ICP备14028887号-23       京公网安备11010102003388号