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

作　　者：HU Jiang JIANG Bo LIU Xin WEN ZaiWen 

机构地区：[1]Beijing International Center for Mathematical Research, Peking University [2]Research Center for Management Science and Data Analytics, School of Information Management and Engineering,Shanghai University of Finance and Economics [3]LSEC, Institute of Computational Mathematics and Scientific/Engineering Computing,Academy of Mathematics and Systems Science, Chinese Academy of Sciences

出　　处：《Science China Mathematics》2016年第8期1543-1560,共18页中国科学：数学（英文版）

基　　金：supported by National Natural Science Foundation of China (Grant Nos. 11401364, 11322109, 11331012, 11471325 and 11461161005);the National High Technology Research and Development Program of China (863 Program) (Grant No. 2013AA122902);the National Center for Mathematics and Interdisciplinary Sciences, Chinese Academy of Sciences;National Basic Research Program of China (973 Program) (Grant No. 2015CB856002)

摘　　要：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.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 rela^xations are illustrated on a few preliminary numerical experiments.

关 键 词：polynomial optimization over a single sphere semidefinite programming best rank-1 tensor ap-proximation Bose-Einstein condensates 

分 类 号：O221[理学—运筹学与控制论]