⚡ electrical engineering

On Stability in Optimistic Bilevel Optimization

This paper proposes a lifted formulation for optimistic bilevel optimization problems involving integer and disjunctive constraints that ensures stability under mild local calmness assumptions without requiring convexity or smoothness, while also enabling an outer approximation algorithm.

Original authors: Johannes O. Royset

Published 2026-08-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Johannes O. Royset

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of mathematical planning, there is a class of problems known as bilevel optimization. These are situations where one decision-maker, the leader, sets a course of action, but the outcome depends entirely on how a second decision-maker, the follower, reacts. The leader must choose a strategy that minimizes their own cost, but they can only do so by anticipating the follower's best response to that strategy. This structure appears everywhere, from setting taxes in an economy to training artificial intelligence models, where a system learns by predicting how data will be processed. However, these problems are notoriously fragile. In the real world, the data used to describe the follower's behavior is rarely perfect; it is often an estimate, a measurement with a slight error, or a simplified model. In traditional approaches, even a tiny, almost invisible change in this data can cause the predicted best response to swing wildly, leading to a completely different and often disastrous decision for the leader. This instability means that a solution that looks perfect on paper can collapse the moment the real world introduces a small imperfection.

Researchers at the University of Southern California have developed a new way to handle these fragile problems that remains steady even when the data is imperfect. Instead of trying to solve the problem exactly as it is written, which often leads to these wild swings, they constructed a "lifted" version of the problem. This new formulation adds a few extra variables and constraints that act as a buffer. Imagine the original problem as a tightrope walker balancing on a single wire; a slight breeze knocks them off. The new method is like giving that walker a long balancing pole. The pole doesn't change the destination, but it allows the walker to absorb small gusts of wind without falling. In this mathematical context, the "pole" consists of auxiliary variables that allow the system to slightly relax the strict rules of the follower's reaction. By doing so, the researchers created a formulation that does not break when the input data changes slightly.

The core of their discovery is that this new approach is fundamentally stable. The team proved that as the approximations of the data become more accurate, the solutions found by this new method naturally converge toward the true, correct solution of the original problem. Crucially, this stability holds even when the problem involves complex, non-smooth, or integer-based constraints, which are common in real-world scenarios like scheduling or logistics. Previous methods often required the problem to be perfectly smooth or convex—mathematical properties that ensure a nice, bowl-shaped landscape—to guarantee stability. This new approach works without those strict requirements, making it applicable to a much wider range of difficult, real-world situations. The researchers showed that the new method not only finds solutions that are close to the truth but also provides reliable bounds, telling decision-makers how good their current best guess really is, even while the data is still being refined.

To demonstrate that this theory works in practice, the team tested their method on several specific examples where traditional approaches failed. In one case, a tiny change in a constraint caused the standard method to produce a solution that was completely different from the original, while the new method produced a solution that smoothly approached the correct answer as the data improved. In another example involving simple integer choices, the standard approach became impossible to solve because the data became slightly infeasible, whereas the new method continued to provide valid, useful results. These tests confirmed that the added variables and the specific way the constraints were reorganized allowed the algorithm to navigate around the instabilities that plague older techniques.

The paper also outlines a practical algorithm for solving these new, lifted problems. Because the reformulated problem involves a large number of constraints that depend on the follower's possible actions, solving it directly is difficult. The researchers proposed an "outer approximation" strategy. This method starts by solving a simplified version of the problem with only a few constraints and then iteratively adds more constraints as needed, based on where the current solution fails to satisfy the full set of rules. This process is efficient and allows the use of standard, powerful computer solvers. In numerical tests, this algorithm successfully solved complex instances involving hundreds of variables and constraints, narrowing the gap between the best possible solution and the computed solution to a tiny fraction of a percent. The results showed that the method is not just theoretically sound but computationally viable, capable of handling the messy, non-convex, and integer-heavy problems that arise in machine learning and engineering.

Ultimately, this work offers a robust alternative to the current state of the art for a class of problems that are critical to modern decision-making. By accepting that data is never perfectly settled and building a formulation that accounts for that uncertainty, the researchers have provided a tool that yields meaningful decisions even when the inputs are imperfect. The method does not require the problem to be simplified or smoothed out to make it solvable; instead, it embraces the complexity and provides a stable path forward. For anyone relying on these types of hierarchical decisions, from policy makers to algorithm designers, this approach ensures that the answers they get are not just mathematical artifacts of a specific dataset, but reliable guides that hold up under scrutiny.

Technical Summary: On Stability in Optimistic Bilevel Optimization

Problem Statement
Bilevel optimization problems are inherently ill-posed in the sense that small perturbations in problem data (objective functions, constraints, or feasible sets) can lead to disproportionately large changes in the solution set. This instability is well-documented in variational analysis and persists even when the lower-level problem appears "nice" (e.g., convex with Slater conditions). In practical settings where data is often uncertain or approximated, blindly solving a bilevel problem using standard formulations may yield meaningless decisions. The paper addresses the challenge of constructing a formulation that remains stable under data perturbations, specifically within the optimistic bilevel setting where the upper-level decision maker anticipates the lower-level problem will select the most favorable optimal solution for the upper level.

Methodology: The Lifted Formulation
The author proposes a lifted formulation, denoted as $(P)_\nu$ , to approximate the original bilevel problem $(P)$ . Unlike the "standard" approach of simply substituting approximated data into the standard bilevel constraints, the proposed method introduces auxiliary variables and a specific penalization structure to enforce stability.

The formulation $(P)_\nu$ minimizes $f_\nu(x, y) + \sigma_\nu \|u\| - \theta_\nu \alpha$ subject to:

Constraint Relaxation: $H_\nu(x, y) + u \in D$ , where $u \in \mathbb{R}^q$ is an auxiliary slack variable allowing for constraint violations, penalized by $\sigma_\nu$ .
Lower-Level Optimality Approximation: A constraint ensuring $y$ is near-optimal for the lower-level problem, formulated as:
$g_\nu(x, y) + \alpha \leq g_\nu(x, z) + \lambda \cdot \text{dist}(H_\nu(x, z), D) + \tau_\nu, \quad \forall z \in Y_\nu$
Here, $\alpha \in (-\infty, 0]$ is an auxiliary variable penalized by $\theta_\nu$ , and $\lambda \in [0, \bar{\lambda}_\nu]$ acts as a penalty parameter for the lower-level feasibility constraints. The term $\text{dist}(\cdot, D)$ measures the distance to the set $D$ , effectively moving the constraint $H(x, z) \in D$ into the objective function via exact penalization principles.

The formulation relies on mild assumptions regarding the convergence of approximating data ( $f_\nu, g_\nu, H_\nu$ ) and the sets ( $X, Y, D$ ), without requiring convexity, smoothness, or strict complementarity conditions.

Key Contributions and Results
The paper establishes a series of theoretical results demonstrating that solving $(P)_\nu$ yields solutions that converge to those of the original problem $(P)$ as the approximation index $\nu \to \infty$ and parameters ( $\sigma_\nu, \theta_\nu, \bar{\lambda}_\nu$ ) are tuned appropriately.

Stability and Bounds: Under basic assumptions (Assumption 2.1), the minimum value of $(P)_\nu$ provides a lower bound on the minimum value of $(P)$ in the limit. Furthermore, sequences of near-optimal solutions to $(P)_\nu$ have cluster points that are feasible for $(P)$ .
Role of Auxiliary Variables:
- The variable $u$ is critical for handling infeasibility in the standard lower-level problem caused by data perturbations. Without $u$ , the lifted problem could become infeasible even when the original problem is solvable.
- The variable $\alpha$ allows the satisfaction of the lower-level optimality constraint without imposing additional assumptions on the existence of exact minimizers.
Convergence to Optimality under Calmness:
- If the lower-level value function satisfies a calmness condition at an optimal solution $x^*$ , the minimum values of $(P)_\nu$ converge to the minimum value of $(P)$ , and the solutions converge to an optimal solution of $(P)$ .
- Local calmness (calmness holding in a neighborhood of a cluster point) is shown to be sufficient for convergence, eliminating the need for the penalty parameter $\lambda$ to be bounded a priori, provided the sequence of solutions has a cluster point.
Computational Tractability: The lifted formulation preserves structural properties (e.g., linearity or convexity) of the original functions. The constraint set involves a finite or infinite number of inequalities indexed by $z \in Y_\nu$ . The paper proposes an Outer Approximation Algorithm that iteratively solves a master problem with a subset of constraints and adds violated constraints (via solving a subproblem) until convergence.
Numerical Validation: The paper presents numerical experiments on mixed-integer linear and quadratic instances. The results demonstrate that the outer approximation algorithm successfully reduces the optimality gap, recovering stable solutions even in cases where the standard formulation fails completely due to instability.

Significance and Claims
The paper claims that the proposed lifted formulation is fundamentally well-posed. Unlike traditional approaches that may fail or produce erratic solutions under data perturbations, $(P)_\nu$ ensures that discrepancies in problem data lead to useful decisions and bounds in the limit as discrepancies vanish.

The author emphasizes that their approach avoids strong assumptions (such as convexity, smoothness, or Slater conditions) that are typically required for stability in bilevel optimization. By leveraging the connection between calmness and exact penalization, and by introducing auxiliary variables to handle constraint violations and near-optimality, the method provides a robust framework for solving optimistic bilevel problems with integer restrictions and disjunctive constraints. The work positions itself as a practical alternative to value-function approaches that often struggle with generalized semi-infinite constraints or require strict feasibility conditions.

The paper concludes that while challenges remain in solving the resulting non-convex or mixed-integer problems, the structural properties of $(P)_\nu$ make it amenable to established algorithmic strategies, including outer approximation and mixed-integer programming techniques.

More like this