Article
Full entry |
PDF
(0.5 MB)
Feedback
PDF
(0.5 MB)
Feedback
Keywords:
two-subnetwork zero-sum game; distributed accelerated algorithm; Nash equilibrium learning; nonsmooth function; continuous-time algorithm
two-subnetwork zero-sum game; distributed accelerated algorithm; Nash equilibrium learning; nonsmooth function; continuous-time algorithm
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.
References:
[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 4184700
[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 3943364
[3] Aubin, J. P., Cellina, A.: Differential Inclusions. Springer-Verlag, Berlin 1984. MR 0755330
[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 2486527
[5] Bertsekas, D. P.: Convex Optimization Algorithms. Athena Scientific, Belmont 2015. MR 3558548
[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 2782122
[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 3272627
[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 4131743
[9] Chen, Z., Liang, S.: Distributed aggregative optimization with quantized communication. Kybernetika 58 (2022), 1, 123-144. DOI | MR 4405950
[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 4164533
[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 3612173
[13] Deng, Z.: Distributed generalized Nash equilibrium seeking algorithm for nonsmooth aggregative games. Automatica 132 (2021), 109794. DOI | MR 4283791
[14] Deng, Z.: Distributed Nash equilibrium seeking for aggregative games with second-order nonlinear players. Automatica 135 (2022), 109980. DOI | MR 4335720
[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 3049216
[16] Goebel, R.: Stability and robustness for saddle-point dynamics through monotone mappings. Syst. Control. Lett. 108 (2017), 16-22. DOI | MR 3709078
[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 4315476
[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 4557578
[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 0937050
[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 3336675
[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 4450544
[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 3554031
[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 4376657
[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
[27] Nesterov, Y.: Smooth minimization of non-smooth functions. Math Program. 103 (2005), 1, 127-152. DOI | MR 2166537
[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 1771507
[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 10.1109/TCSI.2022.3177407
[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 4499055
[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
[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 3766971
[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 3730254
[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
[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 3582442
[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 10.1007/s11432-020-3191-x
[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 10.1007/s11432-021-3485-0
[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 10.1007/s11432-022-3582-5 | MR 4510580
[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 3679324
[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 3780462
[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 3936416
[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 4053524
[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 4504365
[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 3908257
[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 4030790
Search
Partner of
