  In this paper we study a class of unconstrained and constrained bilevel
optimization problems in which the lower level is a possibly nonsmooth convex
optimization problem, while the upper level is a possibly nonconvex
optimization problem. We introduce a notion of $\varepsilon$-KKT solution for
them and show that an $\varepsilon$-KKT solution leads to an
$O(\sqrt{\varepsilon})$- or $O(\varepsilon)$-hypergradient based stionary point
under suitable assumptions. We also propose first-order penalty methods for
finding an $\varepsilon$-KKT solution of them, whose subproblems turn out to be
a structured minimax problem and can be suitably solved by a first-order method
recently developed by the authors. Under suitable assumptions, an
\emph{operation complexity} of $O(\varepsilon^{-4}\log\varepsilon^{-1})$ and
$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. Preliminary numerical results are
presented to illustrate the performance of our proposed methods. To the best of
our knowledge, this paper is the first work to demonstrate that bilevel
optimization can be approximately solved as minimax optimization, and moreover,
it provides the first implementable method with complexity guarantees for such
sophisticated bilevel optimization.
