A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Volume 11 Issue 7
Jul.  2024

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 15.3, Top 1 (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77, TOP 5
Turn off MathJax
Article Contents
W. He and  Y. Wang,  “Distributed optimal variational GNE seeking in merely monotone games,” IEEE/CAA J. Autom. Sinica, vol. 11, no. 7, pp. 1621–1630, Jul. 2024. doi: 10.1109/JAS.2024.124284
Citation: W. He and  Y. Wang,  “Distributed optimal variational GNE seeking in merely monotone games,” IEEE/CAA J. Autom. Sinica, vol. 11, no. 7, pp. 1621–1630, Jul. 2024. doi: 10.1109/JAS.2024.124284

Distributed Optimal Variational GNE Seeking in Merely Monotone Games

doi: 10.1109/JAS.2024.124284
Funds:  This work was supported by the National Natural Science Foundation of China (Basic Science Center Program) (61988101), the Joint Fund of Ministry of Education for Equipment Pre-research (8091B022234), Shanghai International Science and Technology Cooperation Program (21550712400), Shanghai Pilot Program for Basic Research (22TQ1400100-3), the Fundamental Research Funds for the Central Universities, and Shanghai Artifcial Intelligence Laboratory
More Information
  • In this paper, the optimal variational generalized Nash equilibrium (v-GNE) seeking problem in merely monotone games with linearly coupled cost functions is investigated, in which the feasible strategy domain of each agent is coupled through an affine constraint. A distributed algorithm based on the hybrid steepest descent method is first proposed to seek the optimal v-GNE. Then, an accelerated algorithm with relaxation is proposed and analyzed, which has the potential to further improve the convergence speed to the optimal v-GNE. Some sufficient conditions in both algorithms are obtained to ensure the global convergence towards the optimal v-GNE. To illustrate the performance of the algorithms, numerical simulation is conducted based on a networked Nash-Cournot game with bounded market capacities.

     

  • loading
  • [1]
    X. Na and D. J. Cole, “Modelling of a human driver s interaction with vehicle automated steering using cooperative game theory,” IEEE/CAA J. Autom. Sinica, vol. 6, no. 5, pp. 1095–1107, Sept. 2019. doi: 10.1109/JAS.2019.1911675
    [2]
    M. Ye and G. Hu, “Game design and analysis for price-based demand response: An aggregate game approach,” IEEE Trans. Cybernetics, vol. 47, no. 3, pp. 720–730, Mar. 2017. doi: 10.1109/TCYB.2016.2524452
    [3]
    B. Li, Q. Yang, and I. Kamwa, “A novel Stackelberg-game-based energy storage sharing scheme under demand charge,” IEEE/CAA J. Autom. Sinica, vol. 10, no. 2, pp. 462–473, Feb. 2023. doi: 10.1109/JAS.2023.123216
    [4]
    N. Li, L. Chen, and M. A. Dahleh, “Demand response using linear supply function bidding,” IEEE Trans. Smart Grid, vol. 6, no. 4, pp. 1827–1838, Jul. 2015. doi: 10.1109/TSG.2015.2410131
    [5]
    D. Paccagnan, B. Gentile, F. Parise, M. Kamgarpour, and J. Lygeros, “Distributed computation of generalized Nash equilibria in quadratic aggregative games with affine coupling constraints,” in Proc. 55th IEEE Decision and Control, Las Vegas, USA, Dec. 2016, pp. 6123–6128.
    [6]
    J. Wang, Y. Hong, J. Wang, J. Xu, Y. Tang, Q.-L. Han, and J. Kurths, “Cooperative and competitive multi-agent systems: From optimization to games,” IEEE/CAA J. Autom. Sinica, vol. 9, no. 5, Apr. 2022.
    [7]
    S. Le Cleac’h, M. Schwager, and Z. Manchester, “ALGAMES: A fast augmented Lagrangian solver for constrained dynamic games,” Autonomous Robots, vol. 46, no. 1, pp. 201–215, Jan. 2022. doi: 10.1007/s10514-021-10024-7
    [8]
    X. Chen, E. Dall’Anese, C. Zhao, and N. Li, “Aggregate power flexibility in unbalanced distribution systems,” IEEE Trans. Smart Grid, vol. 11, no. 1, pp. 258–269, Jan. 2020. doi: 10.1109/TSG.2019.2920991
    [9]
    C. Li, X. Yu, W. Yu, G. Chen, and J. Wang, “Efficient computation for sparse load shifting in demand side management,” IEEE Trans. Smart Grid, vol. 8, no. 1, pp. 250–261, Jan. 2017. doi: 10.1109/TSG.2016.2521377
    [10]
    H. Yin, U. V. Shanbhag, and P. G. Mehta, “Nash equilibrium problems with scaled congestion costs and shared constraints,” IEEE Trans. Autom. Control, vol. 56, no. 7, pp. 1702–1708, Jul. 2011. doi: 10.1109/TAC.2011.2137590
    [11]
    J. Lei, U. V. Shanbhag, and J. Chen, “Distributed computation of Nash equilibria for monotone aggregative games via iterative regularization,” in Proc. 59th IEEE Decision and Control, Jeju, Korea (South), Dec. 2020, pp. 2285–2290.
    [12]
    E. Benenati, W. Ananduta, and S. Grammatico, “On the optimal selection of generalized Nash equilibria in linearly coupled aggregative games,” in Proc. 61st IEEE Decision and Control. Cancun, Mexico, Dec. 2022, pp. 6389–6394.
    [13]
    M. Ye, Q.-L. Han, L. Ding, S. Xu, and G. Jia, “Distributed Nash equilibrium seeking strategies under quantized communication,” IEEE/CAA J. Autom. Sinica, vol. 11, no. 1, pp. 103–112, Jan. 2024.
    [14]
    Y. Zhu, W. Yu, G. Wen, and G. Chen, “Distributed Nash equilibrium seeking in an aggregative game on a directed graph,” IEEE Trans. Autom. Control, vol. 66, no. 6, pp. 2746–2753, Jun. 2021. doi: 10.1109/TAC.2020.3008113
    [15]
    G. Chen, Y. Ming, Y. Hong, and P. Yi, “Distributed algorithm for ε-generalized Nash equilibria with uncertain coupled constraints,” Automatica, vol. 123, p. 109313, Jan. 2021. doi: 10.1016/j.automatica.2020.109313
    [16]
    G. Belgioioso, P. Yi, S. Grammatico, and L. Pavel, “Distributed generalized Nash equilibrium seeking: An operator-theoretic perspective,” IEEE Control Systems Magazine, vol. 42, no. 4, pp. 87–102, Aug. 2022. doi: 10.1109/MCS.2022.3171480
    [17]
    P. Yi and L. Pavel, “An operator splitting approach for distributed generalized Nash equilibria computation,” Automatica, vol. 102, pp. 111–121, Apr. 2019. doi: 10.1016/j.automatica.2019.01.008
    [18]
    S. Liang, P. Yi, and Y. Hong, “Distributed Nash equilibrium seeking for aggregative games with coupled constraints,” Automatica, vol. 85, pp. 179–185, Nov. 2017. doi: 10.1016/j.automatica.2017.07.064
    [19]
    M. Bianchi, G. Belgioioso, and S. Grammatico, “Fast generalized Nash equilibrium seeking under partial-decision information,” Automatica, vol. 136, p. 110080, Feb. 2022. doi: 10.1016/j.automatica.2021.110080
    [20]
    L. Shi and W. He, “Generalized Nash equilibrium seeking for networked noncooperative games with a dynamic event-triggered mechanism,” Applied Mathematical Modelling, vol. 118, pp. 39–52, Jun. 2023. doi: 10.1016/j.apm.2023.01.012
    [21]
    D. Gadjov and L. Pavel, “Single-timescale distributed GNE seeking for aggregative games over networks via forward backward operator splitting,” IEEE Trans. Autom. Control, vol. 66, no. 7, pp. 3259–3266, Jul. 2021. doi: 10.1109/TAC.2020.3015354
    [22]
    E. Benenati, W. Ananduta, and S. Grammatico, “Optimal selection and tracking of generalized Nash equilibria in monotone games,” IEEE Trans. Autom. Control, vol. 68, no. 12, pp. 7644–7659, Dec. 2023. doi: 10.1109/TAC.2023.3288372
    [23]
    G. Belgioioso and S. Grammatico, “Semi-decentralized generalized Nash equilibrium seeking in monotone aggregative games,” IEEE Trans. Autom. Control, vol. 68, no. 1, pp. 140–155, Jan. 2023. doi: 10.1109/TAC.2021.3135360
    [24]
    G. Belgioioso and S. Grammatico, “A distributed proximal-point algorithm for Nash equilibrium seeking in generalized potential games with linearly coupled cost functions,” in Proc. 18th European Control Conf., Naples, Italy, Aug. 2019, pp. 1–6.
    [25]
    B. Franci, M. Staudigl, and S. Grammatico, “Distributed forward-backward (half) forward algorithms for generalized Nash equilibrium seeking,” in Proc. 19th European Control Conf., St. Petersburg, Russia, Jul. 2020, pp. 1274–1279.
    [26]
    F. Facchinei, A. Fischer, and V. Piccialli, “On generalized Nash games and variational inequalities,” Operations Research Letters, vol. 35, no. 2, pp. 159–164, Mar. 2007. doi: 10.1016/j.orl.2006.03.004
    [27]
    M. Ye, Q.-L. Han, L. Ding, and S. Xu, “Distributed Nash equilibrium seeking in games with partial decision information: A survey,” Proc. the IEEE, vol. 111, no. 2, pp. 140–157, 2023. doi: 10.1109/JPROC.2023.3234687
    [28]
    C.-K. Yu, M. van der Schaar, and A. H. Sayed, “Distributed learning for stochastic generalized Nash equilibrium problems,” IEEE Trans. Signal Processing, vol. 65, no. 15, pp. 3893–3908, Apr. 2017. doi: 10.1109/TSP.2017.2695451
    [29]
    M. Zhu and E. Frazzoli, “Distributed robust adaptive equilibrium computation for generalized convex games,” Automatica, vol. 63, pp. 82–91, Jan. 2016. doi: 10.1016/j.automatica.2015.10.012
    [30]
    A. Cegielski, A. Gibali, S. Reich, and R. Zalas, “An algorithm for solving the variational inequality problem over the fixed point set of a quasi-nonexpansive operator in euclidean space,” Numerical Functional Analysis and Optimization, vol. 34, no. 10, pp. 1067–1096, Aug. 2013. doi: 10.1080/01630563.2013.771656
    [31]
    H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2011, vol. 408.
    [32]
    H. H. Bauschke and J. M. Borwein, “On projection algorithms for solving convex feasibility problems,” SIAM Review, vol. 38, no. 3, pp. 367–426, Jan. 1996. doi: 10.1137/S0036144593251710
    [33]
    R. A. Horn and C. R. Johnson, Matrix Analysis. Cambridge University press, 2012.
    [34]
    N. Ogura and I. Yamada, “Nonstrictly convex minimization over the bounded fixed point set of a nonexpansive mapping,” Numerical Functional Analysis and Optimization, vol. 24, no. 1–2, pp. 129–135, Aug. 2003. doi: 10.1081/NFA-120020250
    [35]
    F. Iutzeler and J. M. Hendrickx, “A generic online acceleration scheme for optimization algorithms via relaxation and inertia,” Optimization Methods and Software, vol. 34, no. 2, pp. 383–405, Nov. 2019. doi: 10.1080/10556788.2017.1396601
    [36]
    I. Yamada, N. Ogura, and N. Shirakawa, “A numerically robust hybrid steepest descent method for the convexly constrained generalized inverse problems,” Contemporary Mathematics, vol. 313, pp. 269–305, Jan. 2002.

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(7)

    Article Metrics

    Article views (164) PDF downloads(36) Cited by()

    Highlights

    • An algorithm is proposed to seek the optimal GNE in a distributed manner
    • Each agent adjusts its update step size solely based on its local information
    • An algorithm, augmented with relaxation acceleration scheme, is also proposed to expedite the convergence speed
    • when the optimal relaxation parameter is difficult to obtain. The time-varying relaxation parameter is adopted to achieve a trade-off in acceleration effects

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return