A sensitivity-based method for bilevel optimization problems: Theoretical analysis and computational performance
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910265436536832 |
|---|---|
| author | Nolasco, Eduardo King, Ross D. Vassiliadis, Vassilios S. |
| author_facet | Nolasco, Eduardo King, Ross D. Vassiliadis, Vassilios S. |
| contents | Bilevel optimization provides a powerful framework for modelling hierarchical decision-making systems. This work presents a sensitivity-based algorithm that addresses the bilevel structure directly by treating the lower-level optimal solution as an implicit, locally differentiable function of the upper-level variables, thereby avoiding classical single-level reformulations. Under standard regularity assumptions on the lower level, an adjoint-based representation of the reduced upper-level gradient is derived, replacing explicit construction of the sensitivity Jacobian with a single linear adjoint solve per iteration and reducing gradient evaluation cost by a factor equal to the upper-level dimension. The reduced problem is solved within an Augmented Lagrangian framework, with inner subproblems managed by an L-BFGS-B quasi-Newton solver. Convergence to KKT points of the reduced problem is established, and these points are shown to be equivalent to S-stationary solutions of the associated mathematical programme with complementarity constraints under MPEC-LICQ. Computational experiments on benchmark bilevel problems validate the method's correctness and robustness, and demonstrate the effectiveness of a pragmatic dual-criterion stopping condition in handling the asymmetric primal-dual convergence rates characteristic of augmented Lagrangian methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_01487 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A sensitivity-based method for bilevel optimization problems: Theoretical analysis and computational performance Nolasco, Eduardo King, Ross D. Vassiliadis, Vassilios S. Optimization and Control 90C26 (Primary) 90C30, 90C31, 90C46 (Secondary) Bilevel optimization provides a powerful framework for modelling hierarchical decision-making systems. This work presents a sensitivity-based algorithm that addresses the bilevel structure directly by treating the lower-level optimal solution as an implicit, locally differentiable function of the upper-level variables, thereby avoiding classical single-level reformulations. Under standard regularity assumptions on the lower level, an adjoint-based representation of the reduced upper-level gradient is derived, replacing explicit construction of the sensitivity Jacobian with a single linear adjoint solve per iteration and reducing gradient evaluation cost by a factor equal to the upper-level dimension. The reduced problem is solved within an Augmented Lagrangian framework, with inner subproblems managed by an L-BFGS-B quasi-Newton solver. Convergence to KKT points of the reduced problem is established, and these points are shown to be equivalent to S-stationary solutions of the associated mathematical programme with complementarity constraints under MPEC-LICQ. Computational experiments on benchmark bilevel problems validate the method's correctness and robustness, and demonstrate the effectiveness of a pragmatic dual-criterion stopping condition in handling the asymmetric primal-dual convergence rates characteristic of augmented Lagrangian methods. |
| title | A sensitivity-based method for bilevel optimization problems: Theoretical analysis and computational performance |
| topic | Optimization and Control 90C26 (Primary) 90C30, 90C31, 90C46 (Secondary) |
| url | https://arxiv.org/abs/2510.01487 |