Abstract
In this paper we propose a sequential minimax optimization (SMO) method forsolving a class of constrained bilevel optimization problems in which thelower-level part is a possibly nonsmooth convex optimization problem, while theupper-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 andpenalty schemes on the bilevel optimization problems. Under suitableassumptions, we establish an operation complexity of$O(\varepsilon^{-7}\log\varepsilon^{-1})$ and$O(\varepsilon^{-6}\log\varepsilon^{-1})$, measured in terms of fundamentaloperations, for SMO in finding an $\varepsilon$-KKT solution of the bileveloptimization problems with merely convex and strongly convex lower-levelobjective functions, respectively. The latter result improves the previousbest-known operation complexity by a factor of $\varepsilon^{-1}$. Preliminarynumerical results demonstrate significantly superior computational performancecompared to the recently developed first-order penalty method.