# Sequential QCQP for Bilevel Optimization with Line Search

arXiv: https://arxiv.org/abs/2505.14647 · HTML: https://mlsanity.com/paper/2505.14647/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 35 references that are in the map.
- First posted on arXiv 20 May 2025.

## Builds on (most cited first, 26 of 26)

- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Control Barrier Function Based Quadratic Programs for Safety Critical Systems](https://mlsanity.com/paper/1609.06408/) (2016)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Forward and Reverse Gradient-Based Hyperparameter Optimization](https://mlsanity.com/paper/1703.01785/) (2017)
- [Hyperparameter optimization with approximate gradient](https://mlsanity.com/paper/1602.02355/) (2016)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [Truncated Back-propagation for Bilevel Optimization](https://mlsanity.com/paper/1810.10667/) (2018)
- [On the Iteration Complexity of Hypergradient Computation](https://mlsanity.com/paper/2006.16218/) (2020)
- [BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach](https://mlsanity.com/paper/2209.08709/) (2022)
- [A Fully First-Order Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2301.10945/) (2023)
- [On Penalty-based Bilevel Gradient Descent Method](https://mlsanity.com/paper/2302.05185/) (2023)
- [Penalty Method for Inversion-Free Deep Bilevel Optimization](https://mlsanity.com/paper/1911.03432/) (2019)
- [Value Function Based Difference-of-Convex Algorithm for Bilevel Hyperparameter Selection Problems](https://mlsanity.com/paper/2206.05976/) (2022)
- [Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifold](https://mlsanity.com/paper/2303.09261/) (2023)
- [A Primal-Dual Approach to Bilevel Optimization with Multiple Inner Minima](https://mlsanity.com/paper/2203.01123/) (2022)
- [Control Barrier Function Based Design of Gradient Flows for Constrained Nonlinear Programming](https://mlsanity.com/paper/2204.01930/) (2022)
- [A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints](https://mlsanity.com/paper/2406.10148/) (2024)
- [Fast UAV Trajectory Optimization using Bilevel Optimization with Analytical Gradients](https://mlsanity.com/paper/1811.10753/) (2018)
- [Robust Safety under Stochastic Uncertainty with Discrete-Time Control Barrier Functions](https://mlsanity.com/paper/2302.07469/) (2023)
- [BIG Hype: Best Intervention in Games via Distributed Hypergradient Descent](https://mlsanity.com/paper/2303.01101/) (2023)
- [Global Convergence of Arbitrary-Block Gradient Methods for Generalized Polyak-Lojasiewicz Functions](https://mlsanity.com/paper/1709.03014/) (2017)
- [Bilevel Optimization for Planning through Contact: A Semidirect Method](https://mlsanity.com/paper/1906.04292/) (2019)
- [Perturbed Gradient Descent via Convex Quadratic Approximation for Nonconvex Bilevel Optimization](https://mlsanity.com/paper/2504.17215/) (2025)
- [Practical Considerations for Discrete-Time Implementations of Continuous-Time Control Barrier Function-Based Safety Filters](https://mlsanity.com/paper/2404.12329/) (2024)
- [Bilevel Optimization for Real-Time Control with Application to Locomotion Gait Generation](https://mlsanity.com/paper/2409.12366/) (2024)
- [Safe Gradient Flow for Bilevel Optimization](https://mlsanity.com/paper/2501.16520/) (2025)

## Abstract (arXiv)

Bilevel optimization involves a hierarchical structure where one problem is nested within another, leading to complex interdependencies between levels. We propose a single-loop, tuning-free algorithm that guarantees anytime feasibility, i.e., approximate satisfaction of the lower-level optimality condition, while ensuring descent of the upper-level objective. At each iteration, a convex quadratically-constrained quadratic program (QCQP) with a closed-form solution yields the search direction, followed by a backtracking line search inspired by control barrier functions to ensure safe, uniformly positive step sizes. The resulting method is scalable, requires no hyperparameter tuning, and converges under mild local regularity assumptions. We establish an O(1/k) ergodic convergence rate in terms of a first-order stationary metric and demonstrate the algorithm's effectiveness on representative bilevel tasks.