Source-linked AI summary
Anytime Primal--Dual Certification of the Maximum Disturbance Radius in Robust MPC
Wenqi Cai, Muhammad Bakr Abdelghany, Kyriakos G. Vamvoudakis, Anthony Tzes
TL;DR
The paper addresses how to assess remaining robustness reserve after an out-of-set disturbance without immediately solving the full optimization problem. It develops independent primal and dual correction hierarchies whose two-sided envelope enables anytime certification, and reports no certificate violations with median speedups up to 4.97x over warm-started full re-optimization at 2% certificate-width tolerance.
Problem
Existing methods primarily optimize and propagate state-dependent robustness reserve under in-set disturbances, leaving post-disturbance assessment without immediate full re-optimization as the central question.
Method
The framework uses shifted feasible-plan and current-multiplier anchors to build independently expandable primal and dual certificate hierarchies combined into a two-sided reserve-depletion envelope.
Results
All tested cases had zero certificate violations, with median speedups up to 4.97x over warm-started full re-optimization at 2% certificate-width tolerance.
Takeaways & Limitations
Every completed reduced solve provides a valid certificate, allowing early termination at a prescribed tolerance while finite expansions recover the exact result.
Abstract
from arXiv · showhide
Adjustable-set robust model predictive control (MPC) characterizes a state-dependent maximum disturbance radius, which can be interpreted as a certified robustness reserve. Existing methods primarily focus on optimizing and propagating this reserve under in-set disturbances. This letter investigates how much reserve remains after a finite out-of-set disturbance without immediately re-solving the full optimization problem. To this end, we propose a two-sided reserve-depletion envelope formed by independent primal and dual correction hierarchies, which supply monotone lower and upper bounds, respectively. The envelope remains valid across active-set changes, has an online-computable width, and contracts monotonically under subspace expansion. Leveraging its finite-step exactness, we present a basis-first adaptive algorithm that operates in an anytime manner: every completed reduced solve returns a valid certificate, enabling early termination once a prescribed tolerance is reached. Across the tested cases, numerical studies report no certificate violations and median speedups of up to 4.97x over warm-started full re-optimization at a 2% certificate-width tolerance.
I. INTRODUCTION
The paper studies certified reserve depletion after finite out-of-set disturbances without immediately solving the full reserve LP. It develops independent primal and dual certificate hierarchies for anytime, two-sided reserve assessment.
- Motivation: Geometric distance to constraint boundaries does not determine disturbance tolerance because dynamics, input limits, and future constraints affect recoverability.The reserve is the largest scaling of a prescribed disturbance set that preserves finite-horizon feasibility under fixed ancillary feedback.
- Motivation: Exact reserve depletion requires solving the full reserve LP at both modeled and realized successor states, which can burden online computation.This motivates certification methods that avoid immediate full re-optimization after an out-of-set disturbance.
- Related work: Existing tools characterize parametric solutions, local primal-dual variations, warm starts, and incomplete optimization, but do not directly provide the proposed reserve-depletion certificate.The paper positions its approach within multiparametric programming, post-optimality analysis, active-set acceleration, and real-time optimization methods.
- Contributions: The framework uses shifted feasible plans and current optimal multipliers as primal and dual anchors for independently expandable certificate hierarchies.These anchors support lower and upper reserve certificates for the realized successor.
- Contributions: The signed primal hierarchy supplies monotone lower certificates, implementable repair, reserve depletion or gain, and finite exactness.The signed adjustment distinguishes positive depletion from negative reserve gain.
- Contributions: The reduced dual hierarchy and adaptive combination provide monotone upper tightening, validity across active-set changes, prescribed-tolerance stopping, and finite-step exactness.Together they form a two-sided reserve-depletion envelope for anytime certification.
A. System and reserve formulation
The paper formulates robust MPC for constrained linear systems with polytopic state, input, and disturbance sets. After eliminating predicted states, the state-dependent reserve becomes a parametric linear program.
- System model: The constrained linear system uses state, input, and disturbance variables with polytopic state and input constraints.The modeled disturbance set is a compact polytope containing the origin and scaled by δ ≥ 0.
- Reserve formulation: The robust MPC formulation uses fixed ancillary feedback and robust terminal ingredients to enforce operation under bounded disturbances.Support-function tightenings induced by the scaled disturbance set vary linearly with δ.
- Reserve formulation: After eliminating predicted states, the decision vector collects the nominal input sequence and auxiliary variables in a condensed linear program.The condensed formulation contains nc scalar inequalities and includes all constraints on z.
- Reserve formulation: The reserve ρ(x) is the state-dependent maximum admissible disturbance scaling represented by the parametric LP.The vector q records each inequality’s tightening per unit increase in δ.
- Shift feasibility: Shift feasibility requires that applying the first control move and shifting the feasible plan yields a feasible successor decision under modeled disturbances.The paper identifies this as the standard tube-MPC shift condition, enforceable with robust invariant terminal sets and controllers.
B. Dual characterization
The reserve admits a dual characterization through strong and weak duality, yielding bounds that remain useful after state changes. It is concave and piecewise affine over its feasible domain.
- Dual characterization: Strong duality provides the exact reserve characterization on the feasible domain, while weak duality supplies valid bounds from feasible primal and dual pairs.A primal-feasible pair gives a lower bound and a dual-feasible multiplier gives an upper bound.
- Reserve properties: ρ is concave and piecewise affine on Xf.This follows from the polyhedral parametric-LP representation.
- Dual characterization: The dual-feasible set is state-independent, so a current optimal multiplier remains dual-feasible after an admissible state displacement.This gives an immediate upper bound on the reserve at the displaced state.
- Motivation for correction hierarchies: The asymmetry between immediately reusable dual feasibility and the need for primal recourse motivates separate primal and dual correction hierarchies.The dual anchor remains feasible after displacement, whereas a lower bound requires constructing a primal-feasible recourse.
III. PRIMAL–DUAL RESERVE CERTIFICATES
The certificate construction evaluates modeled and realized successors after decomposing the disturbance into an in-set component and an excess perturbation. Primal and dual anchors then provide lower and upper reserve certificates.
- Successor construction: The realized disturbance is decomposed relative to the certified set ρkW0 into a modeled component and an excess perturbation.The modeled and excess-perturbed successors are indexed by 0 and e.
- Primal certificate: The shifted plan is primal-feasible at the modeled successor under the tube-MPC shift assumption.This supplies the baseline feasible decision used for primal certification.
- Certificate anchors: A fixed linear prediction map generates a baseline feedforward update and the resulting uncorrected primal anchor.The primal and dual reserve certificates are distinguished by their lower- and upper-bound roles.
A. Primal correction hierarchy
The primal hierarchy builds nested, increasingly flexible primal-feasible corrections that provide monotone lower reserve certificates and become exact at the full correction space.
- Construction: The hierarchy restricts corrections to nested subspaces that progressively free nominal-input corrections, ending at the full-space endpoint.The level-zero space admits no correction, while the full endpoint uses T_Mp = I_nz.
- Construction: The signed reserve-adjustment LP parameterizes corrections and distinguishes reserve depletion from reserve gain.Positive β indicates required reserve reduction, whereas negative β certifies a reserve gain; infeasible reduced levels fall back to zero.
- Guarantees: Primal certificates are feasible at every level, improve monotonically under expansion, and are exactly recoverable at the full endpoint.The fallback ρ = 0 remains valid, and full-space recovery reconstructs the original reserve problem.
- Guarantees: The cumulative reserve guarantee follows by repeatedly shifting and repairing a certified plan while preserving primal feasibility.The result is established by induction from the one-step repair guarantee.
B. Dual correction hierarchy
The dual hierarchy applies nested nullspace corrections to produce valid upper reserve certificates that tighten monotonically and recover the full dual optimum finitely.
- Construction: Dual corrections are restricted to nested subspaces of ker(G^T), preserving the dual equality while progressively releasing additional directions.The terminal subspace recovers the full nullspace.
- Construction: Each reduced dual LP retains dual feasibility while its objective tightens the upper reserve certificate.The current optimal multiplier with zero correction is feasible at every level, ensuring an upper certificate from the outset.
- Guarantees: Dual upper certificates tighten monotonically as the reduced feasible family expands and become exact at the terminal nullspace level.The terminal correction space recovers the full dual problem.
- Implementation: Hierarchy choices may prioritize QR/SVD nullspace directions or empirically useful multiplier-difference directions without changing validity or finite exactness.The analysis requires only nesting and a full-nullspace endpoint.
IV. ANYTIME RESERVE-DEPLETION CERTIFICATION
The certification framework combines statewise primal lower and dual upper bounds into an online reserve-depletion envelope. Its basis-first adaptive algorithm preserves validity after each reduced solve, stops at a prescribed width, and reaches exactness finitely.
- Envelope: The online statewise gap uses independently selected primal and dual levels and measures signed reserve depletion, with negative values denoting reserve gain.The construction evaluates certificates for the modeled and excess successor states.
- Envelope: The two-sided envelope bounds reserve error, has a width nonincreasing in every hierarchy level, and becomes exact when either hierarchy reaches its terminal level for a state.The companion bound may equal the exact value for scalar envelope evaluation.
- Anytime algorithm: Algorithm 1 expands either primal or dual hierarchies, updates the envelope after each reduced solve, and retains a feasible excess-state repair for closed-loop execution.The expansion policy affects contraction speed but not theoretical validity or finite exactness.
- Basis-first implementation: Basis-first initialization can obtain an exact successor reserve without solving a reduced LP when the updated basic solution remains primal-feasible.Because only the right-hand side changes, dual feasibility is preserved and primal feasibility implies optimality.
- Anytime algorithm: Every completed hierarchy solve leaves a valid envelope; the algorithm stops when W_k ≤ ε_cert and a feasible repair is secured, or becomes exact after finite expansion.Exact dual bounds alone do not provide the primal-feasible input required for execution.
V. NUMERICAL STUDY
The numerical study evaluates reserve geometry, finite-perturbation validity, and the computation–tightness tradeoff of the anytime certification algorithm.
- Evaluation: The study uses full re-optimization only to assess exact successor reserves, not to produce the online certificate.This comparison isolates certificate performance from the online method itself.
A. Double integrator: geometry and finite perturbations
The double-integrator study shows that equal geometric margins can correspond to very different certified reserves. After a recycled-basis failure, the certified envelope contains the exact depletion and reaches tolerance before either exact endpoint, unlike the sensitivity prediction.
- Finite perturbations: Finite perturbations are generated as wk = αρks with signed directions and α stratified over [1.02, 2].Only pairs satisfying Theorem 1 domain conditions are retained.
- Certification: The certified envelope contains the exact depletion after every completed solve and reaches the prescribed tolerance after 6 reduced solves.Termination occurs before either exact endpoint in the recycled-basis-failure case.
- Certification: The local sensitivity prediction incurs an absolute error of 2.29 × 10−3 and is not exact in the recycled-basis-failure case.Across the subset, the median normalized sensitivity error is 1.16×10−3.
- Certification: Across 4000 pairs, no bound-validity, monotonicity, endpoint-exactness, or repair-feasibility violation exceeded 10−7.
B. Lateral-vehicle benchmark
The lateral-vehicle benchmark evaluates certificate tightness and computation across horizons using reduced primal–dual expansions and common solver settings. At 2% width tolerance, longer horizons achieve tighter certificates and larger median speedups, while all reported methods avoid certificate violations.
- Algorithm: The adaptive hierarchy expands primal and dual dimensions geometrically, includes terminal levels, and selects expansions using statewise gaps and variable counts.Primal levels are {0, 1, 2, 4, . . . , N}; dual levels are {0, 4, 8, 16, . . . , nλ}.
- Benchmark setup: All methods use the same single-threaded HiGHS dual-simplex backend and 10−8 feasibility tolerances, with timing including projection, basis tests, updates, selection, and solver calls.
- Benchmark setup: At εcert = 2%, N = 40 and N = 60 attain median normalized widths of 0.01109 and 0.00845.These are the highlighted operating points in the computation–tightness tradeoff.
- Results: At εcert = 2%, paired median speedups are 2.03× for N = 40 and 4.97× for N = 60 over warm-started Full.Stars denote warm-started Full as the zero-width endpoint.
- Results: All methods have zero certificate violations, while PDε stops before either exact endpoint in 92.3% of cases.PDε also has the lowest t50 and t95 and the highest early-stop rate among hierarchy-based methods.
- Results: Pε is faster but looser, whereas Dε is tighter but costlier under the present QR ordering; their adaptive combination gives the best time-to-tolerance tradeoff.
VI. CONCLUSION
The letter frames post-disturbance reserve assessment as an interruptible certification task for real-time MPC with limited or variable computation. Experiments identify moderate tolerances and longer horizons as favorable operating conditions, while future work targets broader settings and improved switching.
- Post-disturbance reserve assessment replaces immediate full re-optimization with an interruptible certification task.The approach combines a tunable depletion envelope, an implementable successor repair, and an exact fallback.
- Certified nonzero-width estimates support real-time MPC when computation is limited or variable.
- Moderate tolerances and longer horizons emerge as favorable operating regimes in the experiments.
- Future work targets problem-informed dual hierarchies, cost-aware switching, and extensions to nonlinear, time-varying, and adaptive uncertainty-set MPC.