Matrix Nearness Problems and Eigenvalue Optimization

Matrix nearness problems ask how far a given matrix is from having a prescribed desired or undesired property. The properties considered in this book are spectral properties, and the problem is to determine a nearest unstructured or structured matrix having a spectral property such as singularity, defectivity, instability or stability, or having systems-theoretic spectral properties such as controllability and passivity, or graph-theoretic spectral properties such as connectivity and centrality. These matrix nearness problems are optimization problems that arise naturally in numerical linear algebra, dynamical systems, robust control, graph theory, and other areas of mathematics applied to science and engineering.

This book develops a computational framework for solving a broad class of matrix nearness problems based on eigenvalue optimization. The central observation is that optimal perturbations are often of rank one or can be represented as projections of rank-one matrices onto prescribed linear structures. This leads to efficient two-level algorithms that combine low-rank matrix differential equations for eigenvalue optimization with scalar root-finding techniques. The book presents the mathematical foundations of this approach together with algorithms, convergence analysis, and numerous applications.