Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 x \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

share|improve this question
1  
Something is missing here: If $K$ is a cone, then by B&V's definition, we must have $0 \in K$, but then the set $\{ z \mid z^T x > 0 $ for all $ x \in K \} $ must be empty, since $z^T 0 = 0$. –  copper.hat Jul 6 '12 at 9:30
    
Hi copper.hat, you're not missing anything. I caught that too. It's a bug in the question. It should most likely read as "for all $x \in K, x \not= 0$." –  ted Jul 6 '12 at 23:39
    
X-posted to MO –  Willie Wong Jul 7 '12 at 18:44
    
The question is answered at MO so we can close this query. –  ted Jul 8 '12 at 4:20
add comment

2 Answers

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

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

The other piece of the proof which is to show that $z^\top x = 0$ for $x \in \text{cl}(K) \backslash \{0\}$ only when $z$ is on the boundary of $K^*$. This isn't very difficult.

share|improve this answer
    
You can use double dollar signs to make your LaTeX centered on its own line. –  Henry T. Horton Jul 9 '12 at 0:16
add comment

The question has an additional bug: $K$ should be assumed to be closed. For instance, take $K$ to be the positive orthant together with $0$, i.e., $K=\{x\in\mathbb{R}^{n}:x_{i}>0,i=1,\ldots n\} \cup \{0\}$. Then $K^{\ast}=\mathbb{R}_{+}^{n}=\{x\in \mathbb{R}^{n}:x_{i}\geq0,i=1,\ldots n\}$. Every element $z\in K^{\ast}\backslash \{0\}$ satisfies $z^{T}x>0$ for all $x\in K\backslash \{0\}$, even those at the boundary of $K^{\ast}$.

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