proving the interior of a dual cone is the set of vectors whose inner product is strictly positive on the cone - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T15:29:46Z http://mathoverflow.net/feeds/question/101562 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/101562/proving-the-interior-of-a-dual-cone-is-the-set-of-vectors-whose-inner-product-is proving the interior of a dual cone is the set of vectors whose inner product is strictly positive on the cone ted 2012-07-07T07:28:17Z 2012-07-07T09:40:59Z <p>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).</p> <p>I am working on problem 2.31(d) in Boyd &amp; 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</p> <p>$S = \{ y \mid y^\top x > 0 \text{ for all } x \in \text{cl}(K) \backslash \{0\} \}.$</p> <p>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\} \}$.</p> <p>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'$.</p> <p>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.</p> <p>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 </p> <p>$z'^\top x = (z + \gamma u)^\top x > 0.$</p> <p>I am able to use the Schwartz ineq to show that</p> <p>$z^\top x - \gamma \|x\| \le z^\top x + \gamma u^\top x.$</p> <p>But I can't prove the critical piece, that </p> <p>$0 &lt; z^\top x - \gamma \|x\|.$</p> <p>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$.</p> <p>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.</p> <p>Thanks, -Ted</p> http://mathoverflow.net/questions/101562/proving-the-interior-of-a-dual-cone-is-the-set-of-vectors-whose-inner-product-is/101566#101566 Answer by Dima Pasechnik for proving the interior of a dual cone is the set of vectors whose inner product is strictly positive on the cone Dima Pasechnik 2012-07-07T09:40:59Z 2012-07-07T09:40:59Z <p>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$.</p> <p>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.)</p> <p>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).</p>