Abstract
This paper considers a distributed resource allocation problem over time-varying networks. The objective of each agent in the network is to optimize the sum of separable convex functions subjected to resource constraints by observing its local objective function and the information exchanged with its adjacent neighbors. Thus, the problem lies in a distributed framework. In existing literature dealing with similar problems, the measurement of the gradients/subgradients of the objective functions has been applied in the algorithm design. In this paper, by adding stochastic dithers to the local objective functions and constructing randomized differences, we propose a distributed gradient-free algorithm for solving the problem, and show that the algorithm is strongly convergent; that is, the estimates generated from each agent almost certainly converge to the optimal resource allocation solution of the network. Finally, the effectiveness of the algorithm is validated by conducting numerical experiments.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Hetzer J, Yu D C, Bhattarai K. An economic dispatch model incorporating wind power. IEEE Trans Energy Convers, 2008, 23: 603–611
Guo F, Wen C, Mao J, et al. Distributed economic dispatch for smart grids with random wind power. IEEE Trans Smart Grid, 2016, 7: 1572–1583
Zhang Y, Giannakis G B. Efficient decentralized economic dispatch for microgrids with wind power integration. In: Proceedings of the 6th Annual IEEE Green Technologies Conference, 2014. 7–12
Zhao C, Topcu U, Li N, et al. Design and stability of load-side primary frequency control in power systems. IEEE Trans Automat Contr, 2014, 59: 1177–1189
Mainland G, Parkes D C, Welsh M. Decentralized, adaptive resource allocation for sensor networks. In: Proceedings of the 2nd Conference on Symposium on Networked Systems Design & Implementation, 2005. 315–328
Ozel O, Tutuncuoglu K, Yang J, et al. Transmission with energy harvesting nodes in fading wireless channels: optimal policies. IEEE J Sel Areas Commun, 2011, 29: 1732–1743
Koopman B O. The optimum distribution of effort. J Oper Res Soc Am, 1953, 1: 52–63
D’Amico A A, Sanguinetti L, Palomar D P. Convex separable problems with linear constraints in signal processing and communications. IEEE Trans Signal Process, 2014, 62: 6045–6058
Heal G M. Planning without prices. Rev Economic Studies, 1969, 36: 347–362
Ibaraki T, Katoh N. Resource Allocation Problems: Algorithmic Approaches. Cambridge: MIT Press, 1988
Aybat N S, Hamedani E Y. A distributed ADMM-like method for resource sharing over time-varying networks. SIAM J Optim, 2019, 29: 3036–3068
Lakshmanan H, de Farias D P. Decentralized resource allocation in dynamic networks of agents. SIAM J Optim, 2008, 19: 911–940
Nedić A, Olshevsky A, Shi W. Improved convergence rates for distributed resource allocation. In: Proceedings of IEEE Conference on Decision and Control (CDC), 2018. 172–177
Yi P, Lei J, Hong Y. Distributed resource allocation over random networks based on stochastic approximation. Syst Control Lett, 2018, 114: 44–51
Zhang J, You K, Cai K. Distributed dual gradient tracking for resource allocation in unbalanced networks. IEEE Trans Signal Process, 2020, 68: 2186–2198
Li X, Xie L, Hong Y. Distributed continuous-time algorithm for a general nonsmooth monotropic optimization problem. Int J Robust Nonlin Control, 2019, 29: 3252–3266
Conn A R, Scheinberg K, Vicente L N. Introduction to Derivative-Free Optimization. Philadelphia: SIAM, 2009
Nesterov Y, Spokoiny V. Random gradient-free minimization of convex functions. Found Comput Math, 2017, 17: 527–566
Kiefer J, Wolfowitz J. Stochastic estimation of the maximum of a regression function. Ann Math Statist, 1952, 23: 462–466
Chen H F, Duncan T E, Pasik-Duncan B. A Kiefer-Wolfowitz algorithm with randomized differences. IEEE Trans Automat Contr, 1999, 44: 442–453
Spall J C. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Trans Automat Contr, 1992, 37: 332–341
Hajinezhad D, Hong M, Garcia A. Zeroth order nonconvex multi-agent optimization over networks. 2017. ArXiv:1710.09997
Pang Y, Hu G. A distributed optimization method with unknown cost function in a multi-agent system via randomized gradient-free method. In: Proceedings of the 11th Asian Control Conference (ASCC), 2017. 144–149
Sahu A K, Jakovetic D, Bajovic D, et al. Distributed zeroth order optimization over random networks: a Kiefer-Wolfowitz stochastic approximation approach. In: Proceedings of IEEE Conference on Decision and Control (CDC), 2018. 4951–4958
Wang Y, Zhao W, Hong Y, et al. Distributed subgradient-free stochastic optimization algorithm for nonsmooth convex functions over time-varying networks. SIAM J Control Optim, 2019, 57: 2821–2842
Yuan D M, Ho D W C. Randomized gradient-free method for multiagent optimization over time-varying networks. IEEE Trans Neural Netw Learn Syst, 2015, 26: 1342–1347
Poveda J, Quijano N. Distributed extremum seeking for real-time resource allocation. In: Proceedings of 2013 American Control Conference, 2013. 2772–2777
Ramírez-Llanos E, Martínez S. Gradient-free distributed resource allocation via simultaneous perturbation. In: Proceedings of the 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2016. 590–595
Ramírez-Llanos E, Martínez S. Distributed and robust resource allocation algorithms for multi-agent systems via discrete-time iterations. In: Proceedings of the 54th IEEE Conference on Decision and Control (CDC), 2015. 1390–1395
Kushner H, Yin G G. Stochastic Approximation and Recursive Algorithms and Applications. New York: Springer, 2003
Boyd S, Boyd S P, Vandenberghe L. Convex Optimization. Cambridge: Cambridge University Press, 2004
Ruszczynski A. Nonlinear Optimization. Princeton: Princeton University Press, 2006
Yi P, Hong Y, Liu F. Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and application to economic dispatch of power systems. Automatica, 2016, 74: 259–269
Feijer D, Paganini F. Stability of primal-dual gradient dynamics and applications to network optimization. Automatica, 2010, 46: 1974–1981
Yi P, Hong Y, Liu F. Distributed gradient algorithm for constrained optimization with application to load sharing in power systems. Syst Control Lett, 2015, 83: 45–52
Lei J, Chen H F, Fang H T. Asymptotic properties of primal-dual algorithm for distributed stochastic optimization over random networks with imperfect communications. SIAM J Control Optim, 2018, 56: 2159–2188
Aysal T C, Yildiz M E, Sarwate A D, et al. Broadcast gossip algorithms for consensus. IEEE Trans Signal Process, 2009, 57: 2748–2761
Srivastava K, Nedić A, Stipanović D M. Distributed constrained optimization over noisy networks. In: Proceedings of IEEE Conference on Decision and Control (CDC), 2010. 1945–1950
Zhang Q, Zhang J F. Distributed parameter estimation over unreliable networks with markovian switching topologies. IEEE Trans Automat Contr, 2012, 57: 2545–2560
Chen H F. Stochastic Approximation and Its Applications. Dordrecht: Kluwer Academic Publishers, 2002
Acknowledgements
This work was supported in part by National Key Research and Development Program of China (Grant No. 2018YFA0703800) and National Natural Science Foundation of China (Grant No. 61822312).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Geng, X., Zhao, W. Randomized difference-based gradient-free algorithm for distributed resource allocation. Sci. China Inf. Sci. 65, 142205 (2022). https://doi.org/10.1007/s11432-020-3147-2
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11432-020-3147-2