In this paper we study the relationship between the optimal value of a homogeneous quadratic optimization problem and that of its Semidefinite Programming (SDP) relaxation. We consider two quadratic optimization models: (1) $\min \{ x^* C x \mid x^* A_k x \ge 1, x\in\mathbb{ F}^n, k=0,1,...,m\}$; and (2) $\max \{ x^* C x \mid x^* A_k x \le 1, x\in\mathbb{ F}^n, k=0,1,...,m\}$. If \emph{ one} of $A_k$'s is indefinite while others and $C$ are positive semidefinite, we prove that the ratio between the optimal value of (1) and its SDP relaxation is upper bounded by $O(m^2)$ when $\mathbb{ F}$ is the real line $\mathbb{ R}$, and by $O(m)$ when $\mathbb{ F}$ is the complex plane $\mathbb{ C}$. This result is an extension of the recent work of Luo { \em et al.} \cite{ LSTZ}. For (2), we show that the same ratio is bounded from below by $O(1/\log m)$ for both the real and complex case, whenever all but one of $A_k$'s are positive semidefinite while $C$ can be indefinite. This result improves the so-called approximate S-Lemma of Ben-Tal { \em et al.} \cite{ BNR02}. We also consider (2) with multiple indefinite quadratic constraints and derive a general bound in terms of the problem data and the SDP solution. Throughout the paper, we present examples showing that all of our results are essentially tight.

Categories: math.OC math.NA

Semidefnite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization