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 [Formula: see text] and [Formula: see text], measured in terms of fundamental operations, for SMO in finding an [Formula: see text]-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 [Formula: see text]. 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.