# Conditions for no duality gap in quadratic programming?

Assume $Q \in \mathbb{R}^{n\times n}$, and $b,c,d \in \mathbb{R}^n$. A quadratic programming problem is:

$$\min_{x \in \mathbb{R}^{n}} \tfrac{1}{2} x^T Q x + c^T x,$$

subject to $A x \leq b, E x = d$.

I was wondering what are some sufficient and/or necessary conditions for the quadratic programming problem to have no duality gap? For example, consider cases whether or not $Q$ is symmetric and/or positive semi-definite?

Does any book or website mention about this, such as in Bazaraa's Nonlinear programming: theory and algorithms or Bertsekas's Nonlinear programming?

Thanks and regards!

-
The book "Convex Optimization" by Boyd and Vandenberghe might have something; I know it covers (at least briefly) quadratic programming and it would most certainly cover duality. However, whether or not it covers the specific cases of Q you are interested in I don't recall--it's been a while since I used it. The book is available online: stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf –  Jan Gorzny Jul 14 '11 at 17:18
You can also try this paper –  user13838 Sep 12 '11 at 21:56

First, you can assume $Q$ is symmetric, as otherwise you can convert the problem to one that does contain a symmetric matrix via $P = \frac{1}{2}(Q + Q^T)$. It's not hard to show that $P$ is symmetric and satisfies $x^T P x = x^T Q x$ for all $x$.
Vanderbei's Linear Programming: Foundations and Extensions proves that $Q$ being positive semidefinite is a sufficient condition for no duality gap. (See pp. 378-379 in the first edition.)
Added: For the nonconvex case ($Q$ is not positive semidefinite), finding useful sufficient conditions for no duality gap appears to be an ongoing research problem. For example, see "On the zero duality gap in nonconvex quadratic programming problems," by Zheng, Sun, Li, and Xu (Journal of Global Optimization, 2011, DOI: 10.1007/s10898-011-9660-y), particularly the introduction, where they give an overview of results on conditions for no duality gap, including some necessary and sufficient conditions for certain special cases of quadratic programming - but none, as far as I can tell, in the general case.