First-order penalty methods for bilevel optimization

\(\)
In this paper we study a class of unconstrained and constrained bilevel optimization problems in which the lower-level part is a convex optimization problem, while the upper-level part is possibly a nonconvex optimization problem. In particular, we propose penalty methods for solving them, whose subproblems turn out to be a structured minimax problem and are suitably solved by a first-order method developed in this paper. Under some suitable assumptions, an operation complexity of \({\cal O}(\varepsilon^{-4}\log\varepsilon^{-1})\) and \({\cal O}(\varepsilon^{-7}\log\varepsilon^{-1})\), measured by their fundamental operations, is established for the proposed penalty methods for finding an
\(\varepsilon\)-KKT solution of the unconstrained and constrained bilevel optimization problems, respectively. To the best of our knowledge, the methodology and results in this paper are new.

Citation

arXiv preprint arXiv:2301.01716, 2023

Article

Download

View First-order penalty methods for bilevel optimization