# Non-convex support of a matrix

I have an optimization problem in which the variable to optimize is, among others, a matrix $$S$$. However, I have the constraint that the support of $$S$$ (i.e., where it is non-zero) is fixed (say, $$S_f$$):

$$\mbox{supp} (S)=S_f$$

$$S_f$$ is a $$N$$x$$N$$ matrix with $$1$$ or $$0$$ in the $$(i,j)$$ entry if that entry has to be considered or not in the optimization problem. That is, the optimization problem has to ''fill'' the non-zero entries in an optimal way, provided the support in which the matrix is different from $$0$$. However this constraint (should) make the optimization problem not convex, due to the support term. How can I figure the motivation behind the non-convexity ? (Both through intuition and a proof). And the term support, how is formally defined? I see that there exists the support of a function, but not relative to an element.

Thank you.

• So, $S_f$ is a set of pairs $(i,j)$ for which the $(i,j)$-th entry is nonzero? – Rodrigo de Azevedo Jan 13 at 21:52
• @RodrigodeAzevedo $S_f$ is a $N$x$N$ matrix with $1$ or $0$ in the $(i,j)$ entry if that entry has to be considered or not in the optimization problem. That is, the optimization problem has to ''fill'' the non-zero entries in an optimal way, provided the support in which the matrix is different from $0$. – Alberto Jan 13 at 21:59
• Some would call it "sparsity pattern". – Rodrigo de Azevedo Jan 13 at 22:05
• Build basis matrices of the form $e_i e_j^\top$ and write the matrix along the lines of $\sum_{i,j} x_{ij} e_i e_j^\top$. Then find the $x_{ij}$. – Rodrigo de Azevedo Jan 13 at 22:06
• So I can write as constraint $S= \sum_{i,j} x_{ij} e_i e_j^T$ ? Having the matrix with the sparsity pattern fixed, makes the set non-convex? – Alberto Jan 13 at 22:13