2025/09/22 by Khanh-Hung Giang-Tran, Nam Ho-Nguyen, Giang-Tran, Khanh-Hung +5
Computer Science · Decision Sciences · Mathematics · #90C25 #90C30 #90C46 #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Risk and Portfolio Optimization
paper · pdf · doi:10.48550/arxiv.2509.18304
openalex publication_date 2025/09/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.