We study a variant of the pessimistic bilevel optimization problem, which comprises constraints that must be satisfied for any optimal solution of a subordinate (lower-level) optimization problem. We present conditions that guarantee the existence of optimal solutions in such a problem, and we characterize the computational complexity of various subclasses of the problem. We then focus on problem instances that may lack convexity, but that satisfy a certain independence property. We develop convergent approximations for these instances, and we derive an iterative solution scheme that is reminiscent of the discretization techniques used in semi-infinite programming. We also present a computational study that illustrates the numerical behavior of our algorithm on standard benchmark instances.

global optimization, pessimistic bilevel problem, computational complexity
SIAM Journal on Optimization
Department of Technology and Operations Management

Wiesemann, W, Tsoukalas, A.T., Kleniati, P, & Rustem, B. (2013). Pessimistic bilevel optimization. SIAM Journal on Optimization, 23, 353–380. Retrieved from http://hdl.handle.net/1765/131552