I need to prove that the convex hull of the finite set: $$S= \{x\in\{0,1\}^d|\left\Vert x \right\Vert_0\leq k\}$$ is the set: $$T=\{x\in\left[ 0,1\right]^d|\left\Vert x \right\Vert_1\leq k\}$$

Where $\left\Vert x \right\Vert_0$ is the L0 "norm" (not really a norm), meaning the number of non-zero elements of $x$, and $k$ is an integer.

I already know how to show that $conv S\subseteq T$, but have trouble with the opposite direction. I tried to describe a vector $x\in T$ as a convex combination of those of $S$ but it seemed a little complicated to me. I would appreciate your assistance.

  • $\begingroup$ If $k<1$ then $S$ is just the origin whereas $T$ has an interior. $\endgroup$
    – copper.hat
    Apr 27 '20 at 8:03
  • $\begingroup$ $k$ is an integer, added to the question description, thanks. $\endgroup$ Apr 27 '20 at 8:05

If $x \in \{0,1\}^d$ then $\|x\|_0 = \|x\|_1$. Hence $S \subset T$ and since $T$ is convex, $\operatorname{co} S \subset T$.

Suppose $x$ is an extreme point of $T$, then $x \in \{0,1\}^d$ (and $\|x\|_1 \le k$, of course). To see this, suppose $x_i \in (0,1)$ for some $i$.

If $\|x\|_1 = k$, then there is some $j \neq i$ such that $x_j \in (0,1)$ and hence $\|x+t (e_i-e_j)\|_1 = k$ for $t$ in some open interval containing zero and $x_i+t,x_j-t \in [0,1]$. Hence $x$ cannot be an extreme point.

If $\|x\|_1 < k$ then $x+t e_i \in T$ for $t$ in some open interval containing zero and hence $x$ cannot be extreme.

Hence if $x$ is extreme, then $x\in\{0,1\}^d$ and hence $\|x\|_0 = \|x\|_1 \le k$ and so $x \in S$.

Since $T$ is the convex hull of its extreme points, we see that $T \subset \operatorname{co} S$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.