9.3. Convex Subsets of ${\mathbb{R}}^n$

This section focuses on important convex subsets of ${\mathbb{R}}^n$.

Definition 9.14 (Nonnegative orthant)

The nonnegative orthant denoted by ${\mathbb{R}}_{+}^n$ is defined as:

$${\mathbb{R}}_{+}^n\triangleq \{\mathbf{x}\in {\mathbb{R}}^n|x_i\ge 0,i=1,\dots ,n\}=\{\mathbf{x}\in {\mathbb{R}}^n\Vert x⪰\mathbf{0}\}.$$

Definition 9.15 (Positive orthant)

The positive orthant denoted by ${\mathbb{R}}_{++}^n$ is defined as:

$${\mathbb{R}}_{++}^N\triangleq \{\mathbf{x}\in {\mathbb{R}}^n|x_i>0,i=1,\dots ,n\}=\{\mathbf{x}\in {\mathbb{R}}^n\Vert x\mathrm{succ}\mathbf{0}\}.$$

9.3.1. Simplex

Recall from Definition 9.11 that a simplex is the convex hull of a finite collection of affine independent points. Points, line segments, triangles and tetrahedrons are common examples of simplices in ${\mathbb{R}}^n$. Here, we describe simplices in ${\mathbb{R}}^n$ further.

A simplex has vertices, edges and faces. The faces of a simplex don’t have any curvature.

Definition 9.16 (Regular simplex)

A regular simplex is the set of nonnegative vectors with elements summing up to $a$.

$${\mathrm{\Delta }}_n^a\triangleq \{\mathbf{x}\in {\mathbb{R}}^n|⟨\mathbf{x},\mathbf{1}⟩=a,\mathbf{x}⪰\mathbf{0}\}.$$

Definition 9.17 (Unit simplex)

A unit simplex is the set of nonnegative vectors with elements summing up to $1$.

$${\mathrm{\Delta }}_n\triangleq \{\mathbf{x}\in {\mathbb{R}}^n|⟨\mathbf{x},\mathbf{1}⟩=1,\mathbf{x}⪰\mathbf{0}\}.$$

9.3.2. Polyhedra

Definition 9.18 (Polyhedron)

A polyhedron is defined as the solution set of a finite number of linear inequalities and linear equations.

$$P=\{\mathbf{x}|⟨{\mathbf{a}}_j,\mathbf{x}⟩\le b_j,j=1,\dots ,m,⟨{\mathbf{c}}_k,\mathbf{x}⟩=d_k,k=1,\dots ,p\}$$

A polyhedron thus is the intersection of a finite number of halfspaces ($m$) and hyperplanes ($p$).

Example 9.8 (Polyhedra)

• Affine sets ( subspaces, hyperplanes, lines)

• Rays

• Line segments

• Halfspaces

Theorem 9.43

A polyhedron is a convex set.

Proof. Intersection of convex sets is convex.

Polyhedra are considerably better behaved convex sets than others (like norm balls or ellipsoids) because of their lack of curvature.

We can combine the set of inequalities and equalities in the form of linear matrix inequalities and equalities.

$$P=\{\mathbf{x}|\mathbf{A}\mathbf{x}⪯\mathbf{b},\mathbf{C}\mathbf{x}=\mathbf{d}\}$$

where

$$\begin{array}{rl}& \mathbf{A}=\left[\begin{array}{c}{\mathbf{a}}_1^T\\ ⋮\\ {\mathbf{a}}_m^T\end{array}\right],\mathbf{b}=\left[\begin{array}{c}{b}_1\\ ⋮\\ b_m\end{array}\right]\\ & \mathbf{C}=\left[\begin{array}{c}{\mathbf{c}}_1^T\\ ⋮\\ {\mathbf{c}}_p^T\end{array}\right],\mathbf{d}=\left[\begin{array}{c}{d}_1\\ ⋮\\ d_p\end{array}\right]\end{array}$$

and the symbol $⪯$ means vector inequality or component wise inequality in ${\mathbb{R}}^m$ i.e. $\mathbf{u}⪯\mathbf{v}$ means $u_i\le v_i$ for $i=1,\dots ,m$.

Note that $\mathbf{b}\in {\mathbb{R}}^m$, $\mathbf{A}\in {\mathbb{R}}^{m\times n}$, $\mathbf{A}\mathbf{x}\in {\mathbb{R}}^m$, $\mathbf{d}\in {\mathbb{R}}^p$, $\mathbf{C}\in {\mathbb{R}}^{p\times n}$ and $\mathbf{C}\mathbf{x}\in {\mathbb{R}}^p$.

Example 9.9 (Set of nonnegative numbers)

Let ${\mathbb{R}}_{+}=\{x\in \mathbb{R}|x\ge 0\}$. ${\mathbb{R}}_{+}$ is a polyhedron (a solution set of a single linear inequality). Hence, it is a convex set. Moreover, it is a ray and a convex cone.

Example 9.10 (Nonnegative orthant)

The nonnegative orthant ${\mathbb{R}}_{+}^n$ is a polyhedron (solution set of $n$ linear inequalities). It is also a convex cone.

9.3.3. Polytopes

Definition 9.19 (Polytope)

A bounded polyhedron is known as a polytope.

Theorem 9.44

A nonempty set $C$ of ${\mathbb{R}}^n$ is a (convex) polytope if and only if it is a convex hull of a finite set of points.

Some authors define a polytope as a convex hull of a finite set of points and then show that it must be a bounded polyhedron.

9.3.4. Euclidean Balls

Definition 9.20 (Euclidean ball)

A Euclidean closed ball (or just ball) in ${\mathbb{R}}^n$ has the form

$$B[{\mathbf{x}}_c,r]\triangleq \{\mathbf{x}|\Vert \mathbf{x}-{\mathbf{x}}_c{\Vert }_2\le r\}=\{\mathbf{x}|(\mathbf{x}-{\mathbf{x}}_c{)}^T(\mathbf{x}-{\mathbf{x}}_c)\le r^2\}$$

where $r>0$ and $\Vert \cdot {\Vert }_2$ denotes the Euclidean norm. ${\mathbf{x}}_c$ is the center of the ball. $r$ is the radius of the ball.

An equivalent expression is given by

$$B=\{{\mathbf{x}}_c+r\mathbf{u}|\Vert \mathbf{u}{\Vert }_2\le 1\}.$$

A Euclidean ball is a convex set.

9.3.5. Ellipsoids

Definition 9.21

An ellipsoid is a set of the form

$$\xi =\{\mathbf{x}|(\mathbf{x}-{\mathbf{x}}_c{)}^T{\mathbf{P}}^{-1}(\mathbf{x}-{\mathbf{x}}_c)\le 1\}$$

where $\mathbf{P}={\mathbf{P}}^T\mathrm{succ}0$; i.e., $\mathbf{P}$ is symmetric and positive definite.

The vector ${\mathbf{x}}_c\in {\mathbb{R}}^n$ is the centroid of the ellipse.

Eigen values of the matrix $\mathbf{P}$ (which are all positive) determine how far the ellipsoid extends in every direction from ${\mathbf{x}}_c$.

The lengths of semi-axes of $\xi$ are given by $\sqrt{{\lambda }_i}$ where ${\lambda }_i$ are the eigen values of $\mathbf{P}$.

Remark 9.3

A Euclidean ball is an ellipsoid with $\mathbf{P}=r^{2}I$.

An alternative representation of an ellipsoid is given by

$$\xi =\{{\mathbf{x}}_c+\mathbf{A}\mathbf{u}|\Vert \mathbf{u}{\Vert }_2\le 1\}$$

where $\mathbf{A}$ is a square and nonsingular matrix.

To show the equivalence of the two definitions, we proceed as follows.

Let $\mathbf{P}=\mathbf{A}{\mathbf{A}}^T$. Let $\mathbf{x}$ be any arbitrary element in $\xi$.

Then $\mathbf{x}-{\mathbf{x}}_c=\mathbf{A}\mathbf{u}$ for some $\mathbf{u}$ such that $\Vert \mathbf{u}{\Vert }_2\le 1$.

Thus

$$\begin{array}{rl}& (\mathbf{x}-{\mathbf{x}}_c{)}^T{\mathbf{P}}^{-1}(\mathbf{x}-{\mathbf{x}}_c)=(\mathbf{A}\mathbf{u}{)}^T(\mathbf{A}{\mathbf{A}}^T{)}^{-1}(\mathbf{A}\mathbf{u})\\ & ={\mathbf{u}}^T{\mathbf{A}}^T({\mathbf{A}}^T{)}^{-1}{\mathbf{A}}^{-1}\mathbf{A}\mathbf{u}={\mathbf{u}}^T\mathbf{u}\\ & =\Vert \mathbf{u}{\Vert }_2^2\le 1.\end{array}$$

The two representations of an ellipsoid are therefore equivalent.

Remark 9.4

An ellipsoid is a convex set.