Definition of Convex Sets and Common Convex Sets

Context (title): Definition of Convex Sets and Common Convex Sets

It is generally believed that if a real-world problem can be expressed as a convex optimization problem, then the problem is essentially solved. However, identifying convex optimization problems is still quite challenging. This article will first introduce the definition of convex sets and common convex sets.

Affine Sets

If a set $C\subseteq R^{n}$ is affine, it is equivalent to: for any $x_{1},x_{2}\in C$ and $\theta \in R$, we have $\theta x_{1}+(1-\theta)x_{2}\in C$, meaning that $C$ contains the linear combination of any two points in $C$ where the sum of the coefficients is 1.

Extending this to multiple points: if $\theta_{1}+\theta_{2}+...+\theta_{k}=1$, we call the 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 of all affine combinations of points in a set $C\subseteq R^{n}$ is called the affine hull of $C$:

$$\mathrm{aff}\ C=\{\theta_{1}x_{1}+...+\theta_{k}x_{k}|x_{1},...,x_{k}\in C,\theta_{1}+\theta_{2}+...+\theta_{k}=1\}$$

The affine hull is the smallest affine set containing $C$, meaning if a set $S$ satisfies $C\subseteq S$, then $\mathrm{aff}\ C\subseteq S$. The affine dimension of a set $C$ is defined as the dimension of its affine hull. For example, the dimension of a unit circle in $R^{2}$ is 1, but its affine dimension is 2 because its affine hull is the entire space $R^{2}$.

Convex Sets

If a set $C$ is convex, then 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 affine sets is that affine sets do not require $\theta\ge0$. For example, a line segment is a convex set, while a line is an affine set.

Extending to multiple dimensions, if $\theta_{1}+\theta_{2}+...+\theta_{k}=1,\theta_{i}\ge0$, then the 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 of all convex combinations of points in a set $C\subseteq R^{n}$ is called the convex hull of $C$:

$$\mathrm{conv}\ C=\{\theta_{1}x_{1}+...+\theta_{k}x_{k}|x_{1},...,x_{k}\in C,\theta_{1}+...+\theta_{k}=1,\theta_{i}\ge0\}$$

Like the affine hull, the convex hull is the smallest convex set containing $C$. Generally, if $C\in R^{n}$ is a convex set and $x$ is a random variable with $x\in C$ with probability 1, then $E\ x\in C$.

Some Important Convex Sets

Identifying convex sets is important for recognizing convex optimization problems. Here, we introduce some important convex sets.

Any affine set and subspace is a convex set. Some simple examples include the empty set $\emptyset$, single-point set $\{x_{0}\}$, the entire space $R^{n}$, lines/rays/line segments, all of which are convex.

Some other important convex sets include:

1. Hyperplanes $\{x|a^{T}x=b \}$ and half-spaces $\{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 in $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\}$, which are intersections of finitely many half-spaces and hyperplanes. A simplex is also a convex set and is a special type of polyhedron.
7. Positive semidefinite cone $S_{+}^{n}=\{X\in R^{n*n}|X=X^{T},X\succeq0\}$, which is the set of positive semidefinite symmetric matrices.