Consider the primary optimization problem

$$\begin{array}{ll} \text{minimize} & f_0(c,C)\\ \text{subject to} & C = cc^T\end{array}$$

at this paper. $c$ can only take discrete values, except zero. In equation $(9)$, the author wrote that the constraint is not convex. How can I prove the non-convexity of this equality constraint?


Suppose $c \neq 0$ and $C=cc^T$. Then $C = (-c)(-c)^T$ and so $(C,c), (C,-c)$ are feasible. However the average $(C , 0)$ is not feasible, hence the feasible set is not convex.


Saying "the constraint is convex" means that if the constraint is satisfied at two points, the constraint has to be satisfied at any convex combination of those points. In particular, it must be satisfied at the midpoint of those two points. Now, this constraint is satisfied at $c=\begin{pmatrix}1\\0\end{pmatrix},C=\begin{pmatrix}1&0\\0&0\end{pmatrix}$ and at $c=\begin{pmatrix}-1\\0\end{pmatrix},C=\begin{pmatrix}1&0\\0&0\end{pmatrix}$, but not at the midpoint $c=\begin{pmatrix}0\\0\end{pmatrix},C=\begin{pmatrix}1&0\\0&0\end{pmatrix}$, so it isn't convex.