A note on semidefinite programming relaxations for polynomial optimization over a single sphere

doi:10.1007/s11425-016-0301-5

	A note on semidefinite programming relaxations for polynomial optimization over a single sphere
	Hu Jiang 1; Jiang Bo 2; Liu Xin3 ; Wen ZaiWen 1
	2016-08-01
发表期刊	SCIENCE CHINA-MATHEMATICS
ISSN	1674-7283
卷号	59 期号:8 页码:1543-1560
摘要	We study two instances of polynomial optimization problem over a single sphere. The first problem is to compute the best rank-1 tensor approximation. We show the equivalence between two recent semidefinite relaxations methods. The other one arises from Bose-Einstein condensates (BEC), whose objective function is a summation of a probably nonconvex quadratic function and a quartic term. These two polynomial optimization problems are closely connected since the BEC problem can be viewed as a structured fourth-order best rank-1 tensor approximation. We show that the BEC problem is NP-hard and propose a semidefinite relaxation with both deterministic and randomized rounding procedures. Explicit approximation ratios for these rounding procedures are presented. The performance of these semidefinite relaxations are illustrated on a few preliminary numerical experiments.
关键词	polynomial optimization over a single sphere semidefinite programming best rank-1 tensor approximation Bose-Einstein condensates
DOI	10.1007/s11425-016-0301-5
语种	英语
WOS研究方向	Mathematics
WOS类目	Mathematics, Applied ; Mathematics
WOS记录号	WOS:000380212100007
出版者	SCIENCE PRESS
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/23278
专题	计算数学与科学工程计算研究所
通讯作者	Hu Jiang
作者单位	1.Peking Univ, Beijing Int Ctr Math Res, Beijing 100871, Peoples R China 2.Shanghai Univ Finance & Econ, Sch Informat Management & Engn, Res Ctr Management Sci & Data Analyt, Shanghai 200433, Peoples R China 3.Chinese Acad Sci, Acad Math & Syst Sci, Inst Computat Math & Sci Engn Comp, LSEC, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Hu Jiang,Jiang Bo,Liu Xin,et al. A note on semidefinite programming relaxations for polynomial optimization over a single sphere[J]. SCIENCE CHINA-MATHEMATICS,2016,59(8):1543-1560.
APA	Hu Jiang,Jiang Bo,Liu Xin,&Wen ZaiWen.(2016).A note on semidefinite programming relaxations for polynomial optimization over a single sphere.SCIENCE CHINA-MATHEMATICS,59(8),1543-1560.
MLA	Hu Jiang,et al."A note on semidefinite programming relaxations for polynomial optimization over a single sphere".SCIENCE CHINA-MATHEMATICS 59.8(2016):1543-1560.