REGULARIZED JACOBI-TYPE ADMM-METHOD FOR FINDING SOLUTIONS TO GENERALIZED NASH EQUILIBRIUM PROBLEM
Abstract
In this paper, we extended the well-known alternating direction method of multipliers (ADMM) for optimization problems to generalized Nash equilibrium problems (GNEP) with shared constraints. We developed an ADMM-type algorithm with fixed regularization to tackle the problem (GNEP) where an upper estimate for the operator norm is not known and then we apply a multiplier-penalty in order to get rid of the joint constraints. We equipped the Hilbert space with an appropriate weighted scalar product and it turns out to be weakly convergent under a lipschitz and monotonicity assumption. A proximal term is then added to improve the convergence properties. Furthermore, a comparative analysis of quasi-variational inequality method, interior point method, penalty method and the proposed method are discussed.
References
Benenati, E., Ananduta, W., & Grammatico, S. (2023). Optimal selection and tracking of generalized Nash equilibria in monotone games. IEEE Transactions on Automatic Control. DOI: https://doi.org/10.1109/TAC.2023.3288372
Borgens, E., & Kanzow, C. (2021). ADMM-Type methods for generalized Nash equilibrium problems in Hilbert spaces. SIAM Journal on Optimization, 31(1), 377-403.12. DOI: https://doi.org/10.1137/19M1284336
Braouezec, Y., & Kiani, K. (2023). A generalized Nash equilibrium problem arising in banking regulation: An existence result with Tarski's theorem. Operations Research Letters, 51 (1), 105-110. DOI: https://doi.org/10.1016/j.orl.2022.12.003
Boyd, N. T., Gabriel, S. A., Rest, G., & Dumm, T. (2023). Generalized Nash equilibrium models for asymmetric, non-cooperative games on line graphs: Application to water resource systems. Computers & Operations Research, 154, 106194. DOI: https://doi.org/10.1016/j.cor.2023.106194
Cai, X., Nan, X., & Gao, B. (2023). Distributed adaptive generalized Nash equilibrium seeking algorithm with event-triggered communication. Asian Journal of Control, 25 (3), 2239-2248. DOI: https://doi.org/10.1002/asjc.2904
Castellani, M., & Giuli, M. (2023). A Modified Michael’s Selection Theorem with Application to Generalized Nash Equilibrium Problem. Journal of Optimization Theory and Applications, 196 (1), 199-211. DOI: https://doi.org/10.1007/s10957-022-02090-3
Chen, J., Qian, S., & Qin, S. (2023). An adaptive generalized Nash equilibrium seeking algorithm under high-dimensional input dead-zone. Information Sciences, 626, 354-369. DOI: https://doi.org/10.1016/j.ins.2023.01.056
Deng, Z., & Zhao, Y. (2023). Generalized Nash equilibrium seeking algorithm design for distributed multi-cluster games. Journal of the Franklin Institute, 360 (1), 154-175. DOI: https://doi.org/10.1016/j.jfranklin.2022.11.022
Gahururu, D. B., Hintermüller, M., & Surowiec, T. M. (2023). Risk-neutral PDE-constrained generalized Nash equilibrium problems. Mathematical Programming, 198 (2), 1287-1337. DOI: https://doi.org/10.1007/s10107-022-01800-z
Jordan, M. I., Lin, T., & Zampetakis, M. (2023). First-order algorithms for nonlinear generalized nash equilibrium problems. Journal of Machine Learning Research, 24(38), 1-46.
Laine, F., Fridovich-Keil, D., Chiu, C. Y., & Tomlin, C. (2023). The computation of approximate generalized feedback nash equilibria. SIAM Journal on Optimization, 33(1), 294-318. DOI: https://doi.org/10.1137/21M142530X
Lee, K., & Tang, X. (2023). On the polyhedral homotopy method for solving generalized Nash equilibrium problems of polynomials. Journal of Scientific Computing, 95 (1), 13. DOI: https://doi.org/10.1007/s10915-023-02138-0
Liu, F., Yu, J., Hua, Y., Dong, X., Li, Q., & Ren, Z. (2023). Dynamic generalized Nash equilibrium seeking for N-coalition noncooperative games. Automatica, 147, 110746. DOI: https://doi.org/10.1016/j.automatica.2022.110746
Meng, Q., Nian, X., Chen, Y., & Chen, Z. (2023). Neuro-adaptive control for searching generalized Nash equilibrium of multi-agent games: A two-stage design approach. Neuro computing, 530, 69-80. DOI: https://doi.org/10.1016/j.neucom.2023.01.077
Nash Jr, J. F. (1950). Non-cooperative games. ProQuest LLC. Ann Arbor, MI, 215.
Nie, J., Tang, X., & Zhong, S. (2023). Rational generalized Nash equilibrium problems. SIAM Journal on Optimization, 33(3), 1587-1620. DOI: https://doi.org/10.1137/21M1456285
Shi, L., & He, W. (2023). Generalized Nash equilibrium seeking for networked noncooperative games with a dynamic event-triggered mechanism. Applied Mathematical Modelling, 118, 39-52. DOI: https://doi.org/10.1016/j.apm.2023.01.012
Shehu, Y., Iyiola, O. S., & Akaligwo, E. (2019). Modified inertial methods for finding common solutions to variational inequality problems. Fixed Point Theory, 20(2), 683-702. DOI: https://doi.org/10.24193/fpt-ro.2019.2.45
Singh, A., & Ghosh, D. (2023). A globally convergent improved BFGS method for generalized Nash equilibrium problems. SeMA Journal, 1-27. DOI: https://doi.org/10.1007/s40324-023-00323-7
Zhu, E. L., & Borrelli, F. (2023, May). A sequential quadratic programming approach to the solution of open-loop generalized nash equilibria. In 2023 IEEE International Conference on Robotics and Automation (ICRA) (pp. 3211-3217). DOI: https://doi.org/10.1109/ICRA48891.2023.10160799
Copyright (c) 2023 FUDMA JOURNAL OF SCIENCES
This work is licensed under a Creative Commons Attribution 4.0 International License.
FUDMA Journal of Sciences
