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

2012-07-07T07:28:17Z

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

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

2012-07-07T09:40:59Z

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

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

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

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