×
Dreves, Axel; Kanzow, Christian

Nonsmooth optimization reformulations characterizing all solutions of jointly convex generalized Nash equilibrium problems. (English) Zbl 1227.90040

Comput. Optim. Appl. 50, No. 1, 23-48 (2011).
Summary: 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.

Cited in 18 Documents

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
91A10 Noncooperative games
90C25 Convex programming

Keywords:

generalized Nash equilibrium problem; jointly convex; optimization reformulation; continuity; \(PC^{1}\) mapping; semismoothness; constant rank constraint qualification

Software:

GradSamp
PDF BibTeX XML Cite
\textit{A. Dreves} and \textit{C. Kanzow}, Comput. Optim. Appl. 50, No. 1, 23--48 (2011; Zbl 1227.90040)
Full Text: DOI

References:

[1] 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) · Zbl 1078.65048
[2] Chaney, R.W.: Piecewise C k functions in nonsmooth analysis. Nonlinear Anal., Theory Methods Appl. 15, 649–660 (1990) · Zbl 0714.49017
[3] Clarke, F.H.: Optimization and Nonsmooth Analysis. SIAM, Philadelphia (1990) · Zbl 0696.49002
[4] Facchinei, F., Fischer, A., Piccialli, V.: Generalized Nash equilibrium problems and Newton methods. Math. Program. 117, 163–194 (2009) · Zbl 1166.90015
[5] Facchinei, F., Kanzow, C.: Generalized Nash equilibrium problems. 4OR 5, 173–210 (2007) · Zbl 1211.91162
[6] 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 · Zbl 1211.90228
[7] Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems I. Springer, New York (2003) · Zbl 1062.90001
[8] 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) · Zbl 1201.91006
[9] Fukushima, M.: Restricted generalized Nash equilibria and controlled penalty algorithm. Technical Report 2008-007, Department of Applied Mathematics and Physics, Kyoto University, July 2008 · Zbl 1253.91010
[10] Gürkan, G., Pang, J.-S.: Approximations of Nash equilibria. Math. Program. 117, 223–253 (2009) · Zbl 1216.91003
[11] Harker, P.T.: Generalized Nash games and quasi-variational inequalities. Eur. J. Oper. Res. 54, 81–94 (1991) · Zbl 0754.90070
[12] 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 · Zbl 1170.90495
[13] 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) · Zbl 1170.90495
[14] von Heusinger, A., Kanzow, C.: SC 1 optimization reformulations of the generalized Nash equilibrium problem. Optim. Methods Softw. 23, 953–973 (2008) · Zbl 1154.91356
[15] von Heusinger, A., Kanzow, C.: Relaxation methods for generalized Nash equilibrium problems with inexact line search. J. Optim. Theory Appl. 143, 159–183 (2009) · Zbl 1182.91024
[16] 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 · Zbl 1237.91021
[17] Hogan, W.W.: Point-to-set maps in mathematical programming. SIAM Rev. 15, 591–603 (1973) · Zbl 0256.90042
[18] Janin, R.: Directional derivative of the marginal function in nonlinear programming. Math. Program. Study 21, 110–126 (1984) · Zbl 0549.90082
[19] Jongen, H.Th., Klatte, D., Kummer, B.: Implicit functions and sensitivity of stationary points. Math. Program. 49, 123–138 (1990) · Zbl 0715.65034
[20] Krawczyk, J.B., Uryas’ev, S.P.: Relaxation algorithms to find Nash equilibria with economic applications. Environ. Model. Assess. 5, 63–73 (2000)
[21] Luderer, B., Minchenko, L., Satsura, T.: Multivalued Analysis and Nonlinear Programming Problems with Perturbations. Kluwer, Dordrecht (2002) · Zbl 1061.90105
[22] 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 · Zbl 1220.90136
[23] Outrata, J.V., Kočvara, M., Zowe, J.: Nonsmooth Approach to Optimization Problems with Equilibrium Constraints. Kluwer, Dordrecht (1998) · Zbl 0947.90093
[24] Pang, J.-S., Fukushima, M.: Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games. Comput. Manag. Sci. 2, 21–56 (2005) · Zbl 1115.90059
[25] Pang, J.-S., Ralph, D.: Piecewise smoothness, local invertibility, and parametric analysis of normal maps. Math. Oper. Res. 21, 401–426 (1996) · Zbl 0857.90122
[26] Ralph, D., Dempe, S.: Directional derivatives of the solution of a parametric nonlinear program. Math. Program. 70, 159–172 (1995) · Zbl 0844.90089
[27] Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. A Series of Comprehensive Studies in Mathematics, vol. 317. Springer, Berlin (1998) · Zbl 0888.49001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.