20170510
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 SeminarTechnische Universität Darmstadt
Graduate School CE
Dolivostraße 15
D64293 Darmstadt

Send email to assistants' office
Show a list of open BSc/MSc topics at GSC CE.