Multi-parametric approach for nonlinear bilevel optimization problems and beyond

Abstract

One of the peculiar features of multi-parametric approach for bilevel programs is that most methods using this approach can be extended to tri-level (and generally to $k$-level) programs, which is not always the case with other non-heuristic solution methods. However, most of existing multi-parametric methods work well when the constraint of the lower-level problem is polyhedral. In this article we propose a multi-parametric programming based solution algorithm for bilevel optimization problems whose lower-level problem involves convex smooth nonlinear constraints. The method is also extended to solve some classes of $k$-level convex optimization problems with nonlinear constraints. The algorithm recasts the lower-level problem as a multi-parametric problem and employs an equivalent barrier problem reformulation. The solution obtained through multi-parametric programming is incorporated in the upper-level problem to create a set of single-level optimization problems which are solved using standard global optimization techniques. The proposed algorithm can give an exact global solution to some class of nonlinear Multi-level problems with convex nonlinear constraints.