## 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 language | English (US) |
---|---|

Pages (from-to) | 1716-1736 |

Number of pages | 21 |

Journal | SIAM Journal on Optimization |

Volume | 20 |

Issue number | 4 |

DOIs | |

State | Published - Apr 29 2010 |

## Keywords

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