Stabilizing discrete-time linear systems

Nicolas Gillis, Michael Karow, Punit Sharma

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

Abstract

In this paper, we consider the problem of stabilizing discrete-time linear systems by computing a nearby stable matrix to an unstable one. To do so, we provide a new characterization for the set of stable matrices. We show that a matrix $A$ is stable if and only if it can be written as $A=S^{-1}UBS$, where $S$ is positive definite, $U$ is orthogonal, and $B$ is a positive semidefinite contraction (that is, the singular values of $B$ are less or equal 1). This characterization results in an equivalent optimization problem with a feasible set on which it is easy to project. We propose a very efficient fast projected gradient method to solve the problem in variables $(S,U,B)$. We show the effectiveness of the proposed method compared to other approaches.
BibTeX
@inproceedings{gillis2019stabilizing,
  author = {Nicolas Gillis and Michael Karow and Punit Sharma},
  title = {{Stabilizing discrete-time linear systems}},
  booktitle = {Linear},
  year = {2019},
  doi = {10.1016/j.laa.2019.03.014},
}

Loading related content...

Figure