Convergence, Duality and Well-Posedness in Convex Bilevel Optimization
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_ | 1866918148631953408 |
|---|---|
| author | Giang-Tran, Khanh-Hung Ho-Nguyen, Nam Kılınç-Karzan, Fatma Shen, Lingqing |
| author_facet | Giang-Tran, Khanh-Hung Ho-Nguyen, Nam Kılınç-Karzan, Fatma Shen, Lingqing |
| contents | We consider the convex bilevel optimization problem, also known as simple bilevel programming. There are two challenges in solving convex bilevel optimization problems. Firstly, strong duality is not guaranteed due to the lack of Slater constraint qualification. Secondly, we demonstrate through an example that convergence of algorithms is not guaranteed even when usual subotimality gap bounds are present, due to the possibility of encountering super-optimal solutions. We show that strong duality (but not necessarily dual solvability) is exactly equivalent to ensuring correct asymptotic convergence of both inner and outer function values, and provide a simple condition that guarantees strong duality. Unfortunately, we also show that this simple condition is not sufficient to guarantee convergence to the optimal solution set. We draw connections to Levitin-Polyak well-posedness, and leverage this together with our strong duality equivalence to provide another condition that ensures convergence to the optimal solution set. We also discuss how our conditions have been implicitly present in existing algorithmic work. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_18304 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Convergence, Duality and Well-Posedness in Convex Bilevel Optimization Giang-Tran, Khanh-Hung Ho-Nguyen, Nam Kılınç-Karzan, Fatma Shen, Lingqing Optimization and Control 90C25, 90C30, 90C46 We consider the convex bilevel optimization problem, also known as simple bilevel programming. There are two challenges in solving convex bilevel optimization problems. Firstly, strong duality is not guaranteed due to the lack of Slater constraint qualification. Secondly, we demonstrate through an example that convergence of algorithms is not guaranteed even when usual subotimality gap bounds are present, due to the possibility of encountering super-optimal solutions. We show that strong duality (but not necessarily dual solvability) is exactly equivalent to ensuring correct asymptotic convergence of both inner and outer function values, and provide a simple condition that guarantees strong duality. Unfortunately, we also show that this simple condition is not sufficient to guarantee convergence to the optimal solution set. We draw connections to Levitin-Polyak well-posedness, and leverage this together with our strong duality equivalence to provide another condition that ensures convergence to the optimal solution set. We also discuss how our conditions have been implicitly present in existing algorithmic work. |
| title | Convergence, Duality and Well-Posedness in Convex Bilevel Optimization |
| topic | Optimization and Control 90C25, 90C30, 90C46 |
| url | https://arxiv.org/abs/2509.18304 |