An interval-matrix branch-and-bound algorithm for bounding eigenvalues
File(s)
Author(s)
Nerantzis, D
Adjiman, CSJ
Type
Journal Article
Abstract
We present and explore the behaviour of a branch-and-bound algorithm for calculating valid bounds on the k-th largest eigenvalue of a symmetric interval matrix. Branching on the interval elements of the matrix takes place in conjunction with the application of Rohn’s method (an interval extension of Weyl’s theorem) in order to obtain valid outer bounds on the eigenvalues. Inner bounds are obtained with the use of two local search methods. The algorithm has the theoretical property that it provides bounds to any arbitrary precision > 0 (assuming infinite precision arithmetic) within finite time. In contrast with existing methods, bounds for each individual eigenvalue can be obtained even if its range overlaps with the ranges of other eigenvalues. Performance analysis is carried out through nine examples. In the first example, a comparison of the efficiency of the two local search methods is reported using 4,000 randomly generated matrices. The eigenvalue bounding algorithm is then applied to five randomly generated matrices with overlapping eigenvalue ranges. Valid and sharp bounds are indeed identified given a sufficient number of iterations. Furthermore, most of the range reduction takes place in the first few steps of the algorithm so that significant benefits can be derived without full convergence. Finally, in the last three examples, the potential of the algorithm for use in algorithms to identify index-1 saddle points of nonlinear functions is demonstrated.
Date Issued
2016-07-05
Online Publication Date
2016-07-05
Date Acceptance
2016-04-27
ISSN
1055-6788
Publisher
Taylor & Francis
Start Page
872
End Page
891
Journal / Book Title
Optimization Methods & Software
Volume
32
Issue
4
Copyright Statement
© 2016 The Author(s). Published by Informa UK Limited, trading as Taylor & Francis Group This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons. org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited
Source Database
manual-entry
Sponsor
Engineering & Physical Science Research Council (EPSRC)
Grant Number
EP/J003840/1
Subjects
Science & Technology
Technology
Physical Sciences
Computer Science, Software Engineering
Operations Research & Management Science
Mathematics, Applied
Computer Science
Mathematics
global optimization
branch-and-bound
interval matrix
eigenvalue bounds
index-1 saddle points
POTENTIAL-ENERGY SURFACES
GLOBAL OPTIMIZATION
REAL EIGENVALUES
ALPHA-BB
NP-HARD
STABILITY
STANDARD
0102 Applied Mathematics
0103 Numerical And Computational Mathematics
0802 Computation Theory And Mathematics
Operations Research
Publication Status
Published