Relative Interior of the relative interior of a convex set

Question

Let $X \subseteq \mathbb R^n$ be a convex set. I'm curious whether the relative interior of the relative interior of X is equal to the relative interior of X, i.e., using the notation in this Wikipedia article,

$$\text{relint}(\text{relint}(X)) = \text{relint}(X). $$

Definition of $\text{relint}(X)$ for a convex set $X$ can be reduced to the following: $$\text{relint}(X):=\left\{ x \in X \ | \ \forall y\in X \ \exists \lambda>1 \text{ s.t. } \lambda x + (1- \lambda) y \in X \right\}$$

$\text{relint}(X)$ is also a convex set, which implies that $$\text{relint}(\text{relint}(X)):=\left\{ x \in \text{relint}(X) \ | \ \forall y\in \text{relint}(X) \ \exists \lambda>1 \text{ s.t. } \lambda x + (1- \lambda) y \in \text{relint}(X) \right\}$$

I couldn't show that these two sets are subsets of each other. Does anyone have any idea on whether these sets are equal or not?

Answer 1

As mentioned in the comments, $\text{ri ri }X \subset \text{ri }X$ by definition, so it suffices to show $x \in \text{ri } X$ implies $x \in \text{ri ri }X$.

The intuition of the definition of $x$ being in the relative interior is that from any other point $y \in X$ there is a point "behind" $x$ on the line affinely spanned by $x$ and $y$. To show that $x \in \text{ri }X$ implies $x \in \text{ri ri }X$, we will be exploiting this property a fair bit. I'll first give the intuition of the argument, and then make it rigorous.

As already mentioned our goal is to show that any $x \in \text{ri }X$ is also in $\text{ri ri }X$, and to do this we need to show that from any other point $y$ in the relative interior there is a point $z$ in the relative interior behind $x$. Since $x,y \in X$ there is a point $z'$ behind $x$ that is in $X$. If $z'$ is in the relative interior then $z'$ is our desired $z$. Otherwise the point halfway between $z'$ and $x$ will be our desired $z$ (and we'll call this point $z$ from here on out).

To show that $z$ is in the relative interior we need to show that there is always a point in $X$ behind it when approaching it from any point $a \in X$. (Note that we may assume $a$ does not lie on the line segment containing $x,y,z$ and $z'$.) Here's how we do that:

Start from $a$ and go to the point $b \in X$ that is behind $x$. By convexity every point on the line segment $L$ from $b$ to $z'$ is in $X$, so if we extend the line segment from $a$ to $z$ through $z$ and it intersects $L$ then we get a point $c \in X$ that is behind $z$ when approaching from $a$. I recommend drawing a picture to understand this better.

Suppose $x \in \text{ri }X$ and $y$ be any other point in the relative interior. By definition there exists $\lambda > 1$ such that $z':= \lambda x + (1 - \lambda)y \in X$. If $z'$ is in the relative interior then we're done so suppose not. We claim that $z:= \frac{1 + \lambda} 2 x + \frac {1 - \lambda } 2y$ is in the relative interior. Note that $z$ is already in $X$ by convexity.

Let $a \in \text{ri }X$ be arbitrary. Then there exists $\mu > 1$ such that $b:= \mu x + (1 - \mu)a$ is in $X$. As mentioned, we want a point $c \in X$ that is behind $z$ when approaching from $a$. This point can either be written as a convex combination of $b$ and $z'$ (whence being in $X$ by convexity), or it can be written as an affine combination of $a$ and $z$ i.e. there exists $\alpha > 1 > \beta > 0$ such that:

$$ c = \alpha z + (1 - \alpha)a = \alpha \frac{1 + \lambda} 2 x + \alpha \frac{1 - \lambda} 2 y + (1 - \alpha) a $$

and

$$c = \beta b + (1 - \beta) z' = \beta \mu x + \beta (1 - \mu) a + (1-\beta) \lambda x + (1 - \beta)(1-\mu)y$$

In the two equations for $c$, comparing the coefficients of any of $x,a,$ and $y$ gives us e.g. looking at the coefficients of $y$ in the two equations gives us

$$ \alpha \frac{1- \lambda}2 = (1 - \beta)(1-\lambda) $$

which is a linear equation which is true if and only if $\alpha = 2(1 - \beta)$. By examining the analogous equation obtained by comparing the coefficients of $a$, we see that $\beta = \frac 1 {1 + \mu}$, and this can be verified by looking at the coefficients of $x$. From here it is easy to see $\alpha > 1 > \beta > 0$ as desired, proving that such a point $c$ exists and thus completing the proof that $z \in \text{ri }X$ and also $x \in \text{ri ri } X$ as desired.

Answer 2

Assuming convexity of the set $X \subseteq \mathbb{R}^{n}$ is not necessary, the identity $\mathrm{ri}(\mathrm{ri} X) = \mathrm{ri} X$ holds for any set $X$ (where I have used $\mathrm{ri}$ as a shorthand notation for $\mathrm{relint}$).

Indeed, letting $B = \{x \in \mathbb{R}^{n} : \|x\| \leq 1\}$ denote the unit ball with respect to any norm and letting $\mathrm{aff}(X)$ denote the affine hull of the set $X$, the definition of $\mathrm{ri} X$ can be restated as $$ \mathrm{ri} X = \{x \in X: \exists \varepsilon_{x} > 0 \text{ such that } (x + \varepsilon_{x} B) \cap \mathrm{aff}(X) \subseteq X\}, $$ which is the definition used in Rockafellar's textbook.

We now proceed to prove that $\mathrm{ri}(\mathrm{ri} X) = \mathrm{ri} X$ irrespective of whether $X$ is convex or not. As noted in the comments, the direction $\mathrm{ri} (\mathrm{ri} X) \subseteq \mathrm{ri} X$ is obvious by the definition of $\mathrm{ri} X$.

To prove the other direction, suppose that $x \in \mathrm{ri} X$. Then, there must exist an $\varepsilon_{x} > 0$ such that $(x + \varepsilon_{x}B)\cap \mathrm{aff}(X) \subseteq X$. The last equation can be rewritten as $$ \left( \left(x + \frac{\varepsilon_{x}}{2}B\right) + \frac{\varepsilon_{x}}{2}B \right) \cap \mathrm{aff}(X) \subseteq X $$ which in particular implies that $X \cap (x + \frac{\varepsilon_{x}}{2} B) \subseteq \mathrm{ri} X$. By definition of the relative interior, this in turn implies that $x \in \mathrm{ri}(\mathrm{ri} X)$, thus completing our proof.