On maximal positive invariant set computation for rank-deficient linear systems

1. Problem Statement

The paper addresses the computational challenge of determining the Maximal Positively Invariant (MPI) set for discrete-time linear systems where the closed-loop dynamics matrix is rank-deficient.

• Context: In Model Predictive Control (MPC), the MPI set is crucial as a terminal constraint to guarantee recursive feasibility and stability. It is typically computed via a backward reachability procedure involving the iterative intersection of predecessor sets: $\Omega_{k+1} = A_\circ^{-1}\Omega_k \cap \mathcal{X}$.
• The Issue: Standard optimal control synthesis (e.g., solving the Discrete Algebraic Riccati Equation) or dead-beat control strategies often result in closed-loop matrices ($A_\circ = A + BK$) with eigenvalues at zero.
• Consequence: When $A_\circ$ is singular (rank-deficient), the standard recurrence relation becomes numerically unstable or geometrically ill-defined. The dynamics effectively project the state space onto lower-dimensional subspaces during intermediate steps, causing standard algorithms (using polyhedral or zonotopic representations) to fail or become computationally prohibitive due to the explosion of constraints and iterations required to converge.

2. Methodology

The authors propose a robust algorithm that exploits the Real Schur Decomposition of the closed-loop matrix to handle singularities explicitly. The core idea is to decouple the system dynamics into a stable, non-singular subspace and a nilpotent (zero-eigenvalue) subspace.

A. Mathematical Foundation

1. Schur Decomposition: The closed-loop matrix is decomposed as $A_\circ = USU^\top$, where $U$ is orthogonal and $S$ is upper triangular.
2. Block Partitioning: The matrix $S$ is partitioned such that the zero eigenvalues (and their associated Jordan blocks) are isolated in the bottom-right block ($S_{22}$), while the non-zero eigenvalues reside in the top-left block ($S_{11}$):
   $$S = \begin{bmatrix} S_{11} & S_{12} \\ 0 & S_{22} \end{bmatrix}$$
   Here, $S_{22}$ is nilpotent with index $p+1$ (i.e., $S_{22}^{p+1} = 0$).
3. Coordinate Transformation: The state vector is transformed into $y = U^\top x$, separating the dynamics into two components ($y_1$ and $y_2$). The $y_2$ component vanishes after $p$ steps due to nilpotence.

B. The Proposed Algorithm

The algorithm computes the MPI set in two phases and intersects the results:

1. Phase 1 (Transient Constraints): Compute the intersection of constraints for the first $p$ iterations ($k < p$). During this phase, the nilpotent dynamics are still active, and the full state constraints must be enforced.
2. Phase 2 (Reduced Dynamics): For $k \geq p$, the system dynamics effectively reduce to $z_{k+1} = S_{11}z_k$ in a lower-dimensional subspace ($\mathbb{R}^{d_1}$).
   • The authors compute the MPI set ($\Phi_z$) for this reduced, full-rank system.
   • This reduced set is then "lifted" back to the original space using an auxiliary matrix $T$ (derived from $S_{11}, S_{12}, S_{22}$) to enforce the constraints on the original coordinates.
3. Final Intersection: The final MPI set is the intersection of the transient constraints (Phase 1) and the lifted reduced set (Phase 2).

C. Representations

The method is formulated for two set representations:

• Polyhedral Sets: Using half-space inequalities ($Fx \leq \theta$).
• Constrained Zonotopes (CZ): Using generator matrices and equality constraints. The authors leverage the property that CZs are closed under intersection and linear mapping, allowing the exact recurrence to be performed without approximation.

3. Key Contributions

• Handling Singular Dynamics: The paper provides the first explicit theoretical framework and algorithm to compute MPI sets for systems with closed-loop eigenvalues at zero, a case where standard backward reachability fails.
• Dimensionality Reduction: By utilizing the Schur form, the computationally expensive part of the recurrence (the infinite horizon iteration) is performed in a reduced dimension ($d_1 < n$), significantly lowering complexity.
• Dual Representation Support: The algorithm is applicable to both polyhedral and constrained zonotope representations, offering flexibility for different control applications.
• Robustness: The approach avoids numerical instability associated with inverting singular matrices by working directly with the nilpotent structure.

4. Results and Evaluation

The authors validated their approach using two examples:

1. Numerical Example ($\mathbb{R}^6$):

   • A system with a closed-loop matrix having eigenvalues $\{0, 0, 0, 0.2, 0.5, 0.7\}$.
   • The algorithm successfully computed the MPI set in 0.4 seconds, correctly handling the rank deficiency ($d_2=3$) by reducing the problem to a 3D subspace.

2. Coupled Spring Experiment (CSE):

   • A scalable system with variable mass count ($\ell$), increasing state dimension up to $\mathbb{R}^{20}$.
   • Comparison: The proposed "rank-deficient" method was compared against a standard algorithm (which fails or becomes inefficient for singular cases).
   • Performance Gains:
     • Iterations: The standard method required a massive increase in iterations as dimension grew, whereas the proposed method showed moderate growth.
     • Computation Time: For $\ell \geq 8$, the standard method became computationally prohibitive, while the proposed method remained efficient.
     • Complexity: The number of inequalities required to describe the resulting polyhedral set was significantly lower for the proposed method (e.g., 704 vs. 1496 inequalities for $\ell=10$).

5. Significance

This work resolves a critical bottleneck in the design of Model Predictive Control (MPC) for systems utilizing optimal feedback laws that naturally induce rank deficiency (e.g., Riccati-based control or dead-beat control).

• Enabling Robust MPC: It allows engineers to use theoretically optimal controllers that place poles at zero without sacrificing the ability to compute the necessary terminal invariant sets for stability guarantees.
• Computational Efficiency: By reducing the dimensionality of the reachability problem, it makes the computation of invariant sets feasible for higher-dimensional systems where standard methods would fail.
• Theoretical Rigor: It bridges the gap between algebraic geometry (Schur/Jordan forms) and convex optimization (set invariance), providing a mathematically sound solution for singular linear systems.

In conclusion, the paper presents a necessary advancement for modern control theory, ensuring that the "maximal" property of invariant sets can be computed reliably even when the underlying system dynamics are singular.