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

Zeng, Xianlin ; Dou, Lihua ; Cui, Jinqiang

Kybernetika, Tome 59 (2023) no. 3, pp. 418-436

Abstract (VO)

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.

Détail

DOI : 10.14736/kyb-2023-3-0418

Classification : 37N40, 91A10, 93A14
Keywords: two-subnetwork zero-sum game; distributed accelerated algorithm; Nash equilibrium learning; nonsmooth function; continuous-time algorithm

Bibliographie

[1] Alkousa, M. S., Gasnikov, A. V., Dvinskikh, D. M., Kovalev, D. A., Stonyakin, F. S.: Accelerated methods for saddle-point problem. Comput. Math. and Math. Phys. 60 (2020), 1787-1787. | DOI | MR

[2] Attouch, H., Chbani, Z., Riahi, H.: Rate of convergence of the Nesterov accelerated gradient method in the subcritical case $\alpha\leq 3$. ESAIM: COCV 25 (2019), 2. | DOI | MR

[3] Aubin, J. P., Cellina, A.: Differential Inclusions. Springer-Verlag, Berlin 1984. | MR

[4] Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 21 (2009), 1, 183-202. | DOI | MR

[5] Bertsekas, D. P.: Convex Optimization Algorithms. Athena Scientific, Belmont 2015. | MR

[6] Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40 (2011), 1, 120-145. | DOI | MR

[7] Chen, Y., Lan, G., Ouyang, Y.: Optimal primal-dual methods for a class of saddle point problems. SIAM J. Control Optim. 24 (2014), 4, 1779-1814. | DOI | MR

[8] Chen, S., Liang, S.: Distributed optimization for multi-agent system over unbalanced graphs with linear convergence rate. Kybernetika 56 (2020), 3, 559-577. | DOI | MR

[9] Chen, Z., Liang, S.: Distributed aggregative optimization with quantized communication. Kybernetika 58 (2022), 1, 123-144. | DOI | MR

[10] Chen, G., Ming, Y., Hong, Y., Yi, P.: Distributed algorithm for $\varepsilon$-generalized Nash equilibria with uncertain coupled constraints. Automatica 123 (2021), 109313. | DOI | MR

[11] Chen, J., Sun, J., Wang, G.: From unmanned systems to autonomous intelligent systems. Engineering 8 (2022), 1-5. | DOI

[12] Cherukuri, A., Gharesifard, B., Cortés, J.: Saddle-point dynamics: Conditions for asymptotic stability of saddle points. SIAM J. Control Optim. 55 (2017), 1, 486-511. | DOI | MR

[13] Deng, Z.: Distributed generalized Nash equilibrium seeking algorithm for nonsmooth aggregative games. Automatica 132 (2021), 109794. | DOI | MR

[14] Deng, Z.: Distributed Nash equilibrium seeking for aggregative games with second-order nonlinear players. Automatica 135 (2022), 109980. | DOI | MR

[15] Gharesifard, B., Cortés, J.: Distributed convergence to Nash equilibria in two-network zero-sum games. Automatica 49 (2013), 6, 1683-1692. | DOI | MR

[16] Goebel, R.: Stability and robustness for saddle-point dynamics through monotone mappings. Syst. Control. Lett. 108 (2017), 16-22. | DOI | MR

[17] He, X., Hu, R., Fang, Y. P.: Convergence rates of inertial primal-dual dynamical methods for separable convex optimization problems. SIAM J. Control Optim. 59 (2021), 5, 3278-3301. | DOI | MR

[18] Huang, S., Lei, J., Hong, Y.: A linearly convergent distributed nash equilibrium seeking algorithm for aggregative games. IEEE Trans. Automat. Control , 2022. | DOI | MR

[19] Huang, S., Lei, J., Hong, Y., Shanbhag, U. V.: No-regret distributed learning in two-network zero-sum games. In: 60th IEEE Conference on Decision and Control (CDC), 2021, pp. 924-929.

[20] Ibaraki, T., Katoh, N.: Resource Allocation Problems: Algorithmic Approaches. MIT Press, Cambridge 1988. | MR

[21] Khan, S., Tufail, M., Khan, M. T., Khan, Z. A., Iqbal, J., Wasim, A.: 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.

[22] Kia, S. S., Cortés, J., Martínez, S.: Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication. Automatica 55 (2015), 254-264. | DOI | MR

[23] Li, P., Hu, J., Qiu, L., Zhao, Y., Ghosh, B. K.: A distributed economic dispatch strategy for power-water networks. IEEE Trans. Control. Netw. Syst9 (2022), 1, 356-366. | DOI | MR

[24] Lou, Y., Hong, Y., Xie, L., Shi, G., Johansson, K. H.: Nash equilibrium computation in subnetwork zero-sum games with switching communications. IEEE Trans. Automat. Control 61 (2016), 10, 2920-2935. | DOI | MR

[25] Mo, L., Yu, Y., Ren, G., Yuan, X.: Constrained consensus of continuous-time heterogeneous multi-agent networks with nonconvex constraints and delays. J. Syst. Sci. Complex 35 (2022), 105-122. | DOI | MR

[26] Nesterov, Y.: A method of solving a convex programming problem with convergence rate $O(1/k^2)$. Soviet Math. Doklady 27 (1983), 372-376. | MR

[27] Nesterov, Y.: Smooth minimization of non-smooth functions. Math Program. 103 (2005), 1, 127-152. | DOI | MR

[28] Paoli, L. A.: 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 | MR

[29] Peng, Z., Luo, R., Hu, J., Shi, K., Ghosh, B. K.: 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. | DOI

[30] Shi, B., Du, S. S., Jordan, M. I., Su, W. J.: Understanding the acceleration phenomenon via high-resolution differential equations. Math. Program. 195 (2022), 79-148. | DOI | MR

[31] Su, W., Boyd, S., Candes, E. J.: A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights. Adv. Neural Inf. Process. Syst. 3 (2015), 1, 2510-2518. | MR

[32] Vassilis, A., Jean-Francois, A., Charles, D.: The differential inclusion modeling FISTA algorithm and optimality of convergence $b\leq 3$. SIAM J. Control. Optim. 29 (2018), 1, 551-574. | DOI | MR

[33] Wang, Q., Chen, J., Xin, B., Zeng, X.: Distributed optimal consensus for Euler-Lagrange systems based on event-triggered control. IEEE Trans. Syst. Man Cybern. Syst. 51 (2021), 7, 4588-4598. | DOI

[34] Wang, M., Li, L., Dai, Q., Shi, F.: Resource allocation based on DEA and non-cooperative game. J. Syst. Sci. Complex 34 (2022), 2231-2249. | DOI

[35] Wang, Y., Lin, P., Qin, H.: Distributed classification learning based on nonlinear vector support machines for switching networks. Kybernetika 53 (2017), 4, 595-611. | DOI | MR

[36] Wang, D., Wang, Z., Wu, Z., Wang, W.: 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. | MR

[37] Wibisono, A., Wilson, A. C., Jordan, M. I.: A variational perspective on accelerated methods in optimization. Proc. Natl. Acad. Sci. 113 (2016), 47, 7351-7358. | DOI | MR

[38] Wu, C., Fang, H., Yang, Q., Zeng, X., Wei, Y., Chen, J.: Distributed cooperative control of redundant mobile manipulators with safety constraints. IEEE Trans. Cybernet. 53 (2023), 2, 1195-1207. | DOI

[39] Wu, Y., Liang, Q., Zhao, Y., Hu, J., Xiang, L.: Distributed estimation based output consensus control of heterogeneous leader-follower systems with antagonistic interactions. Sci. China Inf. Sci. 66 (2023), 139204. | DOI

[40] Wu, Y., Liang, Q., Zhao, Y., Hu, J., Xiang, L.: Effective distributed algorithm for solving linear matrix equations. Sci. China Inf. Sci. 66 (2023), 189202. | DOI

[41] Xie, S., Wang, L., Nazari, M. H., Yin, G., Li, G.: Distributed optimization with markovian switching targets and stochastic observation noises with applications to dc microgrids. Sci. China Inf. Sci. 65 (2022), 222205. | DOI | MR

[42] Xu, Y.: Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming. SIAM J. Optim. 27 (2018), 3, 1459-1484. | DOI | MR

[43] Xu, Y., Zhang, S.: Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization. Comput. Optim. Appl. 70 (2018), 91-128. | DOI | MR

[44] Yang, R., Liu, L., Feng, G.: An overview of recent advances in distributed coordination of multi-agent systems. Unmanned Syst. 2022. | DOI

[45] Yang, S., Wang, J., Liu, Q.: Cooperative-competitive multiagent systems for distributed minimax optimization subject to bounded constraints. IEEE Trans. Automat. Control 64 (2019), 4, 358-1372. | DOI | MR

[46] Ye, M., Hu, G., Xu, S.: An extremum seeking-based approach for Nash equilibrium seeking in {$N$}-cluster noncooperative games. Automatica 114 (2020), 108815. | DOI | MR

[47] Ye, M., Yin, J., Yin, L.: Distributed Nash equilibrium seeking for games in second-order systems without velocity measurement. IEEE Trans. Automat. Control. | DOI | MR

[48] Zeng, X., Chen, J., Liang, S., Hong, Y.: Generalized Nash equilibrium seeking strategy for distributed nonsmooth multi-cluster game. Automatica 103 (2019), 20-26. | DOI | MR

[49] Zeng, X., Dou, L., Chen, J.: Accelerated first-order continuous-time algorithm for solving convex-concave bilinear saddle point problem. In: 21st IFAC World Congress, Berlin 2020.

[50] Zeng, X., Lei, J., Chen, J.: Dynamical primal-dual accelerated method with applications to network optimization. IEEE Trans. Automat. Control. | DOI

[51] Zhou, H., Zeng, X., Hong, Y.: Adaptive exact penalty design for constrained distributed optimization. IEEE Trans. Automat. Control 64 (2019), 11, 4661-4667. | DOI | MR