Improved Automatic Computation of Hessian Matrix Spectral Bounds
Moritz Schulze Darup, Martin Mönnigmann · SIAM Journal on Scientific Computing · 2016
This paper presents a fast and powerful method for the computation of eigenvalue bounds for Hessian matrices $ abla^2{\varphi(x)}$ of nonlinear twice continuously differentiable functions $\varphi:\mathcal{U}\subseteq{\mathbb R}^n\rightarrow{\mathbb R}$ on hyperrectangles $\mathcal{B} \subset \mathcal{U}$. The method is based on a recently proposed procedure [M. Mönnigmann, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 1351--1366] for an efficient computation of spectral bounds using extended codelists. Both that approach and the one presented here substantially differ from established methods in that they deliberately do not use any interval matrices and thus result in a favorable numerical complexity of order ${\cal O}(n)\,N(\varphi)$, where $N(\varphi)$ denotes the number of operations needed to evaluate $\varphi$ at a point in its domain. We improve the method presented by Mönnigmann by exploiting sparsity, which naturally arises in the underlying codelists. The new method provides bounds that are as good as or better than those from the most accurate existing method in about 82% of the test cases.