betaFeedback

WorksMathematics

Feasibility certificates for DeePC: A set invariance approach

Abstract

DeePC is posed on a window of past inputs and outputs, so its feasible set is a set of histories and is not available in closed form. We write the DeePC solution as an implicit ReLU network whose weights are built from Hankel matrices and whose activation patterns are the critical regions of the underlying quadratic program. This gives, directly from the Hankel matrices, the feasible set of DeePC as a polyhedral projection, its explicit piecewise-affine control law, and an exact linear model of the history window. We compute three invariant sets of histories: the maximal positively invariant set of the unsaturated linear branch, the region of recursive feasibility of DeePC without terminal ingredients, and the maximal control invariant set of admissible histories. We show these sets are nested and provide numerical examples.

Introduction

Consider an unknown discrete linear time invariant system Σ=(U,Y,B)\Sigma= (\mathcal{U}, \mathcal{Y}, \mathcal{B}) relating an input space U\mathcal{U} to an output space Y\mathcal{Y} by B⊂U×Y\mathcal{B} \subset\mathcal{U} \times\mathcal{Y} and a data set S\mathcal{S} gathered from the system, i.e., S={(uid,yid)}i=1T\mathcal{S} = \{(u_i^d, y_i^d)\}_{i=1}^{T} is a finite sequence of input/output pairs. The celebrated Willems’ Lemma [1] allows us to describe the linear system Σ\Sigma using only information S\mathcal{S}, provided the input sequence is Persistently Exciting (PE), which will be defined below.

Definition 1 (see [2]): For T>0T > 0 and v={vi}i=1T⊂Rmv = \{v_i\}_{i=1}^{T} \subset\mathbb{R}^{m},

  1. the depth-LL block-Hankel matrix is

HL(v):=[v1v2⋯vT−L+1v2v3⋯vT−L+2⋮⋮⋱⋮vLvL+1⋯vT],\mathcal{H}_{L}(v) := \begin{bmatrix} v_1 & v_2 & \cdots& v_{T-L+1}\\ v_2 & v_3 & \cdots& v_{T-L+2}\\ \vdots& \vdots& \ddots& \vdots\\ v_L & v_{L+1} & \cdots& v_T \end{bmatrix},
  1. the sequence v⊂Rmv \subset\mathbb{R}^{m} is Persistently Exciting of order LL if rank⁡(HL(v))=mL\operatorname{rank}(\mathcal{H}_{L}(v)) = mL.

Definition 1–ii) together with [2 Lemma 2], which is a restatement of [1 Thm 1], states that for a data set S\mathcal{S} such that udu^d is PE of order n+tn+t, then any LL–long sequence pair (u,y)={(u0,y0),…,(uL−1,yL−1)}∈B(u, y) = \{(u_0, y_0), \ldots, (u_{L-1}, y_{L-1})\} \in\mathcal{B} can be written as a linear combination of the elements of S\mathcal{S}, i.e., for some g∈RT−L+1g \in\mathbb{R}^{T-L+1}

\begin{bmatrix}u\\y\end{bmatrix} = \begin{bmatrix}\mathcal{H}_{L}(u^d)\\\mathcal{H}_{L}(y^d)\end{bmatrix}g. \tag*{(1)}\end{bmatrix}

Equation (1) is the cornerstone of data-driven controllers. The Hankel matrix of the data set S\mathcal{S} generates all possible trajectories. The relation between HL\mathcal{H}_{L} and the trajectories {u,y}\{u,y\} was established by contradiction, obscuring the relationship between the linear system Σ\Sigma and S\mathcal{S}. In [3], the authors overcome this conceptual barrier by providing constructive proofs for the results in [1]. Furthermore, [4] extends the framework to the continuous-time case. For more in-depth reviews of some recent developments in data-driven predictive control, we refer the reader to the excellent reviews [5, 6].

Data-enabled predictive control

DeePC, initially posed by [7] and rigorously analysed in [8], exploits the relationship (1) and includes it within an optimisation problem. However, DeePC, unlike traditional Model Predictive Control (MPC), is inherently an input/output controller. Since the current state is unavailable, the current operating condition is represented by a finite history window of the Tini>0T_{\mathrm{ini}} > 0 most recent measured inputs and outputs, ξ=(uini,yini)∈R(m+p)Tini\xi= (u_{\mathrm{ini}}, y_{\mathrm{ini}}) \in\mathbb{R}^{(m+p)T_{\mathrm{ini}}}, where uini=(uk−Tini,…,uk−1)⊂RmTiniu_{\mathrm{ini}} = (u_{k-T_{\mathrm{ini}}}, \ldots, u_{k-1}) \subset\mathbb{R}^{mT_{\mathrm{ini}}} and yini=(yk−Tini,…,yk−1)⊂RpTiniy_{\mathrm{ini}} = (y_{k-T_{\mathrm{ini}}}, \ldots, y_{k-1}) \subset\mathbb{R}^{pT_{\mathrm{ini}}}. Furthermore, Tini>0T_{\mathrm{ini}} > 0 satisfies the following assumption:

Assumption 1 (Sufficient initial window length): The initial trajectory length satisfies Tini≥ℓT_{\mathrm{ini}} \ge\ell, where ℓ\ell is the system observability index.1

Under Assumption 1, ξ\xi contains the information about the system’s internal condition required for prediction. The NN–horizon DeePC optimises over future input output predictions, u=(u0,…,uN−1)\mathbf{u}=(u_0,\ldots,u_{N-1}) and y=(y0,…,yN−1)\mathbf{y}=(y_0,\ldots,y_{N-1}) respectively, to regulate the system Σ\Sigma towards a desired reference r=(r0,…,rN−1)\mathbf{r}=(r_0,\ldots,r_{N-1}). The associated quadratic program is

P(r,ξ): min⁡g,u,y J(y,u,r)(2)\mathbb{P}(r,\xi):\ \underset{g,\mathbf{u},\mathbf{y}{}}{\min}\ J(\mathbf{y},\mathbf{u},\mathbf{r}) \tag*{(2)}
s.t.uk∈U,k=0,…,N−1,(3)\mathrm{s.t.}\quad u_k\in\mathbb{U},\quad k=0,\ldots,N-1, \tag*{(3)}
yk∈Y,k=0,…,N−1,(4)y_k\in\mathbb{Y},\quad k=0,\ldots,N-1, \tag*{(4)}
\begin{bmatrix}\mathbf{u}_p\\\mathbf{y}_p\end{bmatrix}g=\xi,\qquad \begin{bmatrix}\mathbf{u}_f\\\mathbf{y}_f\end{bmatrix}g= \begin{bmatrix}\mathbf{u}\\\mathbf{y}\end{bmatrix}, \tag*{(5)}\end{bmatrix}

where

[upuf]=HL(ud),[ypyf]=HL(yd).\begin{bmatrix}\mathbf{u}_p\\\mathbf{u}_f\end{bmatrix}=\mathcal{H}_L(u^d),\qquad \begin{bmatrix}\mathbf{y}_p\\\mathbf{y}_f\end{bmatrix}=\mathcal{H}_L(y^d).

The relations in (2d) ensure consistency with the measured input/output history and future input/output predictions. Consequently, the measured history ξ\xi serves as the known initial condition for the behavioural predictor without explicitly reconstructing the plant state. The cost, in the standard framework, penalises deviations from a reference: J(y,u,r)=∑k=0N−1(∥yfut,k−rk∥Q2+∥ufut,k−uref,k∥R2)J(\mathbf{y},\mathbf{u},\mathbf{r})=\sum_{k=0}^{N-1}\left(\|y_{\mathrm{fut},k}-r_k\|_Q^2+\|u_{\mathrm{fut},k}-u_{\mathrm{ref},k}\|_R^2\right). In [9], the authors modified problem (2) by adding regularisation terms to the cost to ensure the optimisation problem is well-posed. Slack variables in (2d), common in practice [7], soften the consistency constraint, so that (2) becomes feasible for histories that no trajectory of Σ\Sigma generates; they are excluded in this paper. The authors of [10] and [11] reframe the DeePC problem into a min-max robust formulation that optimises worst-case performance over an uncertainty set derived from the non-unique solutions to the behavioural data equations. The constraints of (2) satisfy the following assumption.

Assumption 2: The sets U⊂Rm\mathbb{U}\subset\mathbb{R}^m and Y⊂Rp\mathbb{Y}\subset\mathbb{R}^p are convex and compact. In addition, U\mathbb{U} contains the origin in its non-empty interior.

Stability of the origin is ensured via the addition of suitable terminal ingredients, similar to model-based MPC. [12] includes these terminal sets in the DeePC formulation; [13] extends these ideas to a nonlinear setting, ensuring tracking of a given target. In contrast, [14] modifies (2) to allow updates to the Hankel matrices by imposing additional constraints on u\mathbf{u}. We refer the reader to [15] for an in-depth review of DeePC.

Set Invariance and Feasibility in DeePC: Current Limitations and Contributions

Recursive feasibility is a key issue for predictive-based controllers because it ensures that solutions to (2) exist along the closed-loop trajectories. In nominal linear time-invariant settings with PE data, direct DeePC yields an initial feasible set that is theoretically equivalent to that of standard model-based output-feedback MPC [7], [16]. A similar result was obtained by [17], who studied feasibility in the case of partial information (a hybrid between data-driven and model-based approaches). To enforce recursive feasibility and closed-loop stability, [6], [18] introduced terminal equality constraints and data-driven terminal invariant sets, which guarantee a valid shifted trajectory at each time step while expanding the controllable region. Under measurement noise and disturbances, tube-based and robust min-max formulations preserve recursive feasibility by tightening state/input constraints and introducing initial-condition slack variables [19]. Lastly, [20] proposes a generalisation of finite control sets MPC to DeePC.

Computing feasible sets in data-driven predictive control requires computing a set for histories ξ\xi rather than an initial state. This poses an issue when projecting dataset-dependent trajectory variables. This input-state framework has been used to certify linear control laws by constructing data-driven invariant sets [21], [22] or control barrier functions directly from noise-corrupted trajectories [23], [24]. Furthermore, maintaining recursive feasibility without shrinking the admissible feasible domain under noisy conditions requires specialised set-expansion techniques and robust safety-critical relaxations [24], [25]. In this paper, we will focus on two fronts: DeePC and set-theoretic computations for data-driven predictive controllers. We propose a method for computing the feasible set of (2) that avoids projecting out the dataset-dependent variable g∈RT−L+1g\in\mathbb{R}^{T-L+1}: gg is eliminated in closed form, and only the mNmN future inputs remain. We exploit the structure of (2) to formulate an implicit Neural Network (NN) [26], [27] whose weights are computed from the Hankel matrices and whose activation patterns are the critical regions of (2). The contributions of this paper are:

  1. An interpretation of the DeePC problem in terms of implicit NNs whose activation patterns are the critical regions of (2). This representation allows us to characterise the region where constraints are not triggered. Our first invariant set, akin to the model-based Maximal Positive Invariant (MPI) set and the data-driven version from [23], is in Proposition 2.

  2. A characterisation of the DeePC feasible region in the augmented state ξ\xi, of the explicit Piece-wise Affine (PWA) DeePC law, and of an exact linear model of the history window, all computed from data. Proposition 3 partitions the history space into regions where a linear gain can be applied and shows that these constitute the feasible set of DeePC.

iii) Construction of data-driven invariant sets: the invariant set of the unsaturated branch, the region of recursive feasibility of DeePC without terminal ingredients, and the maximal control invariant set of admissible histories, together with their ordering. Theorem 4 and its corollary show that these invariant sets nest.

These results complement existing feasibility certificates in the DeePC literature and relate them to their model-based counterparts.

Notation: The n×nn \times n identity matrix is In\mathbb{I}_n. For a matrix A∈Rn×mA \in\mathbb{R}^{n \times m}, A†A^{\dagger} is the Moore–Penrose pseudo inverse, im⁡A\operatorname{im} A its range, and, for an index set A\mathcal{A}, AAA_{\mathcal{A}} collects the rows indexed by A\mathcal{A}, AA,BA_{\mathcal{A},\mathcal{B}} the corresponding sub matrix, and Aˉ\bar{\mathcal{A}} is the complement of A\mathcal{A}. ρ(⋅)\rho(\cdot) is the spectral radius and ϕ(v)=max⁡(v,0)\phi(v) = \max(v, 0), taken component-wise, is the ReLU. Inequalities between vectors hold component-wise.

Definition 2 (Implicit neural network): An implicit NN N:Rnz→Rno\mathcal{N}: \mathbb{R}^{n_z} \to\mathbb{R}^{n_o} is defined by the solution of the following system of equations

ζ=Wϕ(ζ)+Yz+b,N(z)=Wfϕ(ζ)+Yfz+bf,(6)\begin{aligned} \zeta&= W\phi(\zeta) + Yz + b,\\ \mathcal{N}(z) &= W_f\phi(\zeta) + Y_fz + b_f, \tag*{(6)} \end{aligned}

for an activation ϕ(⋅)\phi(\cdot), weights W∈Rnc×ncW \in\mathbb{R}^{n_c \times n_c}, Y∈Rnc×nzY \in\mathbb{R}^{n_c \times n_z}, Wf∈Rno×ncW_f \in\mathbb{R}^{n_o \times n_c}, Yf∈Rno×nzY_f \in\mathbb{R}^{n_o \times n_z}, and biases b∈Rnyb \in\mathbb{R}^{n_y}, bf∈Rnob_f \in\mathbb{R}^{n_o}.

Definition 3 (MPI): For f:D→Vf : \mathcal{D} \to\mathcal{V} and S⊆D\mathcal{S} \subseteq\mathcal{D}, the MPI subset of S\mathcal{S} is O(f,S):={ξ∈S:fk(ξ)∈S, ∀k∈N}\mathcal{O}(f,\mathcal{S}) := \{\xi\in\mathcal{S}: f^k(\xi) \in\mathcal{S},\ \forall k \in\mathbb{N}\} where fk(⋅)f^k(\cdot) is the repeated application of the map f(⋅)f(\cdot).

Implicit Neural Network Representation

In this section, we express (2) using an implicit neural network developed in [27]. We condense (2) using the following lemma:

Lemma 1 (Condensed DeePC QP): Suppose Assumptions 1 and 2 hold. Suppose, in addition, Q⪰0Q \succeq0, R≻0R \succ0, and given N\mathcal{N} the basis of ker⁡(Aeq)\operatorname{ker}(A_{\mathrm{eq}}) where Aeq=[Up⊤,Yp⊤]⊤A_{\mathrm{eq}} = [U_p^\top, Y_p^\top]^\top, UfNU_f\mathcal{N} has full row rank. The QP (2) is equivalent to

min⁡12u⊤Hu+z⊤F⊤u,(7)\min\frac{1}{2}u^\top H u + z^\top F^\top u, \tag*{(7)}
s.t. Gu≤Sz+w,(8)\text{s.t. } Gu \le Sz + w, \tag*{(8)}

where z=(ξ,r)z = (\xi,r), H∈RmN×mNH \in\mathbb{R}^{mN \times mN} such that H≻0H \succ0, F∈R(m+p)Tini+Np×NmF \in\mathbb{R}^{(m+p)T_{\mathrm{ini}}+Np \times Nm}, G∈R(nu+ny)N×NmG \in\mathbb{R}^{(n_u+n_y)N \times Nm}, S∈R(nu+ny)N×((m+p)Tini+Np)S \in\mathbb{R}^{(n_u+n_y)N \times((m+p)T_{\mathrm{ini}}+Np)}, and w∈R(nu+ny)Nw \in\mathbb{R}^{(n_u+n_y)N}.

Proof: First, we eliminate the behavioural coefficient gg; in (2d), its role splits into past and future components. The future trajectory is u=Ufgu = U_f g and y=Yfgy = Y_f g. Replacing this in the cost yields

J(g)=g⊤(Uf⊤(IN⊗R)Uf+Yf⊤(IN⊗Q)Yf)g−2r⊤(IN⊗Q)Yfg+r⊤(IN⊗Q)r.J(g) = g^\top\left(U_f^\top(\mathbb{I}_N \otimes R)U_f + Y_f^\top(\mathbb{I}_N \otimes Q)Y_f\right)g - 2r^\top(\mathbb{I}_N \otimes Q)Y_f g + r^\top(\mathbb{I}_N \otimes Q)r.

The consistency conditions are equality constraints Aeqg=ξA_{\mathrm{eq}}g = \xi. Solving these yield g=Aeq+ξ+Ncg = A_{\mathrm{eq}}^+\xi+ \mathcal{N}c with c∈Rdim⁡(ker⁡(Aeq))c \in\mathbb{R}^{\dim(\operatorname{ker}(A_{\mathrm{eq}}))}. By assumption, UfNU_f\mathcal{N} has full row rank, then V=N(UfN)†V = \mathcal{N}(U_f\mathcal{N})^\dagger, yields UfV=ImNU_fV = \mathbb{I}_{mN}. From u=Ufgu = U_f g, we obtain u=UfAeq†ξ+UfNcu = U_fA_{\mathrm{eq}}^\dagger\xi+ U_f\mathcal{N}c which leads to c=(UfN)†(u−UfAeq†ξ)c = (U_f\mathcal{N})^\dagger(u - U_fA_{\mathrm{eq}}^\dagger\xi). The behavioural coefficient vector gg can be expressed as

g=(IT−VUf)Aeq†ξ+Vu+Nc0,c0∈ker⁡UfN.(9)g = (\mathbb{I}_T - VU_f)A_{\mathrm{eq}}^\dagger\xi+ Vu + \mathcal{N}c_0,\qquad c_0 \in\operatorname{ker}U_f\mathcal{N}. \tag*{(9)}

The matrix VV satisfies UfA0=0U_fA_0 = 0. Since Nc0∈ker⁡[Aeq⊤ Uf⊤]⊤⊆ker⁡Yf\mathcal{N}c_0 \in\operatorname{ker}[A_{\mathrm{eq}}^\top\ U_f^\top]^\top\subseteq\operatorname{ker}Y_f (zero input generates zero outputs), the prediction y=Yf(A0ξ+Vu)y = Y_f(A_0\xi+ Vu) does not depend on c0c_0; as JJ and (2b)–(2c) depend on gg only through (u,y)(u,y), the QP (2) becomes a problem in uu alone. From Assumption 2, we have that there exist Py∈Rny×qyP_y \in\mathbb{R}^{n_y \times q_y}, Pu∈Rnu×quP_u \in\mathbb{R}^{n_u \times q_u} with ny>0n_y > 0 and nu>0n_u > 0 that approximate the sets Y\mathbb{Y} and U\mathbb{U}. Substituting u=Ufgu = U_f g and y=Yfgy = Y_f g into the polytopic constraints and stacking the constraints over the prediction horizon gives the prediction constraints Gθ≤w+[Sξ Sr]zG\theta\le w + [S_{\xi}\ S_r]z where G=[(IN⊗Pu)⊤ V⊤Yf⊤(IN⊗Py)⊤]⊤G = [(\mathbb{I}_N \otimes P_u)^\top\ V^\top Y_f^\top(\mathbb{I}_N \otimes P_y)^\top]^\top, w=[(IN⊗qu)⊤ (IN⊗qy)⊤]⊤w = [(\mathbb{I}_N \otimes q_u)^\top\ (\mathbb{I}_N \otimes q_y)^\top]^\top, and

S=[Sξ Sr]=[00−(IN⊗Py)YfA00].S = [S_{\xi}\ S_r] = \begin{bmatrix} 0 & 0\\ -(\mathbb{I}_N \otimes P_y)Y_fA_0 & 0 \end{bmatrix}.

Lastly, the cost matrices are the following:

H=V⊤(Uf⊤(IN⊗R)Uf+Yf⊤(IN⊗Q)Yf)⏟H~V,H = V^\top\underbrace{\left(U_f^\top(\mathbb{I}_N \otimes R)U_f + Y_f^\top(\mathbb{I}_N \otimes Q)Y_f\right)}_{\widetilde{H}}V,
F=[FξFr]=[A0⊤H~(IN⊗Q)Yf]V.F = \begin{bmatrix} F_{\xi}\\ F_r \end{bmatrix} = \begin{bmatrix} A_0^\top\widetilde{H}\\ (\mathbb{I}_N \otimes Q)Y_f \end{bmatrix}V.

Finally, UfV=ImNU_fV = \mathbb{I}_{mN} gives H=IN⊗R+V⊤Yf⊤(IN⊗Q)YfV⪰IN⊗R≻0H = \mathbb{I}_N \otimes R + V^\top Y_f^\top(\mathbb{I}_N \otimes Q)Y_fV \succeq\mathbb{I}_N \otimes R \succ0. ■

The condition of UfN∈RmN×dim⁡ker⁡AeqU_fN \in\mathbb{R}^{mN \times\dim\ker A_{\mathrm{eq}}} being full rank imposes a restriction on the data sequence length, i.e., Tini(m+p)+mN≤TT_{\mathrm{ini}}(m+p)+mN \le T following the dimension theorem. With the DeePC QP in condensed form, we can express its solution using the implicit NNs from Definition 2. This can be summarised in the following lemma, which has been adapted to our setting from [27 Theorem 6]

Lemma 2 (Adapted from [27]). Suppose Lemma 1 holds. The DeePC problem mapping a history z=(ξ,r)z=(\xi,r) to inputs uu written in the compact form

u∗(z)=arg⁡min⁡12u⊤Hu+z⊤Fu,(10)u^*(z)=\arg\min\frac{1}{2}u^\top H u+z^\top F u, \tag*{(10)}
s.t. Gu≤Sz+w,(11)\mathrm{s.t.}\ Gu\le Sz+w, \tag*{(11)}

where H≻0H\succ0 is a positive definite Hessian, and F∈Rn×mNF\in\mathbb{R}^{n\times mN}. This mapping can be expressed as an implicit neural network

ζ=Wϕ(ζ)+Yz+b,(12)\zeta=W\phi(\zeta)+Yz+b, \tag*{(12)}
u∗(z)=Wfϕ(ζ)+Yfz,(13)u^*(z)=W_f\phi(\zeta)+Y_fz, \tag*{(13)}

with ϕ(⋅)\phi(\cdot) being the ReLU activation and with analytic expressions for the weights and biases given by

W=Iny−GH−1G⊤,Wf=−H−1G⊤,b=−w,(14)W=\mathbb{I}_{n_y}-GH^{-1}G^\top,\quad W_f=-H^{-1}G^\top,\quad b=-w, \tag*{(14)}
Y=−S−GH−1F⊤,Yf=−H−1F⊤,bf=0.(15)Y=-S-GH^{-1}F^\top,\quad Y_f=-H^{-1}F^\top,\quad b_f=0. \tag*{(15)}

Zero-Activation Region and Feedback Law

In this section, we analyse the closed-loop behaviour inside the linear branch. The zero-activation condition provides the simplest affine branch of the constrained controller (7b). When ϕ(ζ)=0\phi(\zeta)=0, the implicit NN output is

u∗(ξ,r)=−H−1(Fξξ+Frr).(16)u^*(\xi,r)=-H^{-1}(F_\xi\xi+F_r r). \tag*{(16)}

The associated behavioural parameter is g∗=Γξ−VH−1Frrg^*=\Gamma\xi-VH^{-1}F_r r with Γ=(A0−VH−1Fξ)\Gamma=(A_0-VH^{-1}F_\xi). Replacing this control law into the constraints, we have the admissible set X\mathcal{X} for initial histories:

[(IN⊗Pu)Uini(IN⊗Py)Yini]Γξ≤[1N⊗qu1N⊗qy]−[(IN⊗Pu)Uf(IN⊗Py)Yf]VH−1Frr.\begin{bmatrix} (\mathbb{I}_N\otimes P_u)U_{\mathrm{ini}}\\ (\mathbb{I}_N\otimes P_y)Y_{\mathrm{ini}} \end{bmatrix} \Gamma\xi \le \begin{bmatrix} \mathbb{1}_N\otimes q_u\\ \mathbb{1}_N\otimes q_y \end{bmatrix} - \begin{bmatrix} (\mathbb{I}_N\otimes P_u)U_f\\ (\mathbb{I}_N\otimes P_y)Y_f \end{bmatrix} VH^{-1}F_r r.

Furthermore, the zero-activation branch is polyhedral.

Proposition 1 (Zero-activation admissible region): Suppose Assumptions 1 and 2 hold. Fix r∈RpNr\in\mathbb{R}^{pN}. On the set

Ξ0(r)={ξ:Sξξ+w≥−Srr},(17)\Xi_0(r)=\{\xi:S_\xi\xi+w\ge-S_r r\}, \tag*{(17)}

the solution of (7a) at any ξ∈Ξ0(r)∩X\xi\in\Xi_0(r)\cap\mathcal{X} satisfies ϕ(ζ)=0\phi(\zeta)=0.

Proof. The solution of the nonlinear equation (7a) can be found using fixed point iterations, i.e., ζk+1=Wζk+Yz+b\zeta_{k+1}=W\zeta_k+Yz+b where z=(ξ,r)z=(\xi,r). From Lemma 2, if ξ∈Ξ0(r)\xi\in\Xi_0(r), then Yx+b≤0Yx+b\le0. Consider, an initial ζ0∈Rnc\zeta_0\in\mathbb{R}^{n_c} such that w.l.o.g ζ0≥0\zeta_0\ge0. Then, Wϕ(ζ0)=Wζ0W\phi(\zeta_0)=W\zeta_0 and Yz+b∈R≤0ncYz+b\in\mathbb{R}^{n_c}_{\le0} lead to an iterate ζ1\zeta_1 approaching the nonpositive orthant. As long as ζk∉R≤0nc\zeta_k\notin\mathbb{R}^{n_c}_{\le0}, then ϕ(ζk)≠0\phi(\zeta_k)\ne0. However, since Yz+bYz+b is constant and negative, the iterates converge to R≤0nc\mathbb{R}^{n_c}_{\le0}, i.e., ϕ(ζk)→0\phi(\zeta_k)\to0.

The set Ξ0(r)\Xi_0(r) is not necessarily bounded. Proposition 2 below shows that the rows of X\mathcal{X} restrict only the initial history. From now on we consider regulation, r=0r=0, so that z=ξz=\xi, F=FξF=F_\xi and S=SξS=S_\xi. We write Ξ0=Ξ0(0)\Xi_0=\Xi_0(0),

S^:=Sξ+GH−1Fξ⊤,M:=GH−1G⊤,(18)\hat{S}:=S_\xi+GH^{-1}F_\xi^\top,\qquad M:=GH^{-1}G^\top, \tag*{(18)}

so that Y=−S^Y=-\hat{S}, and E1:=[Im 0]∈Rm×mNE_1:=[\mathbb{I}_m\ 0]\in\mathbb{R}^{m\times mN} selects the input uu applied by the receding-horizon controller.

History Window Closed-Loop Dynamics

The closed-loop analysis requires describing the system evolution in terms of the current ξ\xi and uu. Let Π\Pi be the shift that removes the oldest input/output pair from ξ\xi and EE the matrix that inserts a new pair, so that ξ+=Πξ+E(uk,yk)\xi^+=\Pi\xi+E(u_k,y_k), and let Uf(1),Yf(1)U_f^{(1)},Y_f^{(1)} be the first mm and pp rows of Uf,YfU_f,Y_f.

Lemma 3 (History dynamics): Suppose Assumption 1 hold, let V=im⁡AeqV=\operatorname{im}A_{\mathrm{eq}}, and let [Lξ Lu]=yf(1)Θ⊤[L_\xi\ L_u]=y_f^{(1)}\Theta^\top with Θ=[Aeq⊤ Uf(1)⊤]⊤\Theta=[A_{\mathrm{eq}}^\top\ U_f^{(1)\top}]^\top. Every trajectory of Σ\Sigma satisfies y=Lξξ+Luuy=L_\xi\xi+L_u u and

ξ+=Aξξ+Bξu,Aξ:=Π+E[0Lξ],Bξ:=E[ImLu].(19)\xi^+=A_\xi\xi+B_\xi u,\qquad A_\xi:=\Pi+E\begin{bmatrix}0\\L_\xi\end{bmatrix},\qquad B_\xi:=E\begin{bmatrix}\mathbb{I}_m\\L_u\end{bmatrix}. \tag*{(19)}

Moreover, AξV⊆VA_{\xi}\mathbb{V} \subseteq\mathbb{V} and im⁡Bξ⊆V\operatorname{im} B_{\xi} \subseteq\mathbb{V}.

Proof. For gˉ∈ker⁡Θ\bar{g} \in\ker\Theta, by Assumption 1, we have that yf(1)gˉ=0y_f^{(1)}\bar{g}=0. Hence yf(1)gˉ=yf(1)Θ†Θgˉy_f^{(1)}\bar{g}=y_f^{(1)}\Theta^{\dagger}\Theta\bar{g}. By (1), every trajectory segment satisfies (ξ,u,y)=(Aeqgˉ,Uf(1)gˉ,yf(1)gˉ)(\xi,u,y)=(A_{\mathrm{eq}}\bar{g},U_f^{(1)}\bar{g},y_f^{(1)}\bar{g}) for some gˉ\bar{g}, so y=yf(1)Θ†Θgˉ=Lξξ+Luuy=y_f^{(1)}\Theta^{\dagger}\Theta\bar{g}=L_{\xi}\xi+L_u u, and (19) follows. For ξ∈V\xi\in\mathbb{V} and any uu, ξ+\xi^{+} is a history of Σ\Sigma, hence in V\mathbb{V}; taking u=0u=0 gives AξV⊆VA_{\xi}\mathbb{V}\subseteq\mathbb{V} and then im⁡Bξ⊆V\operatorname{im} B_{\xi}\subseteq\mathbb{V}.

On Ξ0\Xi_0, the closed-loop is linear

ξ+=Aclξ,Acl:=Aξ−BξH−1Fξ,(20)\xi^{+}=A_{\mathrm{cl}}\xi,\qquad A_{\mathrm{cl}}:=A_{\xi}-B_{\xi}H^{-1}F_{\xi}, \tag*{(20)}

built from the Hankel matrices only. On V\mathbb{V}, AclA_{\mathrm{cl}} coincides with the map Π+E[(Uf(1))⊤ (yf(1))⊤]⊤(A0−VH−1Fξ)\Pi+E[(U_f^{(1)})^{\top}\ (y_f^{(1)})^{\top}]^{\top}(A_0-VH^{-1}F_{\xi}) obtained from the first predicted input/output pair of the QP (2).

Membership of Ξ0\Xi_0 only guarantees that the unconstrained prediction is admissible at the current sampling instant. The MPI O∞=O(Acl,Ξ0)\mathcal{O}_{\infty}=\mathcal{O}(A_{\mathrm{cl}},\Xi_0) from Definition 3 is the set that can certify the closed-loop dynamics inside Ξ0\Xi_0. The computation of O∞\mathcal{O}_{\infty} follows the algorithm of Gilbert and Tan [28]: P0:=Ξ0\mathcal{P}_0:=\Xi_0 and

Pk+1:=Pk∩{ξ:S^Aclk+1ξ+w≥0, Aclk+1ξ∈X}.(21)\mathcal{P}_{k+1}:=\mathcal{P}_k\cap\{\xi:\hat{S}A_{\mathrm{cl}}^{k+1}\xi+w\geq0,\ A_{\mathrm{cl}}^{k+1}\xi\in\mathcal{X}\}. \tag*{(21)}

This process and its properties are summarised in the following result:

Proposition 2 (Unsaturated invariant set): Suppose Assumptions 1–2 hold, r=0r=0, and AclA_{\mathrm{cl}} restricted to V\mathbb{V} is Schur. Then:

i) there is a finite k⋆k^{\star} with Pk⋆+1=Pk⋆=O∞\mathcal{P}_{k^{\star}+1}=\mathcal{P}_{k^{\star}}=\mathcal{O}_{\infty}, and O∞\mathcal{O}_{\infty} is a polytope;

ii) for ξ∈O∞\xi\in\mathcal{O}_{\infty}, the QP (2) is feasible along the closed loop trajectory of (20), and u∈Uu\in\mathbb{U}, y∈Yy\in\mathbb{Y}.

for all k∈Nk\in\mathbb{N}

Proof. i) Ξ0\Xi_0 is compact with the origin in its relative interior (Proposition 1) and V\mathbb{V} is AclA_{\mathrm{cl}}-invariant (Lemma 3); finite determination follows from [28 Thm. 4.1] applied on V\mathbb{V}. ii) follows from Proposition 1.

Feasible Sets and Invariance

In this section, we study and analyse the feasible sets of the DeePC problem and their invariance properties. By Lemma 1, the histories for which (2) is feasible form the feasible set

FN:={ξ:∃u∈RmN, Gu≤Sξξ+w},(22)\mathcal{F}_N:=\{\xi:\exists u\in\mathbb{R}^{mN},\ Gu\leq S_{\xi}\xi+w\}, \tag*{(22)}

the projection onto ξ\xi of a polyhedron in R(m+p)Tini+mN\mathbb{R}^{(m+p)T_{\mathrm{ini}}+mN}. The DeePC feasible set (22) depends on the horizon length NN and is not necessarily an invariant set for small NN because its underlying DeePC problem lacks terminal ingredients [12]. As NN grows, the feasible set approaches the maximal control invariant, as shown in the model-based case in [29, 30].

Critical Regions and Affine Control Laws

When the activation pattern of (7a) is fixed, (7b) is affine in ξ\xi; the following result identifies the set on which each pattern is valid.

Proposition 3 (Critical regions): Suppose Assumptions 1 and 2 hold. Fix r=0r=0. Let A={A⊆{1,…,nc}:GA\mathcal{A}=\{\mathcal{A}\subseteq\{1,\ldots,n_c\}:G_{\mathcal{A}} has full row rank}\}, for A∈A\mathcal{A}\in\mathcal{A}, let λA(ξ):=−MAA−1(S^Aξ+wA)\lambda_{\mathcal{A}}(\xi):=-M_{\mathcal{A}\mathcal{A}}^{-1}(\hat{S}_{\mathcal{A}}\xi+w_{\mathcal{A}}) and

RA:={ξ:λA(ξ)≥0, S^Aˉξ+wAˉ+MAˉAλA(ξ)≥0}.(23)\mathcal{R}_{\mathcal{A}}:=\{\xi:\lambda_{\mathcal{A}}(\xi)\geq0,\ \hat{S}_{\bar{\mathcal{A}}}\xi+w_{\bar{\mathcal{A}}}+M_{\bar{\mathcal{A}}\mathcal{A}}\lambda_{\mathcal{A}}(\xi)\geq0\}. \tag*{(23)}

i) For ξ∈RA\xi\in\mathcal{R}_{\mathcal{A}}, the vector ζ\zeta with ζA=λA(ξ)\zeta_{\mathcal{A}}=\lambda_{\mathcal{A}}(\xi) and ζAˉ=−(S^Aˉξ+wAˉ+MAˉAλA(ξ))\zeta_{\bar{\mathcal{A}}}=-(\hat{S}_{\bar{\mathcal{A}}}\xi+w_{\bar{\mathcal{A}}}+M_{\bar{\mathcal{A}}\mathcal{A}}\lambda_{\mathcal{A}}(\xi)) solves (7a).

ii) On RA\mathcal{R}_{\mathcal{A}}, u⋆(ξ)=KAξ+cAu^{\star}(\xi)=K_{\mathcal{A}}\xi+c_{\mathcal{A}} with KA:=−H−1(Fξ⊤−GA⊤MAA−1S^A)K_{\mathcal{A}}:=-H^{-1}(F_{\xi}^{\top}-G_{\mathcal{A}}^{\top}M_{\mathcal{A}\mathcal{A}}^{-1}\hat{S}_{\mathcal{A}}) and cA:=H−1GA⊤MAA−1wAc_{\mathcal{A}}:=H^{-1}G_{\mathcal{A}}^{\top}M_{\mathcal{A}\mathcal{A}}^{-1}w_{\mathcal{A}}.

iii) FN=⋃A∈ARA\mathcal{F}_N=\bigcup_{\mathcal{A}\in\mathcal{A}}\mathcal{R}_{\mathcal{A}}.

Proof. i) Substitute ϕ(ζ)\phi(\zeta), with ϕ(ζ)A=λA(ξ)≥0\phi(\zeta)_{\mathcal{A}}=\lambda_{\mathcal{A}}(\xi)\geq0 and ϕ(ζ)Aˉ=0\phi(\zeta)_{\bar{\mathcal{A}}}=0, in (7a) and use MAAλA(ξ)=−(S^Aξ+wA)M_{\mathcal{A}\mathcal{A}}\lambda_{\mathcal{A}}(\xi)=-(\hat{S}_{\mathcal{A}}\xi+w_{\mathcal{A}}). ii) Follows from (7b) with Wϕ(ζ)=−H−1GA⊤λA(ξ)W\phi(\zeta)=-H^{-1}G_{\mathcal{A}}^{\top}\lambda_{\mathcal{A}}(\xi). iii) ⊇\supseteq follows from i) and Lemma 2. The converse ⊆\subseteq, for ξ∈FN\xi\in\mathcal{F}_N, −(Hu⋆+Fξξ)-(Hu^{\star}+F_{\xi}\xi) is a nonnegative linear combination of the rows of GG active at u⋆u^{\star}; by Carathéodory’s theorem it is a nonnegative combination of linearly independent active rows indexed by some A∈A\mathcal{A}\in\mathcal{A}, and then ξ∈RA\xi\in\mathcal{R}_{\mathcal{A}}.

Proposition 3 is the data-driven counterpart of the explicit solution of multiparametric QPs [31] because we obtain a similar partition of the feasible set FN\mathcal{F}_N into linear regions. This proposition includes the results in Proposition 1, i.e., R∅=Ξ0\mathcal{R}_{\varnothing}=\Xi_0 and K∅=−H−1FξK_{\varnothing}=-H^{-1}F_{\xi}. By Lemma 3, on RA\mathcal{R}_{\mathcal{A}} the closed loop is affine,

ξ+=(Aξ+BξE1KA)ξ+BξE1cA.(24)\xi^{+}=(A_{\xi}+B_{\xi}E_1K_{\mathcal{A}})\xi+B_{\xi}E_1c_{\mathcal{A}}. \tag*{(24)}

We denote by fπf_{\pi} the resulting continuous PWA map on FN\mathcal{F}_N.

Region of recursive feasibility

Feasibility of the QP (2) at ξ\xi does not imply feasibility at ξ+\xi^{+}, as no terminal ingredient is imposed [12]. Using the MPI algorithm with initialisation S0:=X∩FN\mathcal{S}_0 := \mathcal{X} \cap\mathcal{F}_N, the DeePC feasible set is

Cπ:=O(fπ,S0).(25)\mathcal{C}_{\pi} := \mathcal{O}(f_{\pi},\mathcal{S}_0). \tag*{(25)}

For S⊆FN\mathcal{S} \subseteq\mathcal{F}_N, define the predecessor under the DeePC law

Pre⁡π(S):=⋃A{ξ∈RA:AAξ+aA∈S}(26)\operatorname{Pre}_{\pi}(\mathcal{S}) := \bigcup_{\mathcal{A}}\{\xi\in\mathcal{R}_{\mathcal{A}} : A_{\mathcal{A}}\xi+ a_{\mathcal{A}} \in\mathcal{S}\} \tag*{(26)}

and the nested sequence Sj+1:=Sj∩Pre⁡π(Sj)\mathcal{S}_{j+1} := \mathcal{S}_j \cap\operatorname{Pre}_{\pi}(\mathcal{S}_j).

Proposition 4 (Recursive feasibility). Suppose Assumptions 1–2 hold and r=0\mathbf{r}=0.

i) ξ∈Cπ\xi\in\mathcal{C}_{\pi} iff ξ∈X\xi\in\mathcal{X} and QP (2) is feasible along the DeePC closed loop trajectory.

ii) ∀j\forall j, Sj⊇Sj+1⊇Cπ\mathcal{S}_j \supseteq\mathcal{S}_{j+1} \supseteq\mathcal{C}_{\pi}.

Proof: i) If QP (2) is feasible at ξ\xi, the applied input and, by Lemma 3, the measured output coincide with the first predicted pair, which satisfies (2b)–(2c); hence ξ∈X\xi\in\mathcal{X} implies ξ+∈X\xi^{+} \in\mathcal{X} as in Proposition 2. ii) Cπ⊆Pre⁡π(Cπ)\mathcal{C}_{\pi} \subseteq\operatorname{Pre}_{\pi}(\mathcal{C}_{\pi}) and induction give Cπ⊆Sj\mathcal{C}_{\pi} \subseteq\mathcal{S}_j. If Sj+1=Sj\mathcal{S}_{j+1} = \mathcal{S}_j, then Sj⊆Pre⁡π(Sj)\mathcal{S}_j \subseteq\operatorname{Pre}_{\pi}(\mathcal{S}_j), so Sj⊆S0\mathcal{S}_j \subseteq\mathcal{S}_0 is positively invariant and Sj⊆Cπ\mathcal{S}_j \subseteq\mathcal{C}_{\pi}.

Invariant set hierarchy

By Lemma 3, the Maximal Control Invariant (MCI) subset of X\mathcal{X},

C∞:={ξ∈X:∃{uk}k∈N⊆U, Aξξ+Bξuk∈X ∀k∈N},(27)\mathcal{C}_{\infty} := \{\xi\in\mathcal{X} : \exists\{u_k\}_{k\in\mathbb{N}} \subseteq\mathcal{U},\ A_{\xi}\xi+ B_{\xi}u_k \in\mathcal{X}\ \forall k \in\mathbb{N}\}, \tag*{(27)}

is computed from data by Ω0:=X\Omega_0 := \mathcal{X}, Ωj+1:=Ωj∩Pre⁡c(Ωj)\Omega_{j+1} := \Omega_j \cap\operatorname{Pre}_{c}(\Omega_j), where Pre⁡c(Ω):={ξ:∃u∈U, Aξξ+Bξu∈Ω}\operatorname{Pre}_{c}(\Omega) := \{\xi: \exists u \in\mathcal{U},\ A_{\xi}\xi+ B_{\xi}u \in\Omega\} is a projection that eliminates mm variables [32, 33, 34]; [25] constructs such sets in input/output coordinates. The following is our main result and clarifies the relationship between the sets computed in the previous sections.

Theorem 4 (Set hierarchy). Suppose Assumptions 1–2 hold and r=0\mathbf{r}=0. Then

O∞⊆Cπ⊆C∞⊆S0⊆FN,O∞⊆Ξ0⊆S0.(28)\mathcal{O}_{\infty} \subseteq\mathcal{C}_{\pi} \subseteq\mathcal{C}_{\infty} \subseteq\mathcal{S}_0 \subseteq\mathcal{F}_N,\qquad\mathcal{O}_{\infty} \subseteq\Xi_0 \subseteq\mathcal{S}_0. \tag*{(28)}

Proof: On Ξ0\Xi_0, fπ=Aclf_{\pi}=A_{\mathrm{cl}}; hence O∞\mathcal{O}_{\infty} is positively invariant under fπf_{\pi} and O∞⊆Ξ0⊆S0\mathcal{O}_{\infty} \subseteq\Xi_0 \subseteq\mathcal{S}_0, so O∞⊆Cπ\mathcal{O}_{\infty} \subseteq\mathcal{C}_{\pi} by maximality. By Proposition 4 i), Cπ⊆X\mathcal{C}_{\pi} \subseteq\mathcal{X} is invariant under ξ+=Aξξ+Bξu\xi^{+}=A_{\xi}\xi+B_{\xi}u with u=E1u∗(ξ)∈Uu=E_1u^{*}(\xi)\in\mathcal{U}, so Cπ⊆C∞\mathcal{C}_{\pi} \subseteq\mathcal{C}_{\infty}. Let ξ0∈C∞\xi_0 \in\mathcal{C}_{\infty} with admissible inputs {uk}k\{u_k\}_k; the outputs y0,…,yN−1y_0,\ldots,y_{N-1} are entries of ξ1,…,ξN∈X\xi_1,\ldots,\xi_N \in\mathcal{X}, so (u0,…,uN−1)(u_0,\ldots,u_{N-1}) is feasible for (2) by Lemma 1, i.e., ξ0∈FN\xi_0 \in\mathcal{F}_N. The remaining inclusions hold by definition.

The inclusion chains in (28) are strict, i.e., S0∖C∞\mathcal{S}_0 \setminus\mathcal{C}_{\infty} contains histories at which DeePC is feasible although no admissible input avoids a future violation. The horizon NN plays an important role, as FN+1⊆FN\mathcal{F}_{N+1} \subseteq\mathcal{F}_N. Similarly, C∞∖Cπ\mathcal{C}_{\infty} \setminus\mathcal{C}_{\pi} shrinks as NN grows. Our last result addresses how positive invariant sets P\mathcal{P} from a linear gain KK, i.e., certified sets by the linear programs of [21], [22] applied to (19), belong to the hierarchy of Theorem 4.

Corollary 1 (Linear-feedback certificates). Suppose Assumptions 1–2 hold and r=0\mathbf{r}=0. For K∈Rm×(m+p)TiniK \in\mathbb{R}^{m\times(m+p)T_{\mathrm{ini}}}, let

M(K):={ξ:Aξξ+BξKξ, ξ∩{ξ∈X}}.\mathcal{M}(K) := \{\xi: A_{\xi}\xi+ B_{\xi}K\xi,\ \xi\cap\{\xi\in\mathcal{X}\}\}.

Then O∞⊆M(K0)\mathcal{O}_{\infty} \subseteq\mathcal{M}(K_0) and M(K)⊆C∞\mathcal{M}(K) \subseteq\mathcal{C}_{\infty} for every KK. In particular, every P⊆X\mathcal{P} \subseteq\mathcal{X} that is positively invariant for ξ+=(Aξ+BξK)ξ\xi^{+}=(A_{\xi}+B_{\xi}K)\xi with Kξ∈UK\xi\in\mathcal{U} for all ξ∈P\xi\in\mathcal{P} satisfies P⊆M(K)⊆C∞\mathcal{P} \subseteq\mathcal{M}(K) \subseteq\mathcal{C}_{\infty}.

Proof: M(K)⊆X\mathcal{M}(K) \subseteq\mathcal{X} is positively invariant under the admissible input u=Kξu=K\xi, hence M(K)⊆C∞\mathcal{M}(K) \subseteq\mathcal{C}_{\infty} by (27). The O∞⊆Ξ0⊆X\mathcal{O}_{\infty} \subseteq\Xi_0 \subseteq\mathcal{X} is positively invariant under Acl=Aξ+BξK0A_{\mathrm{cl}}=A_{\xi}+B_{\xi}K_0, and K0ξ=E1u∗(ξ)∈UK_0\xi=E_1u^{*}(\xi)\in\mathcal{U} on Ξ0⊆R0\Xi_0 \subseteq\mathcal{R}_0 by (4b); maximality of M(K0)\mathcal{M}(K_0) gives O∞⊆M(K0)\mathcal{O}_{\infty} \subseteq\mathcal{M}(K_0), and maximality gives P⊆M(K)\mathcal{P} \subseteq\mathcal{M}(K).

Corollary 1 adds a branch to (28): O∞⊆M(K0)⊆C∞\mathcal{O}_{\infty} \subseteq\mathcal{M}(K_0) \subseteq\mathcal{C}_{\infty} for the gain of the unsaturated branch and M(K)⊆C∞\mathcal{M}(K) \subseteq\mathcal{C}_{\infty} for every other gain, while no inclusion between M(K)\mathcal{M}(K) and Cπ\mathcal{C}_{\pi} follows from Theorem 4. Hence P⊆C∞\mathcal{P} \subseteq\mathcal{C}_{\infty} is necessary for the linear programs of [21], [22] to be feasible for a candidate set P\mathcal{P}, whatever the gain, and C∞\mathcal{C}_{\infty} bounds every certifiable set. The converse fails: a polyhedral control invariant set need not be invariant under any linear feedback, as noted in [22 Rem. 4] and by the definition of C∞\mathcal{C}_{\infty}. The programs of [21], [22] certify a given set, robustly to noise in [21], with one linear program whose size grows with TT; the recursions above compute maximal sets for exact data, at a cost that does not depend on TT once gg is eliminated but is exponential in ncn_c and mNmN in the worst case.

Illustrative examples

Consider the following baseline system

x+=[0.950.3−0.20.95]x+[01]u,y=[10]x,x^{+} = \begin{bmatrix} 0.95 & 0.3\\ -0.2 & 0.95 \end{bmatrix}x+ \begin{bmatrix} 0\\ 1 \end{bmatrix}u,\qquad y=\begin{bmatrix}1&0\end{bmatrix}x,

with n=ℓ=2n=\ell=2. A noise-free trajectory of length T=500T=500 was generated from x0=0x_0=0. With Tini=2T_{\mathrm{ini}}=2 and N=3N=3, L=5L=5 and rank⁡HL+n(ud)=7\operatorname{rank}\mathcal{H}_{L+n}(u^d)=7, so Assumption 1 holds. The constraints are ∣u∣≤0.5|u|\leq0.5 and ∣y∣≤1|y|\leq1, and Q=1Q=1, R=0.3R=0.3, so nc=12n_c=12.

Since pTini=npT_{\mathrm{ini}} = n, V=R4\mathbb{V} = \mathbb{R}^4. Every set in Figure 1 is computed from the Hankel matrices only. For display, histories are mapped to the current state xkx_k through the true model; as ξ↦(x,uini)\xi\mapsto(x,u_{\mathrm{ini}}) is a linear bijection, each figure shows π(P):={x:ξ∈P}\pi(\mathcal{P}) := \{x: \xi\in\mathcal{P}\}.

Three invariant-set plots

Figure 1. (a) Ξ0\Xi_0, the iterate P1\mathcal{P}_1 of (14) and O∞=P2\mathcal{O}_\infty= \mathcal{P}_2. (b) O∞\mathcal{O}_\infty, O(Acl,R∅)\mathcal{O}(\mathcal{A}_{\mathrm{cl}},\mathcal{R}_\varnothing) (dashed) and the invariant set of the model-based MPC’s unsaturated branch.

In Figure 1 (a), we observe the relation between the unsaturated branch Ξ0∩X\Xi_0 \cap\mathcal{X} and the largest invariant set contained within it O∞\mathcal{O}_\infty. For this system, the algorithm in [28] finished after two iterations, which explains the similar size of these two sets. The data-driven set implicitly constrains inputs and outputs, which makes for more stringent constraints which yield the difference seen in Figure 1 (b). The remaining difference is only because of X\mathcal{X}: π(O∞)=π(X)∩π(O(Acl,R∅))\pi(\mathcal{O}_\infty) = \pi(\mathcal{X}) \cap\pi(\mathcal{O}(\mathcal{A}_{\mathrm{cl}},\mathcal{R}_\varnothing)), where π(X)\pi(\mathcal{X}) is the set of states reachable through an admissible window. The two removed pieces, of area 0.118 each, contain states such as xk=(−0.984,1.317)x_k = (-0.984, 1.317), which can be reached with ∣yk−1∣≤1|y_{k-1}| \le1 only if uk−1≥1.225u_{k-1} \ge1.225. Lastly, for this example, the PWA affine control law yielded three regions; the recursion of Proposition 4 iii) terminated after two iterations, certifying Cπ\mathcal{C}_\pi, see Figure 1 (c). In R4\mathbb{R}^4, O∞⊆Cπ⊆C∞⊆S0\mathcal{O}_\infty\subseteq\mathcal{C}_\pi\subseteq\mathcal{C}_\infty\subseteq\mathcal{S}_0 and Ξ0⊆C∞\Xi_0 \subseteq\mathcal{C}_\infty were verified, and C∞∖Cπ\mathcal{C}_\infty\setminus\mathcal{C}_\pi has empty interior; since both sets are closed, Cπ=C∞\mathcal{C}_\pi= \mathcal{C}_\infty. Thus, for this design, the DeePC policy loses nothing with respect to an unrestricted admissible input, and its region of recursive feasibility is 97.02% of S0\mathcal{S}_0 in projection; the remaining 2.98% is the cost of the horizon N=3N = 3 without terminal ingredients. Restricting DeePC to its unsaturated branch retains 60.72% of Cπ\mathcal{C}_\pi.

Conclusions and Future Work

The DeePC quadratic program admits an exact condensed form on the consistent histories, whose solution is an implicit NN with weights built from Hankel matrices. Its activation patterns are the critical regions of the QP, which yield the feasible set of DeePC, an exact linear model of the history window, and three nested invariant sets, all computed from the Hankel matrices. In the example, the region of recursive feasibility of DeePC without terminal ingredients coincides with the maximal control invariant set of admissible histories. The construction requires exact data, and enumerating activation patterns grows combinatorially with ncn_c and mNmN. Future work will address noisy data, where the condensed problem becomes a least-squares predictor, the sets must be robustified, and Cπ\mathcal{C}_\pi and C∞\mathcal{C}_\infty can be used as data-driven terminal ingredients.

References

  1. [1]J. C. Willems, P. Rapisarda, I. Markovsky, and B. L. M. D. Moor, “A note on persistency of excitation,” Syst. Control Lett., vol. 54, no. 4, pp. 325–329, 2005.
  2. [2]C. D. Pesci and P. Tesi, “Formulas for Data-Driven Control: Stabilization, Optimality, and Robustness,” IEEE TAC, vol. 65, no. 3, pp. 909–924, 2020.
  3. [3]I. Markovsky, E. Prieto-Araujo, and F. Dörfler, “On the persistency of excitation,” Automatica, vol. 147, p. 110657, 2023.DOI
  4. [4]V. G. Lopez and M. A. Muller, “On a Continuous-Time Version of Willems’ Lemma,” Proc. IEEE CDC, vol. 2022-Decem, pp. 2759–2764, 2022.DOI
  5. [5]I. Markovsky and F. Dörfler, “Behavioral systems theory in data-driven analysis, signal processing, and control,” Annual Reviews in Control, vol. 52, pp. 42–64, 2021.
  6. [6]J. Berberich and F. Allgöwer, “An overview of systems-theoretic guarantees in data-driven model predictive control,” Annual Review of Control, Robotics, and Autonomous Systems, vol. 8, no. 1, pp. 77–100, May 2025.DOI
  7. [7]J. Coulson, J. Lygeros, and F. Dörfler, “Data-enabled predictive control: in the shallows of the deep,” in 2019 18th ECC, 2019, pp. 307–312.
  8. [8]J. Berberich, J. Köhler, M. A. Müller, and F. Allgöwer, “Data-driven model predictive control: closed-loop guarantees and experimental results,” at - Automatisierungstechnik, vol. 69, no. 7, pp. 608–618, 2021.DOI
  9. [9]F. Dörfler, J. Coulson, and I. Markovsky, “Bridging direct and indirect data-driven control formulations via regularizations and relaxations,” IEEE TAC, vol. 68, no. 2, pp. 883–897, 2023.
  10. [10]Y. Wang, Q. Liu, and C. Shang, “On min-max robust data-driven predictive control considering non-unique solutions to behavioral representation,” IEEE TAC, 2026.arxiv.org/abs/2501.17350
  11. [11]J. Berberich, J. Köhler, M. A. Müller, and F. Allgöwer, “Robust constraint satisfaction in data-driven MPC,” in Proc. IEEE CDC, 2020, pp. 1260–1267.DOI
  12. [12]——, “On the design of terminal ingredients for data-driven MPC,” IFAC-PapersOnLine, vol. 54, no. 6, pp. 257–263, 2021.
  13. [13]——, “Linear tracking MPC for nonlinear systems part II: the data-driven case,” IEEE TAC, vol. 67, no. 9, pp. 4406–4421, 2022.DOI
  14. [14]L. H. Faro, Y. Nie, and P. Trodden, “Nise-pe constraint: Data-driven predictive control with persistence of excitation,” in 2025 IEEE 64th CDC. IEEE, Dec. 2025, pp. 2274–2280.arxiv.org/abs/2504.04548
  15. [15]P. Verheijen, V. Breschi, and M. Lazar, “Handbook of linear data-driven predictive control: Theory, implementation and design,” Annual Reviews in Control, vol. 56, p. 100914, 2023.DOI
  16. [16]P. Mattsson, F. Bonassi, V. Breschi, and T. B. Schön, “On the equivalence of direct and indirect data-driven predictive control approaches,” IEEE Con. Syst. Lett., vol. 8, pp. 796–801, 2024.DOI
  17. [17]J. D. Watson, “Hybrid data-enabled predictive control: Incorporating model knowledge into the deep,” IEEE Open Journal of Control Systems, vol. 4, pp. 549–561, 2025.arxiv.org/abs/2502.12467
  18. [18]J. Berberich, J. Köhler, M. A. Müller, and F. Allgöwer, “Data-Driven Model Predictive Control with Stability and Robustness Guarantees,” IEEE TAC, vol. 66, no. 4, pp. 1702–1717, 2021.DOI
  19. [19]L. Huang, J. Zhen, J. Lygeros, and F. Dörfler, “Robust data-enabled predictive control: Tractable formulations and performance guarantees,” IEEE TAC, vol. 68, no. 5, pp. 3163–3170, 2023.
  20. [20]M. Klädtke, M. S. Darup, and D. E. Quevedo, “Extending direct data-driven predictive control towards systems with finite control sets,” in 2024 ECC. IEEE, 2024, pp. 3345–3350.DOI
  21. [21]A. Bisoffi, C. De Persis, and P. Tesi, “Controller design for robust invariance from noisy data,” IEEE TAC, vol. 68, no. 1, pp. 636–643, Jan. 2023.DOI
  22. [22]A. Bisoffi, C. D. Persis, and P. Tesi, “Data-based guarantees of set invariance properties,” IFAC-PapersOnLine, vol. 53, no. 2, pp. 3953–3958, 2020.DOI
  23. [23]M. Bajelani and K. V. Heusden, “From raw data to safety: Reducing conservatism by set expansion,” in Proceedings of the 6th L4DC Conference, ser. Proceedings of Machine Learning Research, vol. 242. PMLR, 15–17 Jul 2024, pp. 1305–1317.arxiv.org/abs/2403.15883
  24. [24]J. Liao and W. Xiang, “Data-driven control based on control barrier functions with recursive feasibility guarantee,” IEEE TAC, pp. 1–16, 2026.DOI
  25. [25]M. Bajelani and K. van Heusden, “Data-driven input-output control barrier functions,” IEEE Con. Syst. Let., vol. 9, pp. 216–221, 2025.arxiv.org/abs/2502.17688
  26. [26]L. El Ghaoui, F. Gu, B. Travacca, A. Askari, and A. Tsai, “Implicit deep learning,” SIAM Journal on Mathematics of Data Science, vol. 3, no. 3, pp. 930–958, 2021.arxiv.org/abs/1908.06315
  27. [27]R. Drummond, P. Baldivieso, and G. Valmorbida, “Mapping back and forth between model predictive control and neural networks,” in Proceedings of the 6th Annual L4DC, ser. Proceedings of Machine Learning Research, vol. 242, 2024, pp. 1228–1240.arxiv.org/abs/2404.12030
  28. [28]E. Gilbert and K. Tan, “Linear systems with state and control constraints: the theory and application of maximal output admissible sets,” IEEE TAC, vol. 36, no. 9, pp. 1008–1020, 1991.DOI
  29. [29]M. Schulze Darup and M. Mönnigmann, “On general relations between null-controllable and controlled invariant sets for linear constrained systems,” in Proceedings of the 53rd IEEE CDC, 2014, pp. 6323–6328.
  30. [30]Z. Liu and N. Ozay, “On the convergence of the backward reachable sets of robust controlled invariant sets for discrete-time linear systems,” in 2022 IEEE 61st CDC. IEEE, Dec. 2022, pp. 4270–4275.arxiv.org/abs/2207.04726
  31. [31]A. Bemporad, M. Morari, V. Dua, and E. N. Pistikopoulos, “The explicit linear quadratic regulator for constrained systems,” Automatica, vol. 38, no. 1, pp. 3–20, 2002.DOI
  32. [32]D. P. Bertsekas, “Infinite-time reachability of state-space regions by using feedback control,” IEEE TAC, vol. 17, no. 5, pp. 604–613, 1972.
  33. [33]F. Blanchini, “Set invariance in control,” Automatica, vol. 35, no. 11, pp. 1747–1767, 1999.DOI
  34. [34]F. Blanchini and S. Miani, Set-theoretic methods in control. Boston: Birkhäuser, 2008.

Paper details

vlnc:W_2dnjsk5k
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents