Definition of Convex Sets and Common Convex Sets

It is commonly held that if a real-world problem can be formulated as a convex optimization problem, then the problem is in effect already solved. Recognizing a convex optimization problem, however, is still rather difficult. This article begins by introducing the definition of convex sets and some common convex sets.

Affine Sets

A set $C\subseteq R^{n}$ is affine if and only if, for any $x_{1},x_{2}\in C$ and $\theta \in R$, we have $\theta x_{1}+(1-\theta)x_{2}\in C$; that is, $C$ contains every linear combination of any two of its points whose coefficients sum to 1.

Extending this to the case of multiple points: if $\theta_{1}+\theta_{2}+...+\theta_{k}=1$, we call a point of the form $\theta_{1}x_{1}+\theta_{2}x_{2}+...+\theta_{k}x_{k}$ an affine combination of $x_{1},x_{2},...,x_{k}$. For example, the solution set of a system of linear equations $C=\{x|Ax=b\}$ is an affine set.

The set consisting of all affine combinations of points in $C\subseteq R^{n}$ is called the affine hull of $C$:

The affine hull is the smallest affine set containing $C$; that is, if a set $S$ satisfies $C\subseteq S$, then $\mathrm{aff}\ C\subseteq S$. We also define the affine dimension of a set $C$ as the dimension of its affine hull. For example, the unit circle in $R^{2}$ has dimension 1, but its affine dimension is 2, because its affine hull is the whole space $R^{2}$.

Convex Sets

A set $C$ is convex if, for any $x_{1},x_{2}\in C$ and $0\le \theta\le 1$, we have $\theta x_{1}+(1-\theta)x_{2}\in C$. The difference from an affine set is that an affine set imposes no requirement that $\theta\ge0$. For example, a line segment is a convex set, whereas a line is an affine set.

Extending to the multidimensional case, if $\theta_{1}+\theta_{2}+...+\theta_{k}=1,\theta_{i}\ge0$, then a point of the form $\theta_{1}x_{1}+\theta_{2}x_{2}+...+\theta_{k}x_{k}$ is called a convex combination of $x_{1},x_{2},...,x_{k}$.

The set consisting of all convex combinations of points in $C\subseteq R^{n}$ is called the convex hull of $C$:

As with the affine hull, the convex hull is the smallest convex set containing $C$. More generally, let $C\in R^{n}$ be a convex set, let $x$ be a random variable, and suppose $x\in C$ with probability 1; then $E\ x\in C$.

Some Important Convex Sets

Recognizing convex sets is fairly important for identifying convex optimization problems. Here we introduce some of the more important convex sets.

Any affine set or subspace is convex. Some of the simpler ones, such as the empty set $\emptyset$, a singleton set $\{x_{0}\}$, the whole space $R^{n}$, and lines/rays/line segments, are all convex.

Some other important convex sets are as follows:

1. Hyperplanes $\{x|a^{T}x=b \}$ and halfspaces $\{x|a^{T}x\le b\}$
2. Euclidean balls $B(x_{c},r)=\{x|\ ||x-x_{c}||_{2}\le r\}$
3. Ellipsoids $\xi=\{x|(x-x_{c})^{T}P^{-1}(x-x_{c})\le1\}$
4. Norm balls $\{x|\ ||x-x_{c}||\le r\}$, where $||\cdot||$ is a norm on $R^{n}$
5. Norm cones $C=\{(x,t)|\ ||x||\le t\}\subseteq R^{n+1}$
6. Polyhedra $P=\{x|a_{j}^{T}\le b_{j},j=1,...,m,c_{j}^{T}x=d_{j},j=1,...,p\}$, i.e., the intersection of a finite number of halfspaces and hyperplanes; a simplex is also a convex set and is a special kind of polyhedron
7. The positive semidefinite cone $S_{+}^{n}=\{X\in R^{n*n}|X=X^{T},X\succeq0\}$, i.e., the set of positive semidefinite symmetric matrices