Skip to main content
2 of 3
edited title
Gerald Edgar
  • 41.1k
  • 5
  • 125
  • 219

Reference Request (semidefinite relaxation)

Considering the semidefinite relaxation technique where a quadratic program is relaxed by the full-rank semidefinite programming, 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.

mikitov
  • 342
  • 3
  • 14