| Title:
|
Distributed accelerated Nash equilibrium learning for two-subnetwork zero-sum game with bilinear coupling (English) |
| Author:
|
Zeng, Xianlin |
| Author:
|
Dou, Lihua |
| Author:
|
Cui, Jinqiang |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
59 |
| Issue:
|
3 |
| Year:
|
2023 |
| Pages:
|
418-436 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
two-subnetwork zero-sum game |
| Keyword:
|
distributed accelerated algorithm |
| Keyword:
|
Nash equilibrium learning |
| Keyword:
|
nonsmooth function |
| Keyword:
|
continuous-time algorithm |
| MSC:
|
37N40 |
| MSC:
|
91A10 |
| MSC:
|
93A14 |
| DOI:
|
10.14736/kyb-2023-3-0418 |
| . |
| Date available:
|
2023-07-12T07:22:48Z |
| Last updated:
|
2023-07-12 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/151723 |
| . |
| Reference:
|
[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. MR 4184700, |
| Reference:
|
[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. MR 3943364, |
| Reference:
|
[3] Aubin, J. P., Cellina, A.: Differential Inclusions..Springer-Verlag, Berlin 1984. MR 0755330 |
| Reference:
|
[4] Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems..SIAM J. Imaging Sci. 21 (2009), 1, 183-202. MR 2486527, |
| Reference:
|
[5] Bertsekas, D. P.: Convex Optimization Algorithms..Athena Scientific, Belmont 2015. MR 3558548 |
| Reference:
|
[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. MR 2782122, |
| Reference:
|
[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. MR 3272627, |
| Reference:
|
[8] Chen, S., Liang, S.: Distributed optimization for multi-agent system over unbalanced graphs with linear convergence rate..Kybernetika 56 (2020), 3, 559-577. MR 4131743, |
| Reference:
|
[9] Chen, Z., Liang, S.: Distributed aggregative optimization with quantized communication..Kybernetika 58 (2022), 1, 123-144. MR 4405950, |
| Reference:
|
[10] Chen, G., Ming, Y., Hong, Y., Yi, P.: Distributed algorithm for $\varepsilon$-generalized Nash equilibria with uncertain coupled constraints..Automatica 123 (2021), 109313. MR 4164533, |
| Reference:
|
[11] Chen, J., Sun, J., Wang, G.: From unmanned systems to autonomous intelligent systems..Engineering 8 (2022), 1-5. |
| Reference:
|
[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. MR 3612173, |
| Reference:
|
[13] Deng, Z.: Distributed generalized Nash equilibrium seeking algorithm for nonsmooth aggregative games..Automatica 132 (2021), 109794. MR 4283791, |
| Reference:
|
[14] Deng, Z.: Distributed Nash equilibrium seeking for aggregative games with second-order nonlinear players..Automatica 135 (2022), 109980. MR 4335720, |
| Reference:
|
[15] Gharesifard, B., Cortés, J.: Distributed convergence to Nash equilibria in two-network zero-sum games..Automatica 49 (2013), 6, 1683-1692. MR 3049216, |
| Reference:
|
[16] Goebel, R.: Stability and robustness for saddle-point dynamics through monotone mappings..Syst. Control. Lett. 108 (2017), 16-22. MR 3709078, |
| Reference:
|
[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. MR 4315476, |
| Reference:
|
[18] Huang, S., Lei, J., Hong, Y.: A linearly convergent distributed nash equilibrium seeking algorithm for aggregative games..IEEE Trans. Automat. Control , 2022. MR 4557578, |
| Reference:
|
[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. |
| Reference:
|
[20] Ibaraki, T., Katoh, N.: Resource Allocation Problems: Algorithmic Approaches..MIT Press, Cambridge 1988. MR 0937050 |
| Reference:
|
[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. |
| Reference:
|
[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. MR 3336675, |
| Reference:
|
[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. MR 4450544, |
| Reference:
|
[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. MR 3554031, |
| Reference:
|
[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. MR 4376657, |
| Reference:
|
[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 0701288 |
| Reference:
|
[27] Nesterov, Y.: Smooth minimization of non-smooth functions..Math Program. 103 (2005), 1, 127-152. MR 2166537, |
| Reference:
|
[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. MR 1771507, |
| Reference:
|
[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. 10.1109/TCSI.2022.3177407 |
| Reference:
|
[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. MR 4499055, |
| Reference:
|
[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 3555044 |
| Reference:
|
[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. MR 3766971, |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[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. MR 3730254, |
| Reference:
|
[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 4381757 |
| Reference:
|
[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. MR 3582442, |
| Reference:
|
[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. |
| Reference:
|
[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. 10.1007/s11432-020-3191-x |
| Reference:
|
[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. 10.1007/s11432-021-3485-0 |
| Reference:
|
[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. MR 4510580, 10.1007/s11432-022-3582-5 |
| Reference:
|
[42] Xu, Y.: Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming..SIAM J. Optim. 27 (2018), 3, 1459-1484. MR 3679324, |
| Reference:
|
[43] Xu, Y., Zhang, S.: Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization..Comput. Optim. Appl. 70 (2018), 91-128. MR 3780462, |
| Reference:
|
[44] Yang, R., Liu, L., Feng, G.: An overview of recent advances in distributed coordination of multi-agent systems..Unmanned Syst. 2022. |
| Reference:
|
[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. MR 3936416, |
| Reference:
|
[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. MR 4053524, |
| Reference:
|
[47] Ye, M., Yin, J., Yin, L.: Distributed Nash equilibrium seeking for games in second-order systems without velocity measurement..IEEE Trans. Automat. Control. MR 4504365, |
| Reference:
|
[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. MR 3908257, |
| Reference:
|
[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. |
| Reference:
|
[50] Zeng, X., Lei, J., Chen, J.: Dynamical primal-dual accelerated method with applications to network optimization..IEEE Trans. Automat. Control. |
| Reference:
|
[51] Zhou, H., Zeng, X., Hong, Y.: Adaptive exact penalty design for constrained distributed optimization..IEEE Trans. Automat. Control 64 (2019), 11, 4661-4667. MR 4030790, |
| . |
