6
$\begingroup$

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

$\DeclareMathOperator\cl{cl}$I am working on problem 2.31(d) in Boyd & Vandenberghe's book "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 \cl(K) \setminus \{0\} \}. $$

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

Now, for a point $z \in K'$, it is easy to show that if there exists $x \in \cl(K) \setminus \{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 \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 $\lVert u\rVert = 1$ that

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

I am able to use the Schwartz inequality 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.

$\endgroup$
1
  • $\begingroup$ TeX note: please use $\operatorname{cl}(K) \setminus \{0\}$ \operatorname{cl}(K) \setminus \{0\}, not $\text{cl}(K) \backslash \{0\}$ \text{cl}(K) \backslash \{0\}, for set difference; notice the difference in spacing. (I also recommend, as you notice \operatorname for operators; here it doesn't make much difference, but notice, for example, $\operatorname{cl} K$ \operatorname{cl} K versus $\text{cl} K$ \text{cl} K). I have edited accordingly. $\endgroup$
    – LSpice
    Aug 1, 2022 at 20:41

1 Answer 1

2
$\begingroup$

$\DeclareMathOperator\cl{cl}$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. $\lVert x\rVert=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).

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – ted
    Jul 8, 2012 at 4:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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