Kybernetika 61 no. 3, 377-403, 2025

Adaptive fractional distributed optimization algorithm with directed spanning trees

Huaijin Peng, Yiheng Wei, Shuaiyu Zhou and Dongdong YueDOI: 10.14736/kyb-2025-3-0377

Abstract:

Distributed optimization has garnered significant attention in past decade, yet existing algorithms mainly rely on Laplacian matrix information for parameter settings, limiting their adaptability and applicability. To design the fully distributed algorithm, this paper uses an adaptive weight framework based on directed spanning trees (DST), which not only solves the consensus optimization problem but also can be extended to solve the resource allocation problem. The innovative integration of Nabla fractional calculus further improves performance, enabling efficient discrete-time distributed optimization. Moreover, The proposed algorithms optimality and convergence properties have been rigorously analyzed, which demonstrates that they can converge to the optimal solution of the problem under consideration. Finally, numerical simulations are conducted to validate the algorithm's feasibility and superiority.

Keywords:

directed graphs, resource allocation, distribute optimization, fractional calculus, directed spanning trees, fully distributed

Classification:

05C05, 05C20, 26A33, 90C26

paper.pdf

References:

  1. S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein {et al.}: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Machine Learn. 3 (2011), 1, 1-122.   CrossRef
  2. F. Bullo, J. Cortés and S. Martinez: Distributed control of robotic networks: a mathematical approach to motion coordination algorithms. Princeton University Press, Princeton 2009.   CrossRef
  3. Y. Q. Chen, Q. Gao, Y. H. Wei and Y. Wang: Study on fractional order gradient methods. Appl. Math. Comput. 314 (2017), 310-321.   DOI:10.1016/j.amc.2017.07.023
  4. S. S. Cheng and S. Liang: Distributed optimization for multi-agent system over unbalanced graphs with linear convergence rate. Kybernetika 56 (2020), 3, 559-577.   DOI:10.14736/kyb-2020-3-0559
  5. S. S. Cheng, S. Liang and Y. Fan: Distributed solving {S}ylvester equations with fractional order dynamics. Control Theory Technol. 19 (2021), 2, 249-259.   DOI:10.1007/s11768-021-00044-0
  6. D. R. Ding, Q. L. Han and X. H. Ge: Distributed filtering of networked dynamic systems with non-gaussian noises over sensor networks: a survey. Kybernetika 56 (2020), 1, 5-34.   CrossRef
  7. B. Gharesifard and J. Cortés: Distributed continuous-time convex optimization on weight-balanced digraphs. IEEE Trans. Automat. Control 59 (2014), 3, 781-786.   DOI:10.1109/TAC.2013.2278132
  8. X. L. Hong, Y. H. Wei, S. Y. Zhou and D. D. Yue: Nabla fractional distributed optimization algorithms over undirected/directed graphs. J. Franklin Inst. 361 (2024), 3, 1436-1454.   DOI:10.1016/j.jfranklin.2024.01.013
  9. J. Y. Huang, S. Y. Zhou, H. Tu, Y. H. Yao and Q. S. Liu: Distributed optimization algorithm for multi-robot formation with virtual reference center. IEEE/CAA J. Automat. Sinica 9 (2022), 4, 732-734.   DOI:10.1109/JAS.2022.105473
  10. P. Humblet: A distributed algorithm for minimum weight directed spanning trees. IEEE Trans. Commun. 31 (1983), 6, 756-762.   DOI:10.1109/TCOM.1983.1095883
  11. S. S. Kia, J. Cortés and S. Martínez: Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication. Automatica 55 (2015), 254-264.   DOI:10.1016/j.automatica.2015.03.001
  12. Z. H. Li, Z. T. Ding, J. Y. Sun and Z. K. Li: Distributed adaptive convex optimization on directed graphs via continuous-time algorithms. IEEE Trans. Automat. Control 63 (2018), 5, 1434-1441.   DOI:10.1109/TAC.2017.2750103
  13. S. Liang, L. Y. Wang and G. Yin: Fractional differential equation approach for convex optimization with convergence rate analysis. Optimiz. Lett. 45 (2019), 9, 145-155.   CrossRef
  14. P. Lin, W. Ren and J. A. Farrell: Distributed continuous-time optimization: Nonuniform gradient gains, finite-time convergence, and convex constraint set. IEEE Trans. Automat. Control 62 (2017), 5, 2239-2253.   DOI:10.1109/TAC.2016.2604324
  15. Q. S. Liu, S. F. Yang and Y. G. Hong: Constrained consensus algorithms with fixed step size for distributed convex optimization over multiagent networks. IEEE Trans. Automat. Control 62 (2017), 8, 4259-4265.   DOI:/10.1109/TAC.2017.2681200
  16. D. K. Molzahn, F. Dörfler, H. Sandberg, S. H. Low, S. Chakrabarti, R. Baldick and J. Lavaei: A survey of distributed optimization and control algorithms for electric power systems. IEEE Trans. Smart Grid 8 (2017), 6, 2941-2962.   DOI:10.1109/TSG.2017.2720471
  17. A. Nedić and A. Ozdaglar: Distributed subgradient methods for multi-agent optimization. IEEE Trans. Automat. Control 54 (2009), 1, 48-61.   DOI:10.1109/tac.2008.2009515
  18. W. Ni and X. L. Wang: Averaging approach to distributed convex optimization for continuous-time multi-agent systems. Kybernetika 52 2016), 6, 898-913.   DOI:10.14736/kyb-2016-6-0898
  19. X. T. Ni, Y. H. Wei, S. Y. Zhou and M. Tao: Multi-objective network resource allocation method based on fractional {PID} control. Signal Process. 227 (2025), 109717.   DOI:10.1016/j.sigpro.2024.109717
  20. S. Pu, W. Shi, J. Xu and A. Nedic: Pushpull gradient methods for distributed optimization in networks. IEEE Trans. Automat. Control 66 (2021), 1, 1-16.   CrossRef
  21. Y. F. Pu, J. L. Zhou, Y. Zhang, N. Zhang, G. Huang and P. Siarry: Fractional extreme value adaptive training method: fractional steepest descent approach. IEEE Trans. Neural Networks Learn. Systems 26 (2015), 4, 653-662.   DOI:10.1109/TNNLS.2013.2286175
  22. W. Ren and Y. C. Cao: Distributed Coordination of Multi-Agent Networks: Emergent Problems, Models, and Issues. Springer Science and Business Media, 2010.   CrossRef
  23. Y. W. Song, J. D. Cao and L. Rutkowski: A fixed-time distributed optimization algorithm based on event-triggered strateg. IEEE Trans. Network Sci. Engrg. 9 (2021), 3, 1154-1162.   DOI:10.1109/TNSE.2021.3133541
  24. B. Touri and B. Gharesifard: A modified saddle-point dynamics for distributed convex optimization on general directed graphs. IEEE Trans. Automat. Control 65 (2020), 7, 3098-3103.   DOI:10.1109/TAC.2019.2947184
  25. D. Varagnolo, F. Zanella, A. Cenedese, G. Pillonetto and L. Schenato: Newton-Raphson consensus for distributed convex optimization. IEEE Trans. Automat. Control 61 (2016), 4, 994-1009.   DOI:10.1109/tac.2015.2449811
  26. D. Wang and Z. Z. Gao: Distributed finite-time optimization algorithms with a modified {N}ewton-{R}aphson method. Neurocomputing 536 (2023), 73-79.   DOI:10.1016/j.neucom.2023.03.027
  27. Y. H. Wang, P. Lin and H. S. Qin: Distributed classification learning based on nonlinear vector support machines for switching networks. Kybernetika 53 (2017), 4, 595-611.   DOI:10.14736/kyb-2017-4-0595
  28. X. Y. Wang, G. D. Wang and S. H. Li: Distributed finite-time optimization for integrator chain multiagent systems with disturbances. IEEE Trans. Automat. Control 65 (2020), 12, 5296-5311.   DOI:10.1109/TAC.2020.2979274
  29. Y. H. Wei and Y. Q. Chen: Converse Lyapunov theorem for nabla asymptotic stability without conservativeness. IEEE Trans. Systems Man Cybernet.: Systems 52 (2022), 4, 2676-2687.   DOI:10.1109/TSMC.2021.3051639
  30. Y. H. Wei, Y. Kang, W. D. Yin and Y. Wang: Generalization of the gradient method with fractional order gradient direction. J. Franklin Inst. 357 (2020), 4, 2514-2532.   DOI:10.1016/j.jfranklin.2020.01.008
  31. Y. D. Wei, Y. H. Wei, Y. Q. Chen and Y. Wang: Mittag-Leffler stability of nabla discrete fractional order dynamic systems. Nonlinear Dynamics 101 (2020), 407-417.   DOI:10.1007/s11071-020-05776-3
  32. Y. H. Wei, L. L. Zhao, X. Zhao and J. D. Cao: Fractional difference inequalities for possible Lyapunov functions: A review. Fract. Calculus Appl. Anal. (2024).   DOI:10.1007/s13540-024-00298-w
  33. R. Xin and U. A. Khan: A linear algorithm for optimization over directed graphs with geometric convergence. IEEE Control Systems Lett. 2 (2018), 3, 315-320.   DOI:10.1109/LCSYS.2018.2834316
  34. X. L. Yang, W. M. Zhao, J. X. Yuan, T. Chen, C. Zhang and L. Q. Wang: Distributed optimization for fractional-order multi-agent systems based on adaptive backstepping dynamic surface control technology. Fractal Fractional 6 (2022), 11, 642.   DOI:10.3390/fractalfract6110642
  35. D. D. Yue, S. Baldi, J. D. Cao and B. De Schutter: Distributed adaptive optimization with weight-balancing. IEEE Trans. Automat. Control 67 (2022), 4, 2068-2075.   DOI:10.1109/TAC.2021.3071651
  36. D. D. Yue, S. Baldi, J. D. Cao, Q. Li and B. De Schutter: A directed spanning tree adaptive control solution to time-varying formations. IEEE Trans. Control Network Syst. 8 (2021), 2, 690-701.   DOI:10.1109/TCNS.2021.3050332
  37. Y. K. Zeng, Y. H. Wei, S. Y. Zhou and D. D. Yue: Distributed optimization via active disturbance rejection control: a nabla fractional design. Kybernetika 60 (2024), 1, 90-109.   DOI:10.14736/kyb-2024-1-0090
  38. D. D. Yue, S. Baldi, J. D. Cao, Q. Li and B. De Schutter: Distributed adaptive resource allocation: an uncertain saddle-point dynamics viewpoint. IEEE/CAA J. Automat. Sinica 10 (2023), 12, 2209-2221.   DOI:10.1109/JAS.2023.123402
  39. J. Zhang, L. Liu, X. H. Wang and H. B. Ji: Fully distributed algorithm for resource allocation over unbalanced directed networks without global {L}ipschitz condition. IEEE Trans. Automat. Control 68 (2022), 8, 5119-5126.   DOI:10.1109/TAC.2022.3216972
  40. Y. L. Zheng and Q. S. Liu: A review of distributed optimization: Problems, models and algorithms. Neurocomputing 483 (2022), 446-459.   DOI:10.1016/j.neucom.2021.06.097
  41. S. Y. Zhou, Y. H. Wei, S. Liang and J. Cao: A gradient tracking protocol for optimization over nabla fractional multi-agent systems. IEEE Trans. Signal Inform. Process. Networks 10 (2024), 500-512.   DOI:10.1109/TSIPN.2024.3402354