how to impose binarity constraint in a vector

Question

This is part of a homework problem. In an optimization problem, I need to have a K dimensional vector S, such that each entry of the vector is either 0 or 1, and $l_1$ norm of S is <= K. I can't find a way to write this in a succinct way. Any help?

Answer 1

How about $S\in\{0,1\}^K,\,\|S\|_1 \leq K$?

And, BTW, the former condition implies the latter, so you just need

$S\in\{0,1\}^K$.

Answer 2

How about:

\begin{align} \min_{x\in \Re^k}\quad& \|Wx-b\|\\ &\|x\|_1\leq K\\ &x_i^2=x_i \qquad\forall i \end{align}

This isn't convex since the equality constraint isn't linear but this shouldn't be too hard to solve. Did you specifically want convex constraints?