MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Considering the semidefinite relaxation technique where a quadratic program is relaxed by the full-rank semidefinite programming. This is, $x^TQx$ now reads as Tr$(XQ)$ without any rank constraint in $X$ but assuming that is semidefinite positive.

I would like to have some results regarding the quality of the aproximation.

It is clear that when the obtained matrix is rank-one, the optimal solution corresponds to the semidefinite relaxation one, but, Can we say anything about the non-rank-one solutions?

Furthermore, considering a $2 \times 2$ matrix it is not the same to have a $(1,0.2)$ , $(1,0.001)$ or $(1,0)$ eigen-decomposition. Is there any metric which provides an idea of how 'rank-one' is a matrix?

Thank you in advance.

share|cite|improve this question
Please write out the question formally and more precisely. As it is currently written, it is not really clear which "quadratic program" is meant (maybe it means that $x^TQx=\trace(QX)$, where $X \succeq 0$ by throwing away the rank constraint, but a more precise specification is needed).... – Suvrit Sep 10 '12 at 19:44
Ok, I done it. Thank you. – mikitov Sep 11 '12 at 18:27
What is exactly your quadratic program? Do you have linear constraints? And how do you relax them? – Markus Schweighofer Oct 16 '12 at 21:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.