Explicit MPC for the constrained zonotope case with low-rank matrix updates footnoteinfo Stefan S. Mihai, Florin Stoican, Martin Monnigmann, Bogdan D. Ciubotaru Abstract Solving the explicit Model Predictive Control (MPC) problem requires enumerating all critical regions and their associated feedback laws, a task that scales exponentially with the system dimension and the prediction horizon, as well. When the problem’s constraints are boxes or zonotopes, the feasible domain admits a compact constrained-zonotope representation. Building on this insight, we exploit the geometric properties of the equivalent constrained-zonotope reformulation to accelerate the computation of the explicit solution. Specifically, we formulate the multi-parametric problem in the lifted generator space and solve it using second-order optimality conditions, employ low-rank matrix updates to reduce computation time, and introduce an analytic enumeration of candidate active sets that yields the explicit solution in tree form. keywords Explicit model predictive control; Set-based computing; Linear systems; Constrained zonotopes. † † thanks: [ † † address: Department of Automatic Control and Systems Engineering, Nat. Univ. of Science and Technology Politehnica Bucharest, 060042, Bucharest, Romania. † † address: Automatic Control and System Theory, Ruhr University, Bochum, 44801 Bochum, Germany. footnoteinfo]Corresponding author: Ştefan S. Mihai. , , , , 1 Introduction Fundamentally, Model Predictive Control (MPC) is a feedback control strategy that employs a dynamic model to predict the evolution of the system states and to compute an optimal sequence of constrained control actions over a finite prediction horizon [ 12 ] . A prominent line of research focuses on its explicit formulation , which exploits the multi-parametric structure of the underlying optimization problem [ 4 , 2 , 16 , 17 , 23 ] . The resulting control law is a piecewise affine function with polyhedral support, partitioning the state space into bounded convex polyhedral regions known as critical regions . The main challenge in explicit MPC is the exponential growth of the critical regions’ number with the prediction horizon, making their enumeration computationally demanding. Hence, research has focused on faster implementations, many based on enumerating candidate active constraint sets [ 16 , 1 , 15 ] . Noteworthy, these sets are linked with the face lattice of the polyhedral feasible domain, which can be exploited in the process of solution finding [ 20 , 14 ] . As the system dimension and number of constraints grow, handling polyhedra quickly becomes intractable, motivating alternative formulations. Thanks to their resilience to the “curse of dimensionality,” constrained zonotopes [ 19 ] have been recently used in applications such as reachability analysis [ 3 ] , projection [ 22 ] , and fault diagnosis [ 24 ] . They can approximate any convex set arbitrarily well [ 19 , Theorem 1] and are closed under intersection, Minkowski addition, and affine transformations. We propose a novel explicit MPC approach that exploits the geometric properties of the equivalent constrained-zonotope reformulation, extending our previous work [ 21 ] . First, the multi-parametric problem is formulated in the lifted generator space and solved using second-order optimality conditions. Second, computation is accelerated via low-rank matrix updates, thus reducing the time required to compute each critical region. Finally, we introduce an analytic enumeration of candidate active sets that naturally yields the explicit solution in tree form. The paper is organized as follows. Section 2 introduces the required definitions. Section 3 presents the constrained-zonotope reformulation of the MPC problem. Section 4 outlines the computation of the explicit solution, and Section 5 describes the associated algorithms. Section 6 provides numerical results, followed by conclusions in Section 7 . Notation \mathbb{A} a finite, sorted set of natural numbers V_{\mathbb{A}} the sub-matrix formed from the rows of matrix V indexed by the elements in \mathbb{A} V_{(\mathbb{A})} a matrix computed in relation to \mathbb{A} V^{+} the Moore–Penrose generalized inverse of V v^{(k)} the k -th column of the matrix V \Lambda(V) the spectrum of V , i.e., \{\lambda\in\mathbb{C}:\det(\lambda I-V)=0\} e_{k} the k -th vector of the canonical basis of \mathbb{R}^{n} n_{\bullet} the number of elements in \bullet (e.g., n_{\mathbb{A}}=|\mathbb{A}| ) \otimes the Kronecker product x_{i|j} the predicted value of variable x at time i\geq j , based on information available at time j \circ Hadamard product 2 Context and framework We summarize the standard definitions of polyhedral and constrained zonotopic sets, which will be used later to describe the explicit MPC formulation. Additional details can be found in [ 9 , 19 , 18 ] . Definition 1 (Polyhedral set, polytope) . The matrix pair (A\in\mathbb{R}^{d_{H}\times n},b\in\mathbb{R}^{d_{H}}) gives the half-space representation of a polyhedral set P(A,b)=\bigl\{x\in\mathbb{R}^{n}:\>A_{i}x\leq b_{i},\>\forall i\in\{1,\dots,d_{H}\}\bigr\}, (1) where b_{i} , A_{i} denote the i -th element of vector b , and the i -th row of matrix A , respectively. A bounded polyhedral set is called a polytope. A bounded face F of the polytope P , defined as in Def. 1 , admits a half-space representation obtained by separating the active and inactive constraints, indexed by the sets \mathbb{A} and \mathbb{I} , respectively, where \mathbb{A}\cup\mathbb{I}=\{1,\dots,d_{H}\} and \mathbb{A}\cap\mathbb{I}=\emptyset . The face F is then explicitly given by F(\mathbb{A})=\bigl\{\,x\in\mathbb{R}^{n}:A_{i}x=b_{i},\;\forall i\in\mathbb{A},\\ A_{j}x\leq b_{j},\;\forall j\in\mathbb{I}\,\bigr\}. (2) The collection of all faces forms the face lattice of the polytope, which is a partially ordered set ( poset ). Zonotopes are symmetric polytopes that can be represented as a Minkowski sum of line segments, [ 9 , Chap. 4.8] . Although they exhibit strong numerical robustness in high dimensions, they are not closed under set intersection. Constrained zonotopes (CZs) extend zonotopes to overcome this limitation, [ 19 ] . Definition 2 (Constrained zonotope)) . Vectors c\in\mathbb{R}^{n} , \theta\in\mathbb{R}^{n_{c}} , and matrices G\in\mathbb{R}^{n\times n_{g}} , F\in\mathbb{R}^{n_{c}\times n_{g}} , define the constrained zonotope Z=\left\langle c,G,F,\theta\right\rangle\\ =\left\{x\in\mathbb{R}^{n}:\>x=c+G\xi,\>\|\xi\|_{\infty}\leq 1,F\xi=\theta\right\}. (3) Constrained zonotopes possess several useful properties [ 19 ] , three of which are of particular relevance in this work. First, they are closed under affine transformations: r+RZ_{1}=\left\langle r+Rc_{1},RG_{1},F_{1},\theta_{1}\right\rangle. (4) Second, CZs are closed under Minkowski sum: \mkern-25.0muZ_{1}\oplus Z_{2}=\biggl\langle c_{1}+c_{2},\begin{bmatrix}G_{1}&G_{2}\end{bmatrix},\begin{bmatrix}F_{1}&0\\ 0&F_{2}\end{bmatrix},\begin{bmatrix}\theta_{1}\\ \theta_{2}\end{bmatrix}\biggr\rangle. (5) Third, CZs are closed under set intersection: \mkern-30.0muZ_{1}\cap Z_{2}=\left\langle\mkern-4.0muc_{1},\begin{bmatrix}G_{1}&0\end{bmatrix},\mkern-4.0mu\begin{bmatrix}F_{1}&\hphantom{-}0\\ 0&\hphantom{-}F_{2}\\ G_{1}&-G_{2}\end{bmatrix},\begin{bmatrix}\theta_{1}\\ \theta_{2}\\ c_{2}-c_{1}\end{bmatrix}\right\rangle, (6) where Z_{1}:=\left\langle c_{1},G_{1},F_{1},\theta_{1}\right\rangle and Z_{2}:=\left\langle c_{2},G_{2},F_{2},\theta_{2}\right\rangle . Remark 3 . Operations ( 5 ) and ( 6 ) can be computationally demanding, as they increase the number of generators and constraints. Redundancies may be mitigated using techniques similar to those in [ 19 , 18 ] . Example 4 . Consider a zonotope in \mathbb{R}^{2} described by the center c=\begin{bmatrix}0.15&0.25\end{bmatrix}^{\top} and generator matrix G=\begin{bmatrix}g_{1}&g_{2}&g_{3}\end{bmatrix} , where g_{1}=\begin{bmatrix}-0.75&0\end{bmatrix}^{\top} , g_{2}=\begin{bmatrix}0&0.5\end{bmatrix}^{\top} , and g_{3}=\begin{bmatrix}1&0.25\end{bmatrix}^{\top} . Then, let the plane F\,\xi=\theta , where F=\begin{bmatrix}0.5&-2&0.25\end{bmatrix} and \theta=1 , define the equality constraint; incorporating this constraint as described in ( 3 ) results in the constrained zonotope. (a) (b) Figure 1 : (a) Domain of \xi\in\mathbb{R}^{n_{g}} , n_{g}=3 and hyperplane defined by F\xi=\theta ; (b) Zonotope (black contour) and constrained zonotope (blue) in \mathbb{R}^{n} , n=2 . Both the zonotope \langle c,G,\emptyset,\emptyset\rangle and the constrained zonotope \langle c,G,F,\theta\rangle are illustrated in Fig. 1b . The key difference lies in the admissible values of \xi used to generate points of the form c+G\xi . While the zonotope maps the entire hypercube \|\xi\|_{\infty}\leq 1 , the constrained zonotope restricts \xi to the intersection of this hypercube with a hyperplane, as shown in Fig. 1a . 3 Constrained zonotope formulation Consider a discrete-time, linear time-invariant system characterized by the state-space representation \displaystyle x_{k+1} \displaystyle=A_{d}x_{k}+B_{d}u_{k}, (7) where x_{k}\in\mathbb{R}^{n} and u_{k}\in\mathbb{R}^{m} denote the state and input vectors at time step k and A_{d}\in\mathbb{R}^{n\times n} , B_{d}\in\mathbb{R}^{n\times m} are the state and input matrices. State and input constraints are represented as set membership inclusions x_{k}\in\mathcal{X}\subset\mathbb{R}^{n},u_{k}\in\mathcal{U}\subset\mathbb{R}^{m} , where \mathcal{X} and \mathcal{U} are polytopes. To control such systems, while ensuring constraint satisfaction and cost minimization over a finite prediction horizon of length N , a well-established approach is MPC 1 1 1 To simplify notation, we use the shorthand x_{i|k}=x_{k+i|k} and u_{i|k}=u_{k+i|k} throughout the paper. Whenever clear from context, we denote x_{0}=x_{0|k} . [ 12 ] , respectively \displaystyle\arg\mkern-24.0mu\min_{\begin{subarray}{c}\\ u_{0|k},\ldots,u_{N-1|k}\\ x_{0|k},\ldots,x_{N|k}\end{subarray}}x_{N|k}^{\top} \displaystyle Sx_{N|k}+\mkern-8.0mu\sum_{i=0}^{N-1}\mkern-4.0mu\ell(x_{i|k},u_{i|k}) (8a) \displaystyle\text{s.t. }x_{i+1|k} \displaystyle=A_{d}x_{i|k}+B_{d}u_{i|k}, (8b) \displaystyle x_{i|k} \displaystyle\in\mathcal{X},\ u_{i|k}\in\mathcal{U}, (8c) \displaystyle x_{N|k} \displaystyle\in\mathcal{T}. (8d) The stage cost \ell(x_{i|k},u_{i|k}) is defined as \ell(x_{i|k},u_{i|k})=x_{i|k}^{\top}Qx_{i|k}+u_{i|k}^{\top}Ru_{i|k} , where Q\succeq 0 and R\succ 0 penalize deviations in the state and control input, respectively. The terminal weighting matrix S=S^{\top}\succ 0 , together with the polytopic terminal set \mathcal{T}\subset\mathbb{R}^{n} , ensures recursive feasibility and asymptotic stability [ 12 ] . To close the loop, at simulation step k , the initial predicted state is set to the current state, x_{0|k}=x_{k} , and the control input applied in ( 7 ) is u_{k}=u_{0|k} . Reformulating ( 8 ) into the equivalent multi-parametric quadratic program (mpQP) by using the substitution x_{i|k}=A^{i}x_{0}+\sum_{j=0}^{i-1}A^{i-1-j}Bu_{j|k} (see [ 7 ] ) leads to \displaystyle\arg\min_{\mathbf{u}_{[0:N-1]}} \displaystyle\frac{1}{2}\mathbf{u}_{[0:N-1]}^{\top}\tilde{Q}\mathbf{u}_{[0:N-1]}+x_{0}^{\top}\tilde{H}\mathbf{u}_{[0:N-1]} (9a) s.t. \displaystyle A\mathbf{u}_{[0:N-1]}\leq Ex_{0}+b, (9b) where \tilde{Q}\in\mathbb{R}^{Nm\times Nm} , \tilde{H}\in\mathbb{R}^{n\times Nm} , A\in\mathbb{R}^{q\times Nm} , b\in\mathbb{R}^{q} , and E\in\mathbb{R}^{q\times n} are obtained from ( 8 ) through standard matrix manipulations. Denoting \mathbf{u}_{[0:N-1]}=\begin{bmatrix}u_{0|k}^{\top}&u_{1|k}^{\top}&\dots&u_{N-1|k}^{\top}\end{bmatrix}^{\top} . For further use, \mathbf{x}_{[0:N-1]}=\begin{bmatrix}x_{0|k}^{\top}&x_{1|k}^{\top}&\dots&x_{N-1|k}^{\top}\end{bmatrix}^{\top} , and note the relations \displaystyle\mathbf{x}_{[0:N-1]} \displaystyle=\tilde{A}_{[0:N-1]}x_{0}+\tilde{B}_{[0:N-1]}\mathbf{u}_{[0:N-1]}, (10a) \displaystyle x_{N} \displaystyle=\tilde{A}_{N}x_{0}+\tilde{B}_{N}\mathbf{u}_{[0:N-1]}, (10b) where \displaystyle\tilde{A}_{[0:N-1]} \displaystyle=\begin{bmatrix}I&{A_{d}^{1}}^{\top}&{A_{d}^{2}}^{\top}&\dots&{A_{d}^{N-1}}^{\top}\end{bmatrix}^{\top}, (11a) \displaystyle\tilde{A}_{N} \displaystyle=A_{d}^{N}, (11b) \displaystyle\tilde{B}_{[0:N-1]} \displaystyle=\sum_{i=2}^{N}\sum_{j=1}^{i-1}(e_{i}e_{j}^{\top})\otimes(A_{d}^{i-j-1}B_{d}), (11c) \displaystyle\tilde{B}_{N} \displaystyle=\begin{bmatrix}A_{d}^{N-1}B_{d}&A_{d}^{N-2}B_{d}&\dots&B_{d}\end{bmatrix}. (11d) By revisiting the state and input constraints in ( 8c ) and the terminal constraint ( 8d ), and incorporating the shorthand notation from ( 10 ), we observe that the feasible domain of ( 8 ) can be rewritten as \tilde{\mathcal{X}}\cap\tilde{\mathcal{T}}\cap\tilde{\mathcal{U}} , with \displaystyle\tilde{\mathcal{X}} \displaystyle=\left\{\tilde{A}_{[0:N-1]}x_{0}+\tilde{B}_{[0:N-1]}\mathbf{u}_{[0:N-1]}\in\mathcal{X}\times\ldots\times\mathcal{X}\right\}, \displaystyle\tilde{\mathcal{U}} \displaystyle=\mathcal{U}\times\ldots\times\mathcal{U}, (12) \displaystyle\tilde{\mathcal{T}} \displaystyle=\left\{\tilde{A}_{N}x_{0}+\tilde{B}_{[0:N-1]}\mathbf{u}_{[0:N-1]}\in\mathcal{T}\right\}. Starting from the initial constrained zonotope representation of the constraint sets \mathcal{X} , \mathcal{U} and \mathcal{T} , we derive a constrained zonotope description of the feasible domain associated with ( 8 ), which is then used to efficiently derive the explicit MPC solution. For later use, we denote the equivalent polyhedral representation \tilde{\mathcal{X}}\cap\tilde{\mathcal{U}}\cap\tilde{\mathcal{T}}=\{x\in\mathbb{R}^{Nm}:\>A\,\mathbf{u}_{[0:N-1]}\leq b+Ex_{0}\} , with A\in\mathbb{R}^{q\times Nm} , b\in\mathbb{R}^{q} and F\in\mathbb{R}^{q\times n} , appropriately constructed. Consider the case where the state and input constraints are represented in zonotopic form as \mathcal{X}=\langle c_{\mathcal{X}},G_{\mathcal{X}}\rangle,\quad\mathcal{U}=\langle c_{\mathcal{U}},G_{\mathcal{U}}\rangle . Typically, the terminal set \mathcal{T} is defined as the result of a set recurrence \Omega_{k+1}=(A_{d}+B_{d}K)^{-1}\Omega_{k}\cap\Omega_{0} , where \Omega_{0}=\mathcal{X}\cap\mathcal{U} , for a predefined stabilizing static gain K . Since this terminal set can be conveniently represented as a constrained zonotope [ 10 ] , we express it as \mathcal{T}=\langle c_{\mathcal{T}},G_{\mathcal{T}},F_{\mathcal{T}},\theta_{\mathcal{T}}\rangle . For reference, the generator matrices G_{\{\mathcal{X},\mathcal{U},\mathcal{T}\}} belong to \mathbb{R}^{\{n,m,n\}\times\{g_{X},g_{U},g_{T}\}} , while the constraint parameters (F_{\mathcal{T}},\theta_{\mathcal{T}}) are elements of \mathbb{R}^{c_{\mathcal{T}}\times g_{\mathcal{T}}}\times\mathbb{R}^{c_{\mathcal{T}}} . The notation allows us to express ( 12 ) in the form of a constrained zonotope. Enforcing the stage constraints x_{k}\in\mathcal{X} and control inputs u_{k}\in\mathcal{U} , for k=0:N-1 , along with the terminal constraint x_{N}\in\mathcal{T} , gives \displaystyle\mkern-24.0mu\tilde{A}_{[0:N-1]}x_{0}\mkern-4.0mu+\mkern-4.0mu\tilde{B}_{[0:N-1]}\mathbf{u}_{[0:N-1]} \displaystyle\mkern-4.0mu\in\mkern-4.0mu\langle\mathbf{1}_{N}\mkern-4.0mu\otimes\mkern-4.0muc_{\mathcal{X}},I_{N}\mkern-4.0mu\otimes\mkern-4.0muG_{\mathcal{X}}\rangle, (13a) \displaystyle\mkern-24.0mu\mathbf{u}_{[0:N-1]} \displaystyle\mkern-4.0mu\in\mkern-4.0mu\langle\mathbf{1}_{N}\mkern-4.0mu\otimes\mkern-4.0muc_{\mathcal{U}},I_{N}\mkern-4.0mu\otimes\mkern-4.0muG_{\mathcal{U}}\rangle, (13b) \displaystyle\mkern-24.0mu\tilde{A}_{N}x_{0}+\tilde{B}_{[0:N-1]}\mathbf{u}_{[0:N-1]} \displaystyle\in\langle c_{\mathcal{T}},G_{\mathcal{T}},F_{T},\theta_{T}\rangle. (13c) Lemma 5 . Introducing \xi\in\mathbb{R}^{N(g_{\mathcal{X}}+g_{\mathcal{U}})+G_{\mathcal{T}}} and applying substitution \mathbf{u}_{[0:N-1]}=c_{\mathcal{D}}+G_{\mathcal{D}}\xi in ( 9 ) leads to the equivalent formulation \displaystyle\arg\min_{\xi}\quad \displaystyle\frac{1}{2}\xi^{\top}G_{\mathcal{D}}^{\top}\tilde{Q}G_{\mathcal{D}}\xi+c_{\mathcal{D}}^{\top}\tilde{Q}G_{\mathcal{D}}\xi+x_{0}^{\top}\tilde{H}G_{\mathcal{D}}\xi \displaystyle\qquad\qquad\qquad\>+x_{0}^{\top}\tilde{H}c_{\mathcal{D}}+\frac{1}{2}c_{\mathcal{D}}^{\top}\tilde{Q}c_{\mathcal{D}} (14a) s.t. \displaystyle F_{\mathcal{D}}\xi-\theta_{1,\mathcal{D}}-\theta_{2,\mathcal{D}}x_{0}=\mathbf{0}_{\bar{D}}, (14b) \displaystyle Y\xi-\mathbf{1}_{2\bar{D}}\leq\mathbf{0}_{2\bar{D}}, (14c) where Y=\bigl[\begin{matrix}I_{\bar{D}}&-I_{\bar{D}}\end{matrix}\bigr]^{\top} and \displaystyle\mkern-20.0muc_{\mathcal{D}} \displaystyle=\mathbf{1}_{N}\otimes c_{\mathcal{U}}, (15) \displaystyle\mkern-20.0muG_{\mathcal{D}} \displaystyle=\begin{bmatrix}I_{N}\otimes G_{\mathcal{U}}&\mathbf{0}_{Nn\times(Ng_{X}+g_{T})}\end{bmatrix}, \displaystyle\mkern-20.0muF_{\mathcal{D}} \displaystyle=\begin{bmatrix}\tilde{B}_{[0:N-1]}(I_{N}\otimes G_{\mathcal{U}})&-I_{N}\otimes G_{\mathcal{X}}&\mathbf{0}_{Nn\times g_{T}}\\ \tilde{B}_{N}(I_{N}\otimes G_{\mathcal{U}})&\mathbf{0}_{n\times Ng_{\mathcal{X}}}&-G_{\mathcal{T}}\\ \mathbf{0}_{c_{\mathcal{T}}\times Ng_{\mathcal{U}}}&\mathbf{0}_{c_{\mathcal{T}}\times Ng_{\mathcal{X}}}&F_{\mathcal{T}}\end{bmatrix}, \displaystyle\mkern-20.0mu\theta_{1,\mathcal{D}} \displaystyle=\mkern-8.0mu\begin{bmatrix}\mathbf{1}_{N}\otimes c_{\mathcal{X}}\\ c_{\mathcal{T}}\\ \theta_{\mathcal{T}}\end{bmatrix}\mkern-8.0mu-\mkern-8.0mu\begin{bmatrix}\tilde{B}_{[0:N]}\\ \mathbf{0}_{c_{\mathcal{T}}}\end{bmatrix}\mkern-4.0mu(\mathbf{1}_{N}\otimes c_{\mathcal{U}}),\theta_{2,\mathcal{D}}=\begin{bmatrix}\tilde{A}_{[0:N]}\\ \mathbf{0}_{c_{\mathcal{T}}\times n}\end{bmatrix}. The term \bar{D}=N(g_{\mathcal{X}}+g_{\mathcal{U}})+g_{\mathcal{T}} denotes the number of generators and \bar{n}_{c}=(N+1)n+c_{\mathcal{T}} the number of equalities. \tilde{A}_{[0:N]} and \tilde{B}_{[0:N]} are obtained by vertically concatenating (\tilde{A}_{[0:N-1]},\tilde{A}_{N}) and (\tilde{B}_{[0:N-1]},\tilde{B}_{N}) , respectively. PROOF. Substituting ( 13b ) into ( 13a ), following the approach in ( 6 ), gives the constrained zonotope bounding the control inputs sequence \mathbf{u}_{[0:N-1]} as \biggl\langle\mathbf{1}_{N}\otimes c_{\mathcal{U}},\begin{bmatrix}I_{N}\otimes G_{\mathcal{U}}&\mathbf{0}_{Nm\times Ng_{X}}\end{bmatrix},\\ \begin{bmatrix}\tilde{B}_{[0:N-1]}(I_{N}\otimes G_{\mathcal{U}})&-I_{N}\otimes G_{\mathcal{X}}\end{bmatrix},\\ \mathbf{1}_{N}\otimes c_{\mathcal{X}}-\tilde{B}_{[0:N-1]}(\mathbf{1}_{N}\otimes c_{\mathcal{U}})-\tilde{A}_{[0:N-1]}x_{0}\biggr\rangle. Including ( 13c ) in the previous set and performing a minor regrouping of the terms to highlight x_{0} yields \bigl\{\mathbf{u}_{[0:N-1]}=c_{\mathcal{D}}+G_{\mathcal{D}}\xi,\\ \>F_{D}\xi=\theta_{1,\mathcal{D}}+\theta_{2,\mathcal{D}}x_{0},\>\|\xi\|_{\infty}\leq 1\bigr\}, (16) with c_{\mathcal{D}},G_{\mathcal{D}},F_{\mathcal{D}} , \theta_{1,\mathcal{D}} and \theta_{2,\mathcal{D}} defined as in ( 15 ). Making the change of variable \mathbf{u}_{[0:N-1]}=c_{\mathcal{D}}+G_{\mathcal{D}}\xi allows to reformulate ( 9 ) into ( 14 ), thus concluding the proof. ∎ 4 Solution computation and improvements As per ( 16 ), the decision variable \xi lies in the intersection between a fixed hypercube and an affine subspace, parameterized in x_{0} . Hence, we focus on the structural simplicity of ( 14 ), leveraging its constrained zonotope representation, to compute efficiently the explicit solution. 4.1 The critical region and the associated affine law Although the reformulated problem ( 14 ) features a quadratic cost with strictly positive definite weighting matrix \tilde{Q} , the Hessian G_{\mathcal{D}}^{\top}\tilde{Q}G_{\mathcal{D}} is not strictly positive definite. Since G_{\mathcal{D}}\in\mathbb{R}^{Nm\times\bar{D}} , its rank is at most Nm<\bar{D} , implying rank deficiency. As a result, the Karush–Kuhn–Tucker (KKT) conditions remain necessary but are no longer sufficient. To recover the optimality, second-order conditions must be included to account for the null space of G_{\mathcal{D}}^{\top}\tilde{Q}G_{\mathcal{D}} . Proposition 6 . For a candidate set of active inequalities \mathbb{A}\subset\{1,\ldots,2\bar{D}\} , the optimal solution minimizing ( 14 ) leads to the affine law \mathbf{u}_{(\mathbb{A}),[0:N-1]}^{\star}(x_{0})=G_{\mathcal{D}}K_{(\mathbb{A})}^{-1}\kappa_{2,(\mathbb{A})}x_{0}\\ +\left(c_{\mathcal{D}}+G_{\mathcal{D}}K_{(\mathbb{A})}^{-1}\kappa_{1,(\mathbb{A})}\right), (17) and its associated (possibly empty) critical region \text{CR}_{(\mathbb{A})}=\biggl\{\begin{bmatrix}Y_{\mathbb{I}}K_{(\mathbb{A})}^{-1}\kappa_{2,(\mathbb{A})}\\ -S_{\mathbb{A},2}\end{bmatrix}x_{0}\\ +\begin{bmatrix}Y_{\mathbb{I}}K_{(\mathbb{A})}^{-1}\kappa_{1,(\mathbb{A})}\\ -s_{\mathbb{A},2}\end{bmatrix}\leq\begin{bmatrix}\mathbf{1}_{2\bar{D}-n_{\mathbb{A}}}\\ \mathbf{0}_{n_{\mathbb{A}\hphantom{D-}}}\end{bmatrix}\biggr\}, (18) over which it is active, with the notation \displaystyle K_{(\mathbb{A})} \displaystyle=\begin{bmatrix}Z_{(\mathbb{A})}^{\top}G_{\mathcal{D}}^{\top}\tilde{Q}G_{\mathcal{D}}\\ F_{\mathcal{D}}\\ Y_{\mathbb{A}}\end{bmatrix}, (19a) \displaystyle\mkern-8.0mu\kappa_{1,(\mathbb{A})} \displaystyle\mkern-4.0mu=\mkern-4.0mu\begin{bmatrix}-Z_{(\mathbb{A})}^{\top}G_{\mathcal{D}}^{\top}\tilde{Q}c_{\mathcal{D}}\\ \theta_{1,\mathcal{D}}\\ \mathbf{1}_{n_{\mathbb{A}}}\end{bmatrix}\mkern-8.0mu,\kappa_{2,(\mathbb{A})}\mkern-4.0mu=\mkern-4.0mu\begin{bmatrix}-Z_{(\mathbb{A})}^{\top}G_{\mathcal{D}}^{\top}\tilde{H}^{\top}\\ \theta_{2,\mathcal{D}}\\ \mathbf{0}_{n_{\mathbb{A}}}\end{bmatrix}, (19b) \displaystyle S_{(\mathbb{A})} \displaystyle=-T_{(\mathbb{A})}^{+}G_{\mathcal{D}}^{\top}\bigl(\tilde{Q}G_{\mathcal{D}}K_{(\mathbb{A})}^{-1}\kappa_{2,(\mathbb{A})}+\tilde{H}^{\top}\bigr), (19c) \displaystyle s_{(\mathbb{A})} \displaystyle=-T_{(\mathbb{A})}^{+}G_{\mathcal{D}}^{\top}\tilde{Q}G_{\mathcal{D}}K_{(\mathbb{A})}^{-1}\kappa_{1,(\mathbb{A})}c_{\mathcal{D}}, (19d) \displaystyle T_{(\mathbb{A})} \displaystyle=\begin{bmatrix}F_{\mathcal{D}}^{\top}&Y_{\mathbb{A}}^{\top}\end{bmatrix},\>Z_{(\mathbb{A})}=\mathrm{null}\left(T_{(\mathbb{A})}^{\top}\right), (19e) where \mathbb{I}=\{1,\ldots,2\bar{D}\}\setminus\mathbb{A} , n_{\mathbb{A}} denotes the cardinality of index set \mathbb{A} , and S_{\mathbb{A},2} , s_{\mathbb{A},2} are the sub-matrices gathering the last n_{\mathbb{A}} rows from S_{(\mathbb{A})} , s_{(\mathbb{A})} , corresponding to \mu_{\mathbb{A}} . PROOF. As per [ 6 , Prop. 1.30] , \xi^{\star} is a strict local minimum of ( 14 ) for the given set of active indices \mathbb{A} iff there exist the Lagrangian multipliers \lambda^{\star},\mu^{\star} such that \displaystyle G_{\mathcal{D}}^{\top}\tilde{Q}G_{\mathcal{D}}\xi^{\star}+G_{\mathcal{D}}^{\top}\tilde{Q}c_{\mathcal{D}}+G_{\mathcal{D}}^{\top}\tilde{H}^{\top}x_{0} \displaystyle+{F_{\mathcal{D}}}^{\top}\lambda^{\star}+Y^{\top}_{\mathbb{A}}\mu_{\mathbb{A}}^{\star} \displaystyle=\mathbf{0}_{\bar{D}}, (20a) \displaystyle F_{\mathcal{D}}\xi^{\star}-\theta_{1,\mathcal{D}}-\theta_{2,\mathcal{D}}x_{0} \displaystyle=\mathbf{0}_{\bar{n}_{c}}, (20b) \displaystyle Y\xi^{\star}-\mathbf{1}_{2\bar{D}} \displaystyle\leq\mathbf{0}_{2\bar{D}}, (20c) \displaystyle\mu_{\mathbb{A}}^{\star}>\mathbf{0}_{n_{\mathbb{A}}},\>\mu_{\mathbb{I}}^{\star} \displaystyle=\mathbf{0}_{2\bar{D}-n_{\mathbb{A}}}, (20d) \displaystyle\mu^{\star}\circ\left(Y\xi^{\star}-\mathbf{1}_{2\bar{D}}\right) \displaystyle=\mathbf{0}_{2\bar{D}}, (20e) and, for every z\neq 0 which satisfies F_{\mathcal{D}}z=0 , Y_{\mathbb{A}}z=0 , we have that z^{\top}G_{\mathcal{D}}^{\top}\tilde{Q}G_{\mathcal{D}}z>0. (21) Since, by construction, \tilde{Q}\succ 0 , a necessary and sufficient condition for ( 21 ) to hold is that z is in the null spaces of F_{\mathcal{D}} and Y_{\mathbb{A}} but not in the null space of G_{\mathcal{D}} , respectively z\in\ker F_{\mathcal{D}}\cap\ker Y_{\mathbb{A}},z\notin\ker G_{\mathcal{D}}. (22) By construction, the columns of matrix Z_{(\mathbb{A})} from ( 19e ) describe a basis of the subspace ( 22 ). Left-multiplying with Z_{(\mathbb{A})}^{\top} in ( 20a ) and reordering such that the equalities appear first leads to \displaystyle\mkern-18.0muZ_{(\mathbb{A})}^{\top}\mkern-8.0mu\left(G_{\mathcal{D}}^{\top}\tilde{Q}G_{\mathcal{D}}\xi^{\star}+G_{\mathcal{D}}^{\top}\tilde{Q}c_{\mathcal{D}}+G_{\mathcal{D}}^{\top}\tilde{H}^{\top}x_{0}\mkern-4.0mu\right) \displaystyle=\mathbf{0}_{\bar{D}-\bar{n}_{c}-n_{\mathbb{A}}}, (23a) \displaystyle F_{\mathcal{D}}\xi^{\star}-\theta_{1,\mathcal{D}}-\theta_{2,\mathcal{D}}x_{0} \displaystyle=\mathbf{0}_{\bar{n}_{c}}, (23b) \displaystyle Y_{\mathbb{A}}\xi^{\star}-\mathbf{1}_{n_{\mathbb{A}}} \displaystyle=\mathbf{0}_{n_{\mathbb{A}}}, (23c) \displaystyle\mu_{\mathbb{I}}^{\star} \displaystyle=\mathbf{0}_{2\bar{D}-n_{\mathbb{A}}}, (23d) \displaystyle Y_{\mathbb{I}}\xi^{\star}-\mathbf{1}_{2\bar{D}-n_{\mathbb{A}}} \displaystyle\leq\mathbf{0}_{\bar{D}-n_{\mathbb{A}}}, (23e) \displaystyle\mu_{\mathbb{A}}^{\star} \displaystyle>\mathbf{0}_{n_{\mathbb{A}}}. (23f) After rearranging 2 2 2 The invertibility of K_{(\mathbb{A})}\in\mathbb{R}^{\bar{D}\times\bar{D}} is assumed to hold and it is one of the test conditions appearing later in Algorithm 1 . ( 23a )–( 23c ) to isolate \xi^{\star} and substituting it into ( 20b ), one obtains, using the notation of ( 19 ), both the primal and dual optimal solutions K_{(\mathbb{A})}\xi^{\star}=\kappa_{2,(\mathbb{A})}x_{0}+\kappa_{1,(\mathbb{A})},\ \begin{bmatrix}\lambda^{\star}\\ \mu_{\mathbb{A}}^{\star}\end{bmatrix}=S_{(\mathbb{A})}x_{0}+s_{(\mathbb{A})}. (24) Mapping \mathbf{u}_{[0:N-1]}^{\star}(x_{0})=c_{\mathcal{D}}+G_{\mathcal{D}}\xi^{\star}(x_{0}) yields the optimal affine law ( 17 ), while substituting ( 24 ) into ( 23e )–( 23f ) provides the description of the critical region, leading to ( 18 ) and concluding the proof. ∎ When \mathrm{null}\!\left(T_{(\mathbb{A})}\right)=\{\mathbf{0}_{\bar{D}}\} , the matrix Z_{(\mathbb{A})}\in\mathbb{R}^{\bar{D}\times(\bar{D}-\bar{n}_{c}-n_{\mathbb{A}})} is empty and Prop. 6 reduces to the following result. Corollary 7 . Let \mathbb{A} be a candidate active set such that \bar{D}=\bar{n}_{c}+n_{\mathbb{A}} . Then, the KKT conditions are necessary and sufficient to recover from ( 14 ) the affine law ( 17 ) and the associated critical region ( 18 ), provided that the matrices K_{(\mathbb{A})} , \kappa_{1,(\mathbb{A})} , and \kappa_{2,(\mathbb{A})} (cf. ( 19a )–( 19b )) are redefined by retaining only their last \bar{n}_{c}+n_{\mathbb{A}} rows. PROOF. Applying the KKT conditions to ( 14 ) leads to \begin{bmatrix}G_{\mathcal{D}}^{\top}\tilde{Q}G_{\mathcal{D}}&F_{\mathcal{D}}^{\top}&Y_{\mathbb{A}}^{\top}\\ F_{\mathcal{D}}&\mathbf{0}&\mathbf{0}\\ Y_{\mathbb{A}}&\mathbf{0}&\mathbf{0}\end{bmatrix}\begin{bmatrix}\xi^{\star}\\ \lambda^{\star}\\ \mu^{\star}_{\mathbb{A}}\end{bmatrix}+\\ \begin{bmatrix}\hphantom{-}G_{\mathcal{D}}^{\top}\tilde{H}^{\top}\\ -\theta_{2,\mathcal{D}}\\ \hphantom{-}\mathbf{0}_{n_{\mathbb{A}}}\end{bmatrix}x_{0}+\begin{bmatrix}\hphantom{-}G_{\mathcal{D}}^{\top}\tilde{Q}c_{\mathcal{D}}\\ -\theta_{1,\mathcal{D}}\\ -\mathbf{1}_{n_{\mathbb{A}}}\end{bmatrix}=\mathbf{0}_{\bar{D}+\bar{n}_{c}+n_{\mathbb{A}}}. (25) Solving for the primal solution \xi^{\star} and the dual solutions \lambda^{\star} , \mu_{\mathbb{A}}^{\star} shows, by inspection, that they coincide with the form ( 24 ) if and only if K_{(\mathbb{A})} , \kappa_{1,(\mathbb{A})} , and \kappa_{2,(\mathbb{A})} (cf. ( 19a )–( 19b )) are redefined to retain only their last \bar{n}_{c}+n_{\mathbb{A}} rows. Carrying the remaining steps in Prop. 6 to arrive at ( 17 )–( 18 ) concludes the proof. ∎ 4.2 Iterative updates In ( 19 ), the matrices Z_{(\mathbb{A})} , T_{(\mathbb{A})}^{+} , and K_{(\mathbb{A})}^{-1} need not be recomputed from scratch when the active set \mathbb{A} is updated. We next analyze the effect of an update \bar{\mathbb{A}}=\mathbb{A}\cup\{i\} on each of these matrices. Lemma 8 . Whenever \bar{\mathbb{A}}=\mathbb{A}\cup\{i\} holds, we have Z_{(\bar{\mathbb{A}})}=Z_{(\mathbb{A})}\mathrm{null}\left(Y_{i}Z_{(\mathbb{A})}\right). (26) PROOF. From \bar{\mathbb{A}}=\mathbb{A}\cup\{i\} , we have Z_{(\bar{\mathbb{A}})}=\mathrm{null}\!\left(\begin{bmatrix}F_{\mathcal{D}}^{\top}&Y_{\bar{\mathbb{A}}}^{\top}\end{bmatrix}^{\top}\right)=\mathrm{null}\!\left(\begin{bmatrix}F_{\mathcal{D}}^{\top}&Y_{\mathbb{A}}^{\top}&Y_{i}^{\top}\end{bmatrix}^{\top}\right). Since Z_{(\mathbb{A})}=\mathrm{null}\biggl(\begin{bmatrix}F_{\mathcal{D}}^{\top}&Y_{\mathbb{A}}^{\top}\end{bmatrix}^{\top}\biggr) , any z\in Z_{(\bar{\mathbb{A}})} satisfies: i) F_{\mathcal{D}}z=\mathbf{0} , ii) Y_{\mathbb{A}}z=\mathbf{0} , iii) Y_{i}z=\mathbf{0} . From (i) and (ii), it follows that z\in Z_{(\mathbb{A})} , so there exists v with z=Z_{(\mathbb{A})}v . Substituting into (iii) yields the additional condition Y_{i}Z_{(\mathbb{A})}v=0 , i.e., v\in\mathrm{null}(Y_{i}Z_{(\mathbb{A})}) . Hence, Z_{(\bar{\mathbb{A}})}=Z_{(\mathbb{A})}\,\mathrm{null}\!\left(Y_{i}Z_{(\mathbb{A})}\right) , as in ( 26 ). ∎ Figure 2: Illustration of the update of matrices Z_{(\mathbb{A})} , K_{(\mathbb{A})} . While \mathrm{null}\!\left(Y_{i}Z_{(\mathbb{A})}\right) can be computed by standard methods (e.g., QR factorization), updating K_{(\mathbb{A})}^{-1} is more efficient when a sparse representation is employed. The next result provides such a representation. Lemma 9 . Let z\in\mathbb{R}^{n} be a nonzero row vector and choose an index j with z_{j}\neq 0 . Define the n\times(n-1) matrix V whose columns are V_{ik}=\begin{cases}1,&i=\sigma(k),\\ -\frac{z_{\sigma(k)}}{z_{j}},&i=j,\\ 0,&\text{otherwise},\end{cases} where \sigma(k)=k , for kW=\left[\begin{array}[]{c}Y_{i}\\ \hline\cr Z_{(\mathbb{A}),j}^{\top}G_{D}^{\top}\tilde{Q}G_{D}\end{array}\right], (28) and with v=\begin{bmatrix}v_{1}^{\top}&v_{2}^{\top}\end{bmatrix}^{\top} , the j -th row from matrix V , chosen such that the null matrix update Z_{(\bar{\mathbb{A}})}=Z_{(\mathbb{A})}V=Z_{(\mathbb{A})}\left[\begin{array}[]{c:c}I_{k_{1}}\hfil\lx@intercol\vrule\lx@add@cssclass&\mathbf{0}\\ \hline\cr v_{1}^{\top}\hfil\lx@intercol\vrule\lx@add@cssclass&v_{2}^{\top}\\ \hline\cr\mathbf{0}\hfil\lx@intercol\vrule\lx@add@cssclass&I_{k_{2}}\end{array}\right] (29) holds; P(j,\bar{n}_{c}+i) extracts the j -th row and inserts it at the (\bar{n}_{c}+i) -th position, shifting all subsequent rows, as needed. PROOF. Computing V as in Lemma 9 for z=Y_{i}Z_{(\mathbb{A})} and applying Lemma 8 yields the expression of Z_{(\bar{\mathbb{A}})} in ( 29 ). The update from K_{({\mathbb{A}})} to K_{(\bar{\mathbb{A}})} is twofold: (i) the j -th row is eliminated by a linear combination of the rows of Z_{(\mathbb{A})}^{\top} with weightings given by v , and (ii) a new row Y_{i} is inserted at the position \bar{n}_{c}+i . This can be modeled by first updating the j -th row and then moving it to the position \bar{n}_{c}+i . With the notation of ( 28 ), the update reads K_{(\bar{\mathbb{A}})}=P(j,\bar{n}_{c}+i)\left(K_{({\mathbb{A}})}+UW\right). (30) Then, noting that P(j,\bar{n}_{c}+i)^{-1}=P(j,\bar{n}_{c}+i)^{\top} and applying the Woodbury matrix identity gives ( 27 ), which concludes the proof. ∎ For clarity, Fig. 2 illustrates the updates Z_{(\mathbb{A})}\rightarrow Z_{(\bar{\mathbb{A}})} and K_{(\mathbb{A})}\rightarrow K_{(\bar{\mathbb{A}})} . Patterned rectangles mark the rows modified during the update, while indices 1,2 on matrices Z_{(\mathbb{A})}^{\top} , Y_{\mathbb{A}} , and the vector v denote the row blocks between which a single row is deleted or inserted. Remark 11 . The invertibility of K_{(\bar{\mathbb{A}})} is determined by the factor \bigl(I_{2}+WK_{(\mathbb{A})}^{-1}U\bigr) in ( 27 ). Since this matrix lies in \mathbb{R}^{2\times 2} , the singularity test is both efficient and numerically reliable. Remark 12 . Whenever \bar{\mathbb{A}}=\mathbb{A}\cup{i} holds, we have [ 5 ] T_{(\bar{\mathbb{A}})}^{+}=S_{k}^{\top}\begin{bmatrix}T_{(\mathbb{A})}^{+}-db^{\top}\\ b^{\top}\end{bmatrix}, (31) where d=T_{(\mathbb{A})}^{+}Y_{i}^{\top} , c=\left(Y_{i}^{\top}-T_{(\mathbb{A})}d\right) , and b is a vector b=\begin{cases}\cfrac{c}{c^{\top}c},&\sqrt{c^{\top}c}>\varepsilon,\\ \cfrac{{T_{(\mathbb{A})}^{+\top}}d}{1+d^{\top}d},&\text{otherwise}.\end{cases} The term S_{k}\in\mathbb{R}^{(n+1)\times(n+1)} is a column permutation that moves the last column to position k , i.e., S_{k}=\left(\sum_{j=1}^{k-1}e_{j}e_{j}^{\top}+e_{n+1}e_{k}^{\top}+\sum_{j=k}^{n}e_{j}e_{j+1}^{\top}\right) . We take k=n_{F_{\mathcal{D}}}+\bigl|\{\ell\in\bar{\mathbb{A}}:\ \ell\leq i\}\bigr| ; lastly, \varepsilon is a tolerance. As shown in [ 13 ] , the active sets defining non-empty critical regions are embedded in the face lattice of the polyhedral feasible domain of the MPC problem. Here, owing to the simpler structure, we employ a lifted formulation in \mathbb{R}^{\bar{D}} with variable \xi . According to [ 11 , Prop. 18] , there exists a surjective relation whereby each face of the feasible domain corresponds to a face in the lifted space (though not all faces of \xi map to faces of u ). We exploit this fact to propose a fast necessary check for the non-emptiness of a candidate set \bar{\mathbb{A}}=\mathbb{A}\cup\{i\} . Proposition 13 . Let \mathbb{A} be an active set such that CR_{(\mathbb{A})} is non-empty. Define the corresponding active set of polyhedral constraints \mathbb{A}_{\mathrm{red}}\subset\{1,\ldots,q\} as \mathbb{A}_{\mathrm{red}}=\{\,j:A_{j}\mathbf{u_{[0:N-1]}}_{(\mathbb{A})}=b_{j}+F_{j}x_{0}\,\}. (32) Then, for a candidate set \bar{\mathbb{A}}=\mathbb{A}\cup\{i\} , the following implication holds \Bigl(\not\exists j\text{ s.t. }\bar{\mathbb{A}}_{\mathrm{red}}=\mathbb{A}_{\mathrm{red}}\cup\{j\}\Bigr)\implies\bigl(CR_{(\bar{\mathbb{A}})}=\emptyset\bigr). (33) PROOF. For a candidate active set \bar{\mathbb{A}}=\mathbb{A}\cup\{i\} , we compute \bar{\mathbb{A}}_{\mathrm{red}} as in ( 32 ). If there is no index j such that \bar{\mathbb{A}}_{\mathrm{red}}=\mathbb{A}_{\mathrm{red}}\cup\{j\} , the candidate solution does not lie on a child face of the polyhedral representation. Since, under mild assumptions 3 3 3 We assume LICQ, which can be ensured via slight perturbations of the original constraints. , the explicit solution is continuous and corresponds to a single index update in the active set, implication ( 33 ) follows, concluding the proof. ∎ 5 Explicit MPC algorithm We introduce Algorithm 1 to compute the solution of explicit MPC, adapting to the particular structure and properties of constrained zonotopes. The algorithm follows similar reasoning to that introduced in the previous work for the general polyhedral case (see [ 13 ] ). Algorithm 1 Explicit MPC solution in the CZ case 1: The cost matrices \tilde{Q} and \tilde{H} ; the constrained zonotope matrices in ( 23 ); the matrix Y of the hypercube representation in ( 14c ). 2: The graph \mathcal{L}^{\prime} containing the solution 3: Initialize \mathcal{L}^{\prime} with a node containing \emptyset , denoted as n_{\emptyset} 4: Initialize a queue \mathcal{Q} with \emptyset 5: while \mathcal{Q} is not empty do 6: Extract active set \mathbb{H} from the queue \mathcal{Q} 7: Compute \mathbb{S}_{(\mathbb{H})} as in ( 34 ) 8: Initialize \mathcal{G}\leftarrow\{\emptyset\} 9: for each i in \mathbb{S}_{(\mathbb{H})} do 10: Let h^{\prime}\leftarrow\mathbb{H} 11: Make h^{\prime}(i)\leftarrow 0; h^{\prime}(i+D)\leftarrow 1 12: \mathcal{G}\leftarrow\{\mathcal{G},h^{\prime}\} 13: Make h^{\prime}(i)\leftarrow 1; h^{\prime}(i+D)\leftarrow 0 14: \mathcal{G}\leftarrow\{\mathcal{G},h^{\prime}\} 15: Let n^{\mathbb{H}} be a node for \mathbb{H} in \mathcal{L}^{\prime} 16: for \textbf{each candidate set}\ \mathbb{A}\in\mathcal{G} do 17: Find or create the node n^{\mathbb{A}} for \mathbb{A} in \mathcal{L}^{\prime} 18: if n^{\mathbb{A}} is newly created then 19: Compute the critical region using Alg. 2 20: (L_{(\mathbb{A})},\ell_{(\mathbb{A})},\textit{flag})\leftarrow\texttt{getCriticalRegion}(\mathbb{A}) 21: if flag is false then 22: go to Step 16 [ numerical issues ] 23: if implication ( 33 ) does not hold then 24: go to Step 16 [ quick check ] 25: if the polyhedral set P(L_{(\mathbb{A})},\ell_{(\mathbb{A})}) is empty then 26: go to Step 16 [ Chebishev radius ] 27: Add the active set \mathbb{A} to the queue \mathcal{Q} 28: Add the edge (n^{\mathbb{H}},n^{\mathbb{A}}) to the graph \mathcal{L}^{\prime} 29: Add the edge (n^{\mathbb{H}},n^{\mathbb{A}}) to \mathcal{L}^{\prime} if not already added 30: return the solution graph \mathcal{L}^{\prime} Alg. 1 enumerates nodes from the face lattice of the feasible domain ( 16 ), each corresponding to a non-empty critical region. The resulting structure is a tree in which every node is defined by its active set, together with the associated primal/dual solution and critical region (plus auxiliary data required for internal updates, e.g., Z_{(\mathbb{A})} , K_{(\mathbb{A})}^{-1} , and T^{+}_{(\mathbb{A})} ). The edges are indexed by the constraints which become active in the transition from parent to child. Although the procedure is conceptually simple, its efficiency depends critically on three aspects: i) generation of candidate active sets for a given parent node; ii) reuse of previously computed information in determining the critical region; and, iii) a hierarchy of emptiness checks and stopping conditions to avoid unnecessary computations. These aspects are discussed in detail next. First, since active sets are in bijection with the faces of the feasible domain, each potential child of a parent node ( \mathbb{H} from step 6 ) is either a neighboring face of a higher order or the empty set. In the polyhedral case, this enumeration requires facet–vertex operations [ 13 ] , which are computationally burdensome. In contrast, the constrained zonotope description of ( 16 ) enables explicit enumeration in steps 9 – 14 . Assume that the inequalities |\xi|\leq\mathbf{1}_{\bar{D}} in ( 16 ) are ordered such that the i -th inequality corresponds to \xi_{i}\leq 1 and the (i+D) -th to -\xi_{i}\leq 1 . We then extract the indices for which neither 4 4 4 Both constraints cannot be simultaneously active, since this would require \xi_{i}=1 and \xi_{i}=-1 . constraint in the pair (i,i+D) is active \mathbb{S}_{(\mathbb{A})}=\left\{\,i\in\{1,\dots,D\}:a_{i}\veebar a_{i+D}=0,\ i\in\mathbb{A}\,\right\}. (34) Here, the active set \mathbb{A}=\{a_{1},a_{2},\dots,a_{2D}\} is encoded with logical values, as a_{i}\in\{0,1\} , where a_{i}=1 if the i -th constraint is active. The exclusive OR is defined as x\veebar y=\begin{cases}1,&x\neq y,\\ 0,&x=y.\end{cases} (35) Enumerating over each i\in\mathbb{S}_{(\mathbb{A})} and activating either the i -th or (i+D) -th constraint, as done in steps 9 – 14 , generates all child facets of the face described by \mathbb{A} . Algorithm 2 ( getCriticalRegion ) Compute the critical region with CZ using iterative updates 1: The current active set \bar{\mathbb{A}} of the form \bar{\mathbb{A}}=\mathbb{A}\cup\{i\} , a tolerance \varepsilon 2: Critical region (L_{(\bar{\mathbb{A}})},\ell_{(\bar{\mathbb{A}})}) and a flag success 3: Let D\leftarrow number of columns in G_{D} 4: Initialize L_{(\bar{\mathbb{A}})}\leftarrow\emptyset , \ell_{(\bar{\mathbb{A}})}\leftarrow\emptyset , success \leftarrow true 5: Retrieve Z_{(\mathbb{A})} , K_{(\mathbb{A})}^{-1} , and T^{+}_{(\mathbb{A})} from memory 6: Compute Z_{(\bar{\mathbb{A}})}=Z_{(\mathbb{A})}\mathrm{null}\left(Y_{i}Z_{(\mathbb{A})}\right) as in Lemma 8 7: if Z_{(\bar{\mathbb{A}})}^{\top}G_{D}^{\top}QG_{D}Z_{(\bar{\mathbb{A}})} is not positive definite then 8: success \leftarrow false [ numerical infeasibility ] 9: return (L_{(\bar{\mathbb{A}})},\ell_{(\bar{\mathbb{A}})},\textit{success}) 10: Let k\leftarrow\mathbb{A}\veebar\bar{\mathbb{A}} and compute T^{+}_{(\bar{\mathbb{A}})} as in ( 31 ) 11: Determine matrices U , V as in ( 28 ) 12: if \min_{\lambda\in\Lambda\!\left(I_{2}+VK^{-1}_{({\mathbb{A}})}U\right)}|\lambda|\leq\varepsilon then 13: success \leftarrow false [ singular matrix detected ] 14: return (L_{(\bar{\mathbb{A}})},\ell_{(\bar{\mathbb{A}})},\textit{success}) 15: Compute K^{-1}_{(\bar{\mathbb{A}})} as in Prop. 10 16: Store Z_{(\bar{\mathbb{A}})} , K_{(\bar{\mathbb{A}})}^{-1} , and T^{+}_{(\bar{\mathbb{A}})} in memory 17: Compute S_{(\bar{\mathbb{A}})} and s_{(\bar{\mathbb{A}})} with ( 19c ), ( 19d ) 18: Extract L_{(\bar{\mathbb{A}})} and \ell_{(\bar{\mathbb{A}})} using ( 18 ) 19: return (L_{(\bar{\mathbb{A}})},\ell_{(\bar{\mathbb{A}})},\textit{success}) Secondly, Algorithm 2 details the computation of the critical region in the constrained-zonotope case. For brevity, we only highlight the improvements over [ 21 ] , namely the iterative construction of the matrices Z_{(\bar{\mathbb{A}})} , K_{(\bar{\mathbb{A}})} , and T^{+}_{(\bar{\mathbb{A}})} (steps 6 , 15 and 10 ). Thirdly, we clarify the stopping conditions in Algorithm 1 . Since the full emptiness test is computationally expensive, we adopt a hierarchical approach. If Algorithm 2 returns false (e.g., due to numerical issues or lack of an inverse), we stop early at step 21 . If the necessary condition in Prop. 13 fails at step 23 , we also terminate. Only at step 25 we do perform the full emptiness test. Among the available strategies, our practical implementation computes the Chebyshev radius [ 8 ] of the candidate region and applies a threshold-based rule to discard regions with small radius. 6 Numerical simulation This section presents a comparison of the algorithms introduced in the previous sections. For clarity, we label the results as follows: Algorithm 1 is labeled CZ , and the improvements described in Section 4.2 are labeled CZ (Iterative) and CZ (Iterative | Quick) . We test the methods on an example with the state vector in \mathbb{R}^{4} given as \displaystyle A=\begin{bmatrix}\hphantom{-}0.84&\hphantom{-}0.02&\hphantom{-}0.00&-0.02\\ \hphantom{-}0.01&\hphantom{-}0.88&-0.03&-0.02\\ \hphantom{-}0.04&-0.08&\hphantom{-}0.86&-0.02\\ -0.09&-0.02&-0.02&\hphantom{-}0.88\end{bmatrix},B=\begin{bmatrix}-0.10&\hphantom{-}0.03\\ -0.07&-0.07\\ -0.27&\hphantom{-}0.13\\ \hphantom{-}0.01&-0.00\end{bmatrix}. (36) The associated cost matrices are S=Q=I_{4} and R=0.1\cdot I_{2} , with state and input constraints |x_{k}|\leq 10\cdot\mathbf{1}_{n} and |u_{k}|\leq\mathbf{1}_{m} . All algorithms are run in MATLAB R2024b on a laptop with AMD Ryzen 7 and 16 GB of RAM, on the Windows 11 operating system. Applying Alg. 1 to the dynamics ( 36 ) with prediction horizon N=4 yields the tree structure shown in Fig. 3 . Each edge is labeled with the index of the constraint that becomes active, so the active set of any node can be obtained by tracing a path from the root (empty set) to that node (two examples are highlighted). Although multiple paths may exist depending on the order in which indices are appended, the result is a tree, since Alg. 1 terminates the search once a link is established. Figure 3: Tree structure obtained from Alg. 1 , applied to dynamics ( 36 ), for prediction horizon N=4 . Figure 4 illustrates the computation time of each variant of the algorithm with respect to the prediction horizon. We compare our algorithm with the state-of-the-art solvers, namely YALMIP and MPT3. Several trends are clear. First, for the short to mid horizons (where N\leq 8 ), both iterative variants of our algorithm are consistently faster than YALMIP and MPT3. The iterative quick variant is the best performer. Second, the crossover region (where N\approx 10 ) reveals that the performance converges. The iterative quick variant is roughly on par with the state-of-the-art solvers, whereas the iterative non-quick becomes modestly slower. Third, for long horizons, we notice that YALMIP and MPT3 scale more favorably and overtake our methods. The baseline CZ (non-iterative) degrades the fastest. The iterative quick variant remains the best of our three, but it is slower than YALMIP and MPT3. Considering the scaling behavior, all curves are approximately straight lines on a log-time axis, indicating exponential growth with N . Among our variants, the iterative quick method reduces the slope relative to the plain iterative one, while the non-iterative CZ has the steepest slope. Conversely, YALMIP and MPT3 exhibit nearly identical scaling across the entire range. Notably, our code is implemented in MATLAB without using compiled code (e.g., through mex calls). However, we expect that significant reductions in computation time can be obtained with a C++ compiled version of the code. Figure 4: Computation time vs. prediction horizon N . It is equally important to analyze the time performance while considering the number of critical regions discovered by the algorithms, since generating more solutions leads to an increase in computation time. Differences in the number of regions arise from tolerances, mainly involved in deciding whether a polyhedral set is empty or not. From Figure 5 , we conclude that our algorithm and its variants produce the same number of critical regions when compared to the state-of-the-art solvers, except for the case N=12 , where YALMIP and MPT3 produce slightly more regions in this particular example. This is a clear indicator that our methods work as intended and are comparable to the state-of-the-art solvers. Figure 5: Number of critical regions vs. prediction horizon N . Lastly, Figure 6 provides insights about the behavior of our methods. We have chosen to illustrate only the iterative quick variant, since it considers all stopping criteria discussed in Alg. 2 . Figure 6: Count of the exit conditions vs. prediction horizon N for the iterative quick variant. The figure shows at which points the algorithm exits: when it encounters a numerical tolerance violation (blue), when the quick check is guaranteed (teal), when the region is empty (yellow), or when a new critical region is discovered (purple). As it can be observed, the quick exit condition makes a significant contribution, which justifies the increased performance of this variant. The numerical tolerance cases are also significant; these are cases in which we either have numerical infeasibility (see Step 8 in Algorithm 2 ) or a singular matrix has been detected (see Step 13 of the same algorithm). 7 Conclusions This paper presented a reinterpretation of explicit MPC in which the feasible domain is represented as a constrained zonotope. The multi-parametric problem was formulated in the lifted generator space and solved using second-order optimality conditions. Computational efficiency was enhanced through low-rank matrix updates and an analytic enumeration of candidate active sets naturally yielded the explicit solution in tree form. Numerical results demonstrated improved performance over conventional polyhedral formulations both in computation time and scalability. The code used to generate the results is available at: www.gitlab.com/msstefan/constrained-zonotope-empc/-/tree/paper-1-iterative-updates .