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
    Jul 4, 2016 at 14:32
  • $\begingroup$ what convex relaxation technique can i use? Any references? Thanks $\endgroup$
    – Michael Fan Zhang
    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
    Jul 5, 2016 at 6:37

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.