Journal article

Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint

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.

Publication status:: Published

Peer review status:: Peer reviewed

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Share
Cite

Cite this record

APA Style

Adachi, S., & Nakatsukasa, Y. (2017). Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint. Mathematical Programming, 173(1-2), 79–116.

MLA Style

Adachi, S, and Y Nakatsukasa. “Eigenvalue-Based Algorithm and Analysis for Nonconvex QCQP with One Constraint.” Mathematical Programming, vol. 173, nos. 1-2, 2017, pp. 79–116.

Chicago Style

Adachi, S, and Y Nakatsukasa. 2017. “Eigenvalue-Based Algorithm and Analysis for Nonconvex QCQP with One Constraint.” Mathematical Programming 173 (1-2): 79–116.
Print

Access Document

Files:: Adachi-Nakatsukasa2019_Article_Eigenvalue-basedAlgorithmAndAn.pdf

(Preview, Version of record, pdf, 958.0KB, Terms of use)

Publisher copy:: 10.1007/s10107-017-1206-8

Authors

+ Adachi, S More by this author

Role:: Author

+ Nakatsukasa, Y More by this author

Institution:: University of Oxford
Division:: MPLS Division
Department:: Mathematical Institute
Oxford college:: Christ Church
Role:: Author
ORCID:: 0000-0001-7911-1501

Publisher:: Springer Link
Journal:: Mathematical Programming More from this journal
Volume:: 173
Issue:: 1-2
Pages:: 79-116
Publication date:: 2017-11-10
Acceptance date:: 2017-10-24
DOI:: 10.1007/s10107-017-1206-8
EISSN:: 1436-4646
ISSN:: 0025-5610

Language:: English
Pubs id:: pubs:993762
UUID:: uuid:ec81267c-756b-4db5-a9f4-e3cd60b26b87
Local pid:: pubs:993762
Source identifiers:: 993762
Deposit date:: 2019-04-23
ARK identifier:: ark:/29072/ora_ec81267c756b4db5a9f4e3cd60b26b87

Terms of use

Copyright holder:: Nakatsukasa
Copyright date:: 2017
Notes:: © The Author(s) 2017. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Licence:: CC Attribution (CC BY)

Views and Downloads

About views and downloads

If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP