4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I guess you can find plenty of material out there... $\endgroup$ – AndreaCassioli Jan 2 '17 at 14:18
  • $\begingroup$ I could not find, if you know materials which answer my question, please let me know. $\endgroup$ – eHH Jan 2 '17 at 14:47
  • $\begingroup$ 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. $\endgroup$ – Michael Grant Jan 2 '17 at 16:27
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ how this answers my question ? $\endgroup$ – eHH Jan 2 '17 at 14:45
  • $\begingroup$ A constraint is convex only if the set of matrices that satisfy the constraint is convex. $\endgroup$ – LinAlg Jan 2 '17 at 15:10
  • $\begingroup$ Are A and B matrices or scalars? $\endgroup$ – eHH Jan 2 '17 at 18:57
  • $\begingroup$ 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$. $\endgroup$ – LinAlg Jan 2 '17 at 19:06
  • $\begingroup$ 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 $\endgroup$ – eHH Jan 2 '17 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.