Abstract | ||
---|---|---|
A nonconvex quadratically constrained quadratic programming (QCQP) with one constraint is usually solved via a dual SDP problem, or Moré’s algorithm based on iteratively solving linear systems. In this work we introduce an algorithm for QCQP that requires finding just one eigenpair of a generalized eigenvalue problem, and involves no outer iterations other than the (usually black-box) iterations for computing the eigenpair. Numerical experiments illustrate the efficiency and accuracy of our algorithm. We also analyze the QCQP solution extensively, including difficult cases, and show that the canonical form of a matrix pair gives a complete classification of the QCQP in terms of boundedness and attainability, and explain how to obtain a global solution whenever it exists. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1007/s10107-017-1206-8 | Mathematical Programming |
Keywords | Field | DocType |
QCQP,Generalized eigenvalue problem,Canonical form for symmetric matrix pair,49M37,65K05,90C20,90C30 | Quadratic growth,Mathematical optimization,Linear system,Matrix (mathematics),Algorithm,Canonical form,Eigendecomposition of a matrix,Quadratic programming,Mathematics,Eigenvalues and eigenvectors | Journal |
Volume | Issue | ISSN |
173.0 | 1-2 | 1436-4646 |
Citations | PageRank | References |
1 | 0.36 | 16 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
S. Adachi | 1 | 41 | 7.53 |
Yuji Nakatsukasa | 2 | 97 | 17.74 |