Abstract
Generalized Nash equilibrium problems (GNEPs) allow, in contrast to standard Nash equilibrium problems, a dependence of the strategy space of one player from the decisions of the other players. In this paper, we consider jointly convex GNEPs which form an important subclass of the general GNEPs. Based on a regularized Nikaido-Isoda function, we present two (nonsmooth) reformulations of this class of GNEPs, one reformulation being a constrained optimization problem and the other one being an unconstrained optimization problem. While most approaches in the literature compute only a so-called normalized Nash equilibrium, which is a subset of all solutions, our two approaches have the property that their minima characterize the set of all solutions of a GNEP. We also investigate the smoothness properties of our two optimization problems and show that both problems are continuous under a Slater-type condition and, in fact, piecewise continuously differentiable under the constant rank constraint qualification. Finally, we present some numerical results based on our unconstrained optimization reformulation.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Burke, J.V., Lewis, A.S., Overton, M.L.: A robust gradient sampling algorithm for nonsmooth, nonconvex optimization. SIAM J. Opt. 15, 751–779 (2005)
Chaney, R.W.: Piecewise C k functions in nonsmooth analysis. Nonlinear Anal., Theory Methods Appl. 15, 649–660 (1990)
Clarke, F.H.: Optimization and Nonsmooth Analysis. SIAM, Philadelphia (1990)
Facchinei, F., Fischer, A., Piccialli, V.: Generalized Nash equilibrium problems and Newton methods. Math. Program. 117, 163–194 (2009)
Facchinei, F., Kanzow, C.: Generalized Nash equilibrium problems. 4OR 5, 173–210 (2007)
Facchinei, F., Kanzow, C.: Penalty methods for the solution of generalized Nash equilibrium problems. Technical Report, Institute of Mathematics, University of Würzburg, Germany, January 2009
Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems I. Springer, New York (2003)
Facchinei, F., Pang, J.-S.: Exact penalty functions for generalized Nash problems. In: Di Pillo, G., Roma, M. (eds.) Large Scale Nonlinear Optimization, pp. 115–126. Springer, Berlin (2006)
Fukushima, M.: Restricted generalized Nash equilibria and controlled penalty algorithm. Technical Report 2008-007, Department of Applied Mathematics and Physics, Kyoto University, July 2008
Gürkan, G., Pang, J.-S.: Approximations of Nash equilibria. Math. Program. 117, 223–253 (2009)
Harker, P.T.: Generalized Nash games and quasi-variational inequalities. Eur. J. Oper. Res. 54, 81–94 (1991)
von Heusinger, A.: Numerical methods for the solution of the generalized Nash equilibrium problem. Ph.D. Thesis, Institute of Mathematics, University of Würzburg, August 2009
von Heusinger, A., Kanzow, C.: Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions. Comput. Optim. Appl. 43, 353–377 (2009)
von Heusinger, A., Kanzow, C.: SC 1 optimization reformulations of the generalized Nash equilibrium problem. Optim. Methods Softw. 23, 953–973 (2008)
von Heusinger, A., Kanzow, C.: Relaxation methods for generalized Nash equilibrium problems with inexact line search. J. Optim. Theory Appl. 143, 159–183 (2009)
von Heusinger, A., Kanzow, C., Fukushima, M.: Newton’s method for computing a normalized equilibrium in the generalized Nash game through fixed point formulation. Technical Report, Institute of Mathematics, University of Würzburg, Germany, January 2009
Hogan, W.W.: Point-to-set maps in mathematical programming. SIAM Rev. 15, 591–603 (1973)
Janin, R.: Directional derivative of the marginal function in nonlinear programming. Math. Program. Study 21, 110–126 (1984)
Jongen, H.Th., Klatte, D., Kummer, B.: Implicit functions and sensitivity of stationary points. Math. Program. 49, 123–138 (1990)
Krawczyk, J.B., Uryas’ev, S.P.: Relaxation algorithms to find Nash equilibria with economic applications. Environ. Model. Assess. 5, 63–73 (2000)
Luderer, B., Minchenko, L., Satsura, T.: Multivalued Analysis and Nonlinear Programming Problems with Perturbations. Kluwer, Dordrecht (2002)
Nabetani, K., Tseng, P., Fukushima, M.: Parametrized variational inequality approaches to generalized Nash equilibrium problems with shared constraints. Technical Report, Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Japan, October 2008
Outrata, J.V., Kočvara, M., Zowe, J.: Nonsmooth Approach to Optimization Problems with Equilibrium Constraints. Kluwer, Dordrecht (1998)
Pang, J.-S., Fukushima, M.: Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games. Comput. Manag. Sci. 2, 21–56 (2005)
Pang, J.-S., Ralph, D.: Piecewise smoothness, local invertibility, and parametric analysis of normal maps. Math. Oper. Res. 21, 401–426 (1996)
Ralph, D., Dempe, S.: Directional derivatives of the solution of a parametric nonlinear program. Math. Program. 70, 159–172 (1995)
Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. A Series of Comprehensive Studies in Mathematics, vol. 317. Springer, Berlin (1998)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Dreves, A., Kanzow, C. Nonsmooth optimization reformulations characterizing all solutions of jointly convex generalized Nash equilibrium problems. Comput Optim Appl 50, 23–48 (2011). https://doi.org/10.1007/s10589-009-9314-x
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-009-9314-x