Convex and conic hull

Convex hull of a finite set of points

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

 mbox{{bf Co}} (x_1,ldots,x_m) := left{ sum_{i=1}^m lambda_i x_i ~:~ lambda_i ge 0, ;; i=1,ldots,m, ;; sum_{i=1}^m lambda_i = 1 right}.

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.

alt text 

Example: Convex hull generated by six points in mathbf{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.

Matlab syntax to plot the convex hull (for n=2)
>> inds = convhull(x,y);
>> plot(x,y);
alt text 

Example: Convex hull of the unit basis vectors e_1,e_2,e_3 in mathbf{R}^3. This is the set

 mbox{{bf Co}} (e_1,e_2,e_3)  = left{  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 right} .

By definition, the vector lambda_1 e_1 + lambda_2 e_2 + lambda_3 e_3 is the vector in mathbf{R}^3 with components (lambda_1,lambda_2,lambda_3). Hence, the set above is the set of vectors in mathbf{R}^3 with non-negative components which sum to one:

 mbox{{bf Co}} (e_1,e_2,e_3)  = left{ lambda in mathbf{R}^3 ~:~ lambda ge 0, ;; mathbf{1}^T lambda = 1 right},

where the component-wise inequality notation lambda ge 0 expresses the fact that the vector lambda has non-negative components, and mathbf{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 mathbf{C} in mathbf{R}^n, we can define its convex hull as the set of convex combinations of any finite collection of points contained in it.

alt text 

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

Conic hull

The conic hull of a set of points { x_1,ldots,x_m} is defined as

 left{ sum_{i=1}^m lambda_i x_i ~:~ lambda in mathbf{R}^m_+right}.

Example: The conic hull of the union of the three-dimensional simplex above and the singleton {mathbf{0}} is the whole set mathbf{R}^3_+, which is the set of real vectors that have non-negative components. The figure shows that indeed any vector v in mathbf{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.