提出一种新方法，高效求解含凸或强凸下层问题的双层优化。
Solving bilevel optimization via sequential minimax optimization
- 通过序列极小极大子问题求解，结合修正增广拉格朗日与惩罚项。
- 在强凸下层时，复杂度比之前最优结果快一阶，达O(ε⁻⁶ log ε⁻¹)。
- 适合求解带约束的双层优化，尤其下层为凸或强凸场景。
本文针对一类下层为可能非光滑凸优化、上层为可能非凸优化的约束双层优化问题，提出一种序列极小极大优化（SMO）方法。SMO通过一阶方法求解一系列由修正增广拉格朗日与惩罚项混合构造的极小极大子问题。在合理假设下，建立寻找ε-KKT解的操作复杂度为O(ε⁻⁷ log ε⁻¹)（仅凸下层）和O(ε⁻⁶ log ε⁻¹)（强凸下层）。后一结果相比此前最优复杂度提升了一阶。初步数值实验表明，该方法计算性能显著优于近期提出的首阶惩罚法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。