Numerical Optimization of Eigenvalues of Hermitian Matrix Functions

Abstract

This work concerns the global minimization of a prescribed eigenvalue or a weighted sum of prescribed eigenvalues of a Hermitian matrix-valued function depending on its parameters analytically in a box. We describe how the analytical properties of eigenvalue functions can be put into use to derive piece-wise quadratic functions that underestimate the eigenvalue functions. These piece-wise quadratic under-estimators lead us to a global minimization algorithm, originally due to Breiman and Cutler. We prove the global convergence of the algorithm, and show that it can be effectively used for the minimization of extreme eigenvalues, e.g., the largest eigenvalue or the sum of the largest specified number of eigenvalues. This is particularly facilitated by the analytical formulas for the first derivatives of eigenvalues, as well as analytical lower bounds on the second derivatives that can be deduced for extreme eigenvalue functions. The applications that we have in mind also include the ${\mathrm{H}}_{\infty }$-norm of a linear dynamical system, numerical radius, distance to uncontrollability and various other non-convex eigenvalue optimization problems, for which, generically, the eigenvalue function involved is simple at all points.

25 pages, 3 figures

References in corpus (2)

• Acceleration of univariate global optimization algorithms working with Lipschitz functions and Lipschitz first derivatives
• Lipschitz gradients for global optimization in a one-point-based partitioning scheme

Cited by in corpus (14)

• On applications of quantum computing to plasma simulations
• Calibration artefacts in radio interferometry. I. Ghost sources in WSRT data
• Derivatives of symplectic eigenvalues and a Lidskii type theorem
• Sampling Strategies for Data-Driven Inference of Input-Output System Properties
• Deep Multigrid: learning prolongation and restriction matrices
• Differential equations for real-structured (and unstructured) defectivity measures
• Spectrally Constrained Optimization
• Nonsmooth Rate-of-Convergence Analyses of Algorithms for Eigenvalue Optimization
• A Support Based Algorithm for Optimization with Eigenvalue Constraints
• Residual minimizing shift parameters for the low-rank ADI iteration
• Large-Scale Computation of ${\mathcal{L}}_{\infty }$-Norms by a Greedy Subspace Method
• An unconstrained framework for eigenvalue problems
• Subspace acceleration for large-scale parameter-dependent Hermitian eigenproblems
• An indefinite LOBPCG type of algorithm for detecting a definite Hermitian matrix pair