[Reading Note] Chapter 2.1 Affine and Convex Set

3 minute read

Published: December 16, 2022

Chapter 2.1 Affine and Convex Set

Line: $y=\theta x_1 + (1-\theta) x_2 = x_2 + \theta (x_1-x_2)$, for any $\theta \in \mathbb{R}$.
line segment: $y=\theta x_1 + (1-\theta) x_2$, for $\theta\in[0,1]$.

Affine set [Two points definition]: A set $C\in\mathbb{R}$ is affine if the line through any two distinct points in $C$ lines in $C$.
affine combination: $\theta_1 x_1 + \theta_2 x_2 + \ldots + \theta_k x_k$, where $\theta_1,\ldots,\theta_k\in\mathbb{R}$ and $\theta_1+\ldots+\theta_k=1$.
Affine set [Multi-points definition]: If $C$ is an affine set, $x_1,\ldots,x_k\in C$ and $\theta_1+\ldots+\theta_k=1$, then the point $\theta_1 x_1+\ldots+\theta_k x_k$ belongs to $C$.
If $C$ is an affine set, an $x_0\in C$, then the set $V=C-x_0=\{x-x_0 \| x\in C\}$ is a subspace, i.e., for any $v_1, v_2 \in V$, one can prove that $\alpha v_1 + \beta v_2 \in V$. Conversely, an affine set $C$ can be expressed by a subspace $V$ plus an offset.
Dimension of an affine set $C$ is defined as the dimension of the subspace $V=C-x_0$, where $x_0$ is any element of $C$.
Affine hull: For a set $C\in\mathbb{R}^n$, the affine combination of all points in $C$ is called affine hull of $C$ and denoted ${\bf{aff}} C$:
\[\begin{aligned} {\bf{aff}} C=\{\theta_1 x_1+\ldots+\theta_k x_k \| x_1, x_2, \ldots x_k \in C, \theta_1+\ldots+\theta_k=1\}. \end{aligned}\]

The affine dimension of a set $C$ is defined as the dimension of its affine hull.
The relative interior of a set $C$, ${\bf{relint} C}$ , is (not technically) the points in $C$ that are not on the boundary of the affine hull of $C$. Technically, ${\bf{relint} C}$ is defined as:

\[\begin{aligned} {\bf{relint}} C=\{x\in C \| B(x,r)\cap{\bf{aff}}C \subseteq C {\text{ for some }} r>0\}. \end{aligned}\]

The relative boundary of a set $C$ is defined as ${\bf{cl}} C$\ ${\bf{relint}} C$, where ${\bf{cl}} C$ is the closure of $C$.

Convex set [Two points definition]: A set $C$ is convex if the line segment between any two points in $C$ lies in $C$.
Convex Combination: $\theta_1 x_1 +\ldots+ \theta_k x_k$, where $\theta_1+\ldots\theta_k=1$, and $\theta_i\geq 0$ for $i=1,\ldots,k$.
Convex set [Multi-points definition]: A set is convex if and only if it contains every combination of its points.
Convex hull of a set $C$, denoted by ${\bf{conv}~C}$, is the set of all convex combinations of points in $C$:

\[\begin{aligned} {\bf{conv}}~ C=\{\theta_1 x_1+\ldots+\theta_k x_k \| x_i\in C,\theta_i\geq 0, \theta_1+\ldots+\theta_k=1\}. \end{aligned}\]

Cones: A set $C$ is a cone if for every $x\in C$ and $\theta\geq 0$, it has $\theta x \in C$.
Convex Cone [two points detinition]: A set $C$ is a convex cone if it is convex and a cone. I.e., for any $x_1,x_2\in C$ and $\theta_1,\theta_2\geq 0$, it has $\theta_1 x_1+\theta_2 x_2\in C$.
Conic Combination (nonnegative linear combination): $\theta_1 x_1+\ldots+\theta_k x_k$ with $\theta_i \geq 0$.
Convex Cone [Multi-points detinition]: A set $C$ is a convex cone if an only if it contains all conic combinations of its elements.
Conic hull: The conic hull of a set $C$ is the set of all conic combinations of points in $C$, i.e., $\{\theta_1 x_1+\ldots+\theta_k x_k \| x_i\in C,\theta_i\geq 0,\}$