Efficient computation of spectral bounds for Hessian matrices on hyperrectangles for global optimization

Moritz Schulze Darup, Martin Kastsian, Stefan Mross and Martin Mönnigmann ()

Journal of Global Optimization, 2014, vol. 58, issue 4, 652 pages

Abstract: We compare two established and a new method for the calculation of spectral bounds for Hessian matrices on hyperrectangles by applying them to a large collection of 1,522 objective and constraint functions extracted from benchmark global optimization problems. Both the tightness of the spectral bounds and the computational effort of the three methods, which apply to $$C^2$$ C 2 functions $${\varphi }:\mathbb{R }^n\rightarrow \mathbb{R }$$ φ : R n → R that can be written as codelists, are assessed. Specifically, we compare eigenvalue bounds obtained with the interval variant of Gershgorin’s circle criterion (Adjiman et al. in Comput Chem Eng 22(9):1137–1158, 1998 ; Gershgorin in Izv. Akad. Nauk SSSR, Ser. fizmat. 6:749–754, 1931 ), Hertz (IEEE Trans Autom Control 37:532–535, 1992 ) and Rohn’s (SIAM J Matrix Anal Appl 15(1):175–184, 1994 ) method for tight bounds of interval matrices, and a recently proposed Hessian matrix eigenvalue arithmetic (Mönnigmann in SIAM J. Matrix Anal. Appl. 32(4): 1351–1366, 2011 ), which deliberately avoids the computation of interval Hessians. The eigenvalue arithmetic provides tighter, as tight, and less tight bounds than the interval variant of Gershgorin’s circle criterion in about 15, 61, and 24 % of the examples, respectively. Hertz and Rohn’s method results in bounds that are always as tight as or tighter than those from Gershgorin’s circle criterion, and as tight as or tighter than those from the eigenvalue arithmetic in 96 % of the cases. In 4 % of the examples, the eigenvalue arithmetic results in tighter bounds than Hertz and Rohn’s method. This result is surprising, since Hertz and Rohn’s method provides tight bounds for interval matrices. The eigenvalue arithmetic provides tighter bounds in these cases, since it is not based on interval matrices. Copyright Springer Science+Business Media New York 2014

Keywords: Eigenvalue bounds; Spectral bounds; Hessian; Interval matrix; Global optimization (search for similar items in EconPapers)
Date: 2014
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10898-013-0099-1 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:58:y:2014:i:4:p:631-652

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-013-0099-1

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().