Disciplined Bilevel Programming

Hao Zhu; Joschka Boedecker

Source-linked AI summary

Disciplined Bilevel Programming

Hao Zhu, Joschka Boedecker

arXiv:2609.00644v1Sep 1, 2026math.OCcs.CEcs.LGcs.MS

TL;DR

Bilevel optimization is difficult to solve and often requires tedious, error-prone reformulation from natural models into solver-compatible canonical forms. DBLP automates this process for disciplined upper problems and convex lower problems, while BLVPY approximately solves the resulting reformulations and demonstrates the approach across application domains.

Problem
Existing bilevel solvers require substantial manual analysis and reformulation, including verifying lower-level conditions and encoding dual variables and complementarity constraints.
Method
DBLP canonicalizes suitable convex lower problems into conic form, constructs conic KKT single-level reformulations, relaxes complementarity, and solves them with gap continuation through BLVPY.
Results
BLVPY models and solves bilevel problems across several application domains using compact, human-readable specifications close to the original mathematical formulation.
Takeaways & Limitations
By separating high-level model specification from low-level transformations and solver interfacing, DBLP is intended to make bilevel programming more accessible in practice.
Takeaways & Limitations
DBLP and gap continuation do not guarantee global optimality because their single-level reformulations and relaxations are generally nonconvex and solved approximately.

Abstract

from arXiv · show

Bilevel optimization provides a natural modeling language for hierarchical decision problems. However, applying existing numerical solvers usually requires substantial manual analysis and reformulation. In this paper, we introduce disciplined bilevel programming (DBLP), a symbolic framework that allows users to specify and solve optimistic bilevel problems in a high-level, human-readable way that is close to the mathematical formulation. For problems with a disciplined nonlinear upper problem and a convex lower problem satisfying the disciplined parameterized programming rules, DBLP automatically canonicalizes the lower problem into conic form and constructs an equivalent single-level reformulation using the conic Karush-Kuhn-Tucker conditions. We relax the resulting complementarity constraint and use a gap continuation procedure to approximately solve a sequence of smooth nonlinear problems. We implement DBLP in the open-source Python package BLVPY, an extension of CVXPY for bilevel programming. We demonstrate the modeling and solution capabilities of BLVPY on a range of bilevel optimization problems from several application domains. The proposed framework and implementation allow users to specify and solve bilevel optimization problems within a few lines of code, without prior expertise in bilevel modeling and numerical optimization.

1 Introduction

Bilevel optimization models hierarchical decisions but can be difficult to solve and often requires substantial manual reformulation. DBLP addresses this gap by connecting natural bilevel formulations to solver-ready single-level problems.

Problem setting: Bilevel optimization lets one decision maker anticipate another's optimal response through an upper problem containing a lower optimization problem.The lower solution set is parameterized by the upper variable, and optimistic semantics select the lower optimizer most favorable to the upper objective.
Challenges: Exact bilevel optimization can be NP-hard, so practitioners often use reformulations, approximations, or heuristics without global-optimality guarantees.The difficulty remains even when the involved constraint functions are convex.
Existing methods: KKT reformulations replace convex lower-level optimality with feasibility, stationarity, dual feasibility, and complementarity, but require convexity and suitable constraint qualifications.Exact complementarity also causes standard nonlinear-programming constraint qualifications to fail, motivating regularization and smoothing approaches.
Limitations: Existing bilevel workflows leave a gap between natural mathematical formulations and solver-required canonical forms, making reformulation tedious and error-prone.Users must introduce dual variables and encode complementarity conditions correctly for the selected solver.
Contribution: DBLP provides a symbolic framework for specifying compatible bilevel problems in human-readable form and automatically canonicalizing them into solver-compatible single-level problems.BLVPY implements the associated domain-specific language as an open-source Python package.

2 Disciplined optimization

Disciplined optimization uses compositional rules to verify structural properties and automatically canonicalize compatible models. This paper combines disciplined convex, parameterized, and nonlinear programming concepts to support bilevel modeling.

Disciplined convex programming: Disciplined convex programming constructs convex models from atomic functions and composition rules that preserve convexity.A composition-tree traversal can verify the curvature of objectives and constraints constructively.
Disciplined convex programming: DCP permits convex objectives and constraints through curvature rules for minimization, maximization, and inequality or equality relations.Minimization objectives must be convex, maximization objectives concave, and equality sides affine.
Canonicalization: DCP-compatible models can be automatically canonicalized, so users specify expressions without manually constructing solver-specific forms.CVXPY is among the programming-language implementations of this framework.
Bilevel extension: The paper extends CVXPY with disciplined bilevel modeling, addressing the absence of disciplined bilevel implementations in existing domain-specific languages.The resulting framework combines DPP for lower problems with DNLP for broader nonlinear modeling.
Disciplined parameterized programming: Disciplined parameterized programming restricts parameter use beyond DCP and guarantees affine-solve-affine canonicalization maps for compliant problems.It classifies parameters as affine expressions and restricts products involving parameter-affine and parameter-free expressions.
Disciplined nonlinear programming: Disciplined nonlinear programming extends the atom-and-composition approach to smooth nonconvex optimization and canonicalizes admissible nonsmooth expressions into smooth nonlinear programs.Auxiliary variables with epigraph or hypograph constraints allow standard smooth nonlinear solvers to handle these constructs.

3 Disciplined bilevel programming

DBLP combines a DNLP-compliant upper problem with a DPP-compliant convex lower problem, canonicalizes the lower level conically, and replaces it with equivalent KKT conditions. The resulting lifted problem is DNLP-compliant but nonconvex because of complementarity.

DBLP rules: A disciplined bilevel program has DNLP-compliant upper objectives and constraints and a DPP-compliant convex lower problem parameterized by the upper variable.These rules enable automatic canonicalization of the bilevel problem into a single-level formulation.
Lower-level canonicalization: The lower problem is canonicalized into conic form with affine problem data in the upper parameter.The canonical objective includes c(x)^T u + d(x), while the constraints use A(x)u + s = b(x) and s ∈ K.
Optimality conditions: Under lossless canonicalization, finite attainment, and Slater-type assumptions, conic strong duality makes the KKT conditions necessary and sufficient for lower-level optimality.The recovery map ρ converts canonical variables into the original lower variable.
Single-level reformulation: The KKT conditions yield a lifted single-level nonlinear program with upper variables, canonical lower variables, slacks, and dual variables.The complementarity equation λ^T s = 0 is added alongside primal and dual feasibility, with y = ρ(u).
Reformulation properties: The lifted reformulation preserves DNLP compliance except for the bilinear, nonconvex complementarity relation, while cone-membership constraints remain convex.Consequently, DBLP-compliant reformulations can still be canonicalized into smooth nonlinear programs for standard nonlinear solvers.
Example: In the minimal example, the conic canonicalization is lossless because feasible epigraph lifts attain t = |z − x| and recover the complete lower solution set.The construction uses an epigraph variable and the coordinate recovery map ρ(u) = z.

4 Approximate optimality and continuation

The paper relaxes exact complementarity to avoid numerical difficulties, then solves a sequence of progressively tighter nonlinear problems. The relaxation certifies lower-level objective accuracy, and strong convexity additionally yields solution-distance guarantees.

Exact complementarity can create degenerate feasible geometry, causing standard nonlinear-programming constraint qualifications to fail and creating numerical difficulties.
The relaxed formulation replaces exact complementarity with a tolerance parameter ϵ while retaining the variables and conic constraints of the single-level reformulation.
Every feasible relaxed point recovers a lower-feasible point whose objective is at most ϵ-suboptimal, while the actual complementarity gap provides an a posteriori suboptimality certificate.
Under µ-strong convexity, the lower solution is unique and objective accuracy controls solution accuracy at rate O(√ϵ).To ensure ∥ρ(u) − y⋆(x)∥2 ≤ δ, it suffices to choose ϵ ≤ µδ^2/2.
Gap continuation repeatedly solves the relaxed problem, reduces ϵ by a factor β ∈ (0, 1), and uses each solution to initialize the next problem until ϵ is sufficiently small.Warm starts can make gradually tightened relaxations effective in practice, although the nonlinear subproblems are generally solved only locally and approximately.
The appendix provides an idealized consistency result for globally solved relaxations, but this does not guarantee convergence of the practical continuation algorithm.

5 Implementation

BLVPY implements DBLP as an open-source CVXPY extension with audited canonicalization, initialization, continuation, multistart, and independent residual verification. Its current scope covers DBLP-compliant problems whose lower levels have exact LP or SOCP representations.

BLVPY is an open-source Python implementation of DBLP built as an extension of CVXPY for bilevel optimization.
The solution pipeline has four stages: audited lower-problem canonicalization, lifted-point initialization, gap continuation through a DNLP solver, and independent verification.
The current release supports optimistic bilevel problems whose lower problems are DPP-compliant and canonicalizable into exact LP or SOCP conic forms.
Canonicalization verifies DCP and DPP compliance, audits expression and reduction chains, and extracts affine maps and the recovery map ρ.The audited atom set includes restrictions for geo_mean, pnorm, and power representations when approximation error is nonzero.
Initialization preserves user-specified upper values or derives values from finite and infinite bounds, then projects onto a DCP upper-feasible set when possible.A canonical lower conic solve initializes the lifted variables and the original lower variables through ρ.
Continuation updates only ϵ, uses accepted points as warm starts, and supports multistart paths that return the best accepted upper objective at the final tolerance.The default schedule starts at ϵ(0) = 10^-1, contracts by 0.1, and terminates at 10^-6.
BLVPY independently recomputes feasibility and optimality residuals after each solve and accepts points only when solver status and requested tolerances are satisfied.
A basic example specifies and solves a bilevel problem in a short CVXPY-style script, while prob.solve() performs validation, canonicalization, and gap continuation.

6 Examples

BLVPY demonstrates DBLP across examples in machine learning, security, power planning, traffic tolling, structural design, and control. The returned solutions approximately optimize the corresponding upper-level objectives and satisfy the reported validation checks.

The examples span ridge-regression hyperparameter tuning, Stackelberg security, renewable-capacity planning, Braess-network tolling, truss design, and MPC imitation learning.These examples illustrate modeling capabilities across several application domains.
Ridge regression auto-tuning: The ridge-regression solution selects a regularization parameter that approximately minimizes validation loss.The black-cross solution in Figure 1 corresponds to the minimum of the validation-loss curve.
Stackelberg security game: The optimized security allocation reduces expected defender loss by approximately 80% versus uniform coverage and 90% versus no coverage.The comparison uses a randomly generated instance and normalized quantities.
Renewable capacity planning: The renewable-capacity solution approximately minimizes total renewable and thermal planning cost while producing an optimal dispatch under demand and the renewable limit.The lower plot shows costs versus capacity, and the upper plot shows the corresponding renewable and thermal dispatch.
Planar truss design: The optimized truss design reduces compliance from 1.90 to 1.35, approximately 30%, without additional material by allocating more material to higher-stress members.The comparison is against a uniform design with the same total material volume.
Differentiable model predictive control: In MPC imitation learning, BLVPY-tuned regularization weights reproduce expert behavior in nominal operation and under an unannounced load-torque pulse.The evaluation uses a 36-step receding-horizon rollout and compares against uniform weights δ = η = 0.5.

7 Discussion

DBLP automates bilevel reformulation and solver interfacing for supported problems, while examples demonstrate compact modeling across application domains. The resulting approximate solutions lack global-optimality guarantees but provide lower-level feasibility certificates.

Framework and implementation: DBLP automatically constructs a conic-KKT single-level reformulation and solves it with gap continuation for DNLP-compliant upper and DPP-compliant convex lower problems.BLVPY implements this workflow as a human-readable CVXPY extension.
Limitations and guarantees: DBLP and gap continuation do not guarantee global optimality, even when upper-level objectives and constraints are convex.The single-level reformulation and its relaxation are generally nonconvex and solved approximately by nonlinear solvers.
Limitations and guarantees: If the relaxed constraints are satisfied within tolerance ϵ, the recovered lower point is feasible and at most ϵ-suboptimal for the lower problem.The examples show that such approximately bilevel-feasible points are often good or acceptable in practice.
Framework and implementation: BLVPY represents examples from several application domains in a few lines of code while handling low-level transformations and solver interfacing automatically.The framework is intended to make bilevel programming more accessible in practice.
Application evidence: Figure 8 compares angular speed, current, and control input trajectories for untuned and learned controllers during an unannounced load torque pulse.Target values and safety limits are shown alongside expert demonstration and validation trajectories.

A Proofs

The appendix provides detailed proofs for results stated in the main text.

The appendix contains detailed proofs of the results stated in the main text.

A.1 Proof of proposition 4.1

The proof establishes the lower-level gap identity through primal and dual feasibility, then uses losslessness and recovery to relate canonical and original lower solutions.

Combining the inequalities completes the proof of the proposition.
Primal and dual feasibility reduce the canonical primal-dual gap to the complementarity product sTλ.The derivation substitutes b(x)=A(x)u+s and A(x)Tλ=−c(x).
Weak duality bounds the canonical primal-dual gap relative to the canonical lower optimum q⋆(x).
Losslessness equates the original and canonical lower optimal values for every feasible parameter x.
The recovery map ρ(u) produces a feasible point for the original lower problem and preserves the relevant objective relation.

A.2 Proof of corollary 4.2

Strong convexity of the DPP-compliant lower problem makes its feasible-set minimizer unique, enabling a bound on recovered-point suboptimality.

DPP compliance makes the lower feasible set convex, and strong convexity therefore implies a unique lower minimizer.Two distinct optimal feasible points would have a feasible midpoint with strictly smaller objective value.
The lower solution set is consequently the singleton {y⋆(x)}.
For any feasible lifted point, the recovered point y=ρ(u) can be combined with y⋆(x) through convexity to form a lower-feasible point.
Using lower optimality and µ-strong convexity, the proof derives the recovered-point bound from the relaxed gap tolerance ϵ.

B Consistency of globally solved relaxations

Under lifted-compactness and problem assumptions, globally solving relaxed problems as ϵ decreases to zero yields accumulation points solving the exact reformulation. Their optimal values also converge to the exact reformulation’s optimal value, and the reformulation recovers globally optimal bilevel solutions.

Assumptions: Under the stated assumptions and lifted-compactness condition, the relaxation tolerances ϵ(k) decrease to zero while remaining bounded by ˜ϵ.Compactness is sufficient to ensure the lifted solution sequence has an accumulation point.
Consistency: Every accumulation point of globally optimal relaxed solutions is globally optimal for the exact single-level reformulation.The proof uses nested feasible sets, continuity, closed cones, and vanishing relaxed complementarity.
Consistency: The optimal values of the relaxed problems converge to the optimal value of the exact reformulation.Feasible-set nesting provides monotonicity, while continuity transfers the limiting objective value.
Recovery: The recovery map sends exact-reformulation solutions to feasible bilevel solutions without changing the upper objective, so accumulation points recover globally optimal bilevel solutions.This correspondence relies on conic KKT conditions being necessary and sufficient for the convex lower problem.
Limitation: Without global solves, exact feasibility of limiting relaxed points can persist, but convergence to a globally optimal bilevel solution is not guaranteed.For locally or approximately solved relaxations, the lower-level certificate remains valid when the stated feasibility and relaxed complementarity conditions hold.