Positive semidefinite penalty method for quadratically constrained quadratic programming
文献类型：期刊论文
| 作者 | Gu, Ran1,2; Du, Qiang1,2; Yuan, Ya-xiang3 |
| 刊名 | IMA JOURNAL OF NUMERICAL ANALYSIS
 |
| 出版日期 | 2021-10-01 |
| 卷号 | 41期号:4页码:2488-2515 |
| ISSN号 | 0272-4979 |
| 关键词 | quadratically constrained quadratic programming semidefinite programming semidefinite relaxation penalty function |
| DOI | 10.1093/imanum/draa031 |
| 英文摘要 | 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. |
| 资助项目 | 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 |
| 语种 | 英语 |
| 出版者 | OXFORD UNIV PRESS |
| WOS记录号 | WOS:000730873800004 |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/59736]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | 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. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。