Solving Bilevel Optimization via Sequential Minimax Optimization

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, whereas 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 $\mathcal{O}({\epsilon }^{-7}\log {\epsilon }^{-1})$ and $\mathcal{O}({\epsilon }^{-6}\log {\epsilon }^{-1})$, measured in terms of fundamental operations, for SMO in finding an $\epsilon$-Karush–Kuhn–Tucker 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 with the recently developed first order penalty method.

Funding: This work was partially supported by the Air Force Office of Scientific Research Award [FA9550-24-1-0343], the Office of Naval Research Award [N00014-24-1-2702], and the National Science Foundation Awards [2211491 and 2435911]. It was primarily conducted during Sanyou Mei's PhD studies at the University of Minnesota.