# 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