On approximating the nearest Ω-stable matrix

Neelam Choudhary, Nicolas Gillis, Punit Sharma

On Approximating the Nearest Ω-Stable Matrix

Abstract

This paper presents a novel framework for finding the nearest matrix to a given input such that its eigenvalues are constrained within a specific region Ω of the complex plane. By utilizing dissipative Hamiltonian (DH) reparameterization and Linear Matrix Inequalities (LMIs), the authors transform a non-convex nearness problem into an optimization task with a convex feasible set. A block coordinate descent (BCD) algorithm is proposed to solve the resulting problem, demonstrating effectiveness in control theory and system identification applications.

Introduction

In the fields of control theory and system identification, ensuring the stability of a linear system is a fundamental requirement. However, simple stability—where eigenvalues merely reside in the left-half plane—is often insufficient for practical engineering. Performance specifications frequently demand Ω-stability, where eigenvalues are confined to specific sub-regions of the complex plane to guarantee properties such as minimum decay rates, maximum overshoot, or specific damping ratios.

Problem Formulation

The "nearest Ω-stable matrix" problem seeks a matrix $X$ that minimizes the Frobenius norm distance $\|A - X\|_F$ from a given matrix $A$, subject to the constraint that all eigenvalues of $X$ lie within a predefined region $Ω \subset \mathbb{C}$. This problem is notoriously difficult because the set of matrices with eigenvalues in a specific region is generally non-convex, making standard optimization techniques prone to failure.

Illustration of an Ω-stability region defined by the intersection of a conic sector (θ), a vertical strip (h), and a disk (r).

As shown in the figure above, the region Ω can be constructed as the intersection of several elementary regions. These include conic sectors (limiting damping ratios), vertical strips (setting decay rates), and disks (relevant for discrete-time stability or limiting undamped natural frequency).

Methodology

To address the non-convexity of the constraints, the authors employ a change of variables based on Dissipative Hamiltonian (DH) matrices. A matrix $X$ is represented as:

$$X = (J - R)Q$$

where $J$ is skew-symmetric ($J^T = -J$), $R$ is symmetric positive semidefinite ($R \succeq 0$), and $Q$ is symmetric positive definite ($Q \succ 0$).

The core contribution involves deriving new Linear Matrix Inequalities (LMIs) that characterize the desired regions. By introducing an auxiliary variable $P = Q^{-1}$, the authors reformulate the constraints such that the feasible set becomes convex. While the objective function remains non-convex in $P$, optimizing over a convex set is significantly more tractable than minimizing over a non-convex set.

The proposed solution uses a Block Coordinate Descent (BCD) algorithm that alternates between:

  1. Optimizing $(J, R)$ for a fixed $P$, which constitutes a convex subproblem.
  2. Updating $P$ via a gradient step with a backtracking line search.

Experimental Evaluation

The framework was evaluated using synthetic data and established benchmarks. In synthetic tests with varying noise levels ($\epsilon$), the algorithm's performance was sensitive to initialization. An LMI-based initialization proved superior for low-noise scenarios (finding the best solution 100% of the time at $\epsilon = 0.01$), while a simple identity initialization ($P=I$) showed surprising robustness as noise increased.

On a $5 \times 5$ benchmark matrix from the literature, the BCD algorithm achieved a competitive Frobenius norm error of 0.90. Notably, the method perfectly recovered four of the original eigenvalues on the boundary of the unit disk, suggesting that the DH-based approach preserves important structural properties of the system even when it does not reach the absolute global minimum.

Conclusion

The DH-based reparameterization provides a modular and flexible approach to the Ω-stability problem. While the current implementation relies on computationally intensive interior-point methods that limit scalability for matrices larger than $n=50$, it offers a robust foundation for complex performance-constrained optimization. Future work aims to develop faster first-order algorithms and expand the library of supported LMI regions beyond the conic sectors, strips, and disks studied here.

Summary updated

Abstract

In this paper, we consider the problem of approximating a given matrix with a matrix whose eigenvalues lie in some specific region Ω, within the complex plane. More precisely, we consider three types of regions and their intersections: conic sectors, vertical strips and disks. We refer to this problem as the nearest Ω-stable matrix problem. This includes as special cases the stable matrices for continuous and discrete time linear time-invariant systems. In order to achieve this goal, we parametrize this problem using dissipative Hamiltonian matrices and linear matrix inequalities. This leads to a reformulation of the problem with a convex feasible set. By applying a block coordinate descent method on this reformulation, we are able to compute solutions to the approximation problem, which is illustrated on some examples.
BibTeX
@article{choudhary2020approximating,
  author = {Neelam Choudhary and Nicolas Gillis and Punit Sharma},
  title = {{On approximating the nearest Ω-stable matrix}},
  journal = {Numer. Linear Algebra Appl.},
  year = {2020},
  doi = {10.1002/nla.2282},
}
Figure