2017-05-10

# Efficient calculation of spectral bounds for Hessian matrices on hyperrectangles

## Prof. Dr.-Ing. Martin Mönnigmann, Ruhr-Universität Bochum

18 Jul 2017, 17:00–18:30; Location: S4|10-1

The presentation summarizes progress made over the past few years in the calculation of spectral bounds of interval Hessian matrices. Spectral bounds of this type play an important role in global optimization algorithms. They can be used, for example, to detect if a given optimization problem is convex, or to generate a convex relaxation in case it is not. In technical terms, the problem is the following: Find, in a computationally efficient way, bounds on the eigenvalues of all Hessian matrices in a Hessian matrix set for $$\{\nabla^2\Phi(x)\vee x\in S\}$$ a $$C^2$$-function $$\Phi:U\subset R^n\rightarrow R\$$ on a hyperrectangle $$S\subset U$$. The new method differs from existing ones in that it deliberately does not use any interval matrices. As a result, it exhibits two interesting features: The new method requires only $$\mathcal{O}(n) N(\Phi)$$ operations (where $$N(\Phi)$$ refers to the number of operations necessary to evaluate $$\Phi$$ at a given point). Secondly, for some functions $$\Phi$$, the new method results in tighter eigenvalue bounds than the tightest theoretically possible bounds for the interval Hessian matrix. This is surprising, since the fastest method for calculating the tightest possible eigenvalue bounds for the interval Hessian requires $$\mathcal{O}(2^n)$$ operations, in contrast to the $$\mathcal{O}(n)N(\Phi)$$ operations required here. In this sense, the proposed method belongs to a much more attractive complexity class and it sometimes results in better bounds than one of the best known methods.

Category: CE Seminar