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 relating an input space to an output space by and a data set gathered from the system, i.e., is a finite sequence of input/output pairs. The celebrated Willems’ Lemma [1] allows us to describe the linear system using only information , provided the input sequence is Persistently Exciting (PE), which will be defined below.
Definition 1 (see [2]): For and ,
the depth- block-Hankel matrix is
the sequence is Persistently Exciting of order if .
Definition 1–ii) together with [2 Lemma 2], which is a restatement of [1 Thm 1], states that for a data set such that is PE of order , then any –long sequence pair can be written as a linear combination of the elements of , i.e., for some
Equation (1) is the cornerstone of data-driven controllers. The Hankel matrix of the data set generates all possible trajectories. The relation between and the trajectories was established by contradiction, obscuring the relationship between the linear system and . 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 most recent measured inputs and outputs, , where and . Furthermore, satisfies the following assumption:
Assumption 1 (Sufficient initial window length): The initial trajectory length satisfies , where is the system observability index.1
Under Assumption 1, contains the information about the system’s internal condition required for prediction. The –horizon DeePC optimises over future input output predictions, and respectively, to regulate the system towards a desired reference . The associated quadratic program is
where
The relations in (2d) ensure consistency with the measured input/output history and future input/output predictions. Consequently, the measured history 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: . 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 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 and are convex and compact. In addition, 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 . 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 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 : is eliminated in closed form, and only the 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:
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.
A characterisation of the DeePC feasible region in the augmented state , 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 identity matrix is . For a matrix , is the Moore–Penrose pseudo inverse, its range, and, for an index set , collects the rows indexed by , the corresponding sub matrix, and is the complement of . is the spectral radius and , taken component-wise, is the ReLU. Inequalities between vectors hold component-wise.
Definition 2 (Implicit neural network): An implicit NN is defined by the solution of the following system of equations
for an activation , weights , , , , and biases , .
Definition 3 (MPI): For and , the MPI subset of is where is the repeated application of the map .
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, , , and given the basis of where , has full row rank. The QP (2) is equivalent to
where , such that , , , , and .
Proof: First, we eliminate the behavioural coefficient ; in (2d), its role splits into past and future components. The future trajectory is and . Replacing this in the cost yields
The consistency conditions are equality constraints . Solving these yield with . By assumption, has full row rank, then , yields . From , we obtain which leads to . The behavioural coefficient vector can be expressed as
The matrix satisfies . Since (zero input generates zero outputs), the prediction does not depend on ; as and (2b)–(2c) depend on only through , the QP (2) becomes a problem in alone. From Assumption 2, we have that there exist , with and that approximate the sets and . Substituting and into the polytopic constraints and stacking the constraints over the prediction horizon gives the prediction constraints where , , and
Lastly, the cost matrices are the following:
Finally, gives . ■
The condition of being full rank imposes a restriction on the data sequence length, i.e., 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 to inputs written in the compact form
where is a positive definite Hessian, and . This mapping can be expressed as an implicit neural network
with being the ReLU activation and with analytic expressions for the weights and biases given by
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 , the implicit NN output is
The associated behavioural parameter is with . Replacing this control law into the constraints, we have the admissible set for initial histories:
Furthermore, the zero-activation branch is polyhedral.
Proposition 1 (Zero-activation admissible region): Suppose Assumptions 1 and 2 hold. Fix . On the set
the solution of (7a) at any satisfies .
Proof. The solution of the nonlinear equation (7a) can be found using fixed point iterations, i.e., where . From Lemma 2, if , then . Consider, an initial such that w.l.o.g . Then, and lead to an iterate approaching the nonpositive orthant. As long as , then . However, since is constant and negative, the iterates converge to , i.e., .
The set is not necessarily bounded. Proposition 2 below shows that the rows of restrict only the initial history. From now on we consider regulation, , so that , and . We write ,
so that , and selects the input 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 and . Let be the shift that removes the oldest input/output pair from and the matrix that inserts a new pair, so that , and let be the first and rows of .
Lemma 3 (History dynamics): Suppose Assumption 1 hold, let , and let with . Every trajectory of satisfies and
Moreover, and .
Proof. For , by Assumption 1, we have that . Hence . By (1), every trajectory segment satisfies for some , so , and (19) follows. For and any , is a history of , hence in ; taking gives and then .
On , the closed-loop is linear
built from the Hankel matrices only. On , coincides with the map obtained from the first predicted input/output pair of the QP (2).
Membership of only guarantees that the unconstrained prediction is admissible at the current sampling instant. The MPI from Definition 3 is the set that can certify the closed-loop dynamics inside . The computation of follows the algorithm of Gilbert and Tan [28]: and
This process and its properties are summarised in the following result:
Proposition 2 (Unsaturated invariant set): Suppose Assumptions 1–2 hold, , and restricted to is Schur. Then:
i) there is a finite with , and is a polytope;
ii) for , the QP (2) is feasible along the closed loop trajectory of (20), and , .
for all
Proof. i) is compact with the origin in its relative interior (Proposition 1) and is -invariant (Lemma 3); finite determination follows from [28 Thm. 4.1] applied on . 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
the projection onto of a polyhedron in . The DeePC feasible set (22) depends on the horizon length and is not necessarily an invariant set for small because its underlying DeePC problem lacks terminal ingredients [12]. As 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 ; the following result identifies the set on which each pattern is valid.
Proposition 3 (Critical regions): Suppose Assumptions 1 and 2 hold. Fix . Let has full row rank, for , let and
i) For , the vector with and solves (7a).
ii) On , with and .
iii) .
Proof. i) Substitute , with and , in (7a) and use . ii) Follows from (7b) with . iii) follows from i) and Lemma 2. The converse , for , is a nonnegative linear combination of the rows of active at ; by Carathéodory’s theorem it is a nonnegative combination of linearly independent active rows indexed by some , and then .
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 into linear regions. This proposition includes the results in Proposition 1, i.e., and . By Lemma 3, on the closed loop is affine,
We denote by the resulting continuous PWA map on .
Region of recursive feasibility
Feasibility of the QP (2) at does not imply feasibility at , as no terminal ingredient is imposed [12]. Using the MPI algorithm with initialisation , the DeePC feasible set is
For , define the predecessor under the DeePC law
and the nested sequence .
Proposition 4 (Recursive feasibility). Suppose Assumptions 1–2 hold and .
i) iff and QP (2) is feasible along the DeePC closed loop trajectory.
ii) , .
Proof: i) If QP (2) is feasible at , the applied input and, by Lemma 3, the measured output coincide with the first predicted pair, which satisfies (2b)–(2c); hence implies as in Proposition 2. ii) and induction give . If , then , so is positively invariant and .
Invariant set hierarchy
By Lemma 3, the Maximal Control Invariant (MCI) subset of ,
is computed from data by , , where is a projection that eliminates 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 . Then
Proof: On , ; hence is positively invariant under and , so by maximality. By Proposition 4 i), is invariant under with , so . Let with admissible inputs ; the outputs are entries of , so is feasible for (2) by Lemma 1, i.e., . The remaining inclusions hold by definition.
The inclusion chains in (28) are strict, i.e., contains histories at which DeePC is feasible although no admissible input avoids a future violation. The horizon plays an important role, as . Similarly, shrinks as grows. Our last result addresses how positive invariant sets from a linear gain , 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 . For , let
Then and for every . In particular, every that is positively invariant for with for all satisfies .
Proof: is positively invariant under the admissible input , hence by (27). The is positively invariant under , and on by (4b); maximality of gives , and maximality gives .
Corollary 1 adds a branch to (28): for the gain of the unsaturated branch and for every other gain, while no inclusion between and follows from Theorem 4. Hence is necessary for the linear programs of [21], [22] to be feasible for a candidate set , whatever the gain, and 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 . The programs of [21], [22] certify a given set, robustly to noise in [21], with one linear program whose size grows with ; the recursions above compute maximal sets for exact data, at a cost that does not depend on once is eliminated but is exponential in and in the worst case.
Illustrative examples
Consider the following baseline system
with . A noise-free trajectory of length was generated from . With and , and , so Assumption 1 holds. The constraints are and , and , , so .
Since , . Every set in Figure 1 is computed from the Hankel matrices only. For display, histories are mapped to the current state through the true model; as is a linear bijection, each figure shows .

Figure 1. (a) , the iterate of (14) and . (b) , (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 and the largest invariant set contained within it . 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 : , where is the set of states reachable through an admissible window. The two removed pieces, of area 0.118 each, contain states such as , which can be reached with only if . Lastly, for this example, the PWA affine control law yielded three regions; the recursion of Proposition 4 iii) terminated after two iterations, certifying , see Figure 1 (c). In , and were verified, and has empty interior; since both sets are closed, . 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 in projection; the remaining 2.98% is the cost of the horizon without terminal ingredients. Restricting DeePC to its unsaturated branch retains 60.72% of .
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 and . Future work will address noisy data, where the condensed problem becomes a least-squares predictor, the sets must be robustified, and and can be used as data-driven terminal ingredients.
References
- [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]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]I. Markovsky, E. Prieto-Araujo, and F. Dörfler, “On the persistency of excitation,” Automatica, vol. 147, p. 110657, 2023.DOI
- [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]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]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]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]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]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]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]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]——, “On the design of terminal ingredients for data-driven MPC,” IFAC-PapersOnLine, vol. 54, no. 6, pp. 257–263, 2021.
- [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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]F. Blanchini, “Set invariance in control,” Automatica, vol. 35, no. 11, pp. 1747–1767, 1999.DOI
- [34]F. Blanchini and S. Miani, Set-theoretic methods in control. Boston: Birkhäuser, 2008.