# Convex hull of set in $R^n$

Let's denote by $\cal{F}$ the family of all affine functions $f: \mathbb{R}^n \rightarrow\mathbb{R}$. Let $A\subset \mathbb{R}^n$.

What is a connection between the following definitions of convex hull of $A$:

$$conv_1(A)=\{\sum_{i=1}^n \alpha_i a_i: \alpha_i \in [0,1], a_i \in A, \textrm{ for } i=1,...,n; \sum_{i=1}^n \alpha_i=1, n \in \mathbb{N} \},$$

$$conv_2(A)= \bigcap_{f \in \cal{F} } \{ x\in \mathbb{R}^n : |f(x)| \leq \sup_{y \in A} |f(y)| \}.$$

Thanks.

-
Don't you need something like $\sum_i \alpha_i = 1$? –  dtldarek Mar 13 '12 at 18:27
For $conv_1(A)$, you want to add the condition $\sum_{i=1}^n \alpha_i = 1$. Also the $n$ in the definition of $conv_1$ is not the same as the $n$ in ${\mathbb R}^n$. –  Robert Israel Mar 13 '12 at 18:29
It looks like the first one (with $\sum_i \alpha_i = 1$ condition) is the convex combinations of points, which is indeed the convex hull. The second one looks like the intersection of all the affine sets containing A which is also the convex hull. So the two operators seems equal, but I am not sure (I am not that good with linear algebra). –  dtldarek Mar 13 '12 at 18:38
Sorry for mistakes. In definition of $conv_1$ sum of coefficients should be 1. Moreover affine function have values in $R$. –  Richard Mar 13 '12 at 19:46

I guess the functions in $\mathcal{F}$ should take their values in $\mathbb{R}$. In that case, the two notions coincide when $A$ is compact.

The set $conv_2(A)$ is an intersection closed halfspaces and hence a closed and convex set. For every $a\in A$ and $f\in\mathcal{F}$, $|f(a)|\leq \sup_{y\in A}|f(y)|$, so $A\subseteq conv_2(A)$.

That $conv_2(A)$ contains no point not in the closure of $A$ is a bit more involved. It follows from the separating hyperplane theorem.

-
Sorry, wrong. The absolute values mess this up. For example, for $n=1$ take $A$ to be $[0,\infty)$. Any nonconstant affine function $f$ has $\sup_{y \in A} |f(y)| = \infty$, so $conv_2(A) = \mathbb R$. –  Robert Israel Mar 13 '12 at 18:43
You are right, I need to assume that the maximum is actually achieved. –  Michael Greinecker Mar 13 '12 at 18:54
It would suffice for $A$ to be bounded. But you can't replace affine by linear unless the closed convex hull of $A$ is balanced. –  Robert Israel Mar 13 '12 at 19:22
@Michael. Thanks for answer. Could you bit more detailed about inclusion $conv_2(A) \subset conv_1(A)$? For which sets we use the separating theorem? –  Richard Mar 13 '12 at 20:10
It is a standard fact the convex-hull (according to $conv_1$) of a compact set in $\mathbb{R}^n$ is compact. We want to show that a point $z$ not in the convex hull is not in $conv_2(A)$. For this we separate a closed ball around $z$ from the convex hull with a hyperplane. This gives us an affine function $f$ increasing in the direction of $z$, so $f(z)>\sup_{y\in A}f(y)$, which shows that $z\notin conv_2(A)$. –  Michael Greinecker Mar 13 '12 at 20:24