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

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...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2019-01, Vol.173 (1-2), p.79-116
Main Authors: Adachi, Satoru, Nakatsukasa, Yuji
Format: Article
Language:English
Subjects:
Algorithms
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Eigenvalues
Full Length Paper
Linear systems
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematics
Mathematics and Statistics
Mathematics of Computing
Numerical Analysis
Quadratic programming
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c359t-998e3beba0af8921cfc161f42d9a86b65a71974d077a46d2133ad4c7ec25c83c3
cites cdi_FETCH-LOGICAL-c359t-998e3beba0af8921cfc161f42d9a86b65a71974d077a46d2133ad4c7ec25c83c3
container_end_page 116
container_issue 1-2
container_start_page 79
container_title Mathematical programming
container_volume 173
creator Adachi, Satoru
Nakatsukasa, Yuji
description 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.
doi_str_mv 10.1007/s10107-017-1206-8
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2171995078</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2171995078</sourcerecordid><originalsourceid>FETCH-LOGICAL-c359t-998e3beba0af8921cfc161f42d9a86b65a71974d077a46d2133ad4c7ec25c83c3</originalsourceid><addsrcrecordid>eNp1kE1LAzEQhoMoWKs_wNuC5-hMsptkj1LqBxS1oOeQzWbrlm1Sk63af--WFTx5GmZ43pfhIeQS4RoB5E1CQJAUUFJkIKg6IhPMuaC5yMUxmQCwghYC4ZScpbQGAORKTcjTvF05_2m6naOVSa7OTLcKse3fN5nxw-ZNt09typoQMx-8Df7TfWfL2fIl-xqoLHiXDcfUR9P6_pycNKZL7uJ3Tsnb3fx19kAXz_ePs9sFtbwoe1qWyvHKVQZMo0qGtrEosMlZXRolKlEYiaXMa5DS5KJmyLmpcyudZYVV3PIpuRp7tzF87Fzq9Trs4vBr0gyHbFmAVAOFI2VjSCm6Rm9juzFxrxH0QZsetelBmz5o04cMGzNpYP3Kxb_m_0M__QJvvA</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2171995078</pqid></control><display><type>article</type><title>Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint</title><source>EBSCOhost Business Source Ultimate</source><source>ABI/INFORM Global</source><source>Springer Link</source><creator>Adachi, Satoru ; Nakatsukasa, Yuji</creator><creatorcontrib>Adachi, Satoru ; Nakatsukasa, Yuji</creatorcontrib><description>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.</description><identifier>ISSN: 0025-5610</identifier><identifier>EISSN: 1436-4646</identifier><identifier>DOI: 10.1007/s10107-017-1206-8</identifier><language>eng</language><publisher>Berlin/Heidelberg: Springer Berlin Heidelberg</publisher><subject>Algorithms ; Calculus of Variations and Optimal Control; Optimization ; Combinatorics ; Eigenvalues ; Full Length Paper ; Linear systems ; Mathematical and Computational Physics ; Mathematical Methods in Physics ; Mathematics ; Mathematics and Statistics ; Mathematics of Computing ; Numerical Analysis ; Quadratic programming ; Theoretical</subject><ispartof>Mathematical programming, 2019-01, Vol.173 (1-2), p.79-116</ispartof><rights>The Author(s) 2017</rights><rights>Mathematical Programming is a copyright of Springer, (2017). All Rights Reserved. © 2017. This work is published under http://creativecommons.org/licenses/by/4.0 (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c359t-998e3beba0af8921cfc161f42d9a86b65a71974d077a46d2133ad4c7ec25c83c3</citedby><cites>FETCH-LOGICAL-c359t-998e3beba0af8921cfc161f42d9a86b65a71974d077a46d2133ad4c7ec25c83c3</cites><orcidid>0000-0001-7911-1501</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.proquest.com/docview/2171995078?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,776,780,11668,27903,27904,36039,44342</link.rule.ids></links><search><creatorcontrib>Adachi, Satoru</creatorcontrib><creatorcontrib>Nakatsukasa, Yuji</creatorcontrib><title>Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint</title><title>Mathematical programming</title><addtitle>Math. Program</addtitle><description>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.</description><subject>Algorithms</subject><subject>Calculus of Variations and Optimal Control; Optimization</subject><subject>Combinatorics</subject><subject>Eigenvalues</subject><subject>Full Length Paper</subject><subject>Linear systems</subject><subject>Mathematical and Computational Physics</subject><subject>Mathematical Methods in Physics</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Mathematics of Computing</subject><subject>Numerical Analysis</subject><subject>Quadratic programming</subject><subject>Theoretical</subject><issn>0025-5610</issn><issn>1436-4646</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2019</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNp1kE1LAzEQhoMoWKs_wNuC5-hMsptkj1LqBxS1oOeQzWbrlm1Sk63af--WFTx5GmZ43pfhIeQS4RoB5E1CQJAUUFJkIKg6IhPMuaC5yMUxmQCwghYC4ZScpbQGAORKTcjTvF05_2m6naOVSa7OTLcKse3fN5nxw-ZNt09typoQMx-8Df7TfWfL2fIl-xqoLHiXDcfUR9P6_pycNKZL7uJ3Tsnb3fx19kAXz_ePs9sFtbwoe1qWyvHKVQZMo0qGtrEosMlZXRolKlEYiaXMa5DS5KJmyLmpcyudZYVV3PIpuRp7tzF87Fzq9Trs4vBr0gyHbFmAVAOFI2VjSCm6Rm9juzFxrxH0QZsetelBmz5o04cMGzNpYP3Kxb_m_0M__QJvvA</recordid><startdate>20190101</startdate><enddate>20190101</enddate><creator>Adachi, Satoru</creator><creator>Nakatsukasa, Yuji</creator><general>Springer Berlin Heidelberg</general><general>Springer Nature B.V</general><scope>C6C</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7SC</scope><scope>7WY</scope><scope>7WZ</scope><scope>7XB</scope><scope>87Z</scope><scope>88I</scope><scope>8AL</scope><scope>8AO</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>8FL</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>L.-</scope><scope>L6V</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0C</scope><scope>M0N</scope><scope>M2P</scope><scope>M7S</scope><scope>P5Z</scope><scope>P62</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PTHSS</scope><scope>Q9U</scope><orcidid>https://orcid.org/0000-0001-7911-1501</orcidid></search><sort><creationdate>20190101</creationdate><title>Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint</title><author>Adachi, Satoru ; Nakatsukasa, Yuji</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c359t-998e3beba0af8921cfc161f42d9a86b65a71974d077a46d2133ad4c7ec25c83c3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2019</creationdate><topic>Algorithms</topic><topic>Calculus of Variations and Optimal Control; Optimization</topic><topic>Combinatorics</topic><topic>Eigenvalues</topic><topic>Full Length Paper</topic><topic>Linear systems</topic><topic>Mathematical and Computational Physics</topic><topic>Mathematical Methods in Physics</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Mathematics of Computing</topic><topic>Numerical Analysis</topic><topic>Quadratic programming</topic><topic>Theoretical</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Adachi, Satoru</creatorcontrib><creatorcontrib>Nakatsukasa, Yuji</creatorcontrib><collection>SpringerOpen</collection><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>ABI/INFORM Collection</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection</collection><collection>Science Database (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest Pharma Collection</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Database‎ (1962 - current)</collection><collection>ProQuest Central Essentials</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>ProQuest Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer science database</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ProQuest Engineering Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>ABI/INFORM Global</collection><collection>Computing Database</collection><collection>ProQuest Science Journals</collection><collection>Engineering Database</collection><collection>ProQuest advanced technologies &amp; aerospace journals</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>One Business (ProQuest)</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>Engineering collection</collection><collection>ProQuest Central Basic</collection><jtitle>Mathematical programming</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Adachi, Satoru</au><au>Nakatsukasa, Yuji</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint</atitle><jtitle>Mathematical programming</jtitle><stitle>Math. Program</stitle><date>2019-01-01</date><risdate>2019</risdate><volume>173</volume><issue>1-2</issue><spage>79</spage><epage>116</epage><pages>79-116</pages><issn>0025-5610</issn><eissn>1436-4646</eissn><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.</abstract><cop>Berlin/Heidelberg</cop><pub>Springer Berlin Heidelberg</pub><doi>10.1007/s10107-017-1206-8</doi><tpages>38</tpages><orcidid>https://orcid.org/0000-0001-7911-1501</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0025-5610
ispartof Mathematical programming, 2019-01, Vol.173 (1-2), p.79-116
issn 0025-5610
1436-4646
language eng
recordid cdi_proquest_journals_2171995078
source EBSCOhost Business Source Ultimate; ABI/INFORM Global; Springer Link
subjects Algorithms
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Eigenvalues
Full Length Paper
Linear systems
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematics
Mathematics and Statistics
Mathematics of Computing
Numerical Analysis
Quadratic programming
Theoretical
title Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-22T19%3A42%3A53IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Eigenvalue-based%20algorithm%20and%20analysis%20for%20nonconvex%20QCQP%20with%20one%20constraint&rft.jtitle=Mathematical%20programming&rft.au=Adachi,%20Satoru&rft.date=2019-01-01&rft.volume=173&rft.issue=1-2&rft.spage=79&rft.epage=116&rft.pages=79-116&rft.issn=0025-5610&rft.eissn=1436-4646&rft_id=info:doi/10.1007/s10107-017-1206-8&rft_dat=%3Cproquest_cross%3E2171995078%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c359t-998e3beba0af8921cfc161f42d9a86b65a71974d077a46d2133ad4c7ec25c83c3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2171995078&rft_id=info:pmid/&rfr_iscdi=true