Research map / Optimization / Nonconvex and smooth optimization
A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes BLOCC, a fully first-order, projection-free penalty method with a primal-dual max-min inner solver for bilevel optimization with lower-level coupled convex inequality constraints, achieving O~(eps^-2.5) (and O~(eps^-1.5) for affine constraints) complexity.
Problem
Bilevel optimization where the lower-level problem has coupled inequality constraints g^c(x,y)<=0 that link upper- and lower-level variables; existing methods either need joint projections onto the coupled constraint set or lack finite-time guarantees.
Approach
Reformulates the BLO as a single-level max-min penalty problem using a Lagrangian-based penalty on g(x,y)-v(x) plus a Lagrange term, derives closed-form gradients for v and F_gamma, and solves the inner max-min by primal-dual gradient steps so that no joint projection onto the coupled constraint set is needed.
Key results
- On the 26-node Seville network (NV=49,216), BLOCC converged in about 6.8e4 s with UL utility 98.40 (gamma=2), while LV-HBA failed to converge within 24 hours on networks beyond 3 nodes.
- On the SVM diabetes experiment, BLOCC attained over 0.76 test accuracy within the first 2 iterations and outperformed GAM significantly, comparable to LV-HBA.
- Theoretical complexity is O~(eps^-2.5) for general convex coupled constraints and O~(eps^-1.5) when the constraint is affine in y.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use BLOCC instead of LV-HBA | Transportation, NN=3 · Transportation, NN=3 | Runtime (s): 3.51e2 -> 2.00e1 | Helped |
| use BLOCC instead of LV-HBA | Transportation, NN=3 · Transportation, NN=3 | UL utility: 1.53 -> 1.69 | Mixed |
| increase γ from 2 to 3 (ablation) | BLOCC · Transportation, NN=3 | UL utility: 1.07 -> 1.69 | Helped |
| increase γ from 3 to 4 (ablation) | BLOCC · Transportation, NN=3 | UL utility: 1.69 -> 1.71 | Helped |
| increase γ from 2 to 3 (ablation) | BLOCC · Transportation, NN=9 | UL utility: 8.09 -> 10.37 | Helped |
| increase γ from 3 to 4 (ablation) | BLOCC · Transportation, NN=9 | UL utility: 10.37 -> 11.04 | Helped |
| increase γ from 2 to 3 (ablation) | BLOCC · Transportation, NN=26 (Seville) | UL utility: 98.40 -> 111.39 | Helped |
| increase γ from 3 to 4 (ablation) | BLOCC · Transportation, NN=26 (Seville) | UL utility: 111.39 -> 138.78 | Helped |
| use BLOCC instead of GAM | SVM training · diabetes and fourclass | test accuracy | Helped |
| use BLOCC instead of LV-HBA | SVM training · diabetes and fourclass | test accuracy | No clear effect |
| use BLOCC instead of LV-HBA | Transportation · NN=9 and NN=26 (Seville) | Runtime (s) | Helped |
Surprising findings
- Using the gradient of v(x) without the Lagrange multiplier (as in prior penalty methods) can point in the opposite direction to the true gradient, per their toy example.
Limitations
- General case complexity O~(eps^-2.5) is worse than the O(eps^-1.5) of affine case; requires LICQ and bounded Lagrange multipliers.
- Assumes strong convexity of the lower-level objective and convexity of constraints in y; GAM/BVFSM not applicable to lower-level domain constraints in the transportation experiment.
- Experiments compare only against LV-HBA and GAM on a limited set of problems.
Experimental setup
Datasets: diabetes fourclass Seville transportation network
Benchmarks: diabetes SVM fourclass SVM Seville transportation network design toy bilevel example
Metrics: test accuracy upper-level loss lower-level loss runtime (s) upper-level utility
Baselines: LV-HBA GAM
Builds on: penalty-based bilevel reformulation implicit gradient descent LV-HBA Danskin's theorem
Closest papers by meaning
- TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization (ICML 2025 · similarity 0.89)
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (NeurIPS 2024 · similarity 0.88)
- Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds (NeurIPS 2024 · similarity 0.88)
- A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization (NeurIPS 2025 · similarity 0.88)
- Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems (NeurIPS 2026 · similarity 0.88)
- A Single-Loop Gradient Algorithm for Pessimistic Bilevel Optimization via Smooth Approximation (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.