Solving bilevel optimization via sequential minimax optimization

Abstract

In this paper we propose a sequential minimax optimization (SMO) method for solving a class of constrained bilevel optimization problems in which the lower-level part is a possibly nonsmooth convex optimization problem, while the upper-level part is a possibly nonconvex optimization problem. Specifically, SMO applies a first-order method to solve a sequence of minimax subproblems, which are obtained by employing a hybrid of modified augmented Lagrangian and penalty schemes on the bilevel optimization problems. Under suitable assumptions, we establish an operation complexity of $O({\epsilon }^{-7}\log {\epsilon }^{-1})$ and $O({\epsilon }^{-6}\log {\epsilon }^{-1})$, measured in terms of fundamental operations, for SMO in finding an $\epsilon$-KKT solution of the bilevel optimization problems with merely convex and strongly convex lower-level objective functions, respectively. The latter result improves the previous best-known operation complexity by a factor of ${\epsilon }^{-1}$. Preliminary numerical results demonstrate significantly superior computational performance compared to the recently developed first-order penalty method.

Accepted by Mathematics of Operations Research