Distributed Heterogeneous Multi-Agent Optimization with Stochastic Sub-Gradient

HU Haokun, MO Lipo, CAO Xianbing

Journal of Systems Science & Complexity ›› 2024, Vol. 37 ›› Issue (4) : 1470-1487.

PDF(477 KB)
中国科学院数学与系统科学研究院期刊网
JSSC
PDF(477 KB)
Journal of Systems Science & Complexity ›› 2024, Vol. 37 ›› Issue (4) : 1470-1487. DOI: 10.1007/s11424-024-2149-9

Distributed Heterogeneous Multi-Agent Optimization with Stochastic Sub-Gradient

  • HU Haokun1,2, MO Lipo3,4,5, CAO Xianbing1
Author information +
History +

Abstract

This paper studies the optimization problem of heterogeneous networks under a time-varying topology. Each agent only accesses to one local objective function, which is nonsmooth. An improved algorithm with noisy measurement of local objective functions' sub-gradients and additive noises among information exchanging between each pair of agents is designed to minimize the sum of objective functions of all agents. To weaken the effect of these noises, two step sizes are introduced in the control protocol. By graph theory, stochastic analysis and martingale convergence theory, it is proved that if the sub-gradients are uniformly bounded, the sequence of digraphs is balanced and the union graph of all digraphs is joint strongly connected, then the designed control protocol can force all agents to find the global optimal point almost surely. At last, the authors give some numerical examples to verify the effectiveness of the stochastic sub-gradient algorithms.

Key words

Communication noises / distributed stochastic optimization / heterogeneous networks / sub-gradient measurement noises

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
HU Haokun , MO Lipo , CAO Xianbing. Distributed Heterogeneous Multi-Agent Optimization with Stochastic Sub-Gradient. Journal of Systems Science & Complexity, 2024, 37(4): 1470-1487 https://doi.org/10.1007/s11424-024-2149-9

References

[1] Wang B, Fei Q, and Wu Q H, Distributed time-varying resource allocation optimization based on finite-time consensus approach, IEEE Control Systems Letters, 2021, 5(2):599-604.
[2] Deng Z H, Distributed algorithm design for resource allocation problems of second-order multiagent systems over weight-balanced digraphs, IEEE Transactions on Systems, Man, and Cybernetics:Systems, 2021, 51(6):3512-3521.
[3] Mohebifard R and Hajbabaie A, Distributed optimization and coordination algorithms for dynamic traffic metering in urban street networks, IEEE Transactions on Intelligent Transportation Systems, 2019, 20(5):1930-1941.
[4] Sundhar Ram S, Nedić A, and Veeravalli V V, A new class of distributed optimization algorithms:Application to regression of distributed data, Optimization Methods and Software, 2012, 27(1):71-88.
[5] Wang Y H, Lin P, and Hong Y G, Distributed regression estimation with incomplete data in multi-agent networks, Science China:Information Sciences, 2018, 61(9):162-175.
[6] Nedić A and Ozdaglar A, Distributed subgradient methods for multi-agent optimization, IEEE Transactions on Automatic Control, 2009, 54(1):48-61.
[7] Nedić A, Ozdaglar A, and Parrilo P A, Constrained consensus and optimization in multi-agent networks, IEEE Transactions on Automatic Control, 2010, 55(4):922-938.
[8] Shi G, Johansson K H, and Hong Y, Reaching an optimal consensus:Dynamical systems that compute intersections of convex sets, IEEE Transactions on Automatic Control, 2013, 58(3):610-622.
[9] Qiu Z R, Liu S, and Xie L H, Distributed constrained optimal consensus of multi-agent systems, Automatica, 2016, 68:209-215.
[10] Gharesifard B and Cortés J, Distributed continuous-time convex optimization on weight-balanced digraphs, IEEE Transactions on Automatic Control, 2014, 59(3):781-786.
[11] Kia S S, Cortés J, and Martínez S, Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication, Automatica, 2015, 55:254-264.
[12] Lin P, Ren W, and Farrell J A, Distributed continuous-time optimization:Nonuniform gradient gains, finite-time convergence, and convex constraint set, IEEE Transactions on Automatic Control, 2017, 62(5):2239-2253.
[13] Li T and Zhang J F, Mean square average-consensus under measurement noises and fixed topologies:Necessary and sufficient conditions, Automatica, 2009, 45(8):1929-1936.
[14] Li T and Zhang J F, Consensus conditions of multi-agent systems with time-varying topologies and stochastic communication noises, IEEE Transactions on Automatic Control, 2010, 55(9):2043-2057.
[15] Srivastava K, Nedić A, and Stipanović D M, Distributed constrained optimization over noisy networks, 49th IEEE Conference on Decision and Control (CDC), 2010, 1945-1950.
[16] Wang D, Zhou J, Wang Z H, et al., Random gradient-free optimization for multiagent systems with communication noises under a time-varying weight balanced digraph, IEEE Transactions on Systems, Man, and Cybernetics:Systems, 2020, 50(1):281-289.
[17] Pu S, Olshevsky A, and Paschalidis I C, Asymptotic network independence in distributed stochastic optimization for machine learning:Examining distributed and centralized stochastic gradient descent, IEEE Signal Processing Magazine, 2020, 37(3):114-122.
[18] Chen T, Sun Y, and Yin W, Communication-adaptive stochastic gradient methods for distributed learning, IEEE Transactions on Signal Processing, 2021, 69:4637-4651.
[19] Sundhar Ram S, Nedić A, and Veeravalli V V, Distributed stochastic subgradient projection algorithms for convex optimization, Journal of Optimization Theory and Applications, 2010, 147(3):516-545.
[20] Nedić A and Olshevsky A, Stochastic gradient-push for strongly convex functions on time-varying directed graphs, IEEE Transactions on Automatic Control, 2016, 61(12):3936-3947.
[21] Srivastava K and Nedic A, Distributed asynchronous constrained stochastic optimization, IEEE Journal of Selected Topics in Signal Processing, 2011, 5(4):772-790.
[22] Li T, Fu K L, and Fu X Z, Distributed stochastic subgradient optimization algorithms over random and noisy networks, 2020, arXiv:2008.08796.
[23] Wang D, Yin J J, and Wang W, Distributed randomized gradient-free optimization protocol of multiagent systems over weight-unbalanced digraphs, IEEE Transactions on Cybernetics, 2021, 51(1):473-482.
[24] Zheng Y S, Zhao Q, Ma J Y, et al., Second-order consensus of hybrid multi-agent systems, Systems and Control Letters, 2019, 125:51-58.
[25] Guo S Y, Mo L P, and Yu Y G, Mean-square consensus of heterogeneous multi-agent systems with communication noises, Journal of the Franklin Institute, 2018, 355(8):3717-3736.
[26] Sun F L, Shen Y H, Kurths J, et al., Mean-square consensus of multi-agent systems with noise and time delay via event-triggered control, Journal of the Franklin Institute, 2020, 357(9):5317-5339.
[27] Zhang Z, Chen S M, and Zheng Y S, Fully distributed scaled consensus tracking of high-order multiagent systems with time delays and disturbances, IEEE Transactions on Industrial Informatics, 2022, 18(1):305-314.
[28] Mo L P, Guo S Y, and Yu Y G, Mean-square consensus of heterogeneous multi-agent systems with nonconvex constraints, markovian switching topologies and delays, Neurocomputing, 2018, 291:167-174.
[29] Mo L P, Yu Y G, Ren G J, et al., Constrained consensus of continuous-time heterogeneous multi-agent networks with nonconvex constraints and delays, Journal of System Science and Complexity, 2022, 35(1):105-122.
[30] Mo L P, Zhang Z X, and Yu Y G, Distributed discrete-time optimization of heterogeneous multiagent networks with unbounded position constraints and nonconvex velocity constraints, Neurocomputing, 2021, 466:92-101.
[31] Mo L P, Hu H K, Yu Y G, et al., Distributed optimization without boundedness of gradients for second-order multi-agent systems over unbalanced network, Information Sciences, 2021, 565:177-195.
[32] Liu P, Xiao F, Wei B, et al., Distributed constrained optimization problem of heterogeneous linear multi-agent systems with communication delays, Systems and Control Letters, 2021, 155(1):105002.
[33] Wang Z, Liu J X, Wang D, et al., Distributed cooperative optimization for multiple heterogeneous Euler-Lagrangian systems under global equality and inequality constraints, Information Sciences, 2021, 577:449-466.
[34] Boyd S, Linear Matrix Inequalities in System and Control Theory, SIAM, Philadelphia, 1997.
[35] Chen H F, Stochastic Approximation and Its Application, Kluwer Academic Publishers, Holland, 2002.

Funding

This work was supported by the National Natural Science Foundation of China under Grant No. 61973329, National Key Technology R&D Program of China under Grant No. 2021YFD2100605, and Project of Beijing Municipal University Teacher Team Construction Support Plan under Grant No. BPHR20220104.
PDF(477 KB)

194

Accesses

0

Citation

Detail
Sections
Recommended

/

〈 〉