Convex and conic hull

Convex hull of a finite set of points

The convex hull of a set of points $\{x_1,\dots ,x_m\}$ is defined as the set

$$\text{{bf Co}}(x_1,\dots ,x_m):=\{\sum _{i=1}^m{\lambda }_i{x}_i:{\lambda }_i\ge 0,i=1,\dots ,m,\sum _{i=1}^m{\lambda }_i=1\}.$$

By definition, this set is convex. Note the analogy with the notion of span of a collection of vectors. Here also, we consider combinations of vectors ${\sum }_{i=1}^m{\lambda }_i{x}_i$, but we restrict the weights $\lambda$ to be non-negative and sum to one.

Example: Convex hull generated by six points in $R^2$. Note that one of the points is in the interior of the convex hull, so that the same convex hull is generated with the remaining five points.

>> inds = convhull(x,y);
>> plot(x,y);

Example: Convex hull of the unit basis vectors $e_1,e_2,e_3$ in $R^3$. This is the set $$\text{{bf Co}}(e_1,e_2,e_3)=\{{\lambda }_1{e}_1+{\lambda }_2{e}_2+{\lambda }_3{e}_3:{\lambda }_i\ge 0,i=1,2,3,{\lambda }_1+{\lambda }_2+{\lambda }_3=1\}.$$ By definition, the vector ${\lambda }_1{e}_1+{\lambda }_2{e}_2+{\lambda }_3{e}_3$ is the vector in $R^3$ with components $({\lambda }_1,{\lambda }_2,{\lambda }_3)$. Hence, the set above is the set of vectors in $R^3$ with non-negative components which sum to one: $$\text{{bf Co}}(e_1,e_2,e_3)=\{\lambda \in R^3:\lambda \ge 0,1^T\lambda =1\},$$ where the component-wise inequality notation $\lambda \ge 0$ expresses the fact that the vector $\lambda$ has non-negative components, and $1$ stands for the vector of ones. This set is called the probability simplex.

Convex hull of a set

More generally, for any given set $C$ in $R^n$, we can define its convex hull as the set of convex combinations of any finite collection of points contained in it.

Example: The convex hull of the union of two ellipses.

Conic hull

The conic hull of a set of points $\{x_1,\dots ,x_m\}$ is defined as

$$\{\sum _{i=1}^m{\lambda }_i{x}_i:\lambda \in R_{+}^m\}.$$

Example: The conic hull of the union of the three-dimensional simplex above and the singleton $\left\{0\right\}$ is the whole set $R_{+}^3$, which is the set of real vectors that have non-negative components. The figure shows that indeed any vector $v\in R_{+}^3$ can be obtained by a positive scaling of a vector $v_n$ in the three-dimensional simplex: $v_n=\alpha v$, with $\alpha :=v_1+v_2+v_3\ge 0$.