Approximating the Real Structured Stability Radius with Frobenius Norm\n Bounded Perturbations

Nicola Guglielmi, Mert Gürbüzbalaban, Timothy J. Mitchell, Michael L. Overton

Abstract

We propose a fast method to approximate the real stability radius of a linear dynamical system with output feedback, where the perturbations are restricted to be real-valued and bounded with respect to the Frobenius norm. Our work builds on scalable algorithms designed to approximate spectral value sets and the complex stability radius. Although our algorithm is guaranteed to find only upper bounds to the real stability radius, it is highly effective in practice. This represents the first algorithm to specifically address the Frobenius-norm version of this problem. By focusing on the eigenvalue with the maximal real part (for continuous-time systems) or modulus (for discrete-time systems), the algorithm remains efficient for large-scale systems with sparse matrices.

Introduction

In control theory and dynamical systems, the "stability radius" serves as a critical metric for robustness. It quantifies the smallest perturbation that can be applied to a system's matrices before it loses stability. While methods for calculating the stability radius under complex-valued perturbations or spectral norm bounds are well-established, the real-valued case—particularly under Frobenius norm constraints—has remained a significant challenge for large-scale systems.

The Frobenius norm is often more physically relevant in engineering applications than the spectral norm, yet it lacks the mathematical properties that simplify the complex-valued case. Previous computational approaches were generally limited to small-scale matrices due to $O(n^3)$ complexity or failed to account for real-valued constraints. This paper introduces a scalable solution for engineers working with large, sparse dynamical systems.

The HEC-RF Algorithm

The core contribution of this work is the Hybrid Expansion-Contraction (HEC-RF) algorithm. The method operates through a two-phase iterative process designed to find the smallest destabilizing perturbation.

1. Expansion Phase (SVSA-RF)

This phase utilizes a gradient system derived from an Ordinary Differential Equation (ODE). It iteratively searches for a perturbation of a fixed size ($\epsilon$) that pushes the system's eigenvalues as far as possible toward the instability region (the right-half plane for continuous systems). A key innovation is the use of a rank-2 iteration. This exploits the structure of real-valued perturbations, making the process significantly more efficient than full-matrix updates.

2. Contraction Phase

Once a destabilizing perturbation is identified, the algorithm enters the contraction phase. Using a Newton-bisection method, it shrinks the perturbation size ($\epsilon$) until the system is exactly on the threshold of instability—where the rightmost eigenvalue lies precisely on the imaginary axis.

The algorithm's efficiency stems from its reliance on computing only the single rightmost eigenvalue of a sequence of matrices, rather than performing a full decomposition. This makes it uniquely suited for large-scale, sparse matrices where traditional methods would be computationally prohibitive.

Theoretical Insights and Key Ideas

Real vs. Complex Geometry

The paper notes that real spectral value sets are significantly more complex than their complex counterparts. They can exhibit non-convex shapes and "holes," which complicates the search for a global stability radius. The HEC-RF algorithm navigates this by treating the search as a trajectory of an ODE on a manifold of matrices, ensuring each step moves toward a locally worst-case perturbation.

The Rank-2 Property

In spectral norm problems, the worst-case perturbation is known to have a rank of at most two. The authors demonstrate empirically that this property also holds for the Frobenius norm. By assuming this rank-2 structure, the algorithm simplifies complex matrix mathematics into faster vector operations, enabling its application to high-dimensional systems.

Experimental Results

The authors evaluated HEC-RF on a diverse set of benchmarks, ranging from small-scale dense problems to large-scale sparse systems:

  • Small Dense Problems: The algorithm was tested on 34 systems from the COMPlib library, confirming its accuracy against known benchmarks.
  • Large Sparse Problems: The algorithm was applied to 14 large-scale systems, including models of heat flow and wave equations. For systems like skewlap3d, HEC-RF converged in seconds or minutes, whereas traditional Hamiltonian-based methods would be impossible to execute.
  • Acceleration: A "v2" configuration of the code, utilizing vector extrapolation and early termination, reduced the number of required eigenvalue solves by over 50% without compromising the quality of the stability radius estimate.

Conclusion and Limitations

While HEC-RF is the first practical method for this specific problem to scale to large systems, it does have limitations. Because the underlying optimization problem is non-convex, the algorithm provides an upper bound rather than a guaranteed global minimum. Additionally, while the rank-2 property is supported by extensive empirical evidence, a formal rigorous proof for the Frobenius norm remains an open question for future research.

Despite these theoretical caveats, the algorithm's ability to provide tight, reliable approximations for large-scale sparse systems marks a significant advancement in the robust stability analysis of linear dynamical systems.

Summary updated

Abstract

We propose a fast method to approximate the real stability radius of a linear\ndynamical system with output feedback, where the perturbations are restricted\nto be real valued and bounded with respect to the Frobenius norm. Our work\nbuilds on a number of scalable algorithms that have been proposed in recent\nyears, ranging from methods that approximate the complex or real pseudospectral\nabscissa and radius of large sparse matrices (and generalizations of these\nmethods for pseudospectra to spectral value sets) to algorithms for\napproximating the complex stability radius (the reciprocal of the $H_\\infty$\nnorm). Although our algorithm is guaranteed to find only upper bounds to the\nreal stability radius, it seems quite effective in practice. As far as we know,\nthis is the first algorithm that addresses the Frobenius-norm version of this\nproblem. Because the cost mainly consists of computing the eigenvalue with\nmaximal real part for continuous-time systems (or modulus for discrete-time\nsystems) of a sequence of matrices, our algorithm remains very efficient for\nlarge-scale systems provided that the system matrices are sparse.\n
BibTeX
@article{guglielmi2017approximating,
  author = {Nicola Guglielmi and Mert Gürbüzbalaban and Timothy J. Mitchell and Michael L. Overton},
  title = {{Approximating the Real Structured Stability Radius with Frobenius Norm\textbackslash\{\}n Bounded Perturbations}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2017},
  doi = {10.1137/16m1110169},
}
Figure