Regularizing Bilevel Nonlinear Programs by Lifting

TitleRegularizing Bilevel Nonlinear Programs by Lifting
Publication TypeJournal Article
Year of Publication2013
AuthorsHatz, K, Leyffer, S, Schloder, JP, Bock, HG
JournalSIAM Journal on Optimization

This paper considers a bilevel nonlinear program (NLP) whose lower-level problem satisfies a linear independence constraint qualification (LICQ) and a strong second-order condition (SSOC). One would expect the resulting mathematical program with complementarity constraints (MPCC), whose constraints are the first-order optimality conditions of the lower-level NLP, to satisfy an MPEC-LICQ. We provide an example which demonstrates that this is not the case. A lifting technique is presented to remedy this problem. A componentwise lifting of the inequality constraints of the lower-level problem implies that the resulting MPCC satisfies an MPCC-LICQ which leads to a faster convergence. We generalize the lifting approach to general MPCCs. Convergence results and numerical experiments are provided that show the promise of our approach.