Abstract
In this paper, we address the problem of stabilizing discrete-time linear systems by computing a nearby stable matrix to an unstable one. We introduce a novel characterization for the set of stable matrices, demonstrating that a matrix $A$ is stable if and only if it can be decomposed as $A=S^{-1}UBS$, where $S$ is positive definite, $U$ is orthogonal, and $B$ is a positive semidefinite contraction (singular values $\le 1$). This characterization transforms the nearest stable matrix problem into an optimization task with a feasible set that allows for efficient projection. We propose a fast projected gradient method (FGM) to solve this problem in variables $(S, U, B)$ and demonstrate its superior scalability and effectiveness compared to existing state-of-the-art approaches.
Introduction
In control theory and system identification, discrete-time linear systems are fundamental tools for modeling dynamic processes. The stability of such a system is governed by its transition matrix $A$; specifically, a system is stable if and only if all eigenvalues of $A$ lie within the unit circle of the complex plane.
In practice, researchers often encounter unstable matrices due to measurement noise, modeling errors, or system perturbations. The challenge then becomes finding the "nearest" stable matrix to the original unstable one. This is known as the nearest stable matrix problem. Mathematically, this is a notoriously difficult non-convex optimization problem. The set of stable matrices is neither open nor closed and possesses a complex geometry with sharp edges and "holes," making it difficult for traditional optimization algorithms to navigate without getting trapped in poor local minima or failing to scale to high-dimensional systems.
The SUB Characterization
The core innovation of this work is a new way to represent stable matrices. We prove that stability can be fully characterized by a specific factorization, which we call the SUB form:
$$A = S^{-1}UBS$$
In this decomposition:
- $S$ is a positive definite matrix. This matrix defines the shape of a Lyapunov ellipsoid, which is central to proving stability in linear systems.
- $U$ is an orthogonal matrix, representing a rotation or reflection.
- $B$ is a positive semidefinite contraction, meaning its singular values are restricted to the interval $[0, 1]$.
By reparameterizing the search space into the variables $(S, U, B)$, we move from searching over the "messy" set of stable matrices to searching over well-defined, structured sets. This transformation is the key to developing more efficient numerical methods.
Optimization via Fast Projected Gradient Method (FGM)
Leveraging the SUB characterization, we propose a Fast Projected Gradient Method (FGM). The algorithm operates by taking gradient steps in the $(S, U, B)$ space and then projecting the results back onto their respective feasible sets.
A major advantage of this approach is the computational efficiency of these projections. For example, projecting onto the set of orthogonal matrices involves a polar decomposition, and projecting onto the set of semidefinite contractions is similarly straightforward. These operations typically have a complexity of $O(n^3)$, which is significantly lower than the computational cost of the second-order methods used in previous literature. This efficiency allows the FGM to handle much larger matrices than was previously possible.
Experimental Evaluation
We evaluated the FGM against several benchmark problems and compared its performance to the previous state-of-the-art method, Successive Convex Approximation (SuccConv).
Scalability and Speed
The FGM demonstrates a dramatic improvement in scalability. In our tests, a single iteration of SuccConv for a matrix of size $n=50$ could take approximately 30 seconds. In contrast, the FGM is capable of processing matrices as large as $n=1000$ on a standard laptop within a reasonable timeframe. This represents a significant leap in the size of systems that can be stabilized numerically.
Accuracy and Robustness
We tested the algorithm on several challenging matrix types:
- Grcar Matrices: These are banded Toeplitz matrices with eigenvalues that are highly sensitive and naturally reside outside the unit circle. The FGM consistently found closer stable approximations for these matrices than competing methods.
- Small-scale Benchmarks: On 3x3 and 5x5 matrices designed to trigger local minima, the FGM proved robust.
- Random Matrices: General performance tests confirmed that the SUB-based approach is broadly applicable.
To address the inherent non-convexity of the problem, we employed a multi-start strategy by initializing the algorithm with different random $S$ matrices. This approach frequently allowed the algorithm to escape local minima that trapped other solvers.
Conclusion
The SUB characterization provides a powerful bridge between abstract Lyapunov stability theory and practical numerical optimization. By transforming the nearest stable matrix problem into a structured projection-based task, we have enabled the stabilization of much larger discrete-time systems than previously possible.
Future work will explore extending this framework to complex-valued matrices and investigating port-Hamiltonian structures in discrete time, which are essential for energy-preserving physical simulations. Additionally, we aim to refine initialization heuristics to further improve the likelihood of identifying global optima in the non-convex landscape of stable matrices.
Summary updated