Hardness and Approximation Results for <i>L_p</i>-Ball Constrained Homogeneous Polynomial Optimization Problems

Abstract

In this paper, we establish hardness and approximation results for various L p -ball constrained homogeneous polynomial optimization problems, where p ∈ [2, ∞]. Specifically, we prove that for any given d ≥ 3 and p ∈ [2, ∞], 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 Ω((log n) (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 Ω((log n/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 ∈ {2, ∞}. We believe that the wide array of tools used in this paper will have further applications in the study of polynomial optimization problems.