# In an optimization problem, why is a rank-1 constraint non-convex?

I was studying a problem in a paper in which the author tries to use the semidefinite relaxation (SDR) technique in order to solve it. 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 help me out?

• I guess you can find plenty of material out there... – AndreaCassioli Jan 2 '17 at 14:18
• I could not find, if you know materials which answer my question, please let me know. – eHH Jan 2 '17 at 14:47
• Given the fact that LinAlg's answer was not immediately clear to you, I would suggest that Boyd & Vandenberghe's book "Convex Optimization", specifically through chapter 4, would serve you well. – Michael Grant Jan 2 '17 at 16:27

The matrices $A = (-1)$ and $B=(1)$ are both rank one. However, the matrix $\lambda A + (1-\lambda)B$ with $\lambda=0.5$ does not have rank one. The set of rank one matrices is therefore not convex.
• In this example, they are $1 \times 1$ matrices, but you can easily extend the example to larger matrices. For example, take $A=I$ and $B=-I$. – LinAlg Jan 2 '17 at 19:06
• If we assume $A = I$ and $B=-I$ then the linear combination you mentioned would bring us to a zero matrix which is also rank one. I mean the matrix $\lambda A + (1-\lambda)B$ with $\lambda=0.5$ is a zero matrix which is rank one – eHH Jan 2 '17 at 19:10