Newton's method for computing a normalized equilibrium in the generalized Nash game through fixed point formulation

• 成果类型: Article
• 署名作者: von Heusinger, Anna; Kanzow, Christian; Fukushima, Masao
• 署名单位: University of Wurzburg; Kyoto University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-010-0386-2
• 发表日期: 2012
• 页码: 99-123
• 关键词: optimization reformulations; relaxation algorithms; EQUATIONS; systems; MAPS

摘要

We consider the generalized Nash equilibrium problem (GNEP), where not only the players' cost functions but also their strategy spaces depend on the rivals' decision variables. Existence results for GNEPs are typically shown by using a fixed point argument for a certain set-valued function. Here we use a regularization of this set-valued function in order to obtain a single-valued function that is easier to deal with from a numerical point of view. We show that the fixed points of the latter function constitute an important subclass of the generalized equilibria called normalized equilibria. This fixed point formulation is then used to develop a nonsmooth Newton method for computing a normalized equilibrium. The method uses a so-called computable generalized Jacobian that is much easier to compute than Clarke generalized Jacobian or B-subdifferential. We establish local superlinear/quadratic convergence of the method under the constant rank constraint qualification, which is weaker than the frequently used linear independence constraint qualification, and a suitable second-order condition. Some numerical results are presented to illustrate the performance of the method.