Optimality Conditions and Constraint Qualifications for Generalized Nash Equilibrium Problems and their Practical Implications

Generalized Nash Equilibrium Problems (GNEPs) are a generalization of the classic Nash Equilibrium Problems (NEPs), where each player's strategy set depends on the choices of the other players. In this work we study constraint qualifications and optimality conditions tailored for GNEPs and we discuss their relations and implications for global convergence of algorithms. Surprisingly, differently from the case of nonlinear programming, we show that, in general, the KKT residual can not be made arbitrarily small near a solution of a GNEP. We then discuss some important practical consequences of this fact. We also prove that this phenomenon is not present in an important class of GNEPs, including NEPs. Finally, under a weak constraint qualification introduced, we prove global convergence to a KKT point of an Augmented Lagrangian algorithm for GNEPs and under the quasinormality constraint qualification for GNEPs, we prove boundedness of the dual sequence.

Citation

Submitted

Article

Download

View Optimality Conditions and Constraint Qualifications for Generalized Nash Equilibrium Problems and their Practical Implications