Solving Bilevel Optimization via Sequential Minimax Optimization

• 成果类型: Article; Early Access
• 署名作者: Lu, Zhaosong; Mei, Sanyou
• 署名单位: University of Minnesota System; University of Minnesota Twin Cities; Hong Kong University of Science & Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2024.0521
• 发表日期: 2026-01-06
• 关键词: bilevel optimization; minimax optimization; first order methods; operation complexity; support vector machine; complexity; algorithm

摘要

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 O(E-7log E-1) and O(E-6 log E-1), measured in terms of fundamental operations, for SMO in finding an E-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 E-1. Preliminary numerical results demonstrate significantly superior computational performance compared with the recently developed first order penalty method.