FAST APPROXIMATION OF THE H ∞ NORM VIA HYBRID EXPANSION-CONTRACTION USING SPECTRAL VALUE SETS

Abstract. The H ∞ norm is a well known and important measure arising in many applications that quantifies the least amount of perturbation a linear dynamical system with inputs and outputs can incur such that it may no longer be asymptotically stable. Calculating it is an expensive proposition of finding a global optimum of a nonconvex and nonsmooth optimization problem, and while the standard algorithm by Boyd, Balakrishnan, Bruinsma, and Steinbuch can find the optimal solution, its cubic cost per iteration limits the algorithm’s applicability to rather small dimension systems. In 2013, Guglielmi, Gürbüzbalaban, and Overton presented the first fast algorithm to approximate the H ∞ norm using a spectral value set based approach that does not require reducing the dimension of the system, only that it be sparse and have relatively few inputs and outputs. However, despite its favorable scaling properties and apparent ability to usually provide good approximations to the H ∞ norm, the method can sometimes critically break down in practice. We present an improved spectral value set based algorithm using a novel hybrid expansion-contraction scheme that, under no additional assumptions, guarantees convergence to a stationary point of the optimization problem without incurring breakdown. Furthermore, we present new optimizations to accelerate both methods as well as allow either of the algorithms to extend to cases where the number of inputs and/or outputs may be large. Finally, we present a comprehensive numerical evaluation of both algorithms, along with the various new optimizations, where we demonstrate that compared to the earlier algorithm evaluated on a large-scale test set, hybrid expansion-contraction not only generally produces as good approximations to the H ∞ norm, and sometimes significantly better ones, but also completes the entire test set 3 to 18 times faster, depending on which optimizations are enabled. 1. Introduction. Conside