8
$\begingroup$

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!

  • 0
    You can also try [this paper](http://www.springerlink.com/content/k4077h6x06830415/)2011-09-12

1 Answers 1

6

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.

  • 0
    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.2011-09-13