# proving the interior of a dual cone is the set of vectors whose inner product is strictly positive on the cone

Apologies for posting such a simple question to mathoverflow. I've have been stuck trying to solve this problem for some time and have posted this same query to math.stackexchange (but have received no useful feedback).

I am working on problem 2.31(d) in Boyd & Vandenberghe's book on "Convex Optimization" and the question asks me to prove that the interior of a dual cone $K'$ of a convex cone $K \subseteq R^n$ is equal to the set

$S = { y \mid y^\top x > 0 \text{ for all } x \in \text{cl}(K) \backslash {0} }.$

Recall that the dual cone is the set $K' = \{ y \mid y^\top x \ge 0 \text{ for all } x \in \text{cl}(K) \backslash \{0\} \}$.

Now, for a point $z \in K'$, it is easy to show that if there exists $x \in \text{cl}(K) \backslash \{0\}$ such that $z^\top x = 0$, then $z$ must lie on the boundary of $K'$.

So now I need only show that if $z \in K'$ and $z^\top x > 0$ for all $x \in \text{cl}(K) \backslash \{0\}$, then $z$ lies in the interior of $K'$. Of course this means I need to find an $\epsilon > 0$ such that for all $z' \in D(z,\epsilon)$, we have $z'^\top x > 0$ for all $x \in \text{cl}(K) \backslash \{0\}$. It's here that I am stuck.

First of all, I don't know how to find such an $\epsilon$. But even if I did, I don't know how to show that for any $z' = z + \gamma u$ with $\gamma \in (0,\epsilon)$ and $\|u\| = 1$ that

$z'^\top x = (z + \gamma u)^\top x > 0.$

I am able to use the Schwartz ineq to show that

$z^\top x - \gamma \|x\| \le z^\top x + \gamma u^\top x.$

But I can't prove the critical piece, that

$0 < z^\top x - \gamma \|x\|.$

One difficulty here is that because $x$ ranges over the cone $K$, its norm can be arbitrarily large. Therefore it seems unlikely to find a single $\epsilon$ which bounds the differences of the inner products ($z^\top x$ and $z'^\top x$) for all of $x$ in $K$.

On the other hand, the statement that $S$ is the interior of $K'$ seems entirely reasonable so there should be a way to prove this. Any help is greatly appreciated. I am very interested to see what mathematical technologies I am missing.

Thanks, -Ted

-

Something along the following lines will work: note that $z$ satisfies $z^\top x>0$ for all $x\in cl(K)$ iff $z$ satisfies $z^\top x>0$ for all $x\in cl(K)$ s.t. $\|x\|=1$, i.e. for all $x\in cl(K)\cap S^{n-1}$. Note that $U:=cl(K)\cap S^{n-1}$ is compact, thus the function $x\mapsto z^\top x$, being a continuous function on a compact, reaches its minimum, say, $\delta>0$, on $U$.
Next, for an arbitrary $y\in\mathbb{R}^n$, take $f_y(x)=y^\top x$. Again, $\inf_{x\in U} f_y(x)$ exists, and is equal to $\delta_y$, which might be negative or positive. Still, we can take sufficiently small $\alpha_y>0$ so that $(z+\alpha_y y)^\top x\geq 0$ for all $x\in U$. (I leave the computation of $\alpha_y$ from $\delta$ and $\delta_y$ to you, it's not hard.)
Finally, you need to pick up enough vectors $y$ so that $z$ lies in the interior of the cone spanned by the vectors $z+\alpha_y y$ (note that these lie in $cl(K')$ by construction).
Thanks Dima! I came up with a similar proof offline and was happy to see your answer in agreement. The critical insight is that $z^\top x>0 \iff z^\top x / \|x\|>0.$ So this allows one to do the proof for vectors $x \in \text{cl}(K) \backslash \{0\}$ of unit length, and then extend the result to vectors with arbitrary length. –  ted Jul 8 '12 at 4:22