Abstract

We consider minimization problems with constraints. We show that if the set of constraints is a Riemannian manifold of non positive curvature and the objective function is lower semicontinuous and satisfies the Kurdyka-Lojasiewicz property, then the alternating proximal algorithm in Euclidean space is naturally extended to solve that class of problems. We prove that the sequence generated by our algorithm is well defined and converges to an inertial Nash equilibrium under mild assumptions about the objective function. As an application, we give a welcome result on the difficult problem of "learning how to play Nash" (convergence, convergence in finite time, speed of convergence, constraints in action spaces in the context of "alternating potential games" with inertia).

Author information

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

João Xavier Cruz Neto

Dept. of Mathematics, Federal University of Piauí, Teresina, Brazil

jxavier@ufpi.edu.br

Paulo Roberto Oliveira

PESC/COPPE, Programa de Engenharia de Sistemas e Computação, Rio de Janeiro, Brazil

poliveir@cos.ufrj.br

Pedro A. Soares Jr

PESC/COPPE, Programa de Engenharia de Sistemas e Computação, Rio de Janeiro, Brazil

pedroasoaresjr@gmail.com

Keywords

  • Nash equilibrium
  • convergence
  • finite time
  • proximal algorithm
  • alternation
  • learning in games
  • inertia
  • Riemannian manifold
  • Kurdyka-Lojasiewicz property

Mathematics Subject Classification

65K10, 49J52, 49M27, 90C26, 91B50, 91B06; 53B20

References

  1. P. A. Absil, R. Mahony, R. Sepulchre: Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton (2008).https://doi.org/10.1515/9781400830244Google Scholar
  2. S. Adly, H. Attouch, A. Cabot: Chapter 24, in: Nonsmooth Mechanics and Analysis. Theoretical and Numerical Advances, Advances in Mechanics and Mathematics 12, P. Alart, O. Maisonneuve, R. T. Rockafellar (eds.), Springer, New York (2006).Google Scholar
  3. H. Attouch, J. Bolte, P. Redont, A. Soubeyran: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Lojasiewicz inequality, Math. Oper. Res 35(2) (2010) 438–457.https://doi.org/10.1287/moor.1100.0449Google Scholar
  4. H. Attouch, J. Bolte: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program., Ser. B 116(1–2) (2009) 5–16.https://doi.org/10.1007/s10107-007-0133-5Google Scholar
  5. 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(3) (2008) 485–506.https://doi.org/10.68381/jca15035Google Scholar
  6. H. Attouch, J. Bolte, B. F. Svaiter: Convergence of descent methods for semialgebric and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Program., Ser. A. 137(1–2) (2013) 91–129.https://doi.org/10.1007/s10107-011-0484-9Google Scholar
  7. H. Attouch, P. Redont, A. Soubeyran: A new class of alternating proximal minimization algorithms with costs to move, SIAM J. Optim. 18(3) (2007) 1061–1081.https://doi.org/10.1137/060657248Google Scholar
  8. H. Attouch, A. Soubeyran: Inertia and reactivity in decision making as cognitive variational inequalities, J. Convex Analysis 13(2) (2006) 207–224.https://doi.org/10.68381/jca13022Google Scholar
  9. H. Attouch, A. Soubeyran: Local search proximal algorithms as decision dynamics with costs to move, Set-Valued Var. Anal. 19(1) (2011) 157–177.https://doi.org/10.1007/s11228-010-0139-7Google Scholar
  10. B. Awerbuch, Y. Azar, A. Epstein, V. Mirrokni, A. Skopalik: Fast convergence to nearly optimal solutions in potential games, in: Proc. ACM Conference on Electronic Commerce (Chicago, 2008), L. Fortnow et al. (ed.), Association for Computing Machinery, New York (2008) 264–273.https://doi.org/10.1145/1386790.1386832Google Scholar
  11. G. C. Bento, J. X. da Cruz Neto, P. R. Oliveira: Convergence of inexact descent methods for nonconvex optimization on Riemannian manifolds, arXiv:1103.4828 (2011), preprint.Google Scholar
  12. G. C. Bento, O. P. Ferreira, P. R. Oliveira: Local convergence of the proximal point method for a special class of nonconvex functions on Hadamard manifolds, Nonlinear Anal. 73 (2010) 564–572.https://doi.org/10.1016/j.na.2010.03.057Google Scholar
  13. E. Bierstone, P. D. Milman: Semianalytic and subanalytic sets, Publ. Math., Inst. Hautes Étud. Sci. 67 (1988) 5–42.https://doi.org/10.1007/BF02699126Google Scholar
  14. J. Bolte, A. Daniilidis, A. Lewis: A nonsmooth Morse-Sard theorem for subanalytic functions, J. Math. Anal. Appl 321(2) (2006) 729–740.https://doi.org/10.1016/j.jmaa.2005.07.068Google Scholar
  15. J. Bolte, A. Daniilidis, A. Lewis: The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim. 17(4) (2006) 1205–1223.https://doi.org/10.1137/050644641Google Scholar
  16. J. Bolte, A. Daniilidis, A. Lewis, M. Shiota: Clarke subgradients of stratifiable functions, SIAM J. Optim. 18(2) (2007) 556–572.https://doi.org/10.1137/060670080Google Scholar
  17. Y. Chen, R. Gazzale: When does learning in games generate convergence to Nash equilibria? The role of supermodularity in an experimental setting, Amer. Econ. Rev. 9(5) (2004) 1505–1535.https://doi.org/10.1257/0002828043052349Google Scholar
  18. M. Coste: An Introduction to O-minimal Geometry, PhD Thesis, Istituti Editoriali e Poligrafici Internazionali, Dip. Mat., Univ. Pisa, Pisa (2000), http://www.docstoc.com/docs/2688805.Google Scholar
  19. M. P. Do Carmo: Riemannian Geometry, Birkhäuser, Boston (1992).https://doi.org/10.1007/978-1-4757-2201-7Google Scholar
  20. O. P. Ferreira, P. R. Oliveira: Proximal point algorithm on Riemannian manifolds, Optimization 51(2) (2002) 257–270.https://doi.org/10.1080/02331930290019413Google Scholar
  21. A. Fishbach, M. F. Ferguson: The goal construct in social psychology, in: Social Psychology: Handbook of Basic Principles, A. W. Kruglanski, E. T. Higgins (eds.) Guilford, New York (2007) 490–515.Google Scholar
  22. M. Fukushima, H. Mine: A generalized proximal point algorithm for certain nonconvex minimization problems, Int. J. Syst. Sci. 12(8) (1981) 989–1000.https://doi.org/10.1080/00207728108963798Google Scholar
  23. W. L. Hare, C. Sagastizábal: Computing proximal points of nonconvex functions, Math. Program., Ser. B 116 (2009) 221–258.https://doi.org/10.1007/s10107-007-0124-6Google Scholar
  24. M. W. Hirsch: Differential Topology, Springer, New York (1976).https://doi.org/10.1007/978-1-4684-9449-5Google Scholar
  25. J. Hofbauer, S. Sorin: Best response dynamics for continuous zero-sum games, Discrete Contin. Dyn. Syst., Ser. B 6(1) (2006) 215–224.https://doi.org/10.3934/dcdsb.2006.6.215Google Scholar
  26. C. L. Hull: The goal-gradient hypothesis and maze learning, Psychol. Rev. 39 (1932) 25–43.https://doi.org/10.1037/h0072640Google Scholar
  27. C. L. Hull: The rat’s speed-of-locomotion gradient in the approach to food, J. Comp. Psychol. 17(3) (1934) 393–422.https://doi.org/10.1037/h0071299Google Scholar
  28. M. Jensen, D. Oyama: Stability of pure strategy Nash equilibrium and best response potential games, Dep. of Economics, University of Birmingham (2009), working paper.Google Scholar
  29. D. Kahneman, A. Tversky: Prospect theory: an analysis of decision under risk, Econometrica 47(2) (1979) 263–291.https://doi.org/10.2307/1914185Google Scholar
  30. R. Kivetz, O. Urminsky, Y. H. Zheng: The goal-gradient hypothesis resurrected: Ppurchase acceleration, illusionary goal progress, and customer retention, J. Marketing Res. 43(1) (2006) 39–58.https://doi.org/10.1509/jmkr.43.1.39Google Scholar
  31. K. Kurdyka: On gradients of functions definable in o-minimal structures, Ann. Inst. Fourier 48(3) (1998) 769–783.https://doi.org/10.5802/aif.1638Google Scholar
  32. K. Kurdyka, T. Mostowski, A. Parusinski: Proof of the gradient conjecture of R. Thom, Ann. Math. 152(3) (2000) 763–792.https://doi.org/10.2307/2661354Google Scholar
  33. C. Lageman: Convergence of Gradient-like Dynamical Systems and Optimization Algorithms, Dissertation, Julius-Maximilians-Universität, Würzburg (2007).Google Scholar
  34. Y. S. Ledyaev, Q. J. Zhu: Nonsmooth analysis on smooth manifolds, Trans. Amer. Math. Soc 359(8) (2007) 3687–3732.https://doi.org/10.1090/S0002-9947-07-04075-5Google Scholar
  35. J. Levin: Supermodular games, Lectures Notes, Department of Economics, Caltech (2003), http://www.listserv.cds.caltech.edu.Google Scholar
  36. A. S. Lewis, J. Malick: Alternating projection on manifolds, Math. Oper. Res 33(1) (2008) 216–234.https://doi.org/10.1287/moor.1070.0291Google Scholar
  37. S. Lojasiewicz: Une propriété topologique des sous-ensembles analytiques réels, in: Les Équations aux Dérivées Partielles (Paris, 1962), Éditions du Centre National de la Recherche Scientifique, Paris (1963) 87–89.Google Scholar
  38. P. Milgrom, J. Robert: Rationalizability, learning, and equilibrium in games with strategic complementarities, Econometrica 58(6) (1990) 1255–1277.https://doi.org/10.2307/2938316Google Scholar
  39. D. Monderer, L. Shapley: Fictitious play property for games with identical players, J. Econ. Theory 68(14) (1996) 258–265.https://doi.org/10.1006/jeth.1996.0014Google Scholar
  40. M. Muraven, E. Slessareva: Mechanisms of self-control failure: motivation and limited resources, Pers. Soc. Psychol. Bull. 29 (2003) 894–906.https://doi.org/10.1177/0146167203029007008Google Scholar
  41. J. Nash: The imbedding problem for Riemannian manifolds, Ann. Math. 63(1) (1956) 20–63.https://doi.org/10.2307/1969989Google Scholar
  42. E. A. Papa Quiroz, P. R. Oliveira: Proximal point methods for quasiconvex and convex functions with Bregman distances on Hadamard manifolds, J. Convex Analysis 16(1) (2009) 49–69.https://doi.org/10.68381/jca16003Google Scholar
  43. A. Soubeyran: Variational rationality and the unsatisfied man: routines and a course pursuit between aspirations, capabilities, beliefs, GREQAM, Aix Marseille University (2010), preprint.Google Scholar
  44. A. Soubeyran: Variational rationality, a theory of individual stability and change: worthwhile and ambidextry behaviors, GREQAM, Aix Marseille University (2009), preprint.Google Scholar
  45. D. M. Topkis: Minimizing a submodular function on a lattice, Oper. Res. 26(16) (1979) 305–321.https://doi.org/10.1287/opre.26.2.305Google Scholar
  46. M. Touré-Tillery, A. Fishbach: The course of motivation, J. Consum. Psychol. 21(4) (2011) 414–423.https://doi.org/10.1016/j.jcps.2011.04.004Google Scholar
  47. L. van den Dries: O-minimal structures and real analytic geometry, in: Current Developments in Mathematics (Cambridge, MA, 1998), B. Mazur et al. (ed.), Int. Press, Somerville (1999) 105–152.https://doi.org/10.4310/CDM.1998.v1998.n1.a4Google Scholar
  48. L. van den Dries, C. Miller: Geometric categories and o-minimal structures, Duke Math. J. 84(2) (1996) 497–540.https://doi.org/10.1215/S0012-7094-96-08416-1Google Scholar
  49. X. Vives: Nash equilibrium with strategic complementarities, J. Math. Econ. 19 (1990) 305–321.https://doi.org/10.1016/0304-4068(90)90005-TGoogle Scholar
  50. M. Voorneveld: Best response potential games, Econ. Lett. 66 (2000) 289–295.https://doi.org/10.1016/S0165-1765(99)00196-2Google Scholar
  51. R. A. Wright, R. E. Martin, J. L. Bland: Energy resource depletion, task difficulty, and cardiovascular response to a mental arithmetic challenge, Psychophysiology 40(1) (2003) 98–105.https://doi.org/10.1111/1469-8986.00010Google Scholar

Suggested citation

J. X. Cruz Neto, P. R. Oliveira, P. A. Soares Jr, A. Soubeyran. “Learning how to Play Nash, Potential Games and Alternating Minimization Method for Structured Nonconvex Problems on Riemannian Manifolds.” Journal of Convex Analysis 20 (2013), No. 2, 395–438. https://doi.org/10.68381/jca20025

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2013. Rights now held by Banach Press LLC.