Optimization Models
Home
Software
Links
Index
Contact
1. Introduction
1.1. Overview
1.2. Optimization Models
2. Linear Algebra
2.1. Vectors
2.2. Matrices
2.3. Linear Equations
2.4.  Least-Squares
2.5. Eigenvalues
2.6  Singular Values
3. Convex Models
3.1. Convexity
3.2. LP and QP
3.3. SOCP
3.4. Robust LP
3.5. GP
3.6. SDP
3.7. Non-Convex Models
4. Duality
4.1. Weak Duality
4.2. Strong Duality
4.3.  Applications
5. Case Studies
5.1. Senate Voting
5.2. Antenna Arrays
5.3. Localization
5.4. Circuit Design

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\).