A note on approximating the nearest stable discrete-time descriptor systems with fixed rank

Nicolas Gillis, Michael Karow, Punit Sharma

Abstract

This paper presents a novel approach for the stabilization of discrete-time descriptor systems, which are essential for modeling complex engineering systems where variables are constrained by algebraic equations. The authors address the non-convex optimization problem of finding the nearest stable system by introducing a specific matrix parametrization. By allowing both the state-transition matrix and the descriptor matrix to vary while maintaining a fixed rank, the proposed algorithm significantly reduces approximation error compared to traditional methods. Experimental results on benchmark matrices demonstrate the efficiency and scalability of the approach.

Introduction

In control theory and signal processing, linear systems are typically modeled by the state-space equation $x(k+1) = Ax(k)$. However, many physical systems—such as electrical circuits, chemical processes, and mechanical linkages—are more accurately described by descriptor systems of the form $Ex(k+1) = Ax(k)$. When the descriptor matrix $E$ is singular (not invertible), these are also known as differential-algebraic equations (DAEs).

A fundamental problem in the analysis of these systems is stabilization: given an unstable system $(E, A)$, how can we find the "nearest" stable descriptor system $(\hat{E}, \hat{A})$? Closeness is typically measured using the Frobenius norm of the perturbations. This task is notoriously difficult because the set of stable descriptor systems is non-convex, neither open nor closed, and unbounded. While previous literature has often focused on perturbing only the matrix $A$ (assuming $E$ is fixed), this paper tackles the more general and effective problem of allowing both $E$ and $A$ to change, subject to a fixed-rank constraint on $E$.

Methodology

The core contribution of this work is a structured reformulation of the stabilization problem. The authors prove that any stable, index-one descriptor system can be represented using a specific "quadruple" of matrices $(T, W, U, B)$.

Matrix Parametrization

The target matrices $\hat{E}$ and $\hat{A}$ are expressed through a parametrization involving an orthogonal matrix $U$ and a positive semidefinite contraction $B$ (where eigenvalues are bounded between 0 and 1). This transformation maps the abstract stability constraints into concrete geometric constraints that are easier to optimize.

Block Coordinate Descent (BCD)

Using this new structure, the authors implement an iterative Block Coordinate Descent algorithm. The process alternates between two main steps:

  1. Least Squares Update: Solving for matrices $W$ and $T$ using standard least squares techniques, which provide fast, closed-form solutions.
  2. Gradient Update: Updating $U$ and $B$ using a fast gradient method adapted from standard matrix stabilization literature.

To mitigate the issues associated with non-convexity, the algorithm is initialized using a starting point derived from the polar decomposition of the input matrix, which helps the search begin in a promising region of the parameter space.

Results and Discussion

The proposed "stable pair" approach demonstrates significant improvements over methods that only allow $A$ to vary.

Comparison of convergence speed and final error between the nearest stable matrix approach and the proposed nearest stable matrix pair algorithm.

As shown in Figure 1, the algorithm converges rapidly. In a test case involving a $10 \times 10$ Grcar matrix, the stable pair approach achieved a final error of 1.88, whereas the traditional approach (perturbing only $A$) resulted in an error of 3.88. This represents a reduction in error of over 50%.

Eigenvalue distribution of the original unstable system compared to the stabilized systems. The stabilized eigenvalues are successfully moved onto or inside the unit circle.

Figure 2 illustrates the effect of the stabilization on the system's eigenvalues. The original eigenvalues (blue circles) lie outside the unit circle, indicating instability. Both the "nearest stable matrix" and "nearest stable matrix pair" methods successfully shift these eigenvalues onto the boundary or into the interior of the unit circle (red circles and magenta crosses), satisfying the stability criteria.

Key Insights

  • Joint Perturbation: Allowing $E$ to vary, even slightly, provides much more flexibility in finding a stable neighbor, leading to drastically smaller perturbations.
  • Scalability: The algorithm maintains a computational complexity of $O(n^3)$ per iteration. Tests on matrices up to size $n=1000$ show that it remains practical for large-scale applications.
  • Rank Sensitivity: The error typically changes monotonically with the rank $r$ of $E$. The authors found that the optimal rank for the stabilized system is often close to the numerical rank of the original unstable $E$.

Conclusion

This paper provides a robust framework for approximating the nearest stable descriptor system with a fixed-rank constraint. By leveraging a novel parametrization and an efficient BCD algorithm, the authors offer a tool that outperforms existing methods in terms of approximation accuracy. Future work may focus on extending these results to higher-index descriptor systems and developing more sophisticated initialization schemes to further improve the chances of reaching global optima in the non-convex landscape.

Summary updated

Abstract

Consider a discrete-time linear time-invariant descriptor system $Ex(k+1)=Ax(k)$ for $k \in \mathbb Z_{+}$. In this paper, we tackle for the first time the problem of stabilizing such systems by computing a nearby regular index one stable system $\hat E x(k+1)= \hat A x(k)$ with $\text{rank}(\hat E)=r$. We reformulate this highly nonconvex problem into an equivalent optimization problem with a relatively simple feasible set onto which it is easy to project. This allows us to employ a block coordinate descent method to obtain a nearby regular index one stable system. We illustrate the effectiveness of the algorithm on several examples.
BibTeX
@inproceedings{gillis2019note,
  author = {Nicolas Gillis and Michael Karow and Punit Sharma},
  title = {{A note on approximating the nearest stable discrete-time descriptor systems with fixed rank}},
  booktitle = {Applied Numerical Mathematics},
  year = {2019},
  doi = {10.1016/j.apnum.2019.09.004},
}
Figure