User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

On intrinsic complexity of Nash equilibrium problems and bilevel optimization

Primary tabs

Dorsch, Dominik [RWTH Aachen University] Jongen, Hubertus Th. [RWTH Aachen University] Shikhman, Vladimir [UCL]

We study generalized Nash equilibrium problems (GNEP) and bilevel optimization side by side. This perspective comes from the crucial fact that both problems heavily depend on parametric issues. Observing the intrinsic complexity of GNEP and bilevel optimization, we emphasize that it originates from unavoidable degeneracies occurring in parametric optimization. Under intrinsic complexity we understand the involved geometrical complexity of Nash equilibria and bilevel feasible sets, such as the appearance of kinks and boundary points, non-closedness, discontinuity and bifurcation effects. By taking the study of singularities in parametric optimization into account, the structural analysis of Nash equilibria and bilevel feasible sets is performed. For GNEPs the number of players' common constraints becomes crucial. In fact, for GNEPs without common constraints and for classical NEPs we show that - generically - all Nash equilibria are jointly nondegenerate Karush-Kuhn-Tucker points. Consequently, they are isolated. However, in presence of common constraints Nash equilibria will constitute a higher dimensional set. In bilevel optimization, we describe the global structure of the bilevel feasible set in case of a one-dimensional leader's variable. We point out that the typical discontinuities of the leader's objective function will be caused by follower's singularities. The latter phenomenon occurs independently from the viewpoint of the optimistic or pessimistic approach. In case of higher dimensions, optimistic and pessimistic approaches are discussed with respect to possible bifurcation of the follower's solutions.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès restreint
Publication date 2013
Language Anglais
Journal information "Journal of Optimization Theory and Applications" - Vol. 159, no. 3, p. 606-634 (2013)
Peer reviewed yes
Publisher Springer New York LLC ((United States) New York)
issn 0022-3239
e-issn 1573-2878
Publication status Publié
Affiliation UCL - SST/ICTM/INMA - Pôle en ingénierie mathématique
Links
  1. Bard Jonathan F., Practical Bilevel Optimization, ISBN:9781441948076, 10.1007/978-1-4757-2836-1
  2. Facchinei Francisco, Kanzow Christian, Generalized Nash Equilibrium Problems, 10.1007/s10479-009-0653-x
  3. Dempe, S.: Foundations of Bilevel Programming. Kluwer Academic, Dordrecht (2002)
  4. Pang Jong-Shi, Fukushima Masao, Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games, 10.1007/s10287-004-0010-0
  5. Luo Zhi-Quan, Pang Jong-Shi, Ralph Daniel, Mathematical Programs with Equilibrium Constraints, ISBN:9780511983658, 10.1017/cbo9780511983658
  6. Outrata Jiři, Kočvara Michal, Zowe Jochem, Nonsmooth Approach to Optimization Problems with Equilibrium Constraints, ISBN:9781441948045, 10.1007/978-1-4757-2825-5
  7. Pang Jong-Shi, Scutari Gesualdo, Nonconvex Games with Side Constraints, 10.1137/100811787
  8. Jongen, H.T., Shikhman, V.: Bilevel optimization: on the structure of the feasible set. Math. Program. 1–25 (2012)
  9. Hirsch Morris W., Differential Topology, ISBN:9781468494518, 10.1007/978-1-4684-9449-5
  10. Jongen, H.T., Jonker, P., Twilt, F.: Nonlinear Optimization in Finite Dimensions. Kluwer Academic, Dordrecht (2000)
  11. Jongen, H.T., Meer, K., Triesch, E.: Optimization Theory. Kluwer Academic, Dordrecht (2004)
  12. Jongen H. Th., Jonker P., Twilt F., Critical sets in parametric optimization, 10.1007/bf01582234
  13. Facchinei Francisco, Fischer Andreas, Piccialli Veronica, Generalized Nash equilibrium problems and Newton methods, 10.1007/s10107-007-0160-2
  14. Günzel Harald, The structured jet transversality theorem†, 10.1080/02331930701779039
  15. Stein, O.: On Parametric Semi-infinite Optimization. Shaker, Aachen (1997)
  16. Jongen H. T., Zwier G., On regular minimax optimization, 10.1007/bf00939815
  17. Dempe Stephan, Günzel Harald, Jongen Hubertus Th., On Reducibility in Bilevel Problems, 10.1137/080718231
  18. Scheel Holger, Scholtes Stefan, Mathematical Programs with Complementarity Constraints: Stationarity, Optimality, and Sensitivity, 10.1287/moor.25.1.1.15213
  19. Kojima Masakazu, Strongly Stable Stationary Solutions in Nonlinear Programs, Analysis and Computation of Fixed Points (1980) ISBN:9780125902403 p.93-138, 10.1016/b978-0-12-590240-3.50009-4
  20. C̆ervinka, M., Matonoha, C., Outrata, J.V.: On the computation of relaxed pessimistic solutions to MPECs. Optim. Methods Softw. 28(1) (2013)
  21. Guddat, J., Rückmann, J.-J.: One-parametric optimization: jumps in the set of generalized critical points. Control Cybern. 23, 139–151 (1994)
Bibliographic reference Dorsch, Dominik ; Jongen, Hubertus Th. ; Shikhman, Vladimir. On intrinsic complexity of Nash equilibrium problems and bilevel optimization. In: Journal of Optimization Theory and Applications, Vol. 159, no. 3, p. 606-634 (2013)
Permanent URL http://hdl.handle.net/2078/115757