Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2009-006 (January 29, 2009)
Newton's method for computing a normalized equilibrium in
the generalized Nash game through fixed point formulation
by Anna von Heusinger, Christian Kanzow and Masao Fukushima
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.