Exact-Penalty Prox-Linear Methods for Bilevel Optimization with ℓ1 Lower-Level Gradient Penalty

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 ℓ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 each fixed-penalty problem, we apply a prox-linear procedure that keeps the nonsmooth ℓ1 penalty in its original form and linearizes the smooth mappings. We prove a stationarity-oriented convergence guarantee for the fixed-penalty prox-linear loop. For the unconstrained simple bilevel setting, the prox-linear subproblem admits explicit dual reformulation as a box-constrained quadratic program. This dual structure enables the use of a nonmonotone spectral projected gradient method together with a closed-form primal recovery formula. Numerical experiments on the Minimum Norm Solution Problem show that the proposed method consistently achieves lower-level feasibility and upper-level accuracy, and attains a higher success rate than several existing methods on the tested instances. A Lipschitz least-squares variant is further included to provide a numerical illustration of the global exactness theorem.