2

I'd like to show ri(C1-C2)=ri(C1)-ri(C2) without using the fact that relative interior is preserved under linear transformations. I.e. Is there a way to show this by showing both inclusions?

RV702
  • 111

3 Answers3

1

Yes you can show it by both inclusions. It is tedious but good exercise.

  1. $ri(C_1-C_2)\subset ri(C_1)-ri(C_2)$. Proof: pick $c\in ri(C_1-C_2) \Leftrightarrow c=\alpha x + (1-\alpha) y$ for $x,y\in C_1-C-2$ and $\alpha \in(0,1)$. Moreover $x\in C_1-C_2$ if and only if $x=x_1-x_2$ with $x_1\in C_1$ and $x_2\in C_2$ and the same goes for $y$. So we have $y=y_1-y_2$ with $y_1\in C_1$ and $y_2\in C_2$. $\;$ Now : $$ c= \alpha x + (1-\alpha) y=\underbrace{\alpha x_1 + (1-\alpha) y_1}_{\in\, ri(C_1)} - \left(\underbrace{ \alpha x_2+(1-\alpha) y_2}_{\in\, ri(C_2)} \right)\in ri(C_1)-ri(C_2)$$
  2. $ri(C_1-C_2)\supset ri(C_1)-ri(C_2)$. We want to pick an arbitrary $c\in ri(C_1)-ri(C_2)$ and show it belongs to $ri(C_1-C_2)$. It is essentially doing step 1 backwards. I will leave this as an exercise.
  3. Above assumes the space is finite dimensional so the algebraic interior coincides with the relative interior for convex sets. To prove the first "iff": if x is in the algebraic interior of a convex set then for any y and for some t (scalar) we have x+t.y also is in the algebraic interior, call this point x1=x+t.y. Now consider the point −y then there is some also some small scalar r such that x2=x+r(−y) is also in the algebraic interior. Clearly x lies in the line that connects x1 and x2 so then we can express x as a convex combination them.
  4. Jan van Tiel's little book: "Convex Analysis, An Introductory Text" is a wonderful help for these type of problems.
Sergio Parreiras
  • 3,813
  • Thanks for your help @sergio. One question: you've used the fact that x\in ri(X) iff x=\alpha z+(1-\alpha)y for z,y \in X, \alpha \in (0,1). I haven't seen this result before, do you mind giving me a proof or a link to a proof online? I haven't been able to find Jan van Tiel's book yet. But apart from this, I replicated your working for the reverse inclusion: take c \in ri(C_1)-ri(C_2) i.e. c=c_1-c_2 for c_1\in ri(C_1) and c_2 \in ri(C_2) – RV702 Nov 09 '13 at 01:03
  • Then use the fact you stated to argue I can write c_i as a convex comb of x_i and y_i in C_i, with \alpha \in (0,1). Then I get to line 1 of your proof, and because it is an if and only if statement, I can conclude that c is in ri(C_1-C_2)? – RV702 Nov 09 '13 at 01:05
  • @Rachel: I forgot to ask: is the space in which these sets live finite dimensional? If the answer is no, my proof is not valid. I used the fact that in finite dimensional spaces the relative interior of a convex set is the same as its algebraic interior. In general the algebraic interior contains the interior but the converse only holds in finite dimension. – Sergio Parreiras Nov 09 '13 at 01:27
  • @Rachel the quickest (not the best) reference I was able to find: www.mat.unimi.it/users/libor/AnConvessa/interno_top_alg.pdf – Sergio Parreiras Nov 09 '13 at 01:33
  • yes @Sergio I'm working in Rn. So you are saying in this case, the algebraic interior of a convex set is the relative interior? I know the definition of algebraic interior, which says you can move a little away from a point in the algebraic interior of a set and stay in the set. But I don't see how the RHS of your iff follows? Thanks again – RV702 Nov 09 '13 at 02:02
  • let us continue this discussion in chat – Sergio Parreiras Nov 09 '13 at 17:54
  • Does it hold in normed space provided that $\rm ri C$ and $\rm ri D$ be non empty sets? – Red shoes Jul 26 '17 at 07:01
0

See Corollary 6.6.2 (pp. 49) of "Convex analysis" by Rockafelar.

Peida Tian
  • 121
0

There is actually a simple intuitive explanation.

  1. We first show the forward inclusion must be true, i.e., $ri(C_1 - C_2) \subset ri(C_1) - ri(C_2)$.

Suppose $x\in ri(C_1 - C_2)$, then $\exists, y\in C_1, z\in C_2$ such that $x = y-z$. There are three cases:

a) If $y \in ri(C_1)$ and $z\in ri(C_2)$, then the forward inclusion is true.

b) If $y \in ri(C_1)$ and $z\notin ri(C_2)$, then we can tweak $y$ and $z$ to be $y'$ and $z'$ such that $y' \in ri(C_1)$ and $z' \in ri(C_2)$ and $x = y'-z'$.

c) If $y \notin ri(C_1)$ and $z\notin ri(C_2)$, then $x=y-z \notin ri(C_1 - C_2)$

  1. We now show the backward inclusion must be true. It is true because of part a) in the forward inclusion.

These are intuitive explanation. You need to translate them in mathematical language, but it should be easy to write out the details.

aysljc
  • 133