Scholtes Relaxation Method for Pessimistic Bilevel Optimization

Abstract When the lower-level optimal solution set-valued mapping of a bilevel optimization problem is not single-valued, we are faced with an ill-posed problem, which gives rise to the optimistic and pessimistic bilevel optimization problems, as tractable algorithmic frameworks. However, solving the pessimistic bilevel optimization problem is far more challenging than the optimistic one; hence, the literature has mostly been dedicated to the latter class of the problem. The Scholtes relaxation has appeared to be one of the simplest and most efficient ways to solve the optimistic bilevel optimization problem in its Karush-Kuhn-Tucker (KKT) reformulation or the corresponding more general mathematical program with complementarity constraints (MPCC). Inspired by such a success, this paper studies the potential of the Scholtes relaxation in the context of the pessimistic bilevel optimization problem. To proceed, we consider a pessimistic bilevel optimization problem, where all the functions involved are at least continuously differentiable. Then assuming that the lower-level problem is convex, the KKT reformulation of the problem is considered under the Slater constraint qualification. Based on this KKT reformulation, we introduce the corresponding version of the Scholtes relaxation algorithm. We then construct theoretical results ensuring that the limit of a sequence of global/local optimal solutions (resp. stationary points) of the aforementioned Scholtes relaxation is a global/local optimal solution (resp. stationary point) of the KKT reformulation of the pessimistic bilevel program. The results are accompanied by technical constructions ensuring that the Scholtes relaxation algorithm is well-defined or that the corresponding parametric optimization problem is more tractable. Furthermore, we perform some numerical experiments to assess the performance of the Scholtes relaxation algorithm using various examples. In particular, we study the effectiveness of the algorithm in obtaining solutions that can satisfy the corresponding C-stationarity concept.