Positive semidefinite penalty method for quadratically constrained quadratic programming

doi:10.1093/imanum/draa031

CSpace

	Positive semidefinite penalty method for quadratically constrained quadratic programming
	Gu, Ran 1,2; Du, Qiang 1,2; Yuan, Ya-xiang 3
	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.