<p>Arnaud is correct.  The critical piece I was missing is that for any $z$, $z^\top x &gt; 0 \iff z^\top x / \|x\| &gt; 0.$</p>

<p>So pick $z \in S$. Let $x_0 = \text{arg inf } \{ z^\top x \mid x \in \text{cl}(K) \cap \{0\}, \|x\|=1 \}$
and let $c_{x_0} = z^\top x_0 &gt; 0$.  We know $x_0$ exists because the set $\text{cl}(K)\cap \{x \mid \|x\| = 1 \}$ is closed and bounded.</p>

<p>Now let $\varepsilon = c_{x_0} / 2$ so that for any $z' = z + \gamma u$ where  $\|u\|=1$ and  $\gamma \in (0,\varepsilon)$, we have</p>

<p>$~~~~ z'^\top x_0 \ge c_{x_0} - \gamma &gt; c_{x_0} / 2 &gt; 0.$</p>

<p>Furthermore, for any other $x \in \text{cl}(K)\cap \{x \mid \|x\| = 1 \}$ we know</p>

<p>$~~~~ z'^\top x \ge z'^\top x_0 &gt; 0.$</p>

<p>Therefore, for any $x \in \text{cl}(K) \backslash \{0\}$ we have</p>

<p>$~~~~ z'^\top x / \|x\| &gt; 0$</p>

<p>which proves $z'^\top x &gt; 0$ whenever $z' \in D(z,\varepsilon)$.</p>

CC BY-SA 3.0
2012-07-08T10:48:45.417Z
What is $y$ ? If, like it looks like, $c_{x_0}=\inf \{z^T x|x \in cl(K) , ||x||=1\}$, I don't see why it is positive (and it is not in the example I gave in my last comment)
Arnaud
CC BY-SA 3.0
2012-07-08T21:51:59.140Z
Sorry, typo. $y$ should read as $z$.  So $c_{c_0} = z^\top x_0$ where $x_0$ is the arginf of $z^\top x$ for $x\in K$.

We know $c_{x_0} > 0$ since we chose $z$ from the set $S$ defined above (sorry, that was implied, I didn't say it explicitly in my comment).
ted
CC BY-SA 3.0
2012-07-08T04:46:17.093Z
2012-07-08T21:53:38.863Z
2012-07-08T21:53:38.863Z
ted
<p><sub>Crossposted at <a href="https://math.stackexchange.com/q/167413">Mathematics SE</a> and <a href="https://mathoverflow.net/q/101562">MathOverflow</a></sub></p>
<hr />
<p>In Boyd &amp; Vandenberghe's &quot;Convex Optimization&quot;, question 2.31(d) asks to prove that the interior of the dual cone <span class="math-container">$K^*$</span> is equal to</p>
<p>(1)  <span class="math-container">$\text{int } K^* = \{ z \mid z^\top x &gt; 0 $</span> for all <span class="math-container">$ x \in K \}.$</span></p>
<p>Recall that the dual cone of a cone K is the set:</p>
<p><span class="math-container">$K^* = \{ y \mid y^\top \ge 0 $</span> for all <span class="math-container">$ x \in K \}.$</span></p>
<p>I've spent a solid chunk of time trying to prove this simple and seemingly evident statement about the interior of the dual cone but keep getting stuck on the problem of bounding the inner product of x with a perturbed version of z (details provided below).  Frustratingly, the proof in the book's answer key (available online) takes as given this very fact that that I am stuck on proving.</p>
<p>My work in proving statement (1) is given below.  I hope someone can show me the piece of mathematical technology I'm missing.  Thanks!</p>
<hr />
<p>Question 2.31(d):</p>
<p>Let <span class="math-container">$K$</span> be a convex cone and <span class="math-container">$K^* = \{ y \mid y^\top x \ge 0 $</span> for all <span class="math-container">$ x \in K \}$</span> be its dual cone.</p>
<p>Let <span class="math-container">$S = \{ z \mid z^\top x &gt; 0 $</span> for all <span class="math-container">$ x \in K \}.$</span>   Show that <span class="math-container">$S = \text{int } K^*.$</span></p>
<p>Certainly <span class="math-container">$S \subseteq K^*.$</span>  Now consider some arbitrary point <span class="math-container">$z_0 \in S$</span>.  For all <span class="math-container">$x \in K$</span> we have <span class="math-container">$z_0^\top x &gt; 0$</span>.  It's clear that we need to find an <span class="math-container">$\epsilon$</span> such that for all <span class="math-container">$z' \in D(z_0, \epsilon)$</span>,</p>
<p><span class="math-container">$~~~~ z'^\top x &gt; 0 $</span> for all <span class="math-container">$ x \in K.$</span></p>
<p>Unfortunately, I don't know how to show <span class="math-container">$z'^\top x &gt; 0$</span> for <span class="math-container">$z' \in D(z_0, \epsilon)$</span> when <span class="math-container">$\epsilon$</span> is chosen sufficiently small.</p>
<p>I do know we can write <span class="math-container">$z'$</span> as <span class="math-container">$z_0 + \gamma u$</span> where <span class="math-container">$\|u\| = 1$</span> and <span class="math-container">$\gamma \in (0,\epsilon)$</span>.  And I do know that</p>
<p><span class="math-container">$~~~~ z_0^\top x - \gamma \|x\| ~\le~ z_0^\top x + \gamma u^\top x ~\le~ z_0^\top x + \gamma \|x\|$</span>.</p>
<p>where <span class="math-container">$z_0^\top x &gt; 0$</span> and <span class="math-container">$\gamma \|x\| \ge 0.$</span></p>
<p>However, I don't know how to show the critical piece, that</p>
<p><span class="math-container">$~~~~ z_0^\top x - \gamma \|x\| &gt; 0$</span></p>
<p>when <span class="math-container">$\epsilon$</span> is chosen sufficiently small since <span class="math-container">$x$</span> can range over <span class="math-container">$K$</span> and therefore <span class="math-container">$\|x\|$</span> can be arbitrarily large.</p>
<p>Frustratingly, the solution in B&amp;V just takes it for granted that for sufficiently small <span class="math-container">$\epsilon$</span>,</p>
<p><span class="math-container">$~~~~ z_0^\top x + \gamma u^\top x &gt; 0$</span>.</p>
<p>I've looked online for some matrix perturbation theory results to apply but nothing I've found has been useful.</p>
<p>Any help is greatly appreciated,</p>
<p>Ted</p>

CC BY-SA 3.0
2012-07-06T11:03:03.453Z
The result looks dubious to me if the space has infinite dimension. Otherwise, your inequality holds for a compact basis of the cone, and the result will follow by linearity. Note that your argument only proves that the given set is open, not that it is the interior
Arnaud
CC BY-SA 3.0
2012-07-06T23:54:37.560Z
Hi Arnaud, the book only deals with $R^n$ where $n < \infty$ so we don't have to worry about infinite dimensional spaces.

But good point that I also need to show $\text{int } K^* \subseteq S$.

What do you mean by a compact basis?  Can you provide some more details?  Thanks.
ted
CC BY-SA 3.0
2012-07-07T05:46:26.833Z
Actually, instead of proving $K^* \subseteq S$, I can show that $y \in K^*$ and $y^\top x = 0$ for some $x\in K \backslash \{0\}$ implies $y \in \text{boundary}(K)$, which is easy.
ted
CC BY-SA 3.0
2012-07-08T01:00:26.130Z
Define $K'=\{x \in K| ||x||=1\}$. You want to prove that $z_0^Tx>\gamma ||x||=\gamma$ for $x \in K'$. Since $K'$ is compact, the function $x \rightarrow z_0^Tx$ reaches its minimum $m$, and it suffices to takes $\gamma <m$. Then, for all $x\in K$, $x=\lambda x'$ for some $x' \in K', \lambda >0$, hence $z_0^Tx=\lambda z_0^Tx'>0$. By the way, this question is not a very good fit for cstheory, and would have had better and faster answers on math.stackexchange.com .
Arnaud
CC BY-SA 3.0
2012-07-08T01:09:03.157Z
Hmmm, this only works for closed cones
Arnaud
CC BY-SA 3.0
2012-07-08T01:38:09.810Z
It looks false to me if $K$ is an open cone : take $K=\{x,y \in \mathbb{R}^2|x,y >0\}$, then $K^*=\{x,y \in \mathbb{R}^2|x,y \geq 0\}$, so $int K^*=K$, while $\{z | z^Tu>0,u \in K\}=K^*$
Arnaud
<ds.algorithms><optimization><convex-optimization>
Boyd & Vandenberghe, question 2.31(d). Stuck on simple problem regarding interior of a dual cone
ted
# Boyd & Vandenberghe, question 2.31(d). Stuck on simple problem regarding interior of a dual cone

(Asked by: username_0 on 2012-07-06)

Crossposted at [Mathematics SE](https://math.stackexchange.com/q/167413) and [MathOverflow](https://mathoverflow.net/q/101562)

---

In Boyd & Vandenberghe's "Convex Optimization", question 2.31(d) asks to prove that the interior of the dual cone $K^\*$ is equal to

(1) $\text{int } K^\* = \{ z \mid z^\top x > 0 $ for all $ x \in K \}.$

Recall that the dual cone of a cone K is the set:

$K^\* = \{ y \mid y^\top \ge 0 $ for all $ x \in K \}.$

I've spent a solid chunk of time trying to prove this simple and seemingly evident statement about the interior of the dual cone but keep getting stuck on the problem of bounding the inner product of x with a perturbed version of z (details provided below). Frustratingly, the proof in the book's answer key (available online) takes as given this very fact that that I am stuck on proving.

My work in proving statement (1) is given below. I hope someone can show me the piece of mathematical technology I'm missing. Thanks!

---

Question 2.31(d):

Let $K$ be a convex cone and $K^\* = \{ y \mid y^\top x \ge 0 $ for all $ x \in K \}$ be its dual cone.

Let $S = \{ z \mid z^\top x > 0 $ for all $ x \in K \}.$ Show that $S = \text{int } K^\*.$

Certainly $S \subseteq K^\*.$ Now consider some arbitrary point $z\_0 \in S$. For all $x \in K$ we have $z\_0^\top x > 0$. It's clear that we need to find an $\epsilon$ such that for all $z' \in D(z\_0, \epsilon)$,

$~~~~ z'^\top x > 0 $ for all $ x \in K.$

Unfortunately, I don't know how to show $z'^\top x > 0$ for $z' \in D(z\_0, \epsilon)$ when $\epsilon$ is chosen sufficiently small.

I do know we can write $z'$ as $z\_0 + \gamma u$ where $\|u\| = 1$ and $\gamma \in (0,\epsilon)$. And I do know that

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

where $z\_0^\top x > 0$ and $\gamma \|x\| \ge 0.$

However, I don't know how to show the critical piece, that

$~~~~ z\_0^\top x - \gamma \|x\| > 0$

when $\epsilon$ is chosen sufficiently small since $x$ can range over $K$ and therefore $\|x\|$ can be arbitrarily large.

Frustratingly, the solution in B&V just takes it for granted that for sufficiently small $\epsilon$,

$~~~~ z\_0^\top x + \gamma u^\top x > 0$.

I've looked online for some matrix perturbation theory results to apply but nothing I've found has been useful.

Any help is greatly appreciated,

Ted

**Tags:** ds.algorithms, optimization, convex-optimization
> **Comments:**
> **username_1**: The result looks dubious to me if the space has infinite dimension. Otherwise, your inequality holds for a compact basis of the cone, and the result will follow by linearity. Note that your argument only proves that the given set is open, not that it is the interior  
> **username_0**: Hi Arnaud, the book only deals with $R^n$ where $n < \infty$ so we don't have to worry about infinite dimensional spaces.  But good point that I also need to show $\text{int } K^* \subseteq S$.  What do you mean by a compact basis?  Can you provide some more details?  Thanks.  
> **username_0**: Actually, instead of proving $K^* \subseteq S$, I can show that $y \in K^*$ and $y^\top x = 0$ for some $x\in K \backslash \{0\}$ implies $y \in \text{boundary}(K)$, which is easy.  
> **username_1**: Define $K'=\{x \in K| ||x||=1\}$. You want to prove that $z_0^Tx>\gamma ||x||=\gamma$ for $x \in K'$. Since $K'$ is compact, the function $x \rightarrow z_0^Tx$ reaches its minimum $m$, and it suffices to takes $\gamma <m$. Then, for all $x\in K$, $x=\lambda x'$ for some $x' \in K', \lambda >0$, hence $z_0^Tx=\lambda z_0^Tx'>0$. By the way, this question is not a very good fit for cstheory, and would have had better and faster answers on math.stackexchange.com .  
> **username_1**: Hmmm, this only works for closed cones  
> **username_1**: It looks false to me if $K$ is an open cone : take $K=\{x,y \in \mathbb{R}^2|x,y >0\}$, then $K^*=\{x,y \in \mathbb{R}^2|x,y \geq 0\}$, so $int K^*=K$, while $\{z | z^Tu>0,u \in K\}=K^*$  

---

## 1 answers

### Answer by username_0 on 2012-07-08. Score: 2 | Accepted answer

Arnaud is correct. The critical piece I was missing is that for any $z$, $z^\top x > 0 \iff z^\top x / \|x\| > 0.$

So pick $z \in S$. Let $x\_0 = \text{arg inf } \{ z^\top x \mid x \in \text{cl}(K) \cap \{0\}, \|x\|=1 \}$
and let $c\_{x\_0} = z^\top x\_0 > 0$. We know $x\_0$ exists because the set $\text{cl}(K)\cap \{x \mid \|x\| = 1 \}$ is closed and bounded.

Now let $\varepsilon = c\_{x\_0} / 2$ so that for any $z' = z + \gamma u$ where $\|u\|=1$ and $\gamma \in (0,\varepsilon)$, we have

$~~~~ z'^\top x\_0 \ge c\_{x\_0} - \gamma > c\_{x\_0} / 2 > 0.$

Furthermore, for any other $x \in \text{cl}(K)\cap \{x \mid \|x\| = 1 \}$ we know

$~~~~ z'^\top x \ge z'^\top x\_0 > 0.$

Therefore, for any $x \in \text{cl}(K) \backslash \{0\}$ we have

$~~~~ z'^\top x / \|x\| > 0$

which proves $z'^\top x > 0$ whenever $z' \in D(z,\varepsilon)$.

> **Comments:**
> **username_1**: What is $y$ ? If, like it looks like, $c_{x_0}=\inf \{z^T x|x \in cl(K) , ||x||=1\}$, I don't see why it is positive (and it is not in the example I gave in my last comment)  
> **username_0**: Sorry, typo. $y$ should read as $z$.  So $c_{c_0} = z^\top x_0$ where $x_0$ is the arginf of $z^\top x$ for $x\in K$.  We know $c_{x_0} > 0$ since we chose $z$ from the set $S$ defined above (sorry, that was implied, I didn't say it explicitly in my comment).  

---

