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
hdl.handle.net/1765/131552
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