Bilevel MPC for Linear Systems: A Tractable Reduction and Continuous Connection to Hierarchical MPC

1. Problem Statement

The paper addresses the challenges associated with Bilevel Model Predictive Control (MPC) in linear systems. In a standard bilevel MPC architecture:

• Upper Level: Selects a reference sequence (typically steady-state targets) to optimize a high-level objective (e.g., economics, safety).
• Lower Level: A linear tracking MPC that dynamically tracks the reference sequence provided by the upper level, formulated as a strongly convex Quadratic Program (QP).

The Core Challenge:
Standard approaches to solving bilevel optimization problems involve replacing the lower-level problem with its Karush-Kuhn-Tucker (KKT) conditions, resulting in a Mathematical Program with Complementarity Constraints (MPCC).

• Non-convexity: MPCCs are inherently non-convex due to complementarity conditions.
• Numerical Instability: They often suffer from constraint qualification violations, leading to multiple local solutions, non-uniqueness, and numerical instability.
• Discontinuity: Reformulations using binary variables (to handle complementarity) introduce policy discontinuities and lack scalability, which are undesirable for real-time control applications requiring smooth, unique, and verifiable solutions.

The authors aim to find a tractable, smooth, single-level reduction of the bilevel MPC that preserves optimality, ensures solution uniqueness, and maintains closed-loop stability guarantees without resorting to non-convex MPCC formulations.

2. Methodology

The paper proposes a three-pronged methodology: a tractable reduction, an equivalence proof to centralized MPC, and a connection to standard Hierarchical MPC (HMPC) via move-blocking.

A. Tractable Reduction (Smooth Single-Level Formulation)

Instead of using KKT conditions (which introduce complementarity), the authors propose lifting the lower-level constraints to the upper level and replacing the lower-level optimization with its unconstrained first-order stationarity condition.

• Original Bilevel Problem ($P_1$): Minimizes upper cost subject to the lower-level solution being optimal.
• Proposed Reduction ($P_2$):
  $$\min_{\Theta, U} F_u(U) \quad \text{s.t.} \quad G_u(U) \leq 0, \quad G_l(U) \leq 0, \quad \nabla_U F_l(U; \Theta) = 0$$
  Here, $\Theta$ is the reference parameter, $U$ is the input sequence, $F_l$ is the lower-level cost, and $G_l$ represents lower-level constraints.
• Key Mechanism: The condition $\nabla_U F_l = 0$ is an affine equation in $U$ and $\Theta$. By enforcing stationarity directly, the complementarity constraints (and thus non-convexity) are eliminated.
• Condition for Exactness: Under a verifiable block-matrix nonsingularity condition (Assumption 2: the matrix $\bar{\Gamma}$ derived from system dynamics and weights is nonsingular), the solution set of $P_2$ is a subset of $P_1$ with the same optimal value.

B. Equivalence to Centralized MPC

The authors introduce a Centralized MPC ($P_3$) that minimizes the upper-level cost directly over the input sequence $U$, subject to both upper and lower-level constraints.

• Theorem: Under standard convexity assumptions (strong convexity of the upper cost and convexity of constraints), the bilevel architecture ($P_1$ or $P_2$ coupled with the lower-level tracker) is equivalent to the centralized MPC $P_3$ in terms of the realized input trajectory.
• Implication: This equivalence allows the bilevel system to inherit the closed-loop stability properties and uniqueness guarantees of the centralized MPC.

C. Connection to Hierarchical MPC via Move-Blocking

To bridge the gap between standard HMPC (which is computationally cheap but suboptimal) and full bilevel MPC (optimal but expensive), the authors introduce move-blocking.

• Concept: Move-blocking restricts the reference sequence $\Theta$ to a lower-dimensional subspace defined by a blocking matrix $M$ ($\Theta = M\Phi$).
• Interpolation:
  • Standard HMPC: Corresponds to a "one-block" policy (constant reference over the horizon).
  • Full Bilevel MPC: Corresponds to a full-rank blocking matrix (no restriction).
  • Intermediate: By varying the rank of $M$, one can continuously interpolate between HMPC and bilevel MPC.
• Optimal-Value Ordering: The paper establishes a strict ordering of performance:
  $$V_{\text{Centralized}} \leq V_{\text{Bilevel}} \leq V_{\text{Blocked Bilevel}} \leq V_{\text{HMPC}}$$
  (where lower values indicate better performance).

D. Performance Degradation Certificates

A novel contribution is the derivation of a posteriori bounds for performance degradation.

• Using the strong convexity of the problem, the authors derive an inexpensive upper bound ($\Delta$) on the difference between the optimal value of a blocked formulation and the full bilevel/centralized solution.
• This bound is computed by solving a small non-negative least-squares problem involving active constraints, allowing for a "stop-or-refine" decision: if the bound is small, the computationally cheaper blocked solution is sufficient; if large, more degrees of freedom are needed.

3. Key Contributions

1. Complementarity-Free Reduction: A smooth, single-level QP-solvable formulation ($P_2$) that avoids the non-convexity of MPCCs while recovering the exact optimal value and input trajectory of the original bilevel problem under a verifiable nonsingularity condition.
2. Uniqueness and Stability Guarantees: Proof that the reduced bilevel MPC yields a unique input trajectory identical to a centralized MPC, thereby inheriting closed-loop stability properties.
3. Unified Framework: A theoretical connection showing that standard HMPC is a specific case of bilevel MPC with a specific blocking structure. This enables a principled trade-off between computational efficiency and performance.
4. Inexpensive Certificates: Development of computable, a posteriori bounds that quantify the performance loss due to move-blocking, enabling adaptive control strategies without solving the expensive full problem.
5. Low-Rank Construction: An algorithm to construct low-rank blocking matrices from sampled data that guarantee performance better than or equal to standard HMPC in specific operational regions.

4. Results

The authors validated their theory using a numerical example of a linear integrator system (position/velocity) with a target state outside the feasible set (requiring constraint handling).

• Optimality Recovery: The proposed reduction ($P_2$) reliably reproduced the optimal trajectory of the centralized MPC ($P_3$). In contrast, the standard MPCC-based bilevel formulation ($P_1$) was highly sensitive to initialization, often converging to suboptimal local minima or failing to converge.
• Performance Ordering: Numerical results confirmed the theoretical ordering: Centralized $\approx$ Bilevel $\leq$ Blocked Bilevel $\leq$ HMPC. As the blocking was relaxed (increasing the rank of $M$), performance monotonically improved.
• Certificate Effectiveness: The derived degradation bounds ($\Delta$) successfully upper-bounded the actual performance loss. The bounds were tighter when using the refined version ($\Delta_\epsilon$) and coarse blocking, validating their utility for real-time decision-making.
• Low-Rank Matrix: The constructed low-rank matrix $M^*$ (rank 2) outperformed the standard HMPC (rank 1) while remaining computationally efficient.

5. Significance

This paper significantly advances the practical applicability of bilevel control architectures:

• Real-Time Viability: By eliminating non-convex complementarity constraints, the proposed method makes bilevel MPC solvable with standard, fast QP solvers, addressing the primary barrier to real-time deployment.
• Safety and Verification: The equivalence to centralized MPC provides rigorous stability and uniqueness guarantees, which are critical for safety-critical systems (e.g., autonomous vehicles, aerospace).
• Systematic Design: The move-blocking framework provides a systematic way to tune the complexity-performance trade-off, moving away from ad-hoc heuristics.
• Broad Applicability: The approach is applicable to any linear system where the upper layer optimizes steady-state parameters, covering fields like power grids, HVAC, and autonomous driving.

In summary, the paper transforms bilevel MPC from a theoretically interesting but numerically fragile concept into a tractable, robust, and certifiable control strategy that seamlessly integrates with existing hierarchical frameworks.