2
$\begingroup$

I am working on exercises for a convex analysis course and I am slightly stuck on the following;

Suppose that $A \subset \mathbb{R}^n$ is closed, bounded (compact) and conex. Define the set

$$ A^o = \left\{y \in \mathbb{R}^n : y^Tx \leq 1, \forall x \in A\right\} $$

Show that $A^o$ is convex and $(A^o)^o = A$.

Showing that $A^o$ is convex is easy; take $u,v \in A^o$ and $\theta \in [0,1]\subset \mathbb{R}$. Then for all $x \in A$ we have

$$ (\theta u +(1-\theta)v)^Tx = \theta u^Tx+(1-\theta)v^Tx \leq \theta + (1-\theta) = 1 $$

and so $\theta u +(1-\theta)v \in A^o$.

Also showing that $A \subset (A^o)^o$ is easy since for each $x \in A$ and $y \in A^o$ we have

$$ x^Ty = y^Tx \leq 1. $$

Now showing that $(A^o)^o \subset A$ is where I am getting stuck. The way I've been trying to show this is by contradiction.

I suppose that there exists $x \in (A^0)^0$ so that $x \notin A$. Then let $\xi \in A$ so that

$$ ||x-\xi|| = \text{dist}(x,A). $$

Such a $\xi$ exists since $A$ is compact. Now since $A$ is convex as well as compact we know that the hyperplane

$$ H = \left\{y \in \mathbb{R}^n : a^Ty =b \right\} $$

with $a = x - \xi$ and $b = \frac{a^Tx+a^T\xi}{2}$ is a strict separating hyperplane for the set $A$ and $\{x\}$ with

$$ x \in \left\{y \in \mathbb{R}^n : a^Ty >b \right\} $$

and

$$ A \subset \left\{y \in \mathbb{R}^n : a^Ty < b \right\}. $$

Now this is where I get fully stuck. I have tried every which way that I can think of to get a contradiction from here with no success.

How would you suggest going forward.

NOTE: Hints are also welcome, if I get to a proof with the help of a hint then I will post my final proof as the answer to this question.

Thank you in advance for any help.

$\endgroup$
  • $\begingroup$ Yeah, that's what I am doing in the last part $\endgroup$ – Jandré Snyman Mar 21 at 7:55
  • 1
    $\begingroup$ You need to add the assumption $0 \in A$, since you always have $0 \in (A^o)^o$. Otherwise, the result does not hold: E.g. for $A = \{1\} \subset \mathbb R$ you have $(A^o)^o = [0,1]$. $\endgroup$ – gerw Mar 21 at 11:42
1
$\begingroup$

edit: As per the comment of gerw, the claim is only true if $0\in A$.

It seems to me like you already have a good idea with using seperating hyperplanes.

The next step would be to think of $A^\circ$ not just of a set in $\mathbb R^n$ but as a set of hyperplanes/half-spaces.

You have shown that there are $a,b$ such that $$ A\subset \{y\in\mathbb R^n : a^\top y<b \}. $$ Since $0\in A$, this implies that $b>0$. We can change $a,b$ by scaling such that $b=1$. Then we obtain $$ a^\top y < 1 \qquad\forall y\in A $$ which implies $$ a \in A^\circ. $$ Since $a^\top x > 1$, this shows that $x\not\in (A^\circ)^\circ$. This is a contradiction to your assumption.

$\endgroup$
  • $\begingroup$ Oh wow, that's super simple. I haven't thought of that yet. Thanks very much $\endgroup$ – Jandré Snyman Mar 21 at 9:38
  • $\begingroup$ This does work only if you already know $b > 0$ and this should follow from $0 \in A$. On the other hand, if $0 \not\in A$, the result does not hold since $0 \in (A^o)^o$. $\endgroup$ – gerw Mar 21 at 11:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.