We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming.
- Authors
Lu, Cheng; Deng, Zhibin; Zhou, Jing; Guo, Xiaoling
- Abstract
In this paper, we design an eigenvalue decomposition based branch-and-bound algorithm for finding global solutions of quadratically constrained quadratic programming (QCQP) problems. The hardness of nonconvex QCQP problems roots in the nonconvex components of quadratic terms, which are represented by the negative eigenvalues and the corresponding eigenvectors in the eigenvalue decomposition. For certain types of QCQP problems, only very few eigenvectors, defined as sensitive-eigenvectors, determine the relaxation gaps. We propose a semidefinite relaxation based branch-and-bound algorithm to solve QCQP. The proposed algorithm, which branches on the directions of the sensitive-eigenvectors, is very efficient for solving certain types of QCQP problems.
- Subjects
EIGENVECTORS; DECOMPOSITION method; CONSTRAINED optimization; QUADRATIC programming; COMPUTER algorithms
- Publication
Journal of Global Optimization, 2019, Vol 73, Issue 2, p371
- ISSN
0925-5001
- Publication type
Article
- DOI
10.1007/s10898-018-0726-y