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!

  • $\begingroup$ 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 $\endgroup$
    – Jan Gorzny
    Jul 14 '11 at 17:18
  • $\begingroup$ You can also try this paper $\endgroup$
    – 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.)

Bazaraa, Sherali, and Shetty's Nonlinear Programming: Theory and Algorithms shows that, for general nonlinear programming, the existence of a saddle point for the Lagrangian function is a necessary and sufficient condition for no duality gap. (See Theorem 6.2.5, pp. 269-270, third edition.) So obviously that gives a necessary and sufficient condition for quadratic programming as well. Perhaps there's a way to simplify the theorem about a saddle point to the special case of quadratic programming, but I don't see how to do it right now. (Added: There doesn't seem to be a known useful way to do that. See next paragraph.)

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.

  • $\begingroup$ Thanks for keeping this thread up! It may take me a while to glance/read the literatures you mentioned. I may accept your answer later. $\endgroup$
    – Tim
    Sep 13 '11 at 22:37
  • $\begingroup$ @Tim: The question is so old that I wasn't sure you were interested in it anymore. Thanks for letting me know that you still are. $\endgroup$ Sep 13 '11 at 22:46
  • $\begingroup$ Although I admit I am engaged in different things at different time and may not be able to come back immediately, I am always interested in my previous questions (I have asked a lot actually, and the upvote was given by me immediately when you posted your answer). It has recorded my learning journey, and I wouldn't want to separate my past from my present. $\endgroup$
    – Tim
    Sep 13 '11 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.