A semidefinite relaxation scheme for multivariate quartic polynomial optimization with quadratic constraints

Zhi Quan Luo, Shuzhong Zhang

Research output: Contribution to journalArticlepeer-review

38 Scopus citations

Abstract

We present a general semidefinite relaxation scheme for general n-variate quartic polynomial optimization under homogeneous quadratic constraints. Unlike the existing sum-ofsquares approach which relaxes the quartic optimization problems to a sequence of (typically large) linear semidefinite programs (SDP), our relaxation scheme leads to a (possibly nonconvex) quadratic optimization problem with linear constraints over the semidefinite matrix cone in R n×n. It is shown that each α-factor approximate solution of the relaxed quadratic SDP can be used to generate in randomized polynomial time an O(α)-factor approximate solution for the original quartic optimization problem, where the constant in O(-) depends only on problem dimension. In the case where only one positive definite quadratic constraint is present in the quartic optimization problem, we present a randomized polynomial time approximation algorithm which can provide a guaranteed relative approximation ratio of (1 - O(n-2)).

Original languageEnglish (US)
Pages (from-to)1716-1736
Number of pages21
JournalSIAM Journal on Optimization
Volume20
Issue number4
DOIs
StatePublished - Apr 29 2010

Keywords

  • Approximation ratio
  • Quartic optimization
  • Randomized solution
  • Semidefinite programs relaxation

Fingerprint Dive into the research topics of 'A semidefinite relaxation scheme for multivariate quartic polynomial optimization with quadratic constraints'. Together they form a unique fingerprint.

Cite this