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 \emph{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.
翻译:在本文中,我们研究了一系列不受限制和受限制的双层优化问题,低层部分是一个二次优化问题,而上层部分可能是一个非二次优化问题。特别是,我们提出了解决这些问题的处罚方法,其次问题是结构化的小型问题,通过本文件中开发的一阶方法得到了适当的解决。根据一些适当的假设,一个低层部分是一个二次优化问题,而上层部分可能是一个非一次优化问题。特别是,我们提出解决这些问题的处罚方法,其次问题是结构化的小型问题,通过本文件中开发的一阶方法得到了适当的解决。根据我们的最佳知识,本文中的方法和结果都是新的。