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 | |
发表期刊 | IMA JOURNAL OF NUMERICAL ANALYSIS |
ISSN | 0272-4979 |
卷号 | 41期号:4页码:2488-2515 |
摘要 | 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. |
关键词 | quadratically constrained quadratic programming semidefinite programming semidefinite relaxation penalty function |
DOI | 10.1093/imanum/draa031 |
收录类别 | SCI |
语种 | 英语 |
资助项目 | 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研究方向 | Mathematics |
WOS类目 | Mathematics, Applied |
WOS记录号 | WOS:000730873800004 |
出版者 | OXFORD UNIV PRESS |
引用统计 | |
文献类型 | 期刊论文 |
条目标识符 | http://ir.amss.ac.cn/handle/2S8OKBNM/59737 |
专题 | 中国科学院数学与系统科学研究院 |
通讯作者 | Gu, Ran |
作者单位 | 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 |
推荐引用方式 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. |
条目包含的文件 | 条目无相关文件。 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论