0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So, $S_f$ is a set of pairs $(i,j)$ for which the $(i,j)$-th entry is nonzero? $\endgroup$ – Rodrigo de Azevedo Jan 13 at 21:52
  • $\begingroup$ @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$. $\endgroup$ – Alberto Jan 13 at 21:59
  • $\begingroup$ Some would call it "sparsity pattern". $\endgroup$ – Rodrigo de Azevedo Jan 13 at 22:05
  • $\begingroup$ 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}$. $\endgroup$ – Rodrigo de Azevedo Jan 13 at 22:06
  • $\begingroup$ 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? $\endgroup$ – Alberto Jan 13 at 22:13

Your Answer

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

Browse other questions tagged or ask your own question.