CS Paper Radar

Disciplined Bilevel Programming

Hao Zhu, Joschka Boedecker

cs.CE math.OCcs.LGcs.MS ·submitted 2026-09-01 03:22 UTC · v3
code/data

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

On solving integer bilevel optimization problems with a non-convex quadratic follower objective function using disjunctive cuts

cs.DM math.OC ·2026-10-01 ·Kübra Tanınmış, Elisabeth Gaar, Jon Lee, Ivana Ljubić, Markus Sinnl
similarity 0.66
Abstract

In this work, we study bilevel optimization problems where all variables are integer, all constraints and the leader objective function are linear, and the follower objective function is non-convex quadratic. Relying on bilevel-free sets derived from improving directions, we develop a disjunctive cut approach to exclude bilevel-infeasible solutions within a branch-and-cut algorithm. We show that our disjunctive cuts can be obtained by solving a cut generating linear program. Furthermore, we discuss conditions that allow the number of disjuncts in the cut generating linear program to be reduced, and we propose several strategies to identify improving directions and generate disjunctive cuts efficiently. We evaluate various aspects of the proposed branch-and-cut algorithm on both convex instances from the literature that fit our setting and new non-convex instances and compare the performance of our best approach with existing state-of-the-art approaches, which we significantly outperform.

0.21

Newton-Based Methods for Bilevel Optimization Beyond Lower-Level Strong Convexity

cs.LG math.OC ·2026-10-19 ·Youran Dong, Junfeng Yang, Wei Yao, Jin Zhang
similarity 0.61
Abstract

Bilevel optimization provides a framework for machine learning tasks such as hyperparameter optimization, data reweighting, and meta-learning. Existing Newton-based bilevel methods typically rely on the classical hypergradient formula, which is generally unavailable when lower-level solutions are nonunique and the lower-level Hessian is singular. We develop two Newton-based methods beyond lower-level strong convexity by exploiting curvature shared by the lower-level and multiplier updates. Newton-based GALET handles potentially singular lower-level curvature under a positive spectral-gap condition, exploiting its range structure to avoid the squared-Hessian multiplier system used in GALET. Newton-based BAMM uses a strongly convex aggregation model when the lower-level objective is convex and the upper-level objective is strongly convex in the lower-level variable. We establish convergence guarantees and improved complexity bounds relative to GALET and sl-BAMM under the corresponding assumptions. We further introduce GNBO, a generalized Newton-based framework that captures the shared-curvature structure of the proposed methods and several existing Newton and quasi-Newton bilevel methods. Experiments on synthetic problems, data hyper-cleaning, and GPT-2 data reweighting evaluate the proposed methods across different bilevel learning tasks.

0.07

Mathematical Programming in Machine Learning and Artificial Intelligence: A Unified Taxonomy of Models and Applications

cs.AI math.OC ·2026-09-07 ·Chaosheng Dong
similarity 0.59
Abstract

Mathematical programming provides a common language for many decisions embedded in modern machine-learning (ML) and artificial-intelligence (AI) systems: selecting retrieval context, routing tokens, allocating inference compute, fitting structured predictors, protecting against distribution shift, and balancing competing objectives. However, the relevant literature is fragmented across optimization, information retrieval, recommendation, natural-language processing, computer vision, and learning theory. This paper organizes various applications under common mathematical programming paradigms: linear, quadratic, binary and mixed-integer, conic, bilevel, multi-objective, inverse, distributionally robust, submodular, and min--max optimization. We normalize the models with a mostly unified notation and, for every application, identify inputs, decision variables, a principal formulation, structural properties, solution strategies, and limitations. Across paradigms, we compare tractability, relaxation quality, decomposition, approximation guarantees, and scalability bottlenecks. The paper shows that mathematical programming is most useful not as a claim that all learning is LP or MIP, but as a disciplined interface between predictions and constrained decisions.

0.12

Smoothed Gradient Method for Nonconvex Federated Stochastic Bilevel Optimization

cs.LG ·2026-10-04 ·Xinwen Zhang, Peiran Yu, Zhaosong Lu, Hongchang Gao
similarity 0.57
Abstract

In recent years, federated stochastic bilevel optimization has attracted increasing attention due to its wide range of applications in machine learning. To reduce the computational overhead associated with second-order Hessian and Jacobian matrices, several first-order methods have been proposed. However, existing methods typically impose restrictive assumptions on the lower-level function, suffer from a strong dependence on the condition number in their convergence rates, and require different learning-rate scales for variables across the upper- and lower-level problems, limiting their practical applicability and complicating hyperparameter tuning. To address these challenges, we propose a stochastic doubly smoothed gradient method for nonconvex federated stochastic bilevel optimization problems, which decouples the learning rates of upper- and lower-level variables and does not require a strongly-convex lower-level loss function. We establish rigorous theoretical guarantees for the proposed algorithm, demonstrating an improved convergence rate of $O(κ^{15/2}/ε^5)$ and a communication complexity of $O(κ^{4}/ε^3)$, where $κ$ denotes the condition number and $ε$ represents the solution accuracy. Notably, these bounds exhibit significantly better dependence on the condition number $κ$ than those of existing methods. Extensive experiments validate the effectiveness of our algorithm.

0.07

Generation of Custom Solvers in Rust for Convex Optimization

cs.CE math.OCcs.LGcs.MS ·2026-09-12 ·Hao Zhu, Joschka Boedecker
code/data similarity 0.57
Abstract

We introduce cvxgenrust, an open-source tool for generating custom Rust code that solves families of parameterized convex optimization problems modeled in CVXPY. cvxgenrust canonicalizes a problem family, extracts affine maps to Clarabel cone-program data, and generates a specialized Rust crate that updates parameters and calls Clarabel natively at runtime. The generated solver can also be exposed to Python and registered as a custom CVXPY solver. Our code generator supports a wide range of convex optimization problems up to semidefinite programs and exponential-cone problems. Numerical experiments show reduced runtime relative to direct CVXPY solves and performance comparable to CVXPYgen on shared problem classes.

0.36

Scen-Opt: A Scenario Optimization Toolbox for Data-Driven Convex Programming

cs.MS cs.LGeess.SYmath.OC ·2026-10-06 ·Ben Wooding, Simone Garatti, Marco C. Campi, Abolfazl Lavaei
code/data similarity 0.56
Abstract · 49 pages. Software archived at https://doi.org/10.5281/zenodo.23177690 (v1.0); source code at https://github.com/Kiguli/Scen-Opt; web app at…

The scenario approach is a well-established statistical framework for data-driven decision-making. In particular, in data-driven optimization, the scenario approach unveils how the problem structure governs out-of-sample generalization, and offers a principled basis for assessing and certifying the reliability of the optimal solution as per constraint satisfaction. Despite its strong theoretical development and wide applicability, no software toolbox has been available to date that enables user-friendly, data-driven convex optimization within the scenario-approach framework. In this paper, we introduce Scen-Opt, an open-source software tool that integrates convex programming with data samples while providing statistical guarantees grounded in scenario theory. Scen-Opt is implemented in Python, supporting data-driven linear, quadratic, and semidefinite programming, and offers a Python-based web application with an intuitive and reactive graphical user interface (GUI) built using modern web technologies. Scen-Opt can be used directly through its online interface or installed locally, accommodating both manual input and data-file uploads (CSV, JSON, TXT, TSV, MAT, Excel, NPY, NPZ, Parquet). Built on a Python backend with a modern JavaScript frontend, Scen-Opt offers a highly user-friendly experience and efficient usability across desktops, laptops, tablets, and mobile devices. In this paper, Scen-Opt is applied to a set of representative benchmarks, demonstrating its practical effectiveness for data-driven convex optimization with guaranteed performance.

0.39

Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles

cs.LG math.OCstat.ML ·2026-10-17 ·Qihao Zhou, Shanshui Niu
similarity 0.56
Abstract · 23 pages, 2 figures, 1 table

We study nonconvex--strongly-convex bilevel optimization with finite-sum objectives and fully first-order oracles. We propose Sampled Implicit Corrections for Bilevel Optimization (SICBO), which combines a penalty approximation with variance-reduced corrections for the lower-level variables. Under componentwise lower strong convexity, SICBO finds a point $x$ satisfying $\mathbb{E}\|\nablaΦ(x)\|^2\le\varepsilon^2$ within $\tilde{O}(N+\sqrt{N}κ^{7/2}\varepsilon^{-2})$ component-gradient calls, where $N$ is the total number of components and $κ$ is the normalized lower-level condition number. The bound achieves square-root finite-sum dependence using only gradients and preserves the best known deterministic fully first-order condition-number exponent for smooth problems. Our improvement follows from a curvature-dependent bound for nonlinear correction errors, which permits epochs of length $\tildeΘ(\sqrt{N/κ})$ with batches of size $\tildeΘ(\sqrt{Nκ})$. A single-level reduction shows that the dependence on $N$ and $\varepsilon$ is optimal up to logarithmic factors for fixed $κ$.

0.11

On the Tightness of Standard Relaxations for Mixed-Integer Bilevel Linear Programs

cs.CC math.OC ·2026-09-09 ·Sergey S. Ketkov, Oleg A. Prokopyev
theory similarity 0.56
Abstract

Exact algorithms for solving mixed-integer bilevel linear programs (MIBLPs) typically rely on sequences of lower and upper bounds that converge to the optimal value. These procedures are commonly initialized using the single-level relaxation (SLR), obtained by omitting the follower's optimality condition and solving the resulting single-level optimization problem. In this paper, we investigate whether, for broad classes of MIBLPs, the resulting standard bounds admit uniform improvements that can be computed within the same computational complexity regime. For pure continuous bilevel linear programs, we show that, unless $P = NP$, neither the SLR-based lower bound nor its associated upper bound can be uniformly improved in polynomial time, even for the class of min-max problems. We then extend this analysis to the class of pure integer min-max bilevel linear programs under the assumption that the polynomial hierarchy does not collapse. First, we show that the continuous relaxation of the SLR admits no uniform polynomial-time computable improvement. We then prove that neither the SLR itself nor its associated upper bound admits a uniform improvement by a polynomial-time algorithm with access to a mixed-integer linear programming (MILP) oracle. Importantly, this rules out uniform improvements by iterative MILP-based approaches, including cutting-plane-based and decomposition algorithms. Overall, our results demonstrate that the SLR-based bounds are, in a complexity-theoretic sense, unimprovable systematically within their natural computational regimes.

0.24