FIRST-ORDER PENALTY METHODS FOR BILEVEL OPTIMIZATION

Zhaosong Lu, Sanyou Mei

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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 ϵ-KKT solution for them and show that an ϵ-KKT solution leads to an \scrO(√ϵ)- or \scrO(ϵ)-hypergradient-based stationary point under suitable assumptions. We also propose first-order penalty methods for finding an ϵ-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 operation complexity of \scrO(ϵ-4 log ϵ-1) and \scrO(ϵ-7 log ϵ-1), measured by their fundamental operations, is established for the proposed penalty methods for finding an ϵ-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.

Original languageEnglish (US)
Pages (from-to)1937-1969
Number of pages33
JournalSIAM Journal on Optimization
Volume34
Issue number2
DOIs
StatePublished - 2024

Bibliographical note

Publisher Copyright:
2024 Society for Industrial and Applied Mathematics.

Keywords

  • bilevel optimization
  • first-order methods
  • minimax optimization
  • operation complexity
  • penalty methods

Fingerprint

Dive into the research topics of 'FIRST-ORDER PENALTY METHODS FOR BILEVEL OPTIMIZATION'. Together they form a unique fingerprint.

Cite this