Fast approximation of the H_∞ norm via optimization over spectral value sets

The H_∞ norm of a transfer matrix function for a control system is the reciprocal of the largest value of ε such that the associated ε-spectral value set is contained in the stability region for the dynamical system (the left half-plane in the continuous-time case and the unit disk in the discrete-time case). After deriving some fundamental properties of spectral value sets, particularly the intricate relationship between the singular vectors of the transfer matrix and the eigenvectors of the corresponding perturbed system matrix, we extend an algorithm recently introduced by Guglielmi and Overton [SIAM J. Matrix Anal. Appl., 32 (2011), pp. 1166-1192] for approximating the maximal real part or modulus of points in a matrix pseudospectrum to spectral value sets, characterizing its fixed points. We then introduce a Newton-bisection method to approximate the H _∞ norm, for which each step requires optimization of the real part or the modulus over an ε-spectral value set. Although the algorithm is guaranteed only to find lower bounds on the H_∞ norm, it typically finds good approximations in cases where we can test this. It is much faster than the standard Boyd- Balakrishnan-Bruinsma-Steinbuch algorithm to compute the H_∞ norm when the system matrices are large and sparse and the number of inputs and outputs is small. The main work required by the algorithm is the computation of the spectral abscissa or radius of a sequence of matrices that are rank-one perturbations of a sparse matrix.