# Prove one set is a convex hull of another set

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.

-
its true if k is integer –  Hassan Jun 5 '12 at 2:11
@hassan: I just edited my question to add that $k$ is an integer. –  Truong Jun 5 '12 at 2:14

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.

-
I also believe that I must use polyhedral theory, specifically extreme points. I have been thinking along the same line, but haven't got a proof. Thanks. –  Truong Jun 6 '12 at 14:06
hi Noah, could you please give more details and references, i don't know about the background you used –  Hassan Jun 6 '12 at 14:42
@hassan: My favorite reference for this material is Bertsimas + Tsitsiklis' book "Introduction to Linear Optimization". The relevant portion for the results used in this answer is Section 2.2, which shows the equivalence of various geometric and algebraic notions of extreme points in polyhedra defined by explicit linear inequalities. –  Noah Stein Jun 6 '12 at 14:51
thanks Noah, i think that the porposition is false if k>=n –  Hassan Jun 6 '12 at 14:58
@hassan: Why? In this case $\sum x_i \leq k$ cannot be tight, so that case is irrelevant, but this just means each $x_i$ has a tight bound constraint. –  Noah Stein Jun 6 '12 at 15:13

$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)$$

-
Incorrect because $k e_i$ is not in $A$. Recall that vectors in $A$ are binary vectors, i.e. elements are only 0 or 1. –  Truong Jun 6 '12 at 14:05
that's true, how could we change it ? i ll check –  Hassan Jun 6 '12 at 14:40
OK i miss some details befor, if $k\geq n$ this is not true, and it maybe not true for more cases . –  Hassan Jun 6 '12 at 14:45

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.

-