Optimization Online


Learning how to play Nash, potential games and alternating minimization method for structured nonconvex problems on Riemannian manifolds

J.X. da Cruz Neto(jcruzneto***at***uol.com.br)
P.R. Oliveira(poliveir***at***cos.ufrj.br)
P.A. Soares Jr.(pedrosoares***at***cos.ufrj.br)
A. Soubeyran(antoine.soubeyran***at***univmed.fr)

Abstract: In this paper we consider minimization problems with constraints. We show that if the set of constaints is a Riemannian manifold of non positive curvature and the objective function is lower semicontinuous and satisfi es 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 de fined and converges to an inertial Nash equilibrium under mild assumptions about the objective function. As an application, we give a welcome result on the dificult 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).

Keywords: Nash equilibrium; convergence; finite time; proximal algorithm; alternation; learning in games; inertia; Riemannian manifold; Kurdyka-Lojasiewicz property.

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Other Topics (Game Theory )

Category 3: Applications -- Science and Engineering

Citation: Citation: Programa de Engenharia de Sistemas e Computação - UFRJ - Rio de Janeiro, Brazil

Download: [PDF]

Entry Submitted: 03/23/2012
Entry Accepted: 03/23/2012
Entry Last Modified: 03/23/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society