Optimization Online


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

Ke Hou(khou***at***se.cuhk.edu.hk)
Anthony Man-Cho So(manchoso***at***se.cuhk.edu.hk)

Abstract: In this paper, we establish hardness and approximation results for various $L_p$-ball constrained homogeneous polynomial optimization problems, where $p \in [2,\infty]$. Specifically, we prove that for any given $d \ge 3$ and $p \in [2,\infty]$, 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\left( (\log n)^{(d-2)/p} \big/ n^{d/2-1} \right)$ 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( (\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 \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.

Keywords: Polynomial Optimization; Approximation Algorithms; Diameters of Convex Bodies; Convex Programming

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Working paper, Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, NT, Hong Kong, October 2012.

Download: [PDF]

Entry Submitted: 10/31/2012
Entry Accepted: 10/31/2012
Entry Last Modified: 10/31/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society