{"ID":2921610,"CreatedAt":"2026-06-02T02:42:49.606572591Z","UpdatedAt":"2026-06-03T05:56:00.181519634Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.01055","arxiv_id":"2606.01055","title":"Exact-Penalty Prox-Linear Methods for Bilevel Optimization with $\\ell_1$ Lower-Level Gradient Penalty","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.","short_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...","url_abs":"https://arxiv.org/abs/2606.01055","url_pdf":"https://arxiv.org/pdf/2606.01055v1","authors":"[\"Yutong Zheng\",\"Jiani Li\",\"Qingna Li\"]","published":"2026-05-31T06:51:14Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}