PaperlayerView exact revision on arXiv

Source-linked AI summary

Constraint-Tightening and Stability in Stochastic Model Predictive Control

Matthias Lorenzen, Fabrizio Dabbene, Roberto Tempo, Frank Allgöwer

arXiv:1511.03488v2eess.SYmath.OC

TL;DR

Stochastic MPC must handle uncertainty while retaining recursive feasibility and stability without excessive constraint tightening. The paper separates feasibility from stability and develops a tunable scheme unifying previous approaches. Under mild assumptions, it provides performance and convergence bounds and proves asymptotic stability in probability of the minimal robust positively invariant set.

  • Problem

    Stochastic MPC needs computationally tractable uncertainty propagation and recursive-feasibility guarantees despite allowing probabilistic constraint violations.

  • Method

    The paper separates stability from feasibility and combines stochastic constraint tightening with an additional first-step constraint and a tunable candidate-feasibility probability.

  • Results

    The scheme guarantees recursive feasibility, provides asymptotic performance bounds, and proves asymptotic stability in probability of the minimal robust positively invariant set under mild assumptions.

  • Takeaways & Limitations

    The tuning parameter εf lets designers trade off feasible-region size against convergence speed and performance guarantees.

  • Takeaways & Limitations

    Broader applicability requires relaxing the assumption of identically and independently distributed disturbances and allowing parametric uncertainty.

Abstract

from arXiv · show

Constraint tightening to non-conservatively guarantee recursive feasibility and stability in Stochastic Model Predictive Control is addressed. Stability and feasibility requirements are considered separately, highlighting the difference between existence of a solution and feasibility of a suitable, a priori known candidate solution. Subsequently, a Stochastic Model Predictive Control algorithm which unifies previous results is derived, leaving the designer the option to balance an increased feasible region against guaranteed bounds on the asymptotic average performance and convergence time. Besides typical performance bounds, under mild assumptions, we prove asymptotic stability in probability of the minimal robust positively invariant set obtained by the unconstrained LQ-optimal controller. A numerical example, demonstrating the efficacy of the proposed approach in comparison with classical, recursively feasible Stochastic MPC and Robust MPC, is provided.

I. INTRODUCTION

Stochastic MPC addresses uncertainty with chance constraints, reducing conservatism but complicating uncertainty propagation and recursive feasibility. The paper proposes a tractable, nonconservative scheme that guarantees recursive feasibility while balancing feasible-region size against performance and convergence guarantees.

  • Stochastic MPC allows specified future constraint-violation probabilities, reducing the conservatism of worst-case tightening.
  • Recursive feasibility is difficult because future state distributions depend on the current state and time to go, so violation probabilities can change after replanning.
  • Existing approaches include confidence-region tightening, direct tightening based on uncertainty evolution, and recursively feasible probabilistic tubes.
  • The paper proposes a computationally tractable Stochastic MPC scheme that guarantees recursive feasibility and unifies previous results.
  • A tuning parameter εf balances convergence speed and performance guarantees against the size of the feasible region.
  • The approach shifts computational effort offline and provides an efficient sampling-based solution strategy for offline chance-constrained programs.

B. Receding Horizon Optimization

The receding-horizon controller repeatedly solves a finite-horizon stochastic optimal control problem but applies only its first control action. Its design must preserve constraints, recursive feasibility, and stability after each sampling step.

  • The SMPC algorithm repeatedly solves a finite-horizon optimal control problem and implements only the first control action.
  • The system prediction separates a deterministic nominal trajectory from a zero-mean stochastic error trajectory using prestabilizing feedback.
  • The finite-horizon cost becomes a quadratic function of deterministic nominal states and inputs, with a constant term omitted from optimization.
  • The online problem optimizes a finite-horizon cost over nominal states and inputs subject to derived nominal and terminal constraint sets.
  • Recursive feasibility requires the finite-horizon problem to remain feasible at future sampling times whenever it is initially feasible.
  • The cost and constraint sets are designed jointly to satisfy chance constraints, ensure recursive feasibility, and stabilize the closed-loop system.

III. CONSTRAINT TIGHTENING AND STOCHASTIC MPC ALGORITHM

The paper derives offline constraint tightenings for nominal state and input predictions, then adds terminal and candidate-solution conditions to support chance-constraint satisfaction, recursive feasibility, and stability. The design separates feasibility from stability and uses probabilistic tightening levels to control conservatism.

  • Constraint Tightening and Stochastic MPC Algorithm: The proposed synthesis distinguishes existence of a feasible solution from feasibility of an a priori known candidate solution, which is central to the stability proof.
  • Constraint Tightening: State chance constraints are equivalently enforced through convex nominal-state sets Zl obtained from offline one-dimensional linear chance-constrained problems.
  • Constraint Tightening: The state tightening computes each ηl as the largest nominal margin satisfying the required conditional probability level for every state-constraint row.
  • Constraint Tightening: Input predictions use stochastic rather than robust tightening, allowing feed-forward inputs with static error feedback to remain feasible for most disturbance sequences.
  • Constraint Tightening: Closed-loop hard input constraints remain satisfied because the first input-tightening margin satisfies μ0 = g.
  • Constraint Tightening: A robust positively invariant terminal polytope under uk = Kxk ensures closed-loop constraint satisfaction for every initial state in the terminal set.

B. Recursive Feasibility

The section explains why ordinary stochastic tightening does not ensure recursive feasibility and develops a hybrid tightening strategy that combines first-step feasibility with stability-oriented constraints.

  • Failure of basic tightening: Future violation probabilities change after each disturbance realization, so a constraint feasible at time k may become infeasible at time k+1.The relation H z_l|k ≤ η_l does not imply H z_{l−1|k+1} ≤ η_{l−1}.
  • Existing remedies: Mixed worst-case/stochastic tightening can recover recursive feasibility and stability, but it may be restrictive and increase average cost near chance constraints.A first-input-only constraint is less restrictive when only recursive feasibility is required.
  • Hybrid strategy: The proposed hybrid strategy imposes a first-step constraint for recursive feasibility and stochastic tube tightening with terminal ingredients for stability.This approach requires additional offline reachability and controllability set computations.
  • Design trade-off: The resulting tightening interpolates between recursively feasible probabilistic tubes at ε_f = 0 and the least-restrictive scheme that guarantees only solution existence.The parameter ε_f specifies the allowable probability that the candidate solution is infeasible.
  • Set construction: The nominal feasible set is computed under tightened state, input, and terminal constraints, with projection or backward recursion providing a finite-horizon construction.The set C_T defines feasible states and first inputs for the finite-horizon optimization.
  • Invariant-set requirement: Because the projected state set need not be robust positively invariant, a maximal robust control invariant polytope C_∞ is computed for the disturbance set.This additional invariant-set computation supports the first-step feasibility constraint.

C. Recursive Feasibility of the Candidate Solution

This section distinguishes feasibility of any solution from feasibility of a shifted candidate solution and tightens constraints so candidate feasibility is guaranteed with a prescribed probability.

  • Candidate construction: A shifted solution is constructed at time k+1 from a feasible input trajectory at time k, following standard Robust and Stochastic MPC practice.The construction is formalized as the candidate solution for the next optimization problem.
  • Feasibility distinction: The refined tightening targets feasibility of this explicitly known candidate, not merely existence of some feasible solution at the next time.This distinction is required for the asymptotic stability analysis.
  • Probabilistic tightening: A convex 1−ε_f confidence region W_f for the disturbance is used to define tightened state, input, and terminal constraints.The modified bounds replace η_l, ν_l, and η_f with their refined counterparts.
  • Candidate guarantee: If a feasible continuation exists at time k, the shifted candidate is feasible at time k+1 with probability at least 1−ε_f.The guarantee applies to the propagated shifted states and inputs under the candidate dynamics.
  • Proof mechanism: With probability 1−ε_f, the disturbance lies in W_f, after which terminal recursive feasibility follows from robust invariance and reachability over W_f.State and input constraint satisfaction then follows inductively.
  • Design interpretation: The design parameter ε_f closes the gap between recursively feasible probabilistic tubes and least-restrictive tightening.The former is recovered at ε_f = 0, while the latter considers only existence of a solution.

D. Resulting Stochastic MPC Algorithm

The resulting algorithm separates offline set computation from online quadratic optimization, while its propositions and theorem establish recursive feasibility, constraint satisfaction, bounded average cost, and stability properties.

  • Algorithm structure: The algorithm first computes tightened constraint sets and the invariant first-step constraint offline, then repeatedly solves a linearly constrained quadratic program online.At each step it measures x_k and applies the first optimal input v*_0|k.
  • Performance analysis: The optimal value function is used as a stochastic Lyapunov function to derive the asymptotic average stage-cost bound and bounded state variance.The analysis uses its continuity, convexity, piecewise-quadratic structure, and a Lyapunov-equation terminal cost.
  • Recursive feasibility: Proposition 4 guarantees that if the terminal successor lies in the admissible set, the next optimization remains feasible for every disturbance realization in W.This establishes recursive feasibility of the SMPC algorithm.
  • Stochastic steady behavior: Because additive disturbances persist, the state does not converge to the origin but oscillates around it with bounded variance.The theorem summarizes this behavior together with the asymptotic average cost bound.
  • Constraint satisfaction: The closed loop satisfies hard and probabilistic constraints for all future times, with ε_f bounding the probability that the previously planned trajectory is infeasible.Hard input satisfaction follows from the first-step input construction, while chance satisfaction follows from recursive feasibility.
  • Terminal-region variant: A terminal region that is forward invariant with probability ε_f can replace a robustly forward invariant terminal region while preserving Theorem 1.

B. Asymptotic Stability

Under mild assumptions, the proposed SMPC controller makes the minimal robust positively invariant set asymptotically stable in probability. The proof accommodates transient periods when the a priori candidate solution may become infeasible, while preserving recursive feasibility in the terminal region.

  • Stability result: The minimal robust positively invariant set X∞ is asymptotically stable in probability under the proposed SMPC algorithm.The result is stated under assumptions including the unconstrained LQ-optimal feedback gain, terminal-set containment of X∞, and compactness of the feasible region.
  • Proof structure: The stability proof differs from standard stochastic Lyapunov arguments because candidate infeasibility can occur during a transient phase.The nonzero probability of transient infeasibility is explicitly incorporated into the proof.
  • Terminal behavior: Once the state enters the terminal region, robust forward invariance ensures candidate feasibility thereafter and the controller equals the unconstrained LQR.The unconstrained LQ-optimal solution satisfies the terminal constraints because the terminal region is robustly forward invariant.
  • Attractivity: For any probability ρ, a sufficiently long horizon exists in which the candidate solution remains feasible for Nf consecutive time steps with probability ρ.Such a consecutive feasible interval implies entry into the terminal region.
  • Attractivity: Borel-Cantelli and Fatou’s lemmas show that the probability of failing to approach X∞ converges to zero.The proof bounds the relevant failure-event probabilities and establishes their asymptotic decay.
  • Proof structure: The theorem combines robust stability in the terminal region with attractivity established through eventual periods of consecutive candidate feasibility.Stability follows from the robust case and terminal-region recursive feasibility; attractivity follows from the probability argument in Lemma 4.

C. Discussion: Offline Relaxation of Chance Constraints

The paper discusses offline tightening of chance constraints, contrasting direct single-constraint tightening with joint approximations and confidence-region methods. It emphasizes reduced conservatism while identifying bias and distribution-dependent trade-offs in alternative approaches.

  • Joint versus single chance constraints: A joint chance-constraint tightening can require more inequalities than the original constraint and may not admit a finite linear representation.This differs from Robust Tube MPC, where the tightened set has at most as many linear inequalities as the original set.
  • Joint versus single chance constraints: Single chance constraints avoid increasing the number of tightened constraints but can be more conservative or increase violation probability at some states.Thus, fewer constraints do not guarantee uniformly less conservative or uniformly safer behavior.
  • Confidence-region alternatives: Confidence-region methods tighten constraints rather than directly approximating the true joint chance constraint, with parametrization adding conservatism unless it matches the distribution.The paper’s approach is described as tight for arbitrary distributions and constraints of the stated form.
  • Illustrative example: Jointly optimizing tightening parameters can bias constraint satisfaction toward one bound and produce robust-program behavior for the opposite optimization direction.In Example 1, the lower bound has zero violation probability while the upper bound has ε violation probability; minimizing x coincides with the robust solution.
  • Illustrative example: For uniform disturbances, nonunique optimizers make the conservativeness depend on the chosen optimizer and initial value.The paper identifies this as a standard issue in confidence-region determination.
  • Joint versus single chance constraints: Direct tightening of single chance constraints gives the best worst-case conservativeness when approximating a joint chance constraint offline.Dynamic risk allocation can reduce conservatism further when tightening depends on each violation probability, at the cost of higher online computation.

V. IMPLEMENTATION AND NUMERICAL EXAMPLE

The numerical-example section describes practical solution considerations and evaluates the proposed tightening against classical recursively feasible SMPC and Robust MPC.

  • Numerical example: The numerical example demonstrates the proposed approach’s non-conservativeness regarding allowed violation probability and its increased feasible region.The comparison includes classical recursively feasible Stochastic MPC and Robust MPC.

A. Solving the Single Chance Constrained Programs

The paper reviews deterministic and sampling-based methods for solving single chance-constrained programs. It also describes numerical integration, convolution, Fourier-transform, and sampling approaches for tractable evaluation.

  • Solution methods: Single chance-constrained programs can be solved using deterministic methods or sampling-based solutions for the offline tightening problems.The reviewed methods target programs (10), (13), and (15).
  • Numerical integration: When the uncertainty density is known, multivariate chance constraints can be evaluated numerically using quadrature methods such as Quasi-Monte Carlo or Sparse Grid methods.This formulation permits direct use of nonlinear or stochastic optimization solvers.
  • Numerical integration: Independent uncertainty components reduce the probability calculation to one-dimensional integrals through convolution of the projected density functions.Fourier transforms may be advantageous because the formulation contains multiple convolutions.
  • Sampling methods: Sampling methods are distribution-independent, straightforward to implement, and can use complex simulations or measurements instead of an explicit probability density.The paper notes that specific guarantees about the resulting solutions can be provided.

2) Sampling:

The numerical study uses sampling to approximate offline chance-constrained tightenings and compares the proposed Stochastic MPC with recursively feasible Stochastic MPC and Robust MPC. The proposed scheme achieves lower conservatism while maintaining comparable computation and explicitly controlling predicted feasibility risk.

  • 2) Sampling:: Sampling with sufficiently many disturbance realizations solves the chance-constrained programs to a desired accuracy and confidence.The sampled constraints retain the chance-constraint interpretation with confidence 1−β under the stated sample-size condition.
  • 2) Sampling:: A sorting algorithm solves the sampled approximation exactly because of the problem’s simple structure, avoiding mixed-integer optimization or heuristics.
  • 2) Sampling:: Sampling-based chance-constraint satisfaction holds with confidence (1−β)^p rather than certainty, while recursive feasibility still holds if the true disturbance set is contained in W.
  • B. Numerical Example: The numerical setup uses prediction horizon T = 8, truncated Gaussian disturbances, and a 4 ms approximate computation time for each scheme.
  • B. Numerical Example: 20% average constraint violation occurred during the first 6 steps for 10^4 Monte Carlo realizations, while the proposed direct tightening achieved lower closed-loop cost than the confidence-region approach.
  • B. Numerical Example: 1.7 times the standard SMPC feasible-region size and 3.4 times the Robust MPC size were obtained by the proposed method.

VI. CONCLUSIONS AND FUTURE WORK

The paper concludes that separating recursive feasibility from stability enables a stabilizing Stochastic MPC scheme with a larger feasible region and tunable performance–feasibility trade-offs. It also identifies broader disturbance and uncertainty models as directions requiring further work.

  • VI. CONCLUSIONS AND FUTURE WORK: The proposed algorithm increases the feasible region by separating recursive feasibility and stability requirements.
  • VI. CONCLUSIONS AND FUTURE WORK: The unified scheme lets designers balance convergence speed and performance guarantees against feasible-region size.
  • VI. CONCLUSIONS AND FUTURE WORK: Absolute disturbance bounds provide a first-step constraint for robust recursive feasibility, while stochastic disturbance information yields an asymptotic performance bound.
  • VI. CONCLUSIONS AND FUTURE WORK: Under mild assumptions, the minimal robust positively invariant set X∞ is asymptotically stable with probability one.
  • VI. CONCLUSIONS AND FUTURE WORK: The online computational effort equals nominal MPC, with randomized algorithms used offline to determine constraint tightenings to the desired accuracy.
  • VI. CONCLUSIONS AND FUTURE WORK: Broader applicability requires relaxing the identically and independently distributed disturbance assumption, accommodating parametric uncertainty, and addressing unbounded additive disturbances.
Loading 1511.03488v2…