KMS Of Academy of mathematics and systems sciences, CAS
| Positive semidefinite penalty method for quadratically constrained quadratic programming | |
| Gu, Ran1,2; Du, Qiang1,2; Yuan, Ya-xiang3 | |
| 2021-10-01 | |
| Source Publication | IMA JOURNAL OF NUMERICAL ANALYSIS
 |
| ISSN | 0272-4979 |
| Volume | 41Issue:4Pages:2488-2515 |
| Abstract | Quadratically constrained quadratic programming (QCQP) appears widely in engineering applications such as wireless communications and networking and multiuser detection with examples like the MAXCUT problem and boolean optimization. A general QCQP problem is NP-hard. We propose a penalty formulation for the QCQP problem based on semidefinite relaxation. Under suitable assumptions we show that the optimal solutions of the penalty problem are the same as those of the original QCQP problem if the penalty parameter is sufficiently large. Then, to solve the penalty problem, we present a proximal point algorithm and an update rule for the penalty parameter. Numerically, we test our algorithm on two well-studied QCQP problems. The results show that our proposed algorithm is very effective in finding high-quality solutions. |
| Keyword | quadratically constrained quadratic programming semidefinite programming semidefinite relaxation penalty function |
| DOI | 10.1093/imanum/draa031 |
| Indexed By | SCI |
| Language | 英语 |
| Funding Project | Chinese Academy of Sciences ; National Science Foundation[DMR 1534910] ; National Science Foundation[CCF1704833] ; National Natural Science Foundation of China[11331012] ; National Natural Science Foundation of China[11688101] |
| WOS Research Area | Mathematics |
| WOS Subject | Mathematics, Applied |
| WOS ID | WOS:000730873800004 |
| Publisher | OXFORD UNIV PRESS |
| Citation statistics | |
| Document Type | 期刊论文 |
| Identifier | http://ir.amss.ac.cn/handle/2S8OKBNM/59737 |
| Collection | 中国科学院数学与系统科学研究院 |
| Corresponding Author | Gu, Ran |
| Affiliation | 1.Columbia Univ, Dept Appl Phys & Appl Math, Fu Fdn Sch Engn & Appl Sci, New York, NY 10027 USA 2.Columbia Univ, Data Sci Inst, New York, NY 10027 USA 3.Chinese Acad Sci, Acad Math & Syst Sci, Inst Computat Math & Sci Engn Comp, State Key Lab Sci & Engn Comp, Beijing 100190, Peoples R China |
| Recommended Citation GB/T 7714 | Gu, Ran,Du, Qiang,Yuan, Ya-xiang. Positive semidefinite penalty method for quadratically constrained quadratic programming[J]. IMA JOURNAL OF NUMERICAL ANALYSIS,2021,41(4):2488-2515. |
| APA | Gu, Ran,Du, Qiang,&Yuan, Ya-xiang.(2021).Positive semidefinite penalty method for quadratically constrained quadratic programming.IMA JOURNAL OF NUMERICAL ANALYSIS,41(4),2488-2515. |
| MLA | Gu, Ran,et al."Positive semidefinite penalty method for quadratically constrained quadratic programming".IMA JOURNAL OF NUMERICAL ANALYSIS 41.4(2021):2488-2515. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment