Approximating the Real Structured Stability Radius with Frobenius-Norm Bounded Perturbations

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

TL;DR

This paper introduces the first efficient algorithm to approximate the "real stability radius" for linear dynamical systems, specifically when perturbations are real-valued and bounded by the Frobenius norm. This is crucial for understanding system robustness in practical engineering scenarios where such perturbations are common.

What Problem Does This Paper Address?

In control theory, understanding how robust a system is to uncertainties is paramount. The "stability radius" quantifies this robustness by measuring the smallest perturbation that can destabilize a system. While much research has focused on perturbations measured by the spectral norm (largest singular value), this paper tackles the Frobenius norm, which is often more relevant in applications and computationally convenient. The challenge lies in efficiently computing this "real structured stability radius" for large-scale systems, as existing methods are either computationally prohibitive or don't address the Frobenius norm.

Methods

The authors propose a novel iterative algorithm, Algorithm SVSA-RF, to approximate the Frobenius-norm real stability radius. This method builds upon the theory of "spectral value sets" and an ordinary differential equation (ODE) that describes the evolution of perturbations. The core idea is to numerically integrate this ODE to find equilibrium points, which correspond to locally rightmost points of the spectral value set. The algorithm iteratively updates a perturbation matrix, ensuring it has unit Frobenius norm, and then uses a line search to guarantee progress towards a destabilizing perturbation. This process is embedded within a "hybrid expansion-contraction" framework (Algorithm HEC-RF) that efficiently searches for the stability radius.

Datasets

Not discussed in the paper. The paper focuses on a theoretical and algorithmic development, validated through numerical experiments on a suite of standard benchmark problems (e.g., ROC, CM, AC series) from the control literature.

Key Insights and Ideas

  • Frobenius Norm Matters: The paper highlights the practical relevance of the Frobenius norm for real-valued perturbations, which is often overlooked in favor of the spectral norm.
  • ODE as a Guide: The use of an ODE to characterize equilibrium points of perturbations provides a principled way to search for destabilizing scenarios.
  • Hybrid Expansion-Contraction: This algorithmic strategy effectively balances exploring the parameter space (expansion) with refining the estimate (contraction) to efficiently find the stability radius.
  • Rank-2 Perturbations: The method leverages the fact that for real perturbations, rank-2 matrices are often sufficient to capture the critical scenarios, simplifying the problem.
  • Guaranteed Upper Bounds: The algorithm explicitly generates destabilizing perturbations, ensuring that the computed values are guaranteed upper bounds to the true stability radius.

Key Results

The paper presents a novel algorithm (SVSA-RF and HEC-RF) that efficiently approximates the real structured stability radius with Frobenius-norm bounded perturbations. Numerical experiments on various benchmark problems demonstrate the algorithm's effectiveness, showing good agreement between different configurations and providing approximations with high accuracy. The "accelerated" version of the algorithm, incorporating extrapolation and early termination features, significantly reduces computational cost (eigensolves) on many problems.

Limitations and Future Work

  • Upper Bounds Only: The algorithm guarantees upper bounds, not exact values, for the stability radius.
  • Local vs. Global: While the algorithm aims to find globally rightmost points, it is theoretically guaranteed to find only locally rightmost points.
  • Rank-2 Assumption: The method relies on the assumption that rank-2 perturbations are sufficient for capturing critical scenarios, which is discussed but not fully proven for the Frobenius norm case.
  • Discrete-Time Extension: The paper outlines how the methods can be extended to discrete-time systems, but detailed implementation and results are deferred.
  • Further Acceleration: The authors suggest exploring more advanced extrapolation techniques and investigating the impact of oscillation in iterates for improved performance.

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 Tim Mitchell and Michael L. Overton},
  title = {{Approximating the Real Structured Stability Radius with Frobenius-Norm Bounded Perturbations}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2017},
  doi = {10.1137/16m1110169},
}

Loading related content...

Figure