Abstract

We investigate a modular convex Nash equilibrium problem involving nonsmooth functions acting on linear mixtures of strategies, as well as smooth coupling functions. An asynchronous block-iterative decomposition method is proposed to solve it.

Author information

Contact details are reproduced from the original publication and may be historical.

Minh N. Bùi

Department of Mathematics, North Carolina State University, Raleigh, U.S.A.

mnbui@ncsu.edu

Patrick L. Combettes

Department of Mathematics, North Carolina State University, Raleigh, U.S.A.

plc@math.ncsu.edu

Keywords

  • Block-iterative algorithm
  • game theory
  • monotone operator
  • Nash equilibrium
  • operator splitting

Mathematics Subject Classification

91A10, 47H05, 49M27, 65K15, 47N10

References

  1. F. Acker, M. A. Prestel: Convergence d’un schéma de minimisation alternée, Ann. Fac. Sci. Toulouse V. Sér. Math. 2 (1980) 1–9.https://doi.org/10.5802/afst.541Google Scholar
  2. S. Alwadani, H. H. Bauschke, X. Wang: Attouch-Théra duality, generalized cycles, and gap vectors, SIAM J. Optimization 31 (2021) 1926–1946.https://doi.org/10.1137/21M1392085Google Scholar
  3. A. Argyriou, R. Foygel, N. Srebro: Sparse prediction with the k-support norm, Proc. Adv. Neural Inform. Process. Syst. Conf. 25 (2012) 1457–1465.Google Scholar
  4. H. Attouch, J. Bolte, P. Redont, A. Soubeyran: Alternating proximal algorithms for weakly coupled convex minimization problems. Applications to dynamical games and PDE’s, J. Convex Analysis 15 (2008) 485–506.https://doi.org/10.68381/jca15035Google Scholar
  5. J.-B. Baillon, P. L. Combettes, R. Cominetti: There is no variational characterization of the cycles in the method of periodic projections, J. Funct. Analysis 262 (2012) 400–408.https://doi.org/10.1016/j.jfa.2011.09.002Google Scholar
  6. H. H. Bauschke, P. L. Combettes: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd ed., Springer, New York (2017).https://doi.org/10.1007/978-3-319-48311-5Google Scholar
  7. A. Bensoussan, J.-L. Lions, R. Temam: Sur les méthodes de décomposition, de décentralisation et de coordination, et applications, Cahier IRIA 11 (1972) 5–189.Google Scholar
  8. E. Börgens, C. Kanzow: ADMM-Type methods for generalized Nash equilibrium problems in Hilbert spaces, SIAM J. Optimization 31 (2021) 377–403.https://doi.org/10.1137/19M1284336Google Scholar
  9. A. Borzì, C. Kanzow: Formulation and numerical solution of Nash equilibrium multiobjective elliptic control problems, SIAM J. Control Optimization 51 (2013) 718–744.https://doi.org/10.1137/120864921Google Scholar
  10. R. I. Boţ, S.-M. Grad, G. Wanka: Maximal monotonicity for the precomposition with a linear operator, SIAM J. Optimization 17 (2007) 1239–1252.https://doi.org/10.1137/050641491Google Scholar
  11. L. M. Briceño-Arias, G. Chierchia, E. Chouzenoux, J.-C. Pesquet: A random block-coordinate Douglas-Rachford splitting method with low computational complexity for binary logistic regression, Comput. Optimization Appl. 72 (2019) 707–726.https://doi.org/10.1007/s10589-019-00060-6Google Scholar
  12. L. M. Briceño-Arias, P. L. Combettes: Convex variational formulation with smooth coupling for multicomponent signal decomposition and recovery, Numer. Math. Theory Methods Appl. 2 (2009) 485–508.https://doi.org/10.4208/nmtma.2009.m9009sGoogle Scholar
  13. L. M. Briceño-Arias, P. L. Combettes: Monotone operator methods for Nash equilibria in non-potential games, in: Computational and Analytical Mathematics, D. Bailey et al. (eds.), Springer, New York (2013) 143–159.https://doi.org/10.1007/978-1-4614-7621-4_9Google Scholar
  14. L. M. Briceño-Arias, P. L. Combettes, J.-C. Pesquet, N. Pustelnik: Proximal algorithms for multicomponent image recovery problems, J. Math. Imaging Vision 41 (2011) 3–22.https://doi.org/10.1007/s10851-010-0243-1Google Scholar
  15. M. N. Bùi, P. L. Combettes: Warped proximal iterations for monotone inclusions, J. Math. Analysis Appl. 491 (2020), art. no. 124315.https://doi.org/10.1016/j.jmaa.2020.124315Google Scholar
  16. M. N. Bùi, P. L. Combettes: Multivariate monotone inclusions in saddle form, Math. Oper. Res., published online 2021-12-21.Google Scholar
  17. G. Cohen: Nash equilibria: Gradient and decomposition algorithms, Large Scale Syst. 12 (1987) 173–184.Google Scholar
  18. P. L. Combettes: Systems of structured monotone inclusions: Duality, algorithms, and applications, SIAM J. Optimization 23 (2013) 2420–2447.https://doi.org/10.1137/130904160Google Scholar
  19. P. L. Combettes, J. Eckstein: Asynchronous block-iterative primal-dual decomposition methods for monotone inclusions, Math. Program. B168 (2018) 645–672.https://doi.org/10.1007/s10107-016-1044-0Google Scholar
  20. P. L. Combettes, J.-C. Pesquet: Fixed point strategies in data science, IEEE Trans. Signal Processing 69 (2021) 3878–3905.https://doi.org/10.1109/TSP.2021.3069677Google Scholar
  21. R. Cominetti, F. Facchinei, J. B. Lasserre: Modern Optimization Modelling Techniques, Birkhäuser, Basel (2012).https://doi.org/10.1007/978-3-0348-0291-8Google Scholar
  22. J. Darbon, T. Meng: On decomposition models in imaging sciences and multi-time Hamilton-Jacobi partial differential equations, SIAM J. Imaging Sci. 13 (2020) 971–1014.https://doi.org/10.1137/19M1266332Google Scholar
  23. I. Ekeland, R. Temam: Analyse Convexe et Problèmes Variationnels, Dunod, Paris (1974); English translation: Convex Analysis and Variational Problems, SIAM, Philadelphia (1999).Google Scholar
  24. F. Facchinei, A. Fischer, V. Piccialli: On generalized Nash games and variational inequalities, Oper. Res. Lett. 35 (2007) 159–164.https://doi.org/10.1016/j.orl.2006.03.004Google Scholar
  25. P. Gautam, D. R. Sahu, A. Dixit, T. Som: Forward-backward-half forward dynamical systems for monotone inclusion problems with application to v-GNE, J. Optimization Theory Appl. 190 (2021) 491–523.https://doi.org/10.1007/s10957-021-01891-2Google Scholar
  26. A. Habbal, M. Kallel: Neumann-Dirichlet Nash strategies for the solution of elliptic Cauchy problems, SIAM J. Control Optimization 51 (2013) 4066–4083.https://doi.org/10.1137/120869808Google Scholar
  27. Y. He, R. D. C. Monteiro: Accelerating block-decomposition first-order methods for solving composite saddle-point and two-player Nash equilibrium problems, SIAM J. Optimization 25 (2015) 2182–2211.https://doi.org/10.1137/130943649Google Scholar
  28. A. von Heusinger, C. Kanzow: Relaxation methods for generalized Nash equilibrium problems with inexact line search, J. Optimization Theory Appl. 143 (2009) 159–183.https://doi.org/10.1007/s10957-009-9553-0Google Scholar
  29. C. Kanzow, V. Karl, D. Steck, D. Wachsmuth: The multiplier-penalty method for generalized Nash equilibrium problems in Banach spaces, SIAM J. Optimization 29 (2019) 767–793.https://doi.org/10.1137/17M114114XGoogle Scholar
  30. J. F. Nash, Jr.: Equilibrium points in n-person games, Proc. Nat. Acad. Sci. USA 36 (1950) 48–49.https://doi.org/10.1073/pnas.36.1.48Google Scholar
  31. J. Nash: Non-cooperative games, Ann. Math. 54 (1951) 286–295.https://doi.org/10.2307/1969529Google Scholar
  32. A. Nemirovski: Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems, SIAM J. Optimization 15 (2004) 229–251.https://doi.org/10.1137/S1052623403425629Google Scholar
  33. R. T. Rockafellar: Monotone operators associated with saddle-functions and minimax problems, in: Nonlinear Functional Analysis, Part 1, F. E. Browder (ed.), American Mathematical Society, Providence (1970) 241–250.https://doi.org/10.1090/pspum/018.1/0285942Google Scholar
  34. R. T. Rockafellar: Saddle-points and convex analysis, in: Differential Games and Related Topics, H. W. Kuhn and G. P. Szegö (eds.), North-Holland, Amsterdam (1971) 109–127.Google Scholar
  35. R. T. Rockafellar: Monotone relations and network equilibrium, in: Variational Inequalities and Network Equilibrium Problems, F. Giannessi and A. Maugeri (eds.), Plenum Press, New York (1995) 271–288.https://doi.org/10.1007/978-1-4899-1358-6_21Google Scholar
  36. R. T. Rockafellar: Applications of convex variational analysis to Nash equilibrium, Proc. 7th Int. Conf. on Nonlinear Analysis and Convex Analysis Vol. II, Busan, South Korea (2011) 173–183.Google Scholar
  37. S. Sorin, C. Wan: Finite composite games: Equilibria and dynamics, J. Dyn. Games 3 (2016) 101–120.https://doi.org/10.3934/jdg.2016005Google Scholar
  38. K. K. Thekumparampil, P. Jain, P. Netrapalli, S. Oh: Efficient algorithms for smooth minimax optimization, Proc. 32nd Adv. Neural Inform. Process. Syst. Conf., Vancouver (2019).Google Scholar
  39. T. Yoon, E. K. Ryu: Accelerated algorithms for smooth convex-concave minimax problems with O(1/k 2) rate on squared gradient norm, Proc. 38th Int. Conf. Machine Learn. (2021) 12098–12109.Google Scholar

Suggested citation

M. N. Bùi, P. L. Combettes. “Analysis and Numerical Solution of a Modular Convex Nash Equilibrium Problem.” Journal of Convex Analysis 29 (2022), No. 4, 1007–1021. https://doi.org/10.68381/jca29057

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2022. Rights now held by Banach Press.