Solving linear generalized Nash equilibrium problems numerically. (2nd September 2016)

• Record Type: Journal Article
• Authors: Dreves, Axel; Sudermann-Merx, Nathan
• Is Part Of: Optimization methods and software. Volume 31:Number 5(2016)
• Page Start: 1036
• Page End: 1063
• Publication Date: 2016-09-02
• Subjects: linear generalized Nash equilibrium problem -- potential reduction algorithm -- projected subgradient method -- penalty method -- economic market model; 91A06 -- 91A10 -- 90C51 -- 90C56; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2016.1165676
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : This paper considers the numerical solution of linear generalized Nash equilibrium problems (LGNEPs). Since many methods for nonlinear problems require the nonsingularity of some second-order derivative, standard convergence conditions are not satisfied in our linear case. We provide new convergence criteria for a potential reduction algorithm (PRA) that allow its application to LGNEPs. Furthermore, we discuss a projected subgradient method (PSM) and a penalty method that exploit some known Nikaido–Isoda function-based constrained and unconstrained optimization reformulations of the LGNEP. Moreover, it is shown that normalized Nash equilibria of an LGNEP can be obtained by solving a single linear program. All proposed algorithms are tested on randomly generated instances of economic market models that are introduced and analysed in this paper and that lead to LGNEPs with shared and with non-shared constraints. It is shown that these problems have some favourable properties that can be exploited to obtain their solutions. With the PRA and in particular with the PSM we are able to compute solutions with satisfying precision even for problems with up 10, 000 variables.