7.11. Topology of Convex Sets#

This section focuses on some topological properties of convex sets. Throughout this section, we assume that \(\VV\) is a finite dimensional real normed linear space equipped with a norm \(\| \cdot \| : \VV \to \RR\). It is also equipped with a metric \(d(\bx, \by) = \| \bx - \by \|\). Wherever necessary, it is also equppied with an real inner product \(\langle \cdot, \cdot \rangle : \VV \times \VV \to \RR\).

Primary references for this section are [3, 5, 8, 20].

In a finite dimensional real normed linear space:

  • Linear subspaces are closed.

  • Hyperplanes are closed.

  • Affine subspaces are closed.

  • Interiors of proper linear/affine subspaces are empty.

  • Linear/affine transformations are continuous.

  • Bijective linear/affine transformations are homeomorphisms.

  • Bijective linear/affine transformations preserve interiors and closures.

Following the discussion in Normed Linear Spaces, \(B\) shall denote the open unit ball \(B(\bzero, 1)\). \(\bar{B}\) shall denote the closed unit ball \(B[\bzero, 1]\). The open ball \(B(\bx, r)\) (for some \(r > 0\)) can be written as \(\bx + r B\). Similarly, the closed ball \(B[\bx, r]\) can be written as \(\bx + r \bar{B}\).

We shall use several set and vector arithmetic identities and inequalities in the discussion below. We list them here for quick reference. See Sets in Vector Spaces for detailed discussion.

Let \(C,D,E\) be subsets of \(\VV\). Let \(\bx, \bv, \bz \in \VV\) be arbitrary vectors.

From Theorem 4.17

\[ C = (C + \bz) - \bz. \]
\[ C \subseteq D \iff C + \bz \subseteq D + \bz. \]

From Theorem 4.19,

\[ (C \cap D) + E \subseteq (C + E) \cap (D + E). \]

For any set \(A \subseteq \VV\), the set of points \(\bx\) whose distance from \(A\) is less than \(r\) for some \(r > 0\) is given by:

\[ A + r B = \bigcup_{\ba \in A} \ba + r B = \{\bx \ST \exists \ba \in A, d(\ba, \bx) < r \}. \]

Recall from Theorem 4.42 that \(\bx \in \closure A\) if and only if

\[ \bx \in A + r B \Forall r > 0. \]

Similarly, recall from Theorem 4.39 that \(\bx \in \interior A\) if and only if

\[ \exists r > 0 \text{ such that } \bx + r B \subseteq A. \]

7.11.1. Closed Convex Sets#

Theorem 7.122 (Closed convex set = Closure of the union of line segments)

Let \(\VV\) be a real normed linear space. Let \(C\) be a closed convex set of \(\VV\). Then \(C\) is the closure of the union of all the line segments connecting the points of the set.

Proof. Let \(D = \bigcup_{\bx, \by \in C} [\bx, \by]\). By Theorem 7.12, \(C = D\). Since \(C\) is closed, hence \(D\) is closed, hence \(\closure D = D = C\).

A dual description of a closed convex set is that it is the intersection of all closed half spaces containing the set. This is shown in Theorem 7.170.

7.11.1.1. Closure#

Theorem 7.123 (Closure of a convex set)

Let \(\VV\) be a real normed linear space. Let \(C\) be a convex set of \(\VV\). Then, its closure is convex.

Proof. If \(C\) is empty, then its closure is empty and is therefore convex. Now, assume \(C\) to be nonempty.

  1. Let \(\bx, \by \in \closure C\).

  2. Let \(t \in (0, 1)\).

  3. Let \(\bz = t \bx + (1-t) \by\).

  4. We need to show that \(\bz \in \closure C\).

  5. Since both \(\bx, \by\) are closure points of \(C\), hence there exist sequences \(\{ \bx_n \}\) and \(\{ \by_n \}\) of \(C\) such that \(\lim \bx_n = \bx\) and \(\lim \by_n = \by\).

  6. Then, \(\bz_n = t \bx_n + (1-t) \by_n \in C\) since \(\bx_n, \by_n \in C\) and \(C\) is convex.

  7. By limit arithmetic

    \[ \lim \bz_n = \lim (t \bx_n + (1-t) \by_n) = t \lim \bx_n + (1-t) \lim \by_n = t \bx + (1-t)\by = \bz. \]
  8. Thus, \(\bz = \lim \bz_n\).

  9. Since \(\{ \bz_n \}\) is also a sequence of \(C\), hence \(\bz \in \closure C\).

  10. Thus, for any \(\bx, \by \in \closure C\) and \(t \in (0, 1)\), \( t \bx + (1-t) \by \in \closure C\).

  11. Thus, \(\closure C\) is convex.

7.11.2. Interior#

Theorem 7.124 (Interior of convex sets)

Let \(\VV\) be a real normed linear space. Let \(C\) be a nonempty convex set of \(\VV\). Then, its interior is convex.

Proof. Let \(D = \interior C\). Assume that \(C\) is convex.

  1. Let \(\bx, \by \in D\) and \(t \in (0,1)\). We need to show that \(\bz = t \bx + (1-t)\by \in D\).

  2. Since \(\bx \in D\), there exists an open ball \(B(\bx, r) \subseteq C\).

  3. Let Consider the open ball \(B(\bz, t r)\) radius \(tr\) around \(\bz\).

  4. Let \(\bv \in B(\bz, t r)\).

  5. Let

    \[ \bu = \frac{1}{t} \bv - \frac{1-t}{t} \by. \]

    We can choose such a point \(\bu \in \VV\) since \(t\) is nonzero.

  6. Then, \(\bv = t \bu + (1-t) \by\).

  7. Note that

    \[\begin{split} \| t (\bu - \bx) \| &= \| t\bu - t \bx \| \\ &= \| \bv - (1-t)\by - (\bz - (1-t)\by) \|\\ &= \| \bv - \bz \| \\ & < t r \end{split}\]

    since \(\bv \in B(\bz, tr)\).

  8. Thus, \(\| \bu - \bx \| < r\).

  9. Thus, \(\bu \in B(\bx, r)\).

  10. Thus, \(\bv \in C\) as it is a convex combination of \(\bu\) and \(\by\).

  11. Since this holds true for every \(\bv \in B(\bz, tr)\), hence \(B(\bz, t r) \subseteq C\).

  12. Thus, there is an open ball of radius \(tr\) around \(\bz\) contained in \(C\).

  13. Thus, \(\bz \in \interior C = D\).

  14. We have shown that for any \(\bx, \by \in D\) and \(t \in (0,1)\), \(\bz = t \bx + (1-t)\by \in D\).

  15. Thus, \(D\) is convex.

We provide a shorter but more technical proof.

Proof. Let \(D = \interior C\). Assume that \(C\) is convex.

  1. Fix some \(t \in (0, 1)\).

  2. Since \(C\) is convex, hence \(tC + (1-t)C \subseteq C\).

  3. Hence, \(tD + (1-t)D \subseteq C\).

  4. Since \(D\) is open, hence \(tD\) is open (Theorem 4.48).

  5. Then, \(tD + (1-t)D\) is also open as sum of an open set with any set is open (Theorem 4.49).

  6. But \(D\) is the largest open set contained in \(C\).

  7. Thus, \(tD + (1-t)D \subseteq D\).

  8. Thus, \(D\) contains all its convex combinations.

  9. Thus, \(D\) is convex.

Proof. Another proof can be built based on the general line segment property proved in Theorem 7.126 below.

  1. Let \(\bx, \by \in \interior C\).

  2. Let \(t \in (0, 1)\).

  3. Then, by line segment property \(t \bx + (1 -t) \by \in \interior C\).

  4. Thus, \(\interior C\) is closed under convex combination.

  5. Thus, \(\interior C\) is convex.

Theorem 7.125 (Affine hull of convex sets with empty interior)

Let \(\VV\) be an \(n\)-dimensional real normed linear space. Let \(C\) be a nonempty convex set of \(\VV\). If \(C\) has an empty interior, then it must lie in an affine subspace of dimension less than \(n\).

Conversely, if \(\dim \affine C < n\), then, \(C\) has an empty interior.

Proof. We first show that if \(C\) has an empty interior, then \(\dim \affine C < n\).

  1. Let \(A = \affine C\).

  2. Let \(\dim A = d\).

  3. If \(d < n\), there is nothing to prove.

  4. For contradiction, assume \(d=n\).

  5. Then, it is possible to pick \(n+1\) affine independent points from \(C\).

  6. Let \(\bv_0, \dots, \bv_n\) be one such set of affine independent points of \(C\).

  7. Since \(C\) is convex, it contains the convex hull \(H = \ConvexHull \{\bv_0, \dots, \bv_n \}\); i.e., \(H \subseteq C\).

  8. In an \(n\) dimensional space, the convex hull of a \(n+1\) affine independent points has a nonempty interior.

  9. Thus, the interior of \(C\) must be nonempty.

  10. This is a contradiction, hence \(\dim A < n\) must be true.

Now, assume that \(\dim \affine C < n\).

  1. \(A\) is a proper subspace of \(\VV\).

  2. Then \(A\) has an empty interior as per Theorem 4.169.

  3. \(\interior C \subseteq \interior A\) since \(C \subseteq A\).

  4. Thus, \(\interior C = \EmptySet\).

Example 7.59 (Convex sets with empty interiors)

  1. Let \(\VV = \RR^2\). Let \(A = [0,1] \times \{0\}\). It is the line segment from \(x=0\) to \(x=1\) with \(y=0\) on \(x\)-axis. No open ball of \(\RR^2\) is contained inside \(A\). Hence, \(\interior A = \EmptySet\).

  2. Let \(C\) be any singleton (a point). It is nonempty and its interior is empty.

  3. Let \(\VV = \RR^3\). Any polygon lying within the \(x-y\) plane has an empty interior.

Corollary 7.8 (Convex sets, empty interior, interior of closure)

Let \(\VV\) be an \(n\)-dimensional real normed linear space. Let \(C\) be a nonempty convex set of \(\VV\). If \(C\) has an empty interior then so does its closure.

\[ \interior C = \EmptySet \implies \interior \closure C = \EmptySet. \]

Proof. We proceed as follows:

  1. Let \(A = \affine C\).

  2. Since \(\interior C = \EmptySet\) hence \(\dim A = d < n\) due to Theorem 7.125 above.

  3. Now \(\closure C \subseteq A\) since \(A\) is closed (Theorem 4.168).

  4. Thus, \(\interior \closure C \subseteq \interior A\).

  5. But then \(A\) has an empty interior as per Theorem 4.169.

  6. Thus, \(\interior \closure C = \EmptySet\).

Theorem 7.126 (General line segment property for convex sets)

Let \(\VV\) be a real normed linear space. Let \(C\) be a nonempty convex subset of \(\VV\). Let \(\bx \in \interior C\) and \(\by \in \closure C\). Then,

\[ (1-t) \bx + t \by \in \interior C \Forall t \in [0,1). \]

Proof. Let \(C\) be a convex set. Fix some \(t \in [0,1)\).

  1. Let \(\bz = (1-t) \bx + t \by\). It suffices to show that there is an open ball \(\bz + rB \subseteq C\).

  2. Since \(\by \in \closure C\), hence for every \(r > 0\), we have \(\by \in C + r B\).

  3. Then,

    \[\begin{split} \bz + r B &= (1-t)\bx + t \by + r B \\ &\subseteq (1-t)\bx + t (C + r B) + r B \\ &= (1-t)\bx + (1 + t) rB + t C\\ & = (1 -t)(\bx + r (1+t)(1-t)^{-1} B) + t C. \end{split}\]
  4. Since \(\bx \in \interior C\), hence we can take \(r\) to be so small such that

    \[ \bx + r (1+t)(1-t)^{-1} B \subseteq C. \]
  5. But then

    \[\begin{split} (1 -t)(\bx + r (1+t)(1-t)^{-1} B) + t C &\subseteq (1 -t) C + t C\\ &\subseteq C \end{split}\]

    since \(C\) is convex and \(t \in [0,1)\).

  6. Thus, we established that there exists an \(r > 0\) such that \(\bz + r B \subseteq C\).

  7. Hence, \(\bz \in \interior C\).

Theorem 7.127 (Closure of interior)

Let \(\VV\) be a real normed linear space. For any convex set \(C \subseteq \VV\),

\[ \closure \interior C = \closure C. \]

Proof. Since \(\interior C \subseteq C\), hence \(\closure \interior C \subseteq \closure C\).

For the other direction, we proceed as follows:

  1. Let \(\by \in \closure C\). We need to show that \(\by \in \closure \interior C\).

  2. Choose some \(\bx \in \interior C\).

  3. By Theorem 7.126, the line segment between \(\bx\) and \(\by\) (excluding \(\by\)) lies in \(\interior C\).

  4. For every \(n \in \Nat\), let

    \[ \by_n = \frac{1}{n} \bx + \left (1 - \frac{1}{n} \right ) \by. \]
  5. Then, \(\by_n \in \interior C\) by line segment property.

  6. Thus, \(\{ \by_n \}\) is a sequence of \(\interior C\).

  7. But then, \(\lim_{n \to \infty} \by_n = \by\).

  8. Hence, \(\by\) is an accumulation point of \(\interior C\).

  9. Thus, \(\by \in \closure \interior C\).

  10. Thus, \(\closure C \subseteq \closure \interior C\).

Combining the two inclusions, we get:

\[ \closure \interior C = \closure C. \]

Theorem 7.128 (Interior of closure)

Let \(\VV\) be an \(n\)-dimensional real normed linear space. For any convex set \(C \subseteq \VV\)

\[ \interior C = \interior \closure C. \]

Proof. The statement is trivial for \(C = \EmptySet\). We shall assume that \(C\) is nonempty. Further, if \(\interior C = \EmptySet\), then \(\interior \closure C = \EmptySet\) due to Corollary 7.8 above. We shall assume that \(\interior C\) is nonempty.

Since \(C \subseteq \closure C\), hence \(\interior C \subseteq \interior \closure C\).

For the converse, assume that \(\bx \in \interior \closure C\). Our goal is to show that \(\bx \in \interior C\).

  1. We have, \(\bx \in \closure C\) and there exists \(r > 0\) such that

    \[ (\bx + r B) \subseteq \closure C. \]
  2. Choose a point \(\by \in \interior C\).

  3. Let \(t = \frac{r}{2\| \bx - \by \|}\).

  4. Define

    \[ \bz = (1 + t) \bx - t \by. \]
  5. Note that

    \[\begin{split} d(\bz, \bx) &= \| \bz - \bx \|\\ &= \|(1 + t) \bx - t \by - \bx \|\\ &= t \| \bx - \by \| = \frac{r}{2}. \end{split}\]
  6. Hence, \(\bz \in B(\bx, r) \subseteq \closure C\).

  7. We have found the points \(\by \in \interior C\) and \(\bz \in \closure C\).

  8. Now note that,

    \[ \bx = \frac{t}{1+t} \by + \frac{1}{1+t} \bz. \]
  9. Thus, \(\bx\) is a convex combination of \(\by\) and \(\bz\).

  10. Since \(t > 0\), hence \(\bx\) lies in the line segment between \(\bz\) and \(\by\).

  11. Hence, \(\bx \in \interior C\) due to Theorem 7.126 (line segment property for interior of convex sets).

Thus, we have shown that \(\interior \closure C \subseteq \interior C\) as desired.

7.11.3. Compact Sets#

Theorem 7.129 (Convex hull of compact sets)

Let \(\VV\) be an \(n\)-dimensional real normed linear space. Let \(S \subseteq \VV\) be a compact subset of \(\VV\). Then, \(\ConvexHull(S)\) is compact.

In other words, convex hull of a compact set is compact.

Note that this property doesn’t hold in infinite dimensional spaces.

Proof. Let \(H = \ConvexHull(S)\).

We first show that \(H\) is bounded.

  1. Since \(S\) is compact, hence there exists \(M > 0\) such that \(\| \bx \| \leq M\) for all \(\bx \in S\).

  2. Let \(\by \in H\).

  3. Then, by Theorem 7.19, there exist \(\bx_0, \dots, \bx_n \in S\) and \(t \in \Delta_{n+1}\) such that

    \[ \by = t_0 \bx_0 + \dots + t_n \bx_n. \]
  4. Therefore,

    \[\begin{split} \| \by \| &= \|t_0 \bx_0 + \dots + t_n \bx_n \| \\ &\leq t_0 \| \bx_0 \| + \dots + t_n \| \bx_n \| \\ &\leq (t_0 + \dots + t_n) M = M. \end{split}\]
  5. Thus, \(H\) is bounded.

We now show that \(H\) is closed.

  1. Let \(\{ \bv_k \}\) be a convergent sequence of \(H\).

  2. Let \(\bv = \lim_{k \to \infty} \bv_k\) be the limit of this sequence with \(\bv \in \VV\).

  3. We need to show that \(\bv \in H\).

  4. For every \(k \in \Nat\), by Theorem 7.19, there exist \(\bx_0^k, \dots, \bx_n^k \in S\) and \(\bt^k \in \Delta_{n+1}\) such that

    \[ \bv_k = t_0^k \bx_0^k + \dots + t_n^k \bx_n^k. \]
  5. Consider the vector space \(\WW = \RR^{n+1} \oplus \VV \oplus \dots \oplus \VV\) (\(\VV\) repeated \(n+1\) times).

  6. Then, \(R = \Delta_{n+1} \oplus S \oplus \dots \oplus S \subseteq \WW\).

  7. Since \(\Delta_{n+1}\) is compact in \(\RR^{n+1}\) and \(S\) is compact in \(\VV\), hence \(R\) is compact in the product topology of \(\WW\).

  8. Now, let \(\by_k = (\bt^k, \bx_0^k, \dots, \bx_n^k) \in R\) for every \(k\).

  9. Thus, \(\{ \by_k \}\) is a sequence of the compact set \(R\).

  10. By Theorem 3.75, every sequence of a compact set \(R\) has a convergent subsequence that converges in \(R\).

  11. Let \(\{ \by_{k_j} \}\) with \(k_1 < k_2 < \dots\) be such a convergent subsequence of \(\{ \by_k \}\).

  12. Let the limit of this sequence be

    \[ \by = \lim_{j \to \infty} \by_{k_j} = (\bt, \bx_0, \dots, \bx_n) \]

    with \(\bt \in \Delta_{n +1}\) and \(\bx_0, \dots, \bx_n \in S\) since \(\by \in R\).

  13. This further implies that \(\bt = \lim_{j \to \infty} \bt^{k_j}\) and \(\bx_i = \lim_{j \to \infty} \bx_i^{k_j}\) for every \(i \in 0,\dots,n\).

  14. In turn, \(t_i = \lim_{j \to \infty} t_i^{k_j}\) for every \(i=0, \dots, n\).

  15. Since \(\{ \bv_k \}\) is convergent, hence every subsequence of \(\{ \bv_k \}\) has the same limit.

  16. In particular, \(\bv = \lim_{j \to \infty} \bv_{k_j}\).

  17. Then,

    \[ \bv = \lim_{j \to \infty} \bv_{k_j} = \lim_{j \to \infty} \sum_{i=0}^n t_i^{k_j} \bx_i^{k_j} = \sum_{i=0}^n t_i \bx_i. \]
  18. But then, \(\bv\) is a convex combination of points in \(S\).

  19. Thus, \(\bv \in H\).

  20. Thus, \(H\) is closed.

Finally, by Theorem 4.66, every closed and bounded set of a real \(n\)-dim normed space is compact. Hence, \(H\) is compact.

Theorem 7.130 (Krein Milman theorem)

Let \(\VV\) be an \(n\)-dimensional real normed linear space. Let \(S \subseteq \VV\) be a compact convex subset of \(\VV\). Then,

\[ S = \ConvexHull(\aextreme(S)). \]

In other words, a compact convex set is the convex hull of its extreme points.

7.11.4. Cones#

Theorem 7.131 (Conic hulls of a finite set of points are closed)

Let \(\VV\) be an \(n\)-dimensional real normed linear space. Let \(\ba_1, \dots, \ba_k \in \VV\). Then, their conic hull given by

\[ H = \ConicHull ( \{ \ba_1, \dots, \ba_k \}) \]

is closed.

Proof. Let \(S = \{ \ba_1, \dots, \ba_k \}\).

  1. By the conic representation theorem, each point of \(H\) can be represented as a conic combination of a linearly independent subset of \(S\).

  2. Since the number of points in \(S\) is finite, hence the number of linearly independent subsets of \(S\) is finite.

  3. Let there be \(N\) linearly independent subsets of \(S\). Denote them by \(S_1, \dots, S_N\).

  4. Then,

    \[ H = \bigcup_{i=1}^N \ConicHull (S_i). \]
  5. If \(\ConicHull (S_i)\) are closed, then \(H\) is closed as it is a finite union of closed sets.

  6. Thus, it suffices to show that \(H_i = \ConicHull (S_i)\) are closed for every \(i \in 1,\dots,N\).

Accordingly, let us assume that \(S = \{ \ba_1, \dots, \ba_k \}\) is a linearly independent set of vectors (with \(k \leq n\)) and \(H = \ConicHull(S)\).

  1. Let \(\WW = \span S = \span \{ \ba_1, \dots, \ba_k \}\).

  2. Then, \(S\) is a basis for \(\WW\).

  3. Let \(T : \WW \to \RR^k\) be a coordinate mapping given by

    \[ T (\bx) = \bt \in \RR^m \text{ such that } \bx = t_1 \ba_1 + \dots + t_k \ba_k \]

    for every \(\bx \in \WW\). The mapping is well defined since \(S\) is a basis for \(\WW\). Thus, every \(\bx \in \WW\) is a unique linear combination of elements in the basis \(S\).

  4. It is easy to see that \(T\) is a linear mapping. Moreover, \(T\) is an isomorphism.

  5. Thus, \(T : (\WW , \| \cdot \|) \to (\RR^k, \| \cdot \|_2)\) is continuous due to Theorem 4.63.

  6. Also, we can see that

    \[ H = T^{-1} (\RR^k_+). \]
  7. But \(\RR^k_+\) is a closed set of \(\RR^k\).

  8. Thus, \(H = T^{-1} (\RR^k_+)\) is closed since \(T\) is continuous.

7.11.5. Relative Interior#

One way to think about relative interiors is to think in terms of subspace topology. If \(\VV\) is a normed linear space, then it is a metric space. For any set \(C \subseteq \VV\) let \(A = \affine C\). Then, we can consider the subspace topology by restricting the norm \(\| \cdot \| : \VV \to \RR\) to the affine hull \(A\). In terms of subspace topology, if some set \(X\) is open in \(\VV\), then \(X \cap A\) is relatively open in \(A\).

A set \(C\) may have an empty interior and yet may have a nonempty relative interior. For example, consider a face of a cube in \(\RR^3\). While the cube has a nonempty interior, the face has an empty interior as no open ball is contained inside the face. But, in terms of the subspace topology of the affine hull of the face, the face indeed as a nonempty relative interior.

Often, a convex set lies in a low dimensional (affine or linear) subspace of the ambient vector space. Thus, the interior of the convex set is empty. At the same time, the relative interior of the set (w.r.t. its affine hull) need not be empty. It plays a similar topological role as the interior of a set. We develop some fundamental results on the relative interiors of convex sets in the sequel.

Definition 7.55 (Relative interior point)

Let \(\VV\) be a real normed linear space. Let \(C \subseteq \VV\). We say that \(\bx \in C\) is a relative interior point of \(C\) if there exists an open ball \(B(\bx, r)\) for some \(r > 0\) such that

\[ B(\bx, r) \cap \affine C \subseteq C. \]

Note that, the open ball \(B(\bx, r)\) itself need not be contained inside \(C\).

Definition 7.56 (Relative interior)

The relative interior of a set \(C\), denoted by \(\relint C\) is the set of all its relative interior points.

\[ \relint C \triangleq \{\bx \in C \ST \exists r > 0, B(\bx, r) \cap \affine C \subseteq C \}. \]

The basic definition of relative interior doesn’t require \(\VV\) to be finite dimensional. However, several results in the sequel do depend on \(\VV\) being finite dimensional. We will clearly state this as and when required.

Example 7.60 (Relative interior of a line segment)

Let \(\bx, \by \in \VV\) be distinct points. The line segment between \(\bx\) and \(\by\) is given by

\[ S = \{ t \bx + (1-t) \by \ST t \in [0, 1] \}. \]

The relative interior of \(S\) is given by

\[ \relint S = \{ t \bx + (1-t) \by \ST t \in (0, 1) \}. \]

To see this, we note that the affine hull of \(S\) is the line

\[ L = \{ t \bx + (1-t) \by \ST t \in \RR \}. \]

Then, for every point \(\bz = t \bx + (1-t) \by\) with \(t \in (0, 1)\), there exists \(r > 0\) such that \(B(\bz, r) \cap L \subseteq S\).

Example 7.61 (Relative interior of an arc)

Consider the set of points given by

\[ S = \left \{ (\cos(t), \sin (t)) \ST 0 \leq t \leq \frac{\pi}{2} \right \}. \]

in the ambient space \(\RR^2\). The affine hull of \(S\) is the entire plane \(\RR^2\).

Now, for any \(\bx \in S\), \(r > 0\),

\[ B(\bx, r) \cap \affine (S) = B(\bx, r) \cap \RR^2 = B(\bx, r). \]

It is an open ball in \(\RR^2\) and hence never a subset of \(S\).

Thus, \(\relint S = \EmptySet\).

Theorem 7.132 (Relative interiors are subset)

Let \(\VV\) be a normed linear space.

For any set \(C\) of \(\VV\)

\[ \relint C \subseteq C. \]

Proof. This follows directly from the definition of relative interior.

Theorem 7.133 (Relative interior of singleton)

Let \(\VV\) be a normed linear space. Let \(C = \{ \bx \}\) be a singleton subset of \(\VV\). Then,

\[ \relint C = \relint \{ \bx \} = \{ \bx \}. \]

Proof. We proceed as follows:

  1. The singleton sets are affine.

  2. Thus, \(\affine C = C\).

  3. Now, for any \(r > 0\),

    \[ B(\bx, r) \cap C = \{ \bx \} = C \subseteq C. \]
  4. Thus, \(\bx \in \relint C\).

  5. Since \(\relint C \subseteq C\), hence \(\relint C = \{ \bx \}\).

Basic arithmetic of balls relative to the affine hull will be useful later on.

Theorem 7.134 (Relative ball arithmetic)

Let \(\VV\) be a real normed linear space. Let \(A\) be an affine set and \(\bx \in A\). Let \(L\) be the linear subspace parallel to \(A\) given by \(L = A - A = A - \bx\). Let \(r > 0\). Then,

\[ (B(\bx, r) \cap A) - \bx = B(\bzero, r) \cap L. \]

Alternatively,

\[ B(\bx, r) \cap A = (B(\bzero, r) \cap L) + \bx. \]

For any \(\bx, \by \in A\),

\[ (B(\bx, r) \cap A) - \bx = (B(\by, r) \cap A) - \by. \]

In the simplified notation,

\[ ((\bx + r B) \cap A) - \bx = r B \cap L. \]

Alternatively,

\[ (\bx + r B) \cap A = (r B \cap L) + \bx. \]

And for any \(\bx, \by \in A\)

\[ ((\bx + r B) \cap A) - \bx = ((\by + r B) \cap A) - \by. \]

Proof. We first show that \((B(\bx, r) \cap A) - \bx \subseteq B(\bzero, r) \cap L \).

  1. Let \(\bv \in (B(\bx, r) \cap A) - \bx\).

  2. Then, \(\bv + \bx \in B(\bx, r) \cap A\).

  3. Thus, \(\bv + \bx \in B(\bx, r)\) and \(\bv + \bx \in A\).

  4. Thus, \(\bv \in B(\bzero, r)\) and \(\bv \in A - \bx = L\).

  5. Thus, \(\bv \in B(\bzero, r) \cap L\).

We now show the converse.

  1. Let \(\bv \in B(\bzero, r) \cap L\).

  2. Then, \(\bv \in B(\bzero, r)\) and \(\bv \in L\).

  3. Then, \(\bv + \bx \in B(\bx, r)\) and \(\bv + \bx \in L + \bx = A\).

  4. Then, \(\bv + \bx \in B(\bx, r) \cap A\).

  5. Thus, \(\bv \in (B(\bx, r) \cap A) - \bx\).

  6. Thus, \(B(\bzero, r) \cap L \subseteq (B(\bx, r) \cap A) - \bx\).

We have shown that

\[ (B(\bx, r) \cap A) - \bx = B(\bzero, r) \cap L. \]

Similarly, for any other \(\by \in A\)

\[ (B(\by, r) \cap A) - \by = B(\bzero, r) \cap L. \]

Thus,

\[ (B(\bx, r) \cap A) - \bx = (B(\by, r) \cap A) - \by. \]

Theorem 7.135 (Relative interior and interior)

Let \(\VV\) be a normed linear space. For any subset \(C\) of \(\VV\)

\[ \interior C \subseteq \relint C. \]

If \(\affine C = \VV\), then

\[ \interior C = \relint C. \]

Proof. Let \(\bx \in \interior C\).

  1. Then, there exists \(r > 0\) such that \(B(\bx, r) \subseteq C\).

  2. But \(B(\bx, r) \subseteq C\) implies that \(B(\bx, r) \cap \affine C \subseteq C\).

  3. Thus, \(\bx \in \relint C\) also holds.

  4. Thus, \(\interior C \subseteq \relint C\).

Now consider the case where \(\affine C = \VV\).

  1. Then \(B(\bx, r) \cap \affine C = B(\bx, r)\) since \(B(\bx, r) \subseteq \VV\).

  2. Then, \(\bx\) is a relative interior point of \(C\) if \(B(\bx, r) \subseteq C\) for some \(r > 0\).

  3. But then, \(\bx\) is an interior point of \(C\).

  4. Thus, \(\relint C = \interior C\).

7.11.5.1. Containment Relationship#

In general \(A \subseteq B\) implies that \(\interior A \subseteq \interior B\) and \(\closure A \subseteq \closure B\). However, this is not the case with relative interiors.

Remark 7.8

An inclusion \(A \subseteq B\) does not imply \(\relint A \subseteq \relint B\).

Consider \(C\) to be a cube in \(\RR^3\) and \(A\) to be one of its faces. The relative interiors of both \(A\) and \(C\) are nonempty but disjoint.

However, if the affine hulls of \(A\) and \(B\) are same, then \(A \subseteq B\) does imply that \(\relint A \subseteq \relint B\).

Theorem 7.136 (Relative interior and containment)

Let \(A, B \subseteq \VV\). If \(A \subseteq B \subseteq \affine A\), then \(\relint A \subseteq \relint B\).

Proof. By Theorem 4.142, \(\affine A = \affine B\).

Now, let us focus on the relative interiors.

  1. Let \(\bx \in \relint A\).

  2. Then, there exists \(r > 0\) such that

    \[ B(\bx, r) \cap \affine A \subseteq A. \]
  3. Replace \(\affine A\) by \(\affine B\) and use the fact that \(A \subseteq B\). Thus,

    \[ B(\bx, r) \cap \affine B \subseteq B. \]
  4. Thus, \(\bx \in \relint B\).

Thus, \(\relint A \subseteq \relint B\).

Theorem 7.137 (Relative interior of closure)

Let \(\VV\) be a real finite dimensional normed linear space. For any set \(C \subseteq \VV\)

\[ \relint C \subseteq \relint \closure C. \]

Proof. The statement is trivial for \(C = \EmptySet\). We shall assume that \(C\) is nonempty.

  1. \(C \subseteq \closure C\)

  2. Since \(\VV\) is finite dimensional, hence by Theorem 4.170, \(\affine (\closure C) = \affine C\).

  3. Thus, \(C \subseteq \closure C \subseteq \affine C\).

  4. Thus, by Theorem 7.136, we have \(\relint C \subseteq \relint \closure C\).

7.11.5.2. Relatively Open Sets#

Definition 7.57 (Relatively open set)

We say that a set \(C\) is relatively open if \(C\) is open relative to its affine hull \(\affine C\). In other words, \(C\) is relatively open if

\[ \relint C = C. \]

Theorem 7.138 (Affine sets are relatively open)

Let \(\VV\) be a real normed linear space. Any affine set in \(\VV\) is relatively open. In other words, if \(A\) is affine, then

\[ \relint A = A. \]

Note that this result doesn’t require \(\VV\) to be finite dimensional.

Proof. Let \(A\) be an affine set. Then, \(\affine A = A\). Thus, for any \(\bx \in A\)

\[ B(\bx, r) \cap \affine A = B(\bx, r) \cap A \subseteq A. \]

Thus, every \(\bx \in A\) is a relative interior point of \(A\). Thus,

\[ \relint A = A. \]

Corollary 7.9 (Hyperplanes are relatively open)

The relative interior of a hyperplane is the hyperplane itself. A hyperplane is relatively open.

This is a consequence of the fact that every hyperplane is affine.

An affine set in a finite dimensional vector space is also closed since it is an intersection of hyperplanes and every hyperplane is a closed set. See Theorem 4.168

7.11.5.3. Relative Interior of Relative Interior#

Theorem 7.139 (Relative interior is relatively open)

For any set \(C\),

\[ \relint (\relint C) = \relint C. \]

Thus, \(\relint C\) is relatively open.

Proof. By definition \(\relint (\relint C) \subseteq \relint C\). Thus, we need to show that \(\relint C \subseteq \relint (\relint C)\).

  1. Let \(A = \affine C\).

  2. Let \(\bx \in \relint C\).

  3. Then, there exists \(\epsilon = 2 r > 0\) such that

    \[ (\bx + 2 r B) \cap A \subseteq C. \]
  4. We can write \(\bx + 2 rB\) as

    \[ \bx + 2 r B = (\bx + r B ) + r B. \]
  5. Thus, the previous inclusion can be written as

    \[ ( (\bx + r B) + r B) \cap A \subseteq C. \]
  6. Let \(U = (\bx + r B) \cap A\).

  7. Note that \(U \subseteq C\).

  8. Let \(\by \in U\).

  9. Then, \(\by \in A\) and \(\by \in (\bx + r B)\).

  10. From previous inclusion, we can say that for every \(\by \in U\)

    \[ (\by + r B) \cap A \subseteq C. \]
  11. Thus, \(\by \in \relint C\) for every \(\by \in U\).

  12. Thus, \(U \subseteq \relint C\).

  13. Thus,

    \[ U = (\bx + r B) \cap A \subseteq \relint C. \]
  14. By definition of relative interior, \(\bx \in \relint (\relint C)\).

We have shown that \(\relint C \subseteq \relint (\relint C)\).

7.11.5.4. Relative Boundary#

Definition 7.58 (Relative boundary)

The relative boundary of a set \(C\), denoted by \(\relbd C\) is given by

\[ \relbd C \triangleq \closure C \setminus \relint C. \]

7.11.6. Translations#

Theorem 7.140 (Translations preserve relative interiors)

Let \(\VV\) be a normed linear space. Let \(\ba \in \VV\) be some fixed vector. Let a translation map \(g_a : \VV \to \VV\) be defined as

\[ g_a = \bx + \ba \Forall \bx \in \VV. \]

Then, for any set \(A \subseteq \VV\),

\[ g_a (\relint A) = \relint (g_a (A)). \]

In other words,

\[ \relint (A + \ba) = (\relint A) + \ba. \]

Proof. Let \(\bx \in \relint (A + \ba)\).

  1. Then, there exists \(r > 0\) such that

    \[ (\bx + r B ) \cap \affine (A + \ba) \subseteq A + \ba. \]
  2. Let \(\by = \bx - \ba\).

  3. Since \(\bx \in A + \ba\) hence \(\by \in A\).

  4. Consider the set:

    \[ R = (\by + r B) \cap \affine A. \]
  5. We have

    \[\begin{split} R + \ba &= ((\by + r B) \cap \affine A) + \ba\\ &\subseteq ((\by + r B) + \ba) \cap ((\affine A) + \ba)\\ &= (\bx + r B) \cap (\affine (A + \ba))\\ &\subseteq A + \ba. \end{split}\]
    1. Recall that \((C \cap D) + E \subseteq (C + E) \cap (D + E)\).

    2. \((\affine A) + \ba = \affine (A + \ba)\) since translation which is an affine transformation preserves affine hulls (Theorem 4.163).

  6. Thus, \(R + \ba \subseteq A + \ba\).

  7. Thus, \(R \subseteq A\).

  8. Thus, \(\by \in \relint A\).

  9. Thus, \(\bx - \ba \in \relint A\).

  10. Thus, \(\bx \in \relint A + \ba\).

Thus, \(\relint (A + \ba) \subseteq \relint A + \ba\).

For the converse, assume that \(\bx \in \relint A + \ba\).

  1. Then, \(\bx - \ba \in \relint A\).

  2. Let \(\by = \bx - \ba\).

  3. Then, there exists \(r > 0\) such that

    \[ (\by + r B ) \cap \affine A \subseteq A. \]
  4. Consider the set

    \[ R = (\bx + r B) \cap \affine (A + \ba). \]
  5. We have

    \[\begin{split} R - \ba &= ((\bx + r B) \cap \affine (A + \ba)) - \ba\\ &\subseteq ((\bx + r B) - \ba) \cap ((\affine (A + \ba)) - \ba)\\ &= (\by + r B) \cap (\affine (A + \ba) - \ba)\\ &= (\by + r B) \cap \affine A\\ &\subseteq A. \end{split}\]
  6. Thus, \(R - \ba \subseteq A\).

  7. Thus, \(R \subseteq A + \ba\).

  8. Thus, \(\bx \in \relint (A + \ba)\).

Thus, \(\relint A + \ba \subseteq \relint (A + \ba)\).

Together, we have

\[ \relint A + \ba = \relint (A + \ba) \]

7.11.7. Relative Interiors of Convex Sets#

Relative interiors play the role of interiors for convex sets. Much of the following discussion is focused on the relative interiors of convex sets (in finite dimensional real normed linear spaces).

Theorem 7.141 (Relative interior of a convex set is convex)

Let \(\VV\) be a real normed linear space. If \(C\) is a convex set of \(\VV\), then its relative interior is a convex set.

Proof. If \(C = \EmptySet\), then, \(\relint C = \EmptySet\) is convex. So, assume that \(C\) is nonempty.

  1. Let \(A = \affine C\) be the affine hull of \(C\).

  2. Let \(U = \relint C\) be the relative interior of \(C\).

  3. Let \(L = A - A\) be the linear subspace parallel to \(A\).

  4. Choose \(\bx, \by \in U\). Then, \(\bx, \by \in U \subseteq C \subseteq A\).

  5. Then, there exist open balls \(B(\bx, r_x)\) and \(B(\by, r_y)\) such that

    \[ B(\bx, r_x) \cap A \subseteq C \text{ and } B(\by, r_y) \cap A \subseteq C \]
  6. Let \(t \in (0,1)\).

  7. Let \(\bz = t \bx + (1-t)\by\). Note that \(\bz \in C \subseteq A\) since \(\bx, \by \in C\) and \(\bz\) is their convex combination.

  8. Choose \(r = \min(r_x, r_y)\). We shall show that

    \[ B(\bz, r) \cap A \subseteq C. \]

    Thus, we shall show that \(\bz \in \relint C\).

  9. Towards this, pick any \(\bw \in B(\bz, r) \cap A\).

  10. Let \(\bw = \bz + \ba\).

  11. \(\bw = \bz + \ba \in B(\bz, r) \implies \ba \in B(\bzero, r)\).

  12. \(\bw = \bz + \ba \in A \implies \ba \in A - \bz = L\).

  13. Thus, \(\| \ba \| < r\) and \(\ba \in L\).

  14. Let \(\bu = \bx + \ba\).

  15. Then, \(\bu \in L + \bx = A\) and \(\bu \in B(\bx, r) \subseteq B(\bx, r_x)\).

  16. Thus, \(\bu \in B(\bx, r_x) \cap A \subseteq C\).

  17. Let \(\bv = \by + \ba\).

  18. Then, \(\bv \in L + \by = A\) and \(\bv \in B(\by, r) \subseteq B(\by, r_y)\).

  19. Thus, \(\bv \in B(\by, r_y) \cap A \subseteq C\).

  20. Now,

    \[ \bw = \bz + \ba = t \bx + (1-t)\by + \ba = t (\bx + \ba) + (1-t) (\by + \ba) = t \bu + (1-t) \bv. \]
  21. Thus, \(\bw\) is a convex combination of \(\bu\) and \(\bv\).

  22. Since both \(\bu\) and \(\bv\) are in \(C\), hence \(\bw \in C\) as \(C\) is convex.

  23. We have shown that for every \(\bw \in B(\bz, r) \cap A\), \(\bw \in C\).

  24. Consequently,

    \[ B(\bz, r) \cap A \subseteq C. \]
  25. Thus, \(\bz \in \relint C = U\).

  26. Thus, for every \(\bx, \by \in U\) and \(t \in (0,1)\), \(\bz = t \bx + (1-t) \by \in U\).

  27. Thus, \(U\) is convex.

7.11.7.1. Nonempty Relative Interiors#

Theorem 7.142 (Nonempty relative interiors)

Let \(\VV\) be a real normed linear space. If \(C\) is a nonempty convex set, then its relative interior is nonempty.

Proof. Let \(A = \affine C\) and let \(\dim A = k\).

  1. Choose \(k+1\) affine independent points of \(C\): \(\bv_0, \dots, \bv_k\).

  2. Let \(H = \ConvexHull \{\bv_0, \dots, \bv_k \}\) be their convex hull.

  3. Since \(C\) is convex, it contains the convex hull \(H\); i.e., \(H \subseteq C\).

  4. \(H\) contains all convex combinations of \(\{\bv_0, \dots, \bv_k \}\).

  5. In particular, it contains the point:

    \[ \bv = \frac{1}{k+1} (\bv_0 + \dots + \bv_k). \]
  6. Note that \(\bv \in H \subseteq C\).

  7. Note that \(A = \affine C = \affine \{\bv_0, \dots, \bv_k \} = \affine H\).

  8. Thus, we can select a sufficiently small \(r > 0\) such that all points in \(B(\bv, r) \cap A\) are contained in \(H\).

  9. But then, \(B(\bv, r) \subseteq H \subseteq C\).

  10. Thus, \(\bv \in C\) and \(B(\bv, r) \cap A \subseteq C\).

  11. Thus, \(\bv \in \relint C\).

  12. Thus, the relative interior of \(C\) is nonempty.

7.11.7.2. Line Segment Property#

Theorem 7.143 (Line segment property of relative interior)

Let \(\VV\) be a real \(n\)-dimensional normed linear space. Let \(C\) be a nonempty convex subset of \(\VV\). Let \(\bx \in \relint C\) and \(\by \in \closure C\). Then,

\[ (1-t) \bx + t \by \in \relint C \Forall t \in [0,1). \]

Proof. This is a restatement of the line segment property for interior of a convex set as described in Theorem 7.126. If \(\relint C = \interior C\), then the proof of Theorem 7.126 applies directly.

This argument can be extended for the case where \(\relint C \neq \interior C\) by considering the subspace topology w.r.t. \(\affine C\).

The proof below is based on [5].

Proof. Let \(A = \affine C\). Let \(L\) be the linear subspace parallel to \(A\). Note that for \(t=0\), \((1-t)\bx + t \by = \bx\) which belongs to \(\relint C\) by hypothesis. Thus, we shall only consider \(t \in (0,1)\) in the argument below.

Assume first that \(\by \in C\).

  1. Since \(\bx \in \relint C\), there exists \(r > 0\) such that \(B(\bx, r) \cap A \subseteq C\).

  2. Pick any \(t \in (0, 1)\).

  3. Let \(\bz = (1-t) \bx + t \by\).

  4. Let \(s = (1 - t) r\). Clearly, \(s > 0\).

  5. Consider the open ball \(B(\bz, s)\). We shall show that \(B(\bz, s) \cap A \subseteq C\).

  6. Let \(\bu \in B(\bz, s) \cap A\).

  7. If \(\bu = \bz\), then \(\bu \in C\) since \(C\) is convex.

  8. Otherwise, we can write \(\bu = \bz + p \bv\) where \(\bv\) is a unit norm vector and \(0 < p < s\).

  9. Then, \(\bv \in L\) since \(\bz + p \bv \in A\) and \(\bz \in C \subseteq A\).

  10. We can write

    \[ \bu = \bz + p \bv = (1-t) \bx + t \by + p \bv = (1-t) \left (\bx + \frac{p}{1-t} \bv \right ) + t \by. \]
  11. Let \(\bw = \bx + \frac{p}{1-t} \bv\).

  12. Since \(p < s\), hence \(\frac{p}{1 - t} < \frac{s}{1-t} = r\).

  13. Thus, \(\bw \in B(\bx, r)\).

  14. Also, \(\bx \in C\) and \(\bv \in L\) implies that \(\bw \in A\).

  15. Thus, \(\bw \in B(\bx, r) \cap A \subseteq C\).

  16. Now \(\bu = (1-t) \bw + t \by\) is a convex combination of \(\bw, \by \in C\).

  17. Hence \(\bu \in C\).

  18. Thus, for every \(\bu \in B(\bz, s) \cap A\), \(\bu \in C\).

  19. Thus, \(\bz \in \relint C\).

  20. Thus, \((1-t) \bx + t \by \in \relint C \Forall t \in [0,1)\).

We now consider the case where \(\by \notin C\) but \(\by \in \closure C\).

  1. There exists a sequence \(\{ \by_k \}\) of \(C\) such that \(\by = \lim \by_k\).

  2. Since \(\bx \in \relint C\), there exists \(r > 0\) such that \(B(\bx, r) \cap A \subseteq C\).

  3. Pick any \(t \in (0, 1)\).

  4. Let \(\bz = (1-t) \bx + t \by\).

  5. Let \(\bz_k = (1-t)\bx + t \by_k\).

  6. Then, by the earlier argument \(\bz_k \in \relint C\) since \(\bx \in \relint C\), \(\by_k \in C\) and \(t \in (0,1)\).

  7. Specifically, for every \(k\), \(B(\bz_k, (1-t) r) \cap A \subseteq C\).

  8. By limit arithmetic

    \[ \lim \bz_k = (1-t)\bx + t \lim \by_k = (1-t)\bx + t \by = \bz. \]
  9. Let \(s = \frac{1}{2} (1-t)r\).

  10. Then, there exists \(n_0 \in \Nat\) such that for all \(k > n_0\), \(\| \bz - \bz_k \| < s\).

  11. Consider the set \(B(\bz, s) \cap A\).

  12. Let \(\bu \in B(\bz, s) \cap A\).

  13. Then for every \(k > n_0\),

    \[ \| \bu - \bz_k \| \leq \| \bu - \bz \| + \| \bz - \bz_k \| < s + s = (1-t)r. \]
  14. Thus, \(\bu \in B(\bz_k, (1-t) r) \cap A \subseteq C\) for every \(k > n_0\).

  15. Thus, \(B(\bz, s) \cap A \subseteq C\).

  16. Thus, \(\bz \in \relint C\).

One way to interpret this result is as follows. If we draw a line segment between a point in the relative interior of a convex set \(C\) and a point on the boundary of \(C\), then every point on the segment (except the boundary point) lies inside the relative interior of \(C\).

Theorem 7.144 (Characterization of relative interior in terms of line segments)

Let \(\VV\) be a real \(n\)-dimensional normed linear space. Let \(C\) be a nonempty convex subset of \(\VV\). Then, \(\bx \in \relint C\) if and only if every line segment in \(C\) having \(\bx\) as one endpoint can be prolonged beyond \(\bx\) without leaving \(C\); i.e., for every \(\by \in C\) there exists \(s > 1\) such that

\[ \bx + (s -1) (\bx - \by) \in C. \]

At \(s=0\), we get the point \(\by\). At \(s=1\), we get the point \(\bx\). At \(s=\frac{1}{2}\), we get the point \(\frac{1}{2} (\bx + \by)\). Thus, the formula represents a line starting from \(\by\) going in the direction \(\bx - \by\) towards \(\bx\). For \(s > 1\), it further extends beyond \(\bx\). This is sensible since \(\bx \in \relint C\) hence the line can be extended beyond \(\bx\). It is definitely not possible to extend the line beyond \(\by\) if \(\by \in C \setminus \relint C\).

Proof. Let \(A = \affine C\). Let \(L\) be the linear subspace parallel to \(A\).

  1. Assume that \(\bx \in \relint C\).

  2. Then, there exists \(r > 0\) such that \(B(\bx, r) \cap A \subseteq C\).

  3. Let \(\by \in C\).

  4. Then \(\bv = \bx - \by \in L\).

  5. Let \(\bu = \frac{r}{2 \| \bv \|} \bv\).

  6. Since \(\bx \in C \subseteq A\) and \(\bu \in L\), hence \(\bx + \bu \in A\).

  7. \(\| \bu \| = \frac{r}{2} < r\). Hence, \(\bx + \bu \in B(\bx, r)\).

  8. Thus, \(\bx + \bu \in B(\bx, r) \cap A \subseteq C\).

  9. Clearly,

    \[ \bx + \bu = \bx + \frac{r}{2 \| \bx - \by \|} (\bx - \by). \]
  10. Let \(s = 1 + \frac{r}{2 \| \bx - \by \|}\).

  11. Then, \(\bx + (s - 1) (\bx - \by) = \bx + \bu \in C\).

For the converse, assume that the said condition holds for some \(\bx \in C\).

  1. By Theorem 7.142, \(\relint C\) is nonempty.

  2. Let \(\by \in \relint C\).

  3. If \(\by = \bx\) then \(\bx \in \relint C\) and there is nothing to prove.

  4. Now consider the case where \(\by \neq \bx\).

  5. By hypothesis, since \(\by \in C\), hence there exists \(s > 1\) such that

    \[ \bz = \bx + (s - 1) (\bx - \by) \in C. \]

    Going from \(\by\) to \(\bx\), the point \(\bz\) is behind \(\bx\). Thus, \(\bx\) is between \(\bz\) and \(\by\).

  6. Let \(t = \frac{1}{s}\). Then, \(t \in (0, 1)\).

  7. Now,

    \[\begin{split} \bz = \bx + \left (\frac{1}{t} - 1 \right ) (\bx - \by) \\ & \iff t \bz = t \bx + (1 - t) (\bx - \by) \\ & \iff t \bz = \bx - (1-t) \by \\ & \iff \bx = t \bz + (1-t) \by. \end{split}\]

    We have shown that \(\bx\) is a convex combination of \(\by\) and \(\bz\).

  8. Thus, \(\by \in \relint C\), \(\bz \in C\) and \(t \in (0, 1)\).

  9. By line segment property, \(\bx \in \relint C\).

Several topological properties follow.

7.11.7.3. Affine Hull of Relative Interior#

Theorem 7.145 (Affine hull of relative interior)

Let \(\VV\) be a real \(n\)-dimensional normed linear space. For any nonempty convex set \(C \subseteq \VV\),

\[ \affine \relint C = \affine C. \]

In other words, the affine hull of the relative interior of a convex set is same as the affine hull of the set.

Proof. Let \(A = \affine C\). Let \(R = \relint C\).

  1. From Theorem 7.141, \(R\) is convex.

  2. From Theorem 7.142, \(R\) is nonempty.

  3. Let \(m = \dim A\).

  4. If \(m=0\) then \(C = A = \{ \bx \}\) is a singleton. Also, by Theorem 7.133, \(R = C = A\). Thus, \(\affine R = \affine C\).

  5. We now consider the case where \(m > 0\).

  6. Then, there exist \(m+1\) affine independent vectors \(\bx_0, \dots, \bx_m \in C\) such that

    \[ A = \affine C = \span \{ \bx_0, \dots, \bx_m \}. \]
  7. Pick some \(\bx \in R\). Since \(R\) is nonempty, hence we can pick such \(\bx\).

  8. Consider the points \(\by_i = \frac{1}{2} \bx + \frac{1}{2} \bx_i\) for \(i=0, \dots, m\).

  9. By line segment property, \(\by_i \in R\) since \(\bx \in R\) and \(\bx_i \in C\).

  10. We now claim that \(\{ \by_0, \dots, \by_m \}\) are affine independent.

    1. For contradiction, assume that they are affine dependent.

    2. Then, \(\bu_i = \by_i - \by_0\) for \(i=1,\dots, m\) are linearly dependent.

    3. Thus, there exists a nontrivial linear combination

      \[ \sum_{i=1}^m t_i \bu_i = \bzero. \]
    4. But

      \[\begin{split} \sum_{i=1}^m t_i \bu_i & = \sum_{i=1}^m t_i (\by_i - \by_0)\\ & = \sum_{i=1}^m t_i \left ( \frac{1}{2} \bx + \frac{1}{2} \bx_i - \frac{1}{2} \bx - \frac{1}{2} \bx_0 \right )\\ & = \frac{1}{2}\sum_{i=1}^m t_i (\bx_i - \bx_0) = \bzero. \end{split}\]
    5. Thus, \(\bx_i - \bx_0\) for \(i=1,\dots,m\) are linearly dependent.

    6. Thus, \(bx_i\) for \(i=0,\dots,m\) are affine dependent which contradicts our hypothesis.

  11. Thus \(R\) has \(m+1\) affine independent points given by \(\{ \by_0, \dots, \by_m \}\).

  12. Thus, \(\affine R = A\).

7.11.7.4. Simplex#

Theorem 7.146 (Relative interior of a simplex)

Let \(k+1\) points \(\bv_0, \dots, \bv_k \in \VV\) be affine independent. Let the simplex determined by them be given by

\[ C = \convex \{ \bv_0, \dots, \bv_k\} = \{ t_0 \bv_0 + \dots + t_k \bv_k \ST \bt \succeq \bzero, \bone^T \bt = 1\}. \]

Then, the relative interior of \(C\) is given by

\[ \relint C = \{ t_0 \bv_0 + \dots + t_k \bv_k \ST \bt \succ \bzero, \bone^T \bt = 1\} \]

The relative boundary of \(C\) is given by

\[ \relbd C = \{ t_0 \bv_0 + \dots + t_k \bv_k \ST \bt \succeq \bzero, \bone^T \bt = 1, t_i = 0 \text{ for some } i \}. \]

Proof. TBD

Theorem 7.147 (Barycenter of a simplex is a relative interior point)

Let \(k+1\) points \(\bv_0, \dots, \bv_k \in \VV\) be affine independent. Let the simplex determined by them be given by

\[ C = \convex \{ \bv_0, \dots, \bv_k\} = \{ t_0 \bv_0 + \dots + t_k \bv_k \ST \bt \succeq 0, \bone^T \bt = 1\} \]

Let the barycenter of the simplex by given by \(\bv = \sum_{i=0}^k \frac{1}{k+1}{\bv_i}\). Then, \(\bv \in \relint C\).

In other words, the barycenter of a simplex lies in the relative interior.

Proof. We first claim that the distance of the barycenter from each of the vertices of the simplex is positive.

  1. Let \(d_i = \| \bv_i - \bv \|\) for \(i=0,\dots,k\).

  2. For contradiction, assume that \(d_i = 0\) for some \(i\).

  3. Without loss of generality, assume that it holds for \(i=0\). We can shuffle the vertices for this.

  4. Then,

    \[\begin{split} \bv_0 = \sum_{j=0}^k \frac{1}{k+1}{\bv_j} \\ &\iff (k+1) \bv_0 = \sum_{j=0}^k \bv_j \\ &\iff \sum_{j=0}^k \bv_j - (k+1) \bv_0 = \bzero \\ &\iff \sum_{j=1}^k \bv_j - k \bv_0 = \bzero \\ &\iff \sum_{j=1}^k (\bv_j - \bv_0) = \bzero. \end{split}\]
  5. Thus, the vectors \(\bv_1 - \bv_0, \dots, \bv_k - \bv_0\) are linearly dependent.

  6. That means \(\bv_0, \dots, \bv_k\) are affine dependent. A contradiction.

  7. Hence, \(d_i > 0\) for every \(i=0,\dots,k\).

Let \(A = \affine C\). We now let \(r = \min \{ d_0, \dots, d_m \}\). We claim that \(B(\bv, r) \cap A \subseteq C\).

  1. Let \(\bu \in B(\bv, r) \cap A\).

  2. Since \(\bu \in A\) and \( \{ \bv_0, \dots, \bv_k\}\) provide an affine basis for \(A\), hence, there is a unique affine representation for \(\bu\) given by

    \[ \bu = \sum_{i=0}^k u_i \bv_i, \sum_{i=0}^k u_i = 1. \]

TBD

Theorem 7.148 (Relative interior of convex hull of linearly independent points)

Let \(\VV\) be a real normed linear space. Let \(S = \{\bv_1, \dots, \bv_m \}\) be a set of \(m\) linearly independent vectors.

\[ X = \left \{ \bx \ST \bx = \sum_{i=1}^m t_i \bv_i, \sum_{i=1}^m t_i < 1, t_i > 0, i=1,\dots,m \right \}. \]

Let \(A = \span S\). Then, \(X\) is open relative to \(A\).

Proof. It is clear that \(X \subseteq A\). By \(X\) being open relative to \(A\) we mean that for every \(\bx \in X\), there exists \(r > 0\) such that \(B(\bx, r) \cap A \subseteq X\).

We first establish that \(X\) is convex.

  1. Let \(\bx, \by \in X\) and \(t \in (0, 1)\).

  2. Then,

    \[ \bx = \sum_{i=1} x_i \bv_i \text{ and } \by = \sum_{i=1} y_i \bv_i \]

    such that \(x_i , y_i > 0\), \(\sum_{i=1} x_i < 1\), \(\sum_{i=1} y_i < 1\).

  3. Let \(\bz = t \bx + (1-t) \by\).

  4. Then,

    \[ \bz = \sum_{i=1}^m (t x_i + (1-t) y_i) \bv_i. \]
  5. Then \(t x_i + (1-t) y_i > 0\) since \(t > 0, 1-t > 0, x_i > 0, y_i > 0\).

  6. Also

    \[ \sum_{i=1}^m (t x_i + (1-t) y_i) = t \sum_{i=1}^m x_i + (1-t) \sum_{i=1}^m y_i < t + 1 - t = 1. \]
  7. Thus, \(\bx \in X\).

  8. Thus, \(X\) is convex.

We next show that \(\bc = \frac{1}{m} (\bx_1 + \dots + \bx_m) \in \relint X\).

We now show that \(X\) is relatively open.

  1. Let \(\bx \in X\). Then

    \[ \bx = \sum_{i=1}^m t_i \bv_i \ST \sum_{i=1}^m t_i < 1, t_i > 0, i=1,\dots,m. \]
  2. Let \(t = \sum_{i=1}^m t_i\) and \(s = 1 - t\). Then, \(s > 0\).

  3. Let \(r = \frac{s}{2 m}\).

  4. Let \(p_i = t_i + r\). Then, \(p_i > 0\) and

    \[ \sum_{i=1}^m p_i = \sum_{i=1}^m t_i + \sum_{i=1}^m r = t + \frac{s}{2} = t + \frac{1 - t}{2} < 1. \]

TBD.

7.11.7.5. Closure of Relative Interior#

Theorem 7.149 (Closure of relative interior)

Let \(\VV\) be a real finite dimensional normed linear space. For any convex set \(C \subseteq \VV\),

\[ \closure \relint C = \closure C. \]

Proof. If \(C\) is empty, then this equality holds trivially. We shall now consider the case where \(C\) is nonempty.

Since \(\relint C \subseteq C\), hence \(\closure \relint C \subseteq \closure C\).

For the other direction, we proceed as follows:

  1. Let \(\by \in \closure C\).

  2. By Theorem 7.142, the relative interior of \(C\) is nonempty.

  3. Choose some \(\bx \in \relint C\).

  4. Assume that \(\bx \neq \by\) (otherwise we are done).

  5. By Theorem 7.143, the line segment between \(\bx\) and \(\by\) (excluding \(\by\)) lies in \(\relint C\).

  6. Hence, \(\by\) is a closure point of \(\relint C\).

    1. Let \(\bz_k = \frac{1}{k} \bx + \left (1- \frac{1}{k} \right ) \by\) for every \(k \in \Nat\).

    2. Since \(\bx \in \relint C\), \(\by \in \closure C\), \(\frac{1}{k} \in (0,1]\), hence \(\bz_k \in \relint C\) for every \(k\).

    3. Thus, \(\{ \bz_k \}\) is a sequence of \(\relint C\).

    4. We can see that \(\lim \bz_k = \by\).

    5. Thus, by Theorem 3.31, \(\by\) is a closure point of \(\relint C\).

  7. Thus, \(\by \in \closure \relint C\).

  8. Thus, \(\closure C \subseteq \closure \relint C\).

Combining the two inclusions, we get:

\[ \closure \relint C = \closure C. \]

7.11.7.6. Relative Interior of Closure#

Theorem 7.150 (Relative interior of closure)

Let \(\VV\) be a real finite dimensional normed linear space. For any convex set \(C \subseteq \VV\),

\[ \relint \closure C = \relint C. \]

Proof. The statement is trivial for \(C = \EmptySet\). We shall assume that \(C\) is nonempty.

By Theorem 7.137 \(\relint C \subseteq \relint \closure C\) holds true for any set \(C\).

For the converse, assume that \(\bx \in \relint \closure C\). Our goal is to show that \(\bx \in \relint C\). Towards this, we have to find points \(\by \in \relint C\) and \(\bz \in \closure C\) such that \(\bx\) lies on the line segment between \(\by\) and \(\bz\). Since, \(C\) is nonempty and convex, it is easy to pick a point \(\by \in \relint C\). Then, on the path from \(\by\) to \(\bx\), the point \(\bz\) must be behind \(\bx\) and yet not too far behind \(\bx\) so that we can ensure that \(\bz\) is indeed in \(\closure C\). That is where we use the fact that there is a ball around \(\bx\) whose intersection with \(\affine C\) is totally inside \(\closure C\).

  1. We have, \(\bx \in \closure C\) and there exists \(r > 0\) such that

    \[ (\bx + r B) \cap \affine (\closure C) \subseteq \closure C. \]
  2. Recall from Theorem 4.170 that \(\affine (\closure C) = \affine C\).

  3. Thus, there exists \(r > 0\) such that

    \[ (\bx + r B) \cap \affine C \subseteq \closure C. \]
  4. By Theorem 7.142, the relative interior of \(C\) is nonempty.

  5. Choose a point \(\by \in \relint C\).

  6. Let \(t = \frac{r}{2\| \bx - \by \|}\).

  7. Define

    \[ \bz = (1 + t) \bx - t \by. \]
  8. \(\bz\) is an affine combination of \(\bx\) and \(\by\). Since \(\bx \in \closure C\) and \(\by \in \relint C \subseteq \closure C\), hence \(\bz \in \affine (\closure C) = \affine C\).

  9. Also note that

    \[\begin{split} d(\bz, \bx) &= \| \bz - \bx \|\\ &= \|(1 + t) \bx - t \by - \bx \|\\ &= t \| \bx - \by \| = \frac{r}{2}. \end{split}\]
  10. Hence, \(\bz \in B(x, r)\).

  11. Thus, \(\bz \in B(x, r) \cap \affine C \subseteq \closure C\).

  12. Thus, \(\bz \in \closure C\).

  13. We have found the points \(\by \in \relint C\) and \(\bz \in \closure C\).

  14. Now note that,

    \[ \bx = \frac{t}{1+t} \by + \frac{1}{1+t} \bz. \]
  15. Thus, \(\bx\) is a convex combination of \(\by\) and \(\bz\).

  16. Since \(t > 0\), hence \(\bx\) lies in the line segment between \(\bz\) and \(\by\).

  17. By the line segment property, the line segment between \(\bz\) and \(\by\) (excluding \(\bz\)) lies in \(\relint C\).

  18. Hence, \(\bx \in \relint C\).

Thus, we have shown that \(\relint \closure C \subseteq \relint C\) as desired.

7.11.7.7. Identical Closures and Relative Interiors#

Theorem 7.151 (Same closure means same relative interior)

Let \(\VV\) be a real finite dimensional normed linear space.

Let \(C_1\) and \(C_2\) be convex subsets of \(\VV\). Then,

\[ \closure C_1 = \closure C_2 \iff \relint C_1 = \relint C_2. \]

In other words, if closures are same, then relative interiors must be same too and vice versa.

Proof. From Theorem 7.149, \(\closure \relint C = \closure C\) and from Theorem 7.150, \(\relint \closure C = \relint C\) for any convex set \(C\).

Assume \(\closure C_1 = \closure C_2\). Then,

\[ \relint C_1 = \relint \closure C_1 = \relint \closure C_2 = \relint C_2. \]

Now, assume \(\relint C_1 = \relint C_2\). Then,

\[ \closure C_1 = \closure \relint C_1 = \closure \relint C_2 = \closure C_2. \]

We are done.

Theorem 7.152 (Characterization of identical closures and relative interiors)

Let \(\VV\) be a real \(n\)-dimensional normed linear space. Let \(C_1\) and \(C_2\) be convex subsets of \(\VV\). Then, the following statements are equivalent.

  1. Both sets have same relative interior.

  2. Both sets have same closure.

  3. \( \relint C_1 \subseteq C_2 \subseteq \closure C_1\).

Proof. By Theorem 7.151, statements (1) and (2) are equivalent.

Assume (3) to be true.

  1. Taking closure on all sides, we get

    \[ \closure \relint C_1 \subseteq \closure C_2 \subseteq \closure \closure C_1. \]
  2. By Theorem 7.149, \(\closure \relint C_1 = \closure C_1\).

  3. Since closed sets are their own closures, hence \(\closure \closure C_1 = \closure C_1\).

  4. Thus, it reduces to

    \[ \closure C_1 \subseteq \closure C_2 \subseteq \closure C_1. \]
  5. Thus, \(\closure C_1 = \closure C_2\) must hold true which is (2).

Now, assume (1) and (2) to be true.

  1. Then, \(\relint C_2 \subseteq C_2\).

  2. Also, \(\relint C_1 = \relint C_2\) from (1).

  3. Hence, \(\relint C_1 \subseteq C_2\).

  4. Further, \(C_2 \subseteq \closure C_2 = \closure C_1\) from (2).

  5. Combining, we get \(\relint C_1 \subseteq C_2 \subseteq \closure C_1\) which is (3).

7.11.7.8. Finite Intersections#

Theorem 7.153 (Finite intersections preserve closure)

Let \(\VV\) be a real finite dimensional normed linear space.

Let \(C_1, \dots, C_n\) be convex subsets of \(\VV\) such that \(\cap_i \relint C_i \neq \EmptySet\). Then,

\[ \closure \left( \bigcap_{i=1}^n C_i \right) = \bigcap_{i=1}^n \closure C_i. \]

Theorem 7.154 (Finite intersections preserve relative interior)

Let \(\VV\) be a real finite dimensional normed linear space.

Let \(C_1, \dots, C_n\) be convex subsets of \(\VV\) such that \(\cap_i \relint C_i \neq \EmptySet\). Then,

\[ \relint \left( \bigcap_{i=1}^n C_i \right) = \bigcap_{i=1}^n \relint C_i. \]

Theorem 7.155 (Intersection with affine set preserves relative interior and closure)

Let \(\VV\) be a real finite dimensional normed linear space. Let \(C\) be a convex set of \(\VV\) and \(M\) be an affine set of \(\VV\) such that \(M\) has a nonempty intersection with \(\relint C\). Then,

\[ \relint (M \cap C) = M \cap \relint C. \]

Also,

\[ \closure (M \cap C) = M \cap \closure C. \]

Proof. Since \(\VV\) is finite dimensional, hence

\[ \relint M = \closure M = M \]

due to Theorem 4.168 and Theorem 7.138.

Now, by Theorem 7.154:

\[ \relint (M \cap C) = (\relint M) \cap (\relint C) = M \cap \relint C. \]

Similarly, by Theorem 7.153,

\[ \closure (M \cap C) = (\closure M) \cap (\closure C) = M \cap \closure C. \]

Here is another possible condition under which the containment of relative interior holds.

Theorem 7.156 (Containment of relative interior)

Let \(\VV\) be a real finite dimensional normed linear space. Let \(C_1\) and \(C_2\) be convex sets of \(\VV\) such that \(C_2 \subseteq \closure C_1\) but \(C_2 \not\subseteq \closure C_1 \setminus \relint C_1\). Then,

\[ \relint C_2 \subseteq \relint C_1. \]

In other words, if \(C_2\) is a subset of the closure of \(C_1\) but \(C_2\) is not contained totally inside the relative boundary of \(C_1\), then relative interior of \(C_2\) is a subset of the relative interior of \(C_1\).

Here is an example situation.

  1. Let \(H\) be a hyperplane.

  2. Let \(H_+\) be a corresponding nonnegative closed halfspace.

  3. Then, the boundary (also relative boundary) of \(H_+\) is \(H\).

  4. The interior (also relative interior) of \(H_+\) is the positive open halfspace \(H_{++}\).

  5. Let \(C\) be contained inside \(H_+\) such that \(C \not\subseteq H\). In other words, \(C\) is not totally contained inside the boundary of \(H_+\) which is \(H\).

  6. Then, \(\relint C \subseteq H_{++}\).

  7. Here \(C_1 = H_{++}\) and \(C_2 = C\).

  8. Note that \(C \not\subseteq H_{++}\) but \(C \subseteq \closure H_{++} = H_+\).

  9. \(\closure C_1 \setminus \relint C_1 = \closure H_{++} \setminus \relint H_{++} = H_+ \setminus H_{++} = H\).

Proof. Due to Theorem 7.150

\[ \relint \closure C_1 = \relint C_1. \]

7.11.7.9. Sum of Sets#

Theorem 7.157 (Relative interior of sum of two sets)

Let \(\VV\) be a real finite dimensional normed linear space. Let \(C_1\) and \(C_2\) be convex sets of \(\VV\). Then,

\[ \relint (C_1 + C_2) = \relint C_1 + \relint C_2. \]

Theorem 7.158 (Closure of sum of two sets)

Let \(\VV\) be a real finite dimensional normed linear space. Let \(C_1\) and \(C_2\) be convex sets of \(\VV\). Then,

\[ \closure (C_1 + C_2) \supseteq \closure C_1 + \closure C_2. \]

7.11.7.10. Affine Transformations#

Theorem 7.159 (Affine transformations preserve relative interiors)

Let \(\VV\) and \(\WW\) be finite dimensional normed linear spaces. An affine transformation \(T : \VV \to \WW\) preserves relative interiors of convex sets.

\[ T (\relint C) = \relint (T (C)) \]

for any convex subset \(C\) of \(\VV\).

Proof. By Theorem 4.171, \(T\) is continuous.

Assume \(C\) is a convex subset of \(\VV\). We shall first show that \(\relint T(C) \subseteq T (\relint C)\).

  1. We recall that \(\relint C \subseteq C \subseteq \closure C\).

  2. Thus, \(T (\relint C) \subseteq T (C) \subseteq T (\closure C)\).

  3. By Theorem 7.149, \(\closure \relint C = \closure C\).

  4. Thus, \(T (\closure C) = T (\closure \relint C)\).

  5. By Theorem 4.172, \(T (\closure \relint C) \subseteq \closure T(\relint C)\).

  6. Thus,

    \[ T (\relint C) \subseteq T (C) \subseteq \closure T(\relint C). \]
  7. Letting \(C_1 = T (\relint C)\) and \(C_2 = T(C)\), we see that

    \[ \relint C_1 \subseteq C_1 \subseteq C_2 \subseteq \closure C_2. \]
  8. Thus, by Theorem 7.152 (3), \(\relint C_1 = \relint C_2\). Thus,

    \[ \relint T(C) = \relint T (\relint C) \subseteq T (\relint C). \]

To show the reverse inclusion, we proceed as follows.

  1. Let \(\bx \in T (\relint C)\).

  2. Then, there exists \(\bu \in \relint C\) such that \(\bx = T (\bu)\).

  3. Also, it implies that \(\bx \in T(C)\).

  4. Take any other \(\by \in T (C)\).

  5. Then, there is \(\bv \in C\) such that \(\by = T(\bv)\).

  6. By Theorem 7.144, there exists \(s > 1\) such that

    \[ \bw = \bu + (s -1)(\bu - \bv) \in C \]

    since \(\bu \in \relint C\) and \(\by \in C\).

  7. Then, \(\bz = T (\bw) \in T(C)\).

  8. Note that with \(t = \frac{1}{s}\),

    \[ \bu = t \bw + (1- t) \bv. \]
  9. Thus, \(\bu\) is a convex combination (and hence affine combination) of \(\bw\) and \(\bv\).

  10. Since \(T\) is affine, hence

    \[ T (\bu) = t T(\bw) + (1-t) T(\bv). \]
  11. This is same as:

    \[ \bx = t \bz + (1-t) \by. \]
  12. This can be rewritten as

    \[ \bz = \bx + (s-1)(\bx - \by) \]

    with \(\bz \in C\).

  13. Thus, for every \(\by \in T(C)\), there exists \(s > 1\) such that

    \[ \bz = \bx + (s -1) (\bx - \by) \in C. \]
  14. Thus, by Theorem 7.144, \(\bx \in \relint T(C)\).

  15. Thus, \(T (\relint C) \subseteq \relint T(C)\).

Combining the two inclusions, we get the equality

\[ T (\relint C) = \relint T(C). \]