0
$\begingroup$

I have an optimization problem with a weird constraint as follows. Is it possible to express it in some ways that have convex properties:

matrix $\mathbf{X}$ is either

$[1 \ 0 \ 0 \ 0 \ 0\\ \ 0 \ 0 \ 0 \ 0 \ 0\\ \ 0 \ 0 \ 0 \ 0 \ 0]$

or

$[0 \ 1 \ 0 \ 1 \ 0\\ \ 0 \ 0 \ 0 \ 0 \ 0\\ \ 0 \ 0 \ 0 \ 0 \ 0]$

Or is it possible to expressed some constraint that for a $3\times 1$ vector, it can have either two zeros or three zeros? Thanks

Improve this question
$\endgroup$
3
  • $\begingroup$ Such a constraint cannot be convex (otherwise you'd have to admit "two-and-a-half zeros"). You could introduce a convex relaxation, which often (but not always) leads to the desired property of the solution. $\endgroup$
    – Christian Clason
    Commented Jul 4, 2016 at 14:32
  • $\begingroup$ what convex relaxation technique can i use? Any references? Thanks $\endgroup$
    – Michael Fan Zhang
    Commented Jul 5, 2016 at 1:07
  • $\begingroup$ You write $X=t A + (1-t)B$, where $A$ and $B$ are the two matrices you list. What you wish to do is to do minimize over $t\in \{0,1\}$, which is non-convex. Convex relaxation would be to minimize over $t\in[0,1]$ instead and hope that the optimal value is either $0$ or $1$ (which it often is, but this depends on the rest of the problem). $\endgroup$
    – Christian Clason
    Commented Jul 5, 2016 at 6:37

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .