PaperlayerView exact revision on arXiv

Source-linked AI summary

The Scenario Approach for Stochastic Model Predictive Control with Bounds on Closed-Loop Constraint Violations

Georg Schildbach, Lorenzo Fagiano, Christoph Frei, Manfred Morari

arXiv:1307.5640v2math.OC

TL;DR

Chance-constrained SMPC is difficult to solve and prior scenario approaches can be overly conservative. The paper introduces a structure-aware scenario method with average-in-time constraints, reducing scenarios while preserving closed-loop violation bounds and supporting sample removal.

  • Problem

    Chance-constrained finite-horizon SMPC is generally non-convex and computationally intractable, while existing scenario approaches can over-satisfy closed-loop constraints.

  • Method

    The method exploits the multi-stage MPC structure, interprets probabilistic constraints as average-in-time, and supports finite-sample scenarios with a-posteriori removal.

  • Results

    The expected time-average of closed-loop constraint violations remains below the specified level ε, while a numerical example uses 19 samples instead of about 400 and obtains 9.87% violations instead of about 0.05%.

  • Takeaways & Limitations

    The approach greatly reduces scenario counts and supports computationally efficient SMPC for problems with many decision variables.

  • Takeaways & Limitations

    Recursive feasibility may require practical justification or soft constraints, and explicit guarantees may be unavailable for some difficult stochastic systems.

Abstract

from arXiv · show

Many practical applications of control require that constraints on the inputs and states of the system be respected, while optimizing some performance criterion. In the presence of model uncertainties or disturbances, for many control applications it suffices to keep the state constraints at least for a prescribed share of the time, as e.g. in building climate control or load mitigation for wind turbines. For such systems, a new control method of Scenario-Based Model Predictive Control (SCMPC) is presented in this paper. It optimizes the control inputs over a finite horizon, subject to robust constraint satisfaction under a finite number of random scenarios of the uncertainty and/or disturbances. While previous approaches have shown to be conservative (i.e. to stay far below the specified rate of constraint violations), the new method is the first to account for the special structure of the MPC problem in order to significantly reduce the number of scenarios. In combination with a new framework for interpreting the probabilistic constraints as average-in-time, rather than pointwise-in-time, the conservatism is eliminated. The presented method retains the essential advantages of SCMPC, namely the reduced computational complexity and the handling of arbitrary probability distributions. It also allows for adopting sample-and-remove strategies, in order to trade performance against computational complexity.

1 Introduction

The paper addresses computationally difficult chance-constrained SMPC problems and conservatism in existing scenario-based approaches. It proposes average-in-time chance constraints and structure-aware scenario reduction to improve tractability and performance.

  • Motivation: SMPC minimizes cost while requiring state constraints to hold with a specified probability under stochastic disturbances or model uncertainty.Applications include building climate control, wind turbine control, and network traffic control.
  • Motivation: Chance-constrained finite-horizon optimal control problems are generally non-convex and computationally intractable, often requiring multivariate convolution integrals.This challenge must be addressed at every sampling step.
  • Prior approaches: Scenario-based MPC handles generic probability distributions using random scenarios, but early methods remain computationally demanding or lack specific satisfaction guarantees.These approaches approximate open-loop control laws using basis functions or related sample-based constructions.
  • Prior approaches: Previous scenario approaches are conservative in receding-horizon operation because they target robust solutions or over-satisfy closed-loop chance constraints.The resulting violation rates can remain far below the specified levels.
  • Contributions: The proposed approach interprets chance constraints as time-average requirements, exploits finite-horizon problem structure to reduce samples, and supports a-posteriori sample removal.It also accommodates multiple simultaneous state chance constraints.
  • Paper scope: The paper develops the method theoretically and demonstrates it through a numerical example after formulating the optimal control problem and its scenario-based approximation.The paper also analyzes closed-loop properties before presenting conclusions.

2 Optimal Control Problem

The optimal control problem models linear stochastic dynamics with uncertain system matrices and additive disturbances, using feedback policies to minimize expected cost. State constraints are enforced for a prescribed fraction of time rather than necessarily at every step.

  • System model: The system has linear stochastic dynamics with random system and input matrices and additive disturbances driven by uncertainty δ_t.The uncertainty distribution may be generic and need not be known explicitly when samples can be obtained.
  • Control policy: Future inputs are selected through a static state-feedback law based only on the current system state.This avoids explicitly specifying all uncertain future inputs.
  • Objective: The objective is to minimize the time-average of expected stage costs over a long horizon.An alternative formulation can minimize a desired quantile of discounted costs, corresponding to value-at-risk.
  • Constraints: State constraints are required to hold for a given fraction of time because robust satisfaction at every time can be overly restrictive or impossible with unknown, unbounded disturbance support.Relaxing robust satisfaction can improve cost performance when low costs occur near the constraint boundary.
  • Constraints: Constraint violations are represented by an indicator variable M_t that equals one when the next state lies outside the constraint set.The expected time-average of these violations is bounded by a specified ε.
  • Assumptions: The optimal control problem assumes measured states, bounded convex feasible inputs, a convex state constraint set, and a convex stage cost.Typical input and state sets are polytopic or ellipsoidal.
  • Optimization formulation: The dynamics are recursively substituted in the optimization so that state variables are eliminated and the state-feedback law remains the free decision variable.The resulting formulation explicitly combines the system dynamics, initial condition, and control policy.
  • Applications: Building climate control and wind turbine control exemplify problems where occasional state-constraint violations may be acceptable while optimizing energy consumption, comfort, or power efficiency.These applications motivate average-in-time constraint handling under uncertainty.

3 Scenario-Based Model Predictive Control

SCMPC approximates stochastic MPC by enforcing state constraints across sampled uncertainty scenarios, then repeatedly applying the first input of the optimized scenario solution. This yields tractable convex programs while allowing scenario removal and tunable control parameterizations, but requires an assumption of feasibility at every time step.

  • 3.1 Stochastic Model Predictive Control (SMPC): SMPC predicts states and inputs over a finite horizon under uncertain dynamics, with predicted states random because future uncertainties affect the dynamics.The current measured state initializes the prediction, and predicted states can be eliminated recursively from the optimization.
  • 3.1 Stochastic Model Predictive Control (SMPC): The stochastic FHOCP is difficult because chance-constrained feasible sets are generally non-convex, motivating scenario-based approximation.MPC repeatedly solves a tractable finite-horizon problem, while SMPC adds probabilistic state constraints.
  • 3.2 Scenario-Based Model Predictive Control (SCMPC): SCMPC replaces the stochastic problem with K sampled scenarios, enforcing constraints on each sampled trajectory while averaging the cost across scenarios.Each scenario defines a deterministic affine trajectory, but the trajectories remain dependent on the optimized inputs.
  • 3.2 Scenario-Based Model Predictive Control (SCMPC): At every time step, SCMPC solves the scenario program using the measured state and applies only the first input of the optimal finite-horizon sequence.This receding-horizon feedback law is called the scenario solution.
  • 3.2 Scenario-Based Model Predictive Control (SCMPC): The sampled scenario program is convex and can become a linear, second-order cone, or quadratic program depending on the constraint sets and stage cost.Control inputs may also be parameterized by uncertainty basis functions, trading feedback quality against decision-variable count and computational complexity.
  • 3.3 A-Posteriori Scenario Removal: A-posteriori scenario removal mitigates erratic behavior from unlikely sampled outliers by removing R scenarios after sampling, at the cost of increasing the original sample size K.SCMPC lacks inherent recursive-feasibility guarantees, so the analysis assumes every finite-horizon scenario program remains feasible almost surely.

4 Problem Structure and Sample Complexity

The paper reduces SCMPC sample complexity by exploiting the multi-stage structure of finite-horizon stochastic programs and support ranks, while deriving closed-loop guarantees for admissible sample-removal pairs.

  • Sample-removal selection: The sample-removal pair (K, R) balances constraint robustness, computational complexity, and closed-loop cost: increasing K generally lowers violations but raises complexity and cost.Increasing R raises the required lower bound on K, while potentially improving solution quality and reducing closed-loop cost.
  • Support rank: The finite-horizon stochastic program contains multiple stage-wise chance constraints, requiring an extension of the classic scenario approach and separate support-rank bounds.Support rank bounds the number of support constraints contributed by each chance constraint.
  • Support rank: Support rank can replace the classic decision-space bound Nm with much lower problem-structure-dependent bounds such as l ≤ n or m.For purely additive disturbances, each state constraint has support rank at most l; with additive and multiplicative disturbances, the first-step rank is at most m.
  • Support rank: These bounds decouple the required sample size K from the prediction horizon N and, for parameterized laws, from the number of basis functions at later stages.The decoupling follows from support-rank bounds for the first predicted step.
  • Sample-removal selection: Admissibility of (K, R) is tested through a one-dimensional integral whose bound decreases with K and increases with R, enabling bisection-based selection.For fixed R, sufficiently large K always yields an admissible pair; R = 0 also admits an exact analytic formula.
  • Closed-loop properties: Under the stated assumptions and an admissible sample-removal pair, expected closed-loop time-average constraint violations remain below ε, with almost-sure satisfaction established asymptotically.Theorem 15 covers any finite horizon, while Theorem 17 establishes the stronger almost-sure result as T →∞.

5 Numerical Example

The numerical examples evaluate SCMPC with joint and individual chance constraints under stochastic system dynamics. The results show little conservatism, reduced sample sizes relative to previous approaches, and a minor effect on average cost but a significant effect on cost variability.

  • 5 Numerical Example: The example uses a stochastic linear system with random matrices, additive disturbances, bounded inputs, two state constraints, quadratic costs, and MPC horizon N = 5.The constraints are considered jointly or individually, with X := X1 ∩ X2 for the joint case.
  • 5.2 Joint Chance Constraint: R = 0 and R = 100 produce similar trajectory means, but R = 0 has stronger outliers in the joint-constraint experiment.Figure 3 marks violating states in red and other states in black relative to the boundary of X.
  • 5.2 Joint Chance Constraint: With no removals, there is essentially no conservatism; minor conservatism for small removal sizes disappears as R →∞.The simulation covers T = 10, 000 closed-loop time steps.
  • 5 Numerical Example: Sample removal has a minor effect on average closed-loop cost ℓavg but significantly affects the standard deviation ℓstd.This pattern is reported for both the joint and individual chance-constraint examples.
  • 5.2 Joint Chance Constraint: 19 samples achieve 9.87% empirical closed-loop violations, compared with about 400 samples and about 0.05% violations for previous SCMPC approaches.For horizon N = 20, previous approaches require about 900 samples and yield about 0.2% violations.
  • 5.3 Individual Chance Constraints: For separate constraints X1 and X2, all cases show very little conservatism in simulations over T = 10, 000 time steps.The individual probability levels are ε1 = 5% and ε2 = 10%, with support rank bounded by ρ1 = 1.

6 Conclusion

The paper develops SCMPC by combining average-in-time violation probabilities with support-rank reductions and a-posteriori constraint removal. This greatly reduces scenario counts and supports tractable SMPC applications to large-scale problems.

  • 6 Conclusion: The approach interprets constraint violations in average time and exploits the multi-stage FHOCP structure to greatly reduce the number of scenarios.It also accommodates a-posteriori constraint removal strategies.
  • 6 Conclusion: The computational efficiency is presented as enabling tractable SMPC applications with hundreds of decision variables.This is the paper's stated scope for large-scale problems.

A Proof of Lemmas 10 and 11

The proof develops a structural representation of constrained states and identifies a projection onto the constrained components. This representation supports the subsequent support-rank analysis.

  • A Proof of Lemmas 10 and 11: The constrained state is expressed by recursively substituting the system dynamics.The resulting representation separates the effects of decision variables, uncertainty, and additive terms.
  • A Proof of Lemmas 10 and 11: The proof introduces abbreviations for the system matrices used in the constrained-state representation.These abbreviations apply for i = 0, ..., N −1.
  • A Proof of Lemmas 10 and 11: If the constraint's support rank is l, a projection matrix P ∈ Rl×n captures the constrained directions of the state.The support rank is the co-dimension of the largest unconstrained linear subspace.
  • A Proof of Lemmas 10 and 11: When only the first two state components are constrained, l = 2 and P may contain the first two unit vectors as rows.This gives a concrete example of the projection construction.

Proof of Lemma 10

The proof bounds support rank by identifying an unconstrained null space in the decision-variable matrix. Additive disturbances do not affect this null space, yielding the stated support-rank bound.

  • Proof of Lemma 10: When the relevant system matrix B is constant, the constrained-state expression reduces to the form used to analyze its rank.The reduction applies for any i ∈ {1, ..., N}.
  • Proof of Lemma 10: The first l × Nm matrix has rank at most l, so its null space has dimension at least Nm − l.Because disturbances enter only through an additive term, they do not affect this null space.
  • Proof of Lemma 10: The null space is an unconstrained subspace, proving ρi ≤ l ≤ n for every constraint i.This establishes the support-rank bound used by Lemma 10.

Proof of Lemma 11

The proof bounds the relevant rank by exploiting null-space structure in the decision vector and the first matrix’s rank limitation.

  • For the first state constraint, these observations yield ρ1 ≤ m and prove Lemma 11.
  • The last (N −1)m decision-vector variables always lie in its null space.
  • The first matrix has rank at most m for every outcome of B̄(k).

Parameterized Control Laws

The paper extends the Lemma 11 rank argument to parameterized control laws by rewriting the scenario-dependent inputs in matrix-vector form and substituting them into the constraint expression.

  • The argument of Lemma 11 is extended to parameterized control laws introduced in Remark 7.
  • The scenario-dependent control inputs are expressed as a matrix-vector product using an abbreviation and the identity matrix I ∈ R^m×m.
  • Substituting this representation for the original decision vector preserves the same rank argument in (25).
Loading 1307.5640v2…