8
$\begingroup$

I am trying to solve Exercise 2.39 at Boyd and Vandenberghe's Convex Optimization book. In one source, the answer is given as:

2.39 Separation of cones. Let $K$ and $\tilde K$ be two convex cones whose interiors are nonempty and disjoint. Show that there is a nonzero $y$ such that $y\in K^*$, $-y\in\tilde K^*$.

Solution. Let $y\ne0$ be the normal vector of a separating hyperplane separating the interiors: $y^\top x\ge\alpha$ for $x\in\boldsymbol{\operatorname{int}}K_1$ and $y^\top x\le\alpha$ for $x\in\boldsymbol{\operatorname{int}}K_2$. We must have $\alpha=0$ because $K_1$ and $K_2$ are cones, so if $x\in\boldsymbol{\operatorname{int}}K_1$, then $tx\in\boldsymbol{\operatorname{int}}K_1$ for all $t>0$. This means that $$y\in(\boldsymbol{\operatorname{int}}K_1)^*=K_1^*,\quad-y\in(\boldsymbol{\operatorname{int}}K_2)^*=K_2^*.$$

I don't get the final part $(\boldsymbol{\operatorname{int}}K)^* = K^*$. Why is this a valid equality? My idea is because if a boundary point of $K$ has $y^\top x < 0$ this would contradict $\boldsymbol{\operatorname{int}}K$ being an open set, but I can not formalize this.

$\endgroup$
2
$\begingroup$

Ok, after seeing the wrong attempt below which has been edited multiple times, I believe it is time to close this question. I will just leave my attempt:

Assume $K^* \neq (\operatorname{int}K)^*$, so $\exists x_0 \in \operatorname{bd} K: \ x_0^\top y < 0$. Because of the strict inequality, we know that we can take a very small ball around $x_0$, say $B(x_0)$ and all the points $x' \in B(x_0)$ will have $x'^\top y < 0$. By the definition of the boundary, we have $(B(x_0) \cap \operatorname{int} K)\neq \emptyset $ hence for some $x \in \operatorname{int}K$ we have $x^\top y < 0$, which is a contradiction. Hence $K^* = \operatorname{int}K^*$.

| improve this answer | |
$\endgroup$
1
$\begingroup$

A new approach focusing only on $(\boldsymbol{\operatorname{int}}K)^* = K^*$, since that seems to be the biggest problem to you.

From section 2.6 of Convex Optimization (Boyd, Vanderberghe) we have that:

  • (3) $K^*$ is closed and convex.
  • (1) $K^{**}$ is the closure of the convex hull.
  • (2) For $K$ convex and closed, $K^{**} = K$.

I will add a conjecture:

  • (X) The dual cone of a closed and convex cone is unique.

Now, we know that $K$ is the closure of the convex hull of $\boldsymbol{\operatorname{int}}K $, that is, $(\boldsymbol{\operatorname{int}}K)^{**}=K $ (1).

But, $K$ is convex and closed, such that $ K = K^{**} = (\boldsymbol{\operatorname{int}}K)^{**} $ (2).

Both $ K^{*}$ and $ (\boldsymbol{\operatorname{int}}K)^{*} $ are closed and convex (3), therefore, $K^{**} = (\boldsymbol{\operatorname{int}}K)^{**} \iff K^{*} = (\boldsymbol{\operatorname{int}}K)^{*}$ (X).

| improve this answer | |
$\endgroup$

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.