Randomized Lagrangian stochastic approximation for large-scale constrained stochastic Nash games

Zeinab Alizadeh, Afrooz Jalilzadeh, Farzad Yousefian

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

In this paper, we consider stochastic monotone Nash games where each player’s strategy set is characterized by possibly a large number of explicit convex constraint inequalities. Notably, the functional constraints of each player may depend on the strategies of other players, allowing for capturing a subclass of generalized Nash equilibrium problems (GNEP). While there is limited work that provide guarantees for this class of stochastic GNEPs, even when the functional constraints of the players are independent of each other, the majority of the existing methods rely on employing projected stochastic approximation (SA) methods. However, the projected SA methods perform poorly when the constraint set is afflicted by the presence of a large number of possibly nonlinear functional inequalities. Motivated by the absence of performance guarantees for computing the Nash equilibrium in constrained stochastic monotone Nash games, we develop a single timescale randomized Lagrangian multiplier stochastic approximation method where in the primal space, we employ an SA scheme, and in the dual space, we employ a randomized block-coordinate scheme where only a randomly selected Lagrangian multiplier is updated. We show that our method achieves a convergence rate of Olog(k)k for suitably defined suboptimality and infeasibility metrics in a mean sense.

Original languageEnglish (US)
Pages (from-to)377-401
Number of pages25
JournalOptimization Letters
Volume18
Issue number2
DOIs
StatePublished - Mar 2024

Keywords

  • Constrained optimization
  • Generalized Nash games
  • Lagrangian dual method
  • Stochastic Nash game
  • Stochastic approximation

ASJC Scopus subject areas

  • Business, Management and Accounting (miscellaneous)
  • Control and Optimization

Fingerprint

Dive into the research topics of 'Randomized Lagrangian stochastic approximation for large-scale constrained stochastic Nash games'. Together they form a unique fingerprint.

Cite this