Efficient calculation of spectral bounds for Hessian matrices on hyperrectangles

Start date:18. July 2017
Start time:17:00 Uhr
End time:17:45 Uhr
Organizer:Graduate School Computational Engineering
Speaker:Prof. Dr.-Ing. Martin Mönnigmann, Ruhr-Universität Bochum
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 {2Φ(x)xS} a C2-function Φ:URnR  on a hyperrectangle SU. 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 O(n)N(Φ) operations (where N(Φ) refers to the number of operations necessary to evaluate Φ at a given point). Secondly, for some functions Φ, 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 O(2n) operations, in contrast to the O(n)N(Φ) 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.


Communication and Marketing

Hochschulstraße 10
64289 Darmstadt

+49 6151 16-25501

If you know about other events at the department not listed yet, please notify us at events(a-t)informatik.tu-darmstadt.de.

A A A | Drucken Print | Impressum Impressum | Sitemap Sitemap | Suche Search | Kontakt Contact | Website Analysis: More Information
zum Seitenanfangzum Seitenanfang