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

1 Answer 1

8
$\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.

$\endgroup$
8
  • 1
    $\begingroup$ how this answers my question ? $\endgroup$
    – eHH
    Commented Jan 2, 2017 at 14:45
  • $\begingroup$ A constraint is convex only if the set of matrices that satisfy the constraint is convex. $\endgroup$
    – LinAlg
    Commented Jan 2, 2017 at 15:10
  • $\begingroup$ Are A and B matrices or scalars? $\endgroup$
    – eHH
    Commented Jan 2, 2017 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
    Commented Jan 2, 2017 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
    Commented Jan 2, 2017 at 19:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .