Semidefinite relaxation

1

Hello all,

I was studying a problem in a paper in which the author tries to use the semidefinite relaxation (SDR) technique in order to solve the problem. After changing the original problem using the SDR technique, a rank-1 constraint is added to the problem. The author states that this constraint is non-convex, and it should be relaxed. I do not know why the rank-1 constraint is a non-convex constraint. Could someone explain to me in details?

2

A matrix, M, is rank one if and only if it is an outer product of a vector, x, with itself. So a rank one constraint is of the form M == x*x' . That s non-convex.

Perhaps you should study Boyd and Vandenberghe "Convex Optimization " http://web.stanford.edu/~boyd/cvxbook/ to better prepare you to read research papers.