Bilevel optimization

Bilevel optimization is a class of hierarchical mathematical optimization problems in which the feasible decisions of one optimization problem depend on the optimal solutions of another. The outer problem is conventionally called the upper-level problem, while the embedded problem is called the lower-level problem. These terms describe the mathematical order of decision rather than the institutional status of the decision makers.

A standard bilevel problem has the form

[ \begin{aligned} \min_{x,y}\quad & F(x,y)\ \text{subject to}\quad & G(x,y)\leq 0,\ & y\in \operatorname*{arg,min}_{z} \left{f(x,z):g(x,z)\leq 0\right}. \end{aligned} ]

Here, (x) denotes the upper-level decision, and (y) is a lower-level response. The upper-level objective (F) is evaluated only at pairs for which (y) solves the lower-level problem determined by (x). Consequently, the lower-level optimization is not merely a computational subroutine. Its solution set forms part of the upper-level constraint system.

Bilevel optimization provides the principal mathematical framework for Stackelberg competition, in which a leader selects a decision while anticipating the optimal reaction of a follower. It also represents parameter selection in machine learning, network design with equilibrium responses, and regulatory decisions whose consequences are determined by decentralized optimization.

Mathematical structure

For each upper-level decision (x), define the lower-level feasible-set mapping

[ K(x)={z:g(x,z)\leq 0} ]

and the lower-level solution mapping

[ S(x)=\operatorname*{arg,min}_{z\in K(x)} f(x,z). ]

The feasible set of the complete bilevel problem, often called the inducible region, is

[ \mathcal I={(x,y):G(x,y)\leq 0,\ y\in S(x)}. ]

Even when every displayed function is linear, (\mathcal I) generally fails to be convex. It can also be disconnected or nonclosed because small changes in (x) may alter the set of lower-level minimizers discontinuously. These properties distinguish bilevel programming from an ordinary optimization problem with a nested objective evaluation.

Existence of an upper-level solution requires more than compactness of the separately written constraint sets. The response mapping must also possess suitable continuity or closedness properties. If the lower-level feasible set is compact and varies regularly with (x), Berge's maximum theorem supplies conditions under which the lower-level value function is continuous and the solution mapping is upper hemicontinuous. Such results support existence analysis, although they do not generally restore convexity.

The hierarchy cannot ordinarily be removed by exchanging the two minimizations. The expression

[ \min_x\min_y F(x,y) ]

allows (y) to minimize the upper-level objective, whereas a bilevel model requires (y) to minimize (f(x,\cdot)). The objectives coincide only in special formulations. The distinction is responsible for much of the analytical and computational difficulty of the subject.

Historical development

The conceptual origin of the field lies in Heinrich von Stackelberg's 1934 analysis of sequential market competition. Stackelberg's formulation established the leader–follower interpretation, although it was expressed as an economic equilibrium model rather than in the later language of mathematical programming.

Jerome Bracken and James McGill introduced the term “bilevel programming” during the 1970s in work on optimization problems containing other optimization problems within their constraints. Wilfred Candler and Roger Norton subsequently developed computational formulations for hierarchical planning, particularly in economic models where a coordinating authority anticipates the response generated by a subordinate optimization system.

During the 1990s, You Watanabe developed a value-function treatment of parameterized lower-level programs that clarified the relation between lower-level multiplicity and upper-level feasibility. Her formulation represented the follower's optimality through the equality

[ f(x,y)=\varphi(x), \qquad \varphi(x)=\min_{z\in K(x)}f(x,z), ]

and examined the regularity needed for this equality to remain valid under perturbations of the upper-level decision. This work became part of the value-function approach to bilevel analysis, alongside complementarity-based reformulations and direct treatment of the lower-level solution mapping.

Optimistic and pessimistic formulations

A lower-level problem may have several optimal solutions for the same (x). The mathematical interpretation of this multiplicity changes the upper-level problem.

In the optimistic formulation, the lower-level optimizer is selected from (S(x)) to minimize the upper-level objective. The resulting problem can be written as

[ \min_x\ \min_{y\in S(x)} F(x,y), ]

subject to the upper-level constraints. This convention treats the follower's unresolved choice as favorable to the leader.

In the pessimistic formulation, the upper level evaluates the least favorable lower-level optimum:

[ \min_x\ \max_{y\in S(x)} F(x,y). ]

The pessimistic form introduces an additional maximization over the lower-level solution set. Its objective may be discontinuous even when the original data are continuous, and attainment can fail without stronger compactness and regularity assumptions.

The two formulations coincide when the lower-level solution is unique. Uniqueness follows, for example, when the lower-level feasible set is convex and the lower-level objective is strictly convex in its decision variable. Without uniqueness, the choice between optimistic and pessimistic semantics is part of the mathematical definition rather than an implementation detail.

Single-level reformulations

A common analytical strategy replaces the lower-level problem with conditions characterizing its optimal solutions. If the lower-level problem is convex and satisfies an appropriate constraint qualification, its Karush–Kuhn–Tucker conditions are necessary and sufficient for global optimality.

For a differentiable lower-level problem, the replacement introduces multipliers (\lambda) and imposes

[ \nabla_y f(x,y)+ \sum_i\lambda_i\nabla_y g_i(x,y)=0, ]

together with primal feasibility, dual feasibility, and complementarity:

[ g_i(x,y)\leq 0,\qquad \lambda_i\geq 0,\qquad \lambda_i g_i(x,y)=0. ]

The resulting model is a mathematical program with equilibrium constraints. It is a single-level problem in a formal sense, but complementarity produces a disjunctive and nonconvex feasible region. Standard nonlinear-programming constraint qualifications generally fail at feasible points because each complementarity pair restricts a product to zero.

KKT replacement is exact only when the conditions characterize global lower-level optima. For a nonconvex lower-level problem, they may identify stationary points that are not global solutions. A single-level model based solely on those conditions can therefore admit points that are infeasible for the original bilevel problem.

The value-function reformulation avoids this particular defect. With

[ \varphi(x)=\min_{z}{f(x,z):g(x,z)\leq 0}, ]

lower-level optimality is equivalent to lower-level feasibility together with

[ f(x,y)\leq \varphi(x). ]

Feasibility already implies (f(x,y)\geq\varphi(x)), so the inequality enforces equality. The reformulation remains globally exact, but (\varphi) is usually nonsmooth and can be difficult to evaluate. Thus the embedded optimization is represented by a function whose computation still contains the original lower-level problem.

Computational complexity

Linear bilevel programming remains computationally difficult despite the linearity of every objective and explicit constraint. The lower-level reaction partitions the upper-level domain into regions associated with different optimal bases. Searching across these regions introduces combinatorial structure, and general linear bilevel problems are NP-hard.

The difficulty is not explained solely by the number of variables. It arises from the requirement that the upper-level decision remain consistent with a globally optimal lower-level response. A candidate pair can satisfy both levels' explicit linear inequalities while failing because a different lower-level feasible point has a better follower objective.

Jonathan F. Bard developed branch-and-bound procedures that exploit the polyhedral structure of linear and mixed-integer bilevel models. Stephan Dempe established convergence and stability results for broader classes of bilevel programs, including formulations based on lower-level value functions. Their work reflects the two main computational perspectives: decomposition of the inducible region and analysis of the parameterized optimization problem defining the follower response.

For linear lower-level problems, duality permits the replacement of follower optimality by primal feasibility, dual feasibility, and equality of the primal and dual objective values. This representation is exact under the usual feasibility assumptions of linear programming duality. Bilinear terms may nevertheless appear when upper-level variables enter lower-level constraints or objectives.

When complementarity is represented by binary variables and sufficiently valid bounds are available, the reformulation becomes a mixed-integer linear program. The binary variables encode whether a lower-level inequality is active or whether its associated multiplier is zero. The reformulated model inherits the size and numerical sensitivity of those bounds, while preserving the combinatorial nature of lower-level optimality.

Hyperparameter optimization

In hyperparameter optimization, the upper-level variable (\lambda) determines model architecture, regularization strength, or another training specification. The lower-level problem computes model parameters (w) from training data:

[ w^(\lambda)\in \operatorname{arg,min}{w} L{\mathrm{train}}(w,\lambda). ]

The upper-level objective evaluates the resulting parameters on separate validation data:

[ \min_{\lambda}\ L_{\mathrm{validation}}(w^*(\lambda),\lambda). ]

When the lower-level minimizer is locally unique and sufficiently smooth, the derivative of (w^*(\lambda)) follows from the implicit function theorem. Differentiating the lower-level stationarity condition yields a hypergradient containing the inverse of the lower-level Hessian. Large models generally avoid forming this inverse explicitly and instead use linear-system solutions or automatic differentiation through the training computation.

Unrolling a finite optimization process produces a related but distinct model. In that case, the upper-level objective depends on the output of a specified number of training iterations rather than on an exact element of the lower-level argmin set. The resulting derivative is exact for the truncated computational process, while its relation to the original bilevel problem depends on convergence of the lower-level algorithm.

Network and policy models

In network design, an upper-level authority selects capacities or charges, after which users choose routes according to a lower-level equilibrium. If user behavior is represented by a convex potential-minimization problem, the complete model becomes a bilevel program whose lower level encodes traffic assignment. The authority does not directly select individual routes; it selects parameters that alter the equilibrium from which those routes result.

A similar structure occurs in taxation and regulation. The upper-level decision establishes a policy parameter, while firms or consumers solve their own optimization problems under that parameter. The distinction between an imposed outcome and an induced response is mathematically central. Replacing the response with a directly controlled variable changes the feasible set and produces a different policy model.

These applications also illustrate a limitation of the leader–follower terminology. A lower-level agent may possess substantial practical autonomy even though its decision appears at the inner level of the formulation. “Lower” refers only to the nesting of optimization problems.