Hardness and Approximation Results for Lp-Ball Constrained Homogeneous Polynomial Optimization Problems

• 成果类型: Article
• 署名作者: Hou, Ke; So, Anthony Man-Cho
• 署名单位: Chinese University of Hong Kong; Chinese University of Hong Kong
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2014.0644
• 发表日期: 2014
• 页码: 1084-1108
• 关键词: bi-quadratic optimization; biquadratic optimization; semidefinite; NORM

摘要

In this paper, we establish hardness and approximation results for various L-p-ball constrained homogeneous polynomial optimization problems, where p is an element of [2,infinity]. Specifically, we prove that for any given d >= 3 and p is an element of [2,infinity], both the problem of optimizing a degree-d homogeneous polynomial over the L-p-ball and the problem of optimizing a degree-d multilinear form (regardless of its super-symmetry) over L-p-balls are NP-hard. On the other hand, we show that these problems can be approximated to within a factor of Omega((logn)((d-2)/P)/n(d/2-1)) in deterministic polynomial time, where n is the number of variables. We further show that with the help of randomization, the approximation guarantee can be improved to Omega((logn/n)(d/2-1)), which is independent of p and is currently the best for the aforementioned problems. Our results unify and generalize those in the literature, which focus either on the quadratic case or the case where p is an element of [2,infinity]. We believe that the wide array of tools used in this paper will have further applications in the study of polynomial optimization problems.