Approximation algorithms for quadratic programming

Minyue Fu, Zhi-Quan Luo and Yinyu Ye

We consider the problem of approximating the global minimum of a general quadratic program (QP) with $n$ variables subject to $m$ ellipsoidal constraints. For $m=1$, we rigorously show that an $\epsilon$-minimizer, where error $\epsilon\in (0,1)$, can be obtained in polynomial time, meaning that the number of arithmetic operations is a polynomial in $n$, $m$, and $\log(1/\epsilon)$. For $m\ge 2$, we present a polynomial-time $(1-\frac{1}{m^2})$-approximation algorithm as well as a semidefinite programming relaxation for this problem. In addition, we present approximation algorithms for solving QP under the box constraints and the assignment polytope constraints.

Manuscript, Department of Electrical and Computer Engineering, McMaster University, Hamilton, Ontario, CANADA L8S 4K1