4
$\begingroup$

Define two sets:

  • $A = \{x \in \{0,1\}^n : \lVert x \rVert_1 \leq k\}$ is a finite set of binary vectors;
  • $B = \{x \in [0,1]^n : \lVert x \rVert_1 \leq k\}$ is an infinite set of real-valued vectors, whose elements are between $0$ and $1$;

where $0 \leq k \leq n$, $k$ is an integer and $\lVert x \rVert_1$ denotes the $l_1$ norm: $\lVert x \rVert_1 = \sum_{i=1}^{n} \lvert x_i \rvert$.

I believe $B$ is the convex hull of $A$ ($conv(A)$), but cannot prove it. It is easy to show $conv(A) \subseteq B$. I'm stuck at the reverse direction. I'm thinking of using induction proof: assume it holds for $0 \leq k < n$, prove that it also holds for $k+1$; but I haven't succeeded.

  • 0
    @hassan: I just edited my question to add that $k$ is an integer.2012-06-05

3 Answers 3

0

It is true that $\mathbb{co} A = B$, but the proof is a little tedious.

Since $A \subset B$, it is clear that $\mathbb{co} A \subset B$. The other direction requires a little more work:

Both $A$ and $B$ are closed bounded sets, hence compact. $B$ is convex. The convex hull $\mathbb{co} A$ is closed and compact (follows from compactness and Carathéodory's theorem).

Let $E$ be the set of extreme points of $B$. The basic idea is to show that $E \subset A$. Since the Krein-Milman theorem tells us that $B = \overline{\mathbb{co}} E$, it then will follow that $B \subset \mathbb{co} A$.

To characterize the extreme points, I need some notation and a lemma.

Let $C = \{ x \in \mathbb{R}^n | \; g_i (x) \leq 0, \; \forall i \in I \}$, where each $g_i$ has the form $g_i(x) = \langle \gamma_i, x \rangle - \beta_i$. (Note that $B$ has this form.) Define the 'active index set' $I_{x_0} = \{ i \in I | g_i(x_0) = 0 \}$.

Lemma: $x_0$ is an extreme point of $C$ iff $x_0 \in C$ and $\mathbb{sp} \{ \gamma_i \}_{i \in I_{x_0}} = \mathbb{R}^n$.

Proof: ($\implies$): Suppose $x_0$ is an extreme point of $C$, but $\mathbb{sp} \{ \gamma_i \}_{i \in I_{x_0}} \neq \mathbb{R}^n$. Then choose a non-zero $h \in \mathbb{sp} \{ \gamma_i \}_{i \in I_{x_0}}^{\bot}$. Furthermore note that if $ i \notin I_{x_0}$, then there exists a neighborhood $U$ of $x_0$ such that $i \notin I_x$, forall $x \in U$. Now consider the points $x_0 + \lambda h$, and observe that for $\lambda$ small enough, $x_0 \pm\lambda h \in C$ (since all constraints are satisfied). We can write $x_0 = \frac{1}{2} ( (x_0+\lambda h) + (x_0-\lambda h))$ which contradicts the fact that $x_0$ is extreme.

($\impliedby$): Now suppose $x_0 \in C$ and $\mathbb{sp} \{ \gamma_i \}_{i \in I_{x_0}} = \mathbb{R}^n$. Suppose $x_0 = \lambda x + (1-\lambda) y$, with $x,y \in C$, and $\lambda \in (0,1)$. Let $i \in I_{x_0}$, then $g_i(x_0) = \lambda g_i(x) + (1-\lambda) g_i(y) = 0$. It follows that $g_i(x) = g_i(y) = 0$, from which we have $\langle \gamma_i, x_0 \rangle = \langle \gamma_i, x \rangle = \langle \gamma_i, y \rangle$, for all $i \in I_{x_0}$. However, this implies that $x_0-x$ and $x_0-y$ lie in the complement of $\mathbb{sp} \{ \gamma_i \}_{i \in I_{x_0}}$, which is $\{ 0 \}$ by assumption. Hence $x = y = x_0$. It follows that $x_0$ is extreme.

Now back to the set $B$. Let $x$ be an extreme point of $B$. $B$ is defined by $2n+1$ constraints, however of the $2n$ constraints $x_i \in [0,1]$, at most $n$ can be active. Hence at most $n+1$ constraints can be active (and any $n$ of these are linearly independent).

There are two possibilities: (1) $x_1+...+x_n = k$. In this case, $n-1$ of the other constraints must be active (ie, $x_i$ is either $0$ or $1$ for $n-1$ indices $i$). Since $k$ is an integer, it then follows that the remaining $x_i$ must also be $0$ or $1$. Thus $x = \sum_{j \in J} e_j$, where $|J| = k$. (2) $x_1+...+x_n < k$. In this case all of the $x_i$ must be either $0$ or $1$ (at most $k-1$ can be $1$, of course). This gives $x = \sum_{j \in J} e_j$, where $|J| < k$.

This characterizes the extreme points of $B$ as having the form $x = \sum_{j \in J} e_j$, where $|J| \leq k$, and it a straightforward observation to note that all such $x$ satisfy $x \in A$. Hence we have the desired result.

0

$B = B_1 \cup B_2$

where

$B_1 = \{x \in [0,1]^n : \lVert x \rVert_1 = k\}$

and

$B_2 = \{x \in [0,1]^n : \lVert x \rVert_1 < k\}$

Let $x \in B$

Cas 1: $x \in B_1$ lets write x in its cartesien representation ($(e_i)i$ is the trivial base of the orthonormal space $\mathbb{R}^n$ and $(x_i)i$ the cordianates of x in this base)

$x=\sum_{k=1}^{n}{x_i.ei}$

$x=\sum_{k=1}^{n}{\frac{x_i}{k}*k.ei}$

we have all the vectors $k.e_i \in A$

and we have $\sum_{k=1}^{n}\frac{x_i}{k}=1$ and all $\frac{x_i}{k} \geq 0$

so $x \in conv(A)$

$B_1 \subset conv(A)$

Cas 2: $x \in B_2$

suppose $x\neq O$

if we can find y such that $x=\lambda.y+(1-\lambda).O = \lambda.y$ and $y \in B_1$ and $\lambda \in [0,1]$. then we can conclude that $x \in conv(A)$

that $y$ is $y=\frac{k}{\lVert x \rVert_1}x$ and $\lambda = \frac{\lVert x \rVert_1}{k}$ $B_2 \subset conv(A)$

then $B \subset conv(A)$

to summerize

  1. B is convex (its the intersection of Ball (O,k) and the positive Orthant, both convex sets)
  2. $conv(A)$ is the smallest convex that contain A
  3. $A \subset B$
  4. $B \subset conv(A)$

we can conclude that $B = conv(A)$

  • 0
    OK i miss some details befor, if $k\geq n$ this is not true, and it maybe not true for more cases .2012-06-06
0

I think there are probably a variety of proofs with lengths depending on the amount of polyhedral theory you want to invoke. Here is one method: show that all extreme points of $B$ are in $A$. This suffices by compactness of $B$.

Let $x$ be an extreme point of $B$. The set $B$ is defined by $2n + 1$ linear inequalities: $0\leq x_i\leq 1$ and $\sum x_i \leq k$. At an extreme point $n$ of these constraints must be tight (hold with equality). For each $x_i$ at most one of the bound constraints $0\leq x_i$ or $x_i\leq 1$ can be tight.

Suppose $x\not\in A$. There is some $j$ without a tight bound constraint: $x_j\in (0,1)$. Given that, the only way to have $n$ inequalities tight at $x$ is to have $\sum x_i = k$ and also have each $x_i$ with $i\neq j$ satisfy some bound constraint. But then $x_j = k - \sum_{i\neq j} x_i$ is an integer, a contradiction.

  • 0
    true, Bk is Bn in this case2012-06-06