View PDF HTML (experimental)

Abstract:Bilevel optimization is a fundamental framework for hierarchical decision-making, but its solution is challenging due to the implicit and typically set-valued nature of the lower-level optimality condition. In this paper,
we study bilevel optimization problems through an exact-penalty reformulation based on the $\ell_1$-norm of the lower-level gradient. Under suitable regularity assumptions,
we show that this penalty defines a distance-bound function and yields an exact penalty property for sufficiently large penalty parameters.
To solve the resulting nonsmooth penalized problem, we propose an exact-penalty prox-linear (EPPL) method and establish a stationarity-oriented convergence guarantee. We further specialize the method to the simple bilevel setting, where the subproblem admits an explicit dual reformulation as a box-constrained quadratic program. This structure leads to a dual spectral projected gradient method with closed-form primal recovery, for which convergence of the inner dual iterates is proved.
Numerical experiments on a minimum-norm least-squares bilevel model show that the proposed method is effective in reducing both the lower-level and upper-level gaps to high accuracy.
Compared with several existing methods, the proposed approach attains the best final solution accuracy on the tested instance.

Submission history

From: Qingna Li [view email]
[v1] Sun, 31 May 2026 06:51:14 UTC (549 KB)