0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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 $\endgroup$ – Arnaud Jul 6 '12 at 11:03
  • $\begingroup$ 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. $\endgroup$ – ted Jul 6 '12 at 23:54
  • $\begingroup$ 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. $\endgroup$ – ted Jul 7 '12 at 5:46
  • $\begingroup$ 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 . $\endgroup$ – Arnaud Jul 8 '12 at 1:00
  • $\begingroup$ Hmmm, this only works for closed cones $\endgroup$ – Arnaud Jul 8 '12 at 1:09
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Arnaud Jul 8 '12 at 10:48
  • $\begingroup$ 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). $\endgroup$ – ted Jul 8 '12 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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