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

preprint2012arXivOpen access

Abstract

In this paper, we establish hardness and approximation results for various LpL_p-ball constrained homogeneous polynomial optimization problems, where p∈[2,∞]p \in [2,\infty]. Specifically, we prove that for any given d≥3d \ge 3 and p∈[2,∞]p \in [2,\infty], both the problem of optimizing a degree-dd homogeneous polynomial over the LpL_p-ball and the problem of optimizing a degree-dd multilinear form (regardless of its super-symmetry) over LpL_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/nd/2−1)Ω((\log n)^{(d-2)/p} \big/ n^{d/2-1}) in deterministic polynomial time, where nn 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)Ω((\log n/n)^{d/2-1}), which is independent of pp 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,∞p \in {2,\infty}. We believe that the wide array of tools used in this paper will have further applications in the study of polynomial optimization problems.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.