Kybernetika 59 no. 3, 418-436, 2023

Distributed accelerated Nash equilibrium learning for two-subnetwork zero-sum game with bilinear coupling

Xianlin Zeng, Lihua Dou and Jinqiang CuiDOI: 10.14736/kyb-2023-3-0418

Abstract:

This paper proposes a distributed accelerated first-order continuous-time algorithm for $O({1}/{t^2})$ convergence to Nash equilibria in a class of two-subnetwork zero-sum games with bilinear couplings. First-order methods, which only use subgradients of functions, are frequently used in distributed/parallel algorithms for solving large-scale and big-data problems due to their simple structures. However, in the worst cases, first-order methods for two-subnetwork zero-sum games often have an asymptotic or $O(1/t)$ convergence. In contrast to existing time-invariant first-order methods, this paper designs a distributed accelerated algorithm by combining saddle-point dynamics and time-varying derivative feedback techniques. If the parameters of the proposed algorithm are suitable, the algorithm owns $O(1/t^2)$ convergence in terms of the duality gap function without any uniform or strong convexity requirement. Numerical simulations show the efficacy of the algorithm.

Keywords:

continuous-time algorithm, two-subnetwork zero-sum game, distributed accelerated algorithm, Nash equilibrium learning, nonsmooth function

Classification:

91A10, 37N40, 93A14

paper.pdf

References:

  1. M. S. Alkousa, A. V. Gasnikov, D. M. Dvinskikh, D. A. Kovalev and F. S. Stonyakin: Accelerated methods for saddle-point problem. Comput. Math. and Math. Phys. 60 (2020), 1787-1787.   DOI:10.1134/S0965542520110020
  2. H. Attouch, Z. Chbani and H. Riahi: Rate of convergence of the Nesterov accelerated gradient method in the subcritical case $\alpha\leq 3$. ESAIM: COCV 25 (2019), 2.   DOI:10.1051/cocv/2017083
  3. J. P. Aubin and A. Cellina: Differential Inclusions. Springer-Verlag, Berlin 1984.   CrossRef
  4. A. Beck and M. Teboulle: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 21 (2009), 1, 183-202.   DOI:10.1137/080716542
  5. D. P. Bertsekas: Convex Optimization Algorithms. Athena Scientific, Belmont 2015.   CrossRef
  6. A. Chambolle and T. Pock: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40 (2011), 1, 120-145.   DOI:10.1007/s10851-010-0251-1
  7. Y. Chen, G. Lan and Y. Ouyang: Optimal primal-dual methods for a class of saddle point problems. SIAM J. Control Optim. 24 (2014), 4, 1779-1814.   DOI:10.1137/130919362
  8. S. Chen and S. Liang: Distributed optimization for multi-agent system over unbalanced graphs with linear convergence rate. Kybernetika 56 (2020), 3, 559-577.   DOI:10.31857/S0044452920070438
  9. Z. Chen and S. Liang: Distributed aggregative optimization with quantized communication. Kybernetika 58 (2022), 1, 123-144.   DOI:10.14736/kyb-2022-1-0123
  10. G. Chen, Y. Ming, Y. Hong and P. Yi: Distributed algorithm for $\varepsilon$-generalized Nash equilibria with uncertain coupled constraints. Automatica 123 (2021), 109313.   DOI:10.1016/j.automatica.2020.109313
  11. J. Chen, J. Sun and G. Wang: From unmanned systems to autonomous intelligent systems. Engineering 8 (2022), 1-5.   DOI:10.1155/2022/1426724
  12. A. Cherukuri, B. Gharesifard and J. Cortés: Saddle-point dynamics: Conditions for asymptotic stability of saddle points. SIAM J. Control Optim. 55 (2017), 1, 486-511.   DOI:10.1137/15M1026924
  13. Z. Deng: Distributed generalized Nash equilibrium seeking algorithm for nonsmooth aggregative games. Automatica 132 (2021), 109794.   DOI:10.1016/j.automatica.2021.109794
  14. Z. Deng: Distributed Nash equilibrium seeking for aggregative games with second-order nonlinear players. Automatica 135 (2022), 109980.   DOI:10.1016/j.automatica.2021.109980
  15. B. Gharesifard and J. Cortés: Distributed convergence to Nash equilibria in two-network zero-sum games. Automatica 49 (2013), 6, 1683-1692.   DOI:10.1016/j.automatica.2013.02.062
  16. R. Goebel: Stability and robustness for saddle-point dynamics through monotone mappings. Syst. Control. Lett. 108 (2017), 16-22.   DOI:10.1016/j.sysconle.2017.07.014
  17. X. He, R. Hu and Y. P. Fang: Convergence rates of inertial primal-dual dynamical methods for separable convex optimization problems. SIAM J. Control Optim. 59 (2021), 5, 3278-3301.   DOI:10.1137/20M1355379
  18. S. Huang, J. Lei and Y. Hong: A linearly convergent distributed nash equilibrium seeking algorithm for aggregative games. IEEE Trans. Automat. Control , 2022.   DOI:10.1109/TAC.2022.3154356
  19. S. Huang, J. Lei, Y. Hong and U. V. Shanbhag: No-regret distributed learning in two-network zero-sum games. In: 60th IEEE Conference on Decision and Control (CDC), 2021, pp. 924-929.   CrossRef
  20. T. Ibaraki and N. Katoh: Resource Allocation Problems: Algorithmic Approaches. MIT Press, Cambridge 1988.   CrossRef
  21. S. Khan, M. Tufail, M. T. Khan, Z. A. Khan, J. Iqbal and A. Wasim: A novel framework for multiple ground target detection, recognition and inspection in precision agriculture applications using a UAV. Unmanned Syst. 10 (2022), 1, 45-56.   CrossRef
  22. 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
  23. P. Li, J. Hu, L. Qiu, Y. Zhao and B. K. Ghosh: A distributed economic dispatch strategy for power-water networks. IEEE Trans. Control. Netw. Syst9 (2022), 1, 356-366.   DOI:10.1109/TCNS.2021.3104103
  24. Y. Lou, Y. Hong, L. Xie, G. Shi and K. H. Johansson: Nash equilibrium computation in subnetwork zero-sum games with switching communications. IEEE Trans. Automat. Control 61 (2016), 10, 2920-2935.   DOI:10.1109/TAC.2015.2504962
  25. L. Mo, Y. Yu, G. Ren and X. Yuan: Constrained consensus of continuous-time heterogeneous multi-agent networks with nonconvex constraints and delays. J. Syst. Sci. Complex 35 (2022), 105-122.   DOI:10.1007/s11424-021-0092-6
  26. Y. Nesterov: A method of solving a convex programming problem with convergence rate $O(1/k^2)$. Soviet Math. Doklady 27 (1983), 372-376.   CrossRef
  27. Y. Nesterov: Smooth minimization of non-smooth functions. Math Program. 103 (2005), 1, 127-152.   DOI:10.1007/s10107-004-0552-5
  28. L. A. Paoli: An existence result for vibrations with unilateral constraints: Case of a nonsmooth set of constraints. Math. Models Methods Appl. Sci. 10 (2000), 6, 815-831.   DOI:10.1142/S0218202500000422
  29. Z. Peng, R. Luo, J. Hu, K. Shi and B. K. Ghosh: Distributed optimal tracking control of discrete-time multiagent systems via event-triggered reinforcement learning. IEEE Trans. Circuits Syst. I Regular Papers 69 (2022), 9, 3689-3700.   CrossRef
  30. B. Shi, S. S. Du, M. I. Jordan and W. J. Su: Understanding the acceleration phenomenon via high-resolution differential equations. Math. Program. 195 (2022), 79-148.   DOI:10.1007/s10107-021-01681-8
  31. W. Su, S. Boyd and E. J. Candes: A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights. Adv. Neural Inf. Process. Syst. 3 (2015), 1, 2510-2518.   CrossRef
  32. A. Vassilis, A. Jean-Francois and D. Charles: The differential inclusion modeling FISTA algorithm and optimality of convergence $b\leq 3$. SIAM J. Control. Optim. 29 (2018), 1, 551-574.   DOI:10.1137/17m1128642
  33. Q. Wang, J. Chen, B. Xin and X. Zeng: Distributed optimal consensus for Euler-Lagrange systems based on event-triggered control. IEEE Trans. Syst. Man Cybern. Syst. 51 (2021), 7, 4588-4598.   DOI:10.1109/TSMC.2019.2944857
  34. M. Wang, L. Li, Q. Dai and F. Shi: Resource allocation based on DEA and non-cooperative game. J. Syst. Sci. Complex 34 (2022), 2231-2249.   DOI:10.1007/s11424-021-0259-1
  35. Y. Wang, P. Lin and H. 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
  36. D. Wang, Z. Wang, Z. Wu and W. Wang: Distributed convex optimization for nonlinear multi-agent systems disturbed by a second-order stationary process over a digraph. Sci. China Inf. Sci. 65 (2022), 132201.   CrossRef
  37. A. Wibisono, A. C. Wilson and M. I. Jordan: A variational perspective on accelerated methods in optimization. Proc. Natl. Acad. Sci. 113 (2016), 47, 7351-7358.   DOI:10.13109/kont.2016.47.2.113
  38. C. Wu, H. Fang, Q. Yang, X. Zeng, Y. Wei and J. Chen: Distributed cooperative control of redundant mobile manipulators with safety constraints. IEEE Trans. Cybernet. 53 (2023), 2, 1195-1207.   DOI:10.1109/TCYB.2021.3104044
  39. Y. Wu, Q. Liang, Y. Zhao, J. Hu and L. Xiang: Distributed estimation based output consensus control of heterogeneous leader-follower systems with antagonistic interactions. Sci. China Inf. Sci. 66 (2023), 139204.   CrossRef
  40. Y. Wu, Q. Liang, Y. Zhao, J. Hu and L. Xiang: Effective distributed algorithm for solving linear matrix equations. Sci. China Inf. Sci. 66 (2023), 189202.   CrossRef
  41. S. Xie, L. Wang, M. H. Nazari, G. Yin and G. Li: Distributed optimization with markovian switching targets and stochastic observation noises with applications to dc microgrids. Sci. China Inf. Sci. 65 (2022), 222205.   CrossRef
  42. Y. Xu: Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming. SIAM J. Optim. 27 (2018), 3, 1459-1484.   DOI:10.1137/16M1082305
  43. Y. Xu and S. Zhang: Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization. Comput. Optim. Appl. 70 (2018), 91-128.   DOI:10.1007/s10589-017-9972-z
  44. R. Yang, L. Liu and G. Feng: An overview of recent advances in distributed coordination of multi-agent systems. Unmanned Syst. 2022.   DOI:10.1142/S2301385021500199
  45. S. Yang, J. Wang and Q. Liu: Cooperative-competitive multiagent systems for distributed minimax optimization subject to bounded constraints. IEEE Trans. Automat. Control 64 (2019), 4, 358-1372.   DOI:10.1109/TAC.2018.2862471
  46. M. Ye, G. Hu and S. Xu: An extremum seeking-based approach for Nash equilibrium seeking in {$N$}-cluster noncooperative games. Automatica 114 (2020), 108815.   DOI:10.1016/j.automatica.2020.108815
  47. M. Ye, J. Yin and L. Yin: Distributed Nash equilibrium seeking for games in second-order systems without velocity measurement. IEEE Trans. Automat. Control.   DOI:10.1109/TAC.2021.3131553
  48. X. Zeng, J. Chen, S. Liang and Y. Hong: Generalized Nash equilibrium seeking strategy for distributed nonsmooth multi-cluster game. Automatica 103 (2019), 20-26.   DOI:10.1016/j.automatica.2019.01.025
  49. X. Zeng, L. Dou and J. Chen: Accelerated first-order continuous-time algorithm for solving convex-concave bilinear saddle point problem. In: 21st IFAC World Congress, Berlin 2020.   CrossRef
  50. X. Zeng, J. Lei and J. Chen: Dynamical primal-dual accelerated method with applications to network optimization. IEEE Trans. Automat. Control.   DOI:10.1109/TAC.2022.3152720
  51. H. Zhou, X. Zeng and Y. Hong: Adaptive exact penalty design for constrained distributed optimization. IEEE Trans. Automat. Control 64 (2019), 11, 4661-4667.   DOI:10.1109/tac.2019.2902612