Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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).

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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