{"ID":2844138,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.07398","arxiv_id":"2511.07398","title":"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(\\varepsilon^{-7}\\log\\varepsilon^{-1})$ and $O(\\varepsilon^{-6}\\log\\varepsilon^{-1})$, measured in terms of fundamental operations, for SMO in finding an $\\varepsilon$-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 $\\varepsilon^{-1}$. Preliminary numerical results demonstrate significantly superior computational performance compared to the recently developed first-order penalty method.","short_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...","url_abs":"https://arxiv.org/abs/2511.07398","url_pdf":"https://arxiv.org/pdf/2511.07398v1","authors":"[\"Zhaosong Lu\",\"Sanyou Mei\"]","published":"2025-11-10T18:51:05Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.LG\",\"math.NA\",\"stat.ML\"]","methods":"[]","has_code":false}