Necessary optimality conditions in pessimistic bilevel programming

Abstract

This article is devoted to the so-called pessimistic version of bilevel programming programs. Minimization problems of this type are challenging to handle partly because the corresponding value functions are often merely upper (while not lower) semicontinuous. Employing advanced tools of variational analysis and generalized differentiation, we provide rather general frameworks ensuring the Lipschitz continuity of the corresponding value functions. Several types of lower subdifferential necessary optimality conditions are then derived by using the lower-level value function approach and the Karush–Kuhn–Tucker representation of lower-level optimal solution maps. We also derive upper subdifferential necessary optimality conditions of a new type, which can be essentially stronger than the lower ones in some particular settings. Finally, certain links are established between the obtained necessary optimality conditions for the pessimistic and optimistic versions in bilevel programming.

Keywords:

• optimization and variational analysis
• pessimistic bilevel programs
• two-level value functions
• sensitivity analysis
• generalized differentiation
• optimality conditions

Acknowledgements

The authors are gratefully indebted to two anonymous referees and also to Jacqueline Morgan and Jiří Outrata whose comments allowed us to improve the original presentation of this article. A.B. Zemkoho acknowledges the financial support by the Deutscher Akademischer Austausch Dienst (DAAD). Research of B.S. Mordukhovich was partially supported by the USA National Science Foundation under grant DMS-007132, by Australian Research Council under grant DP-12092508, by the European Regional Development Fund (FEDER), and by the following Portuguese agencies: Foundation for Science and Technology, Operational Program for Competitiveness Factors, and Strategic Reference Framework under Grant PTDC/MAT/111809/2009.