Numerical Methods For Generalized Nash Equilibrium Problems Based On Their Approximate Reformulations

The generalized Nash equilibrium problem (GNEP) is an extension of the standard Nash equilibrium problem (NEP). Unlike the standard Nash equilibrium problem, in the generalized Nash equilibrium problem, the strategy set of each player depends both on the decision vari-ables of this player and on the decision variables of all other players. This feature makes the generalized Nash equilibrium model be able to describe practical phenomena in a competi-tive market. Recently, the generalized Nash equilibrium problem has been widely used in many fields such as economics, engineering, transportation, electricity, computer science, telecommu-nications and environmental pollution. However, unlike the standard Nash equilibrium problem, there are only a few methods available for solving the generalized Nash equilibrium problem. This dissertation focuses on the study of penalty methods and semismooth Newton methods for generalized Nash equilibrium problems. The main results obtained in this dissertation are summarized as follows:1. After giving the introduction, background and current research of the generalized Nash equilibrium problem in Chapter1, Chapter2focuses on the penalty method and the bar-rier method for the generalized Nash equilibrium problem. Based on the relationship between the generalized Nash equilibrium problem and the quasi-variational inequality, we give the penalty model for the generalized Nash equilibrium problem with equality constraints and the barrier model for the generalized Nash equilibrium problem with in-equality constrains. Under some conditions, we present the convergence analysis of these two methods for solving the generalized Nash equilibrium problem and report our numer-ical results to show the efficiency of the methods.2. The main idea of Chapter3is using the Newton method for semismooth equations to solve the generalized Nash equilibrium problem. Based on the Karush-Kuhn-Tucker condition of each player, a non-smooth system for the generalized Nash equilibrium problem is formulated by combining all Karush-Kuhn-Tucker conditions of N players. The Newton method is adopted for solving the non-smooth system. We demonstrate the ninsingularity of Clarke’s generalized Jacobian of this system at a solution point. Several numerical results are reported.3. The main idea of Chapter4is to employ the Nikaido-Isoda-function to transform the gen-eralized Nash equilibrium problem into two problems, a minimax problem and a mathe-matical program with complementarity constraints. We introduce the Fisher-Burmeister function to transform the Karush-Kuhn-Tucker system of the minimax problem into a semismooth system and prove the strong BD-regularity of this system at a solution point. Using a smoothing function, we study a smoothing method for the Karush-Kuhn-Tucker system of the mathematical program with complementarity constraints, and numerical results show that our methods are practical.