convex-opt

Convex Optimization (1)

Convex Sets

Lines and Line Segments

Suppose \(x_1 \neq x_2\) are two points in \(\mathbb{R}^n\). Points of the form:

\[y = \theta x_1 + (1 - \theta) x_2\]

Where \(\theta \in \mathbb{R}\), form the line passing through \(x_1, x_2\). The parameter value \(\theta = 0\) corresponds to \(y = x_2\), and the parameter value \(\theta = 1\) corresponds to \(y = x_1\). Values of the parameter \(\theta\) between \(0\) and \(1\) correspond to the closed line segment between \(x_1, x_2\).

Affine Sets

A set \(C \subseteq \mathbb{R}^n\) is affine if the line through any two distinct points in \(C\) lies in \(C\) (For any \(x_1, x_2 \in C\) and \(\theta \in \mathbb{R}, y = \theta x_1 + (1 - \theta)x_2 \in C\)), in other words, \(C\) contains linear combination of any two points in \(C\), provided the coefficients in the linear combination sum to \(1\).

We refer to a point of the form \(\theta_1 x_1 + .... + \theta_k x_k, \; \theta_1 + .... + \theta_k = 1\) as an affine combination of the points \(x_1, ...., x_k\). It can be shown that an affine set contains every affine combination of its points. That is, if \(C\) is an affine set, \(x_1, ...., x_k \in C\), and \(\theta_1 + .... + \theta_k = 1\), then the point \(\theta_1x_1 + .... + \theta_k x_k\) also belongs to \(C\).

If \(C\) is an affine set and \(x_0 \in C\), then the set:

\[V = C - x_0 = \{x - x_0 | x \in C\}\]

is a subspace (closed under additional and multiplication and contains \(0\)). The 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\).

The set of all affine combinations of points in some set \(C \subseteq \mathbb{R}^n\) is called the affine hull of \(C\):

\[\text{aff} C = \{\theta_1 x_1 + .... + \theta_k x_k | x_1, ...., x_k \in C, \theta_1 + .... + \theta_k = 1\}\]

The affine hull is the smallest affine set that contains \(C\), in the following sense: if \(S\) is any affine set with \(C \subseteq S\), then \(\text{aff} C \subseteq S\).

Affine Dimension and Relative Interior

The Affine Dimension of a set \(C\) is defined to be the dimension of its affine hull.