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
1  
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

 
discard

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

Browse other questions tagged or ask your own question.