Abstract
This paper proposes a novel distributed mechanism, named gradient push algorithm (GPA), to improve the shortage in convex function optimization, such as limitations of adjacent matrix and fixed topology. The algorithm is raised based on gradient algorithm and perturbed push sum protocol in dynamic topology of wireless sensor network (WSN). First, we develop the update rule of GPA, and bring 4 lemmas to reveal its convergence attribution. Second, in order to prove convergence of the lemma, we analyze the algorithm quantitatively, whose result shows that perturbed push sum protocol (PSP) converged to the optimal solution at rate of \( O\left( {{{\ln t} \mathord{\left/ {\vphantom {{\ln t} {\sqrt t }}} \right. \kern-0pt} {\sqrt t }}} \right) \). Finally, we check its convergence through simulation. Both theory analysis and simulation results show that, the new algorithm avoids the limitation of adjacent matrix, and will convergent to the same optimal solution, which meets the need of dynamic topology in WSN.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ram, S.S., Nedic, A., Veeravalli, V.V.: A new class of distributed optimization algorithms: application to regression of distributed data. Optim. Methods Softw. 27(1), 71–88 (2012)
Duchi, J.C., Agarwal, A., Wainwright, M.J.: Dual averaging for distributed optimization: convergence analysis and network scaling. IEEE Trans. Autom. Control 57(3), 592–606 (2012)
Lucchi, A., Marquez-Neila, P., Becker, C., et al.: Learning structured models for segmentation of 2-D and 3-D imagery. IEEE Trans. Med. Imaging 34, 1096–1110 (2015)
Zhang, H., Wang, J., Tan, P., et al.: Learning CRFs for image parsing with adaptive subgradient descent. In: Proceedings of 2013 IEEE International Conference on Computer Vision (ICCV), pp. 1–8, March 2014
Xi, C., Ksam, U.A.: Directed-distributed gradient descent. In: Proceedings of 2015 53rd Annual Allerton Conference on Communication Control and Computing (Allerton), pp. 1022–1026 (2015)
Dominguez-Garcia, A.D., Hadjicostis, C.: Distributed strategies for average consensus in directed graphs. In: Proceedings of the IEEE Conference on Decision and Control, December 2011
Mechaik, M.M., Dvorak, S.L.: Series expansions for the incomplete Lipschitz-Hankel integral Ye0(a, z). Radio Sci. 31, 409–422 (1996)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Zhu, Q., Wang, Y., Song, Xo., Huang, H. (2021). Design of Gradient Push Algorithm in Time-Varying Directed Graph. In: Barolli, L., Poniszewska-Maranda, A., Park, H. (eds) Innovative Mobile and Internet Services in Ubiquitous Computing . IMIS 2020. Advances in Intelligent Systems and Computing, vol 1195. Springer, Cham. https://doi.org/10.1007/978-3-030-50399-4_34
Download citation
DOI: https://doi.org/10.1007/978-3-030-50399-4_34
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-50398-7
Online ISBN: 978-3-030-50399-4
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)