A Barrier-Based First-Order Method for Constrained Bilevel Optimization

Bilevel optimization (BLO) problems find wide-ranging applications in network optimization, transportation, game theory, and machine learning. Recently, there has been significant interest in developing efficient gradient-based algorithms for solving BLO problems, with a particular focus on first-order methods due to their scalability. However, lower-level (LL) constraints introduce challenges for first-order gradient-based methods. To address these challenges, this paper focuses on barrier-reformulated constrained BLO problems, where the LL problem is transformed by incorporating a log barrier into the objective function. We propose a first-order method for barrier-reformulated constrained BLO problems with a non-asymptotic convergence guarantee to an ϵ-stationary point. The convergence rate is near-optimal in terms of dependency on ϵ, though at the cost of a linear dependence on dimension. We also demonstrate the effectiveness of the proposed method through the linear price-setting experiment.