A Discretization Approach for Bilevel Optimization with Low-Dimensional and Non-Convex Lower-Level
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908366986543104 |
|---|---|
| author | Jiang, Xiaotian Tsaknakis, Ioannis Khanduri, Prashant Hong, Mingyi |
| author_facet | Jiang, Xiaotian Tsaknakis, Ioannis Khanduri, Prashant Hong, Mingyi |
| contents | Bilevel optimization (BLO) problem, where two optimization problems (referred to as upper- and lower-level problems) are coupled hierarchically, has wide applications in areas such as machine learning and operations research. Recently, many first-order algorithms have been developed for solving bilevel problems with strongly convex and/or unconstrained lower-level problems; this special structure of the lower-level problem is needed to ensure the tractability of gradient computation (among other reasons). In this work, we deal with a class of more challenging BLO problems where the lower-level problem is non-convex and constrained. We propose a novel approach that approximates the value function of the lower-level problem by first sampling a set of feasible solutions and then constructing an equivalent convex optimization problem. This convexified value function is then used to construct a penalty function for the original BLO problem. We analyze the properties of the original BLO problem and the newly constructed penalized problem by characterizing the relation between their KKT points, as well as the local and global minima of the two problems. We then develop a gradient descent-based algorithm to solve the reformulated problem, and establish its finite-time convergence guarantees. Finally, we conduct numerical experiments to corroborate the theoretical performance of the proposed algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_10830 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Discretization Approach for Bilevel Optimization with Low-Dimensional and Non-Convex Lower-Level Jiang, Xiaotian Tsaknakis, Ioannis Khanduri, Prashant Hong, Mingyi Optimization and Control Bilevel optimization (BLO) problem, where two optimization problems (referred to as upper- and lower-level problems) are coupled hierarchically, has wide applications in areas such as machine learning and operations research. Recently, many first-order algorithms have been developed for solving bilevel problems with strongly convex and/or unconstrained lower-level problems; this special structure of the lower-level problem is needed to ensure the tractability of gradient computation (among other reasons). In this work, we deal with a class of more challenging BLO problems where the lower-level problem is non-convex and constrained. We propose a novel approach that approximates the value function of the lower-level problem by first sampling a set of feasible solutions and then constructing an equivalent convex optimization problem. This convexified value function is then used to construct a penalty function for the original BLO problem. We analyze the properties of the original BLO problem and the newly constructed penalized problem by characterizing the relation between their KKT points, as well as the local and global minima of the two problems. We then develop a gradient descent-based algorithm to solve the reformulated problem, and establish its finite-time convergence guarantees. Finally, we conduct numerical experiments to corroborate the theoretical performance of the proposed algorithm. |
| title | A Discretization Approach for Bilevel Optimization with Low-Dimensional and Non-Convex Lower-Level |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2505.10830 |