凸優化:錐分離


8

我正在嘗試解決Boyd和Vandenberghe的《凸優化》一書中的練習2.39。在一個source中,答案為:

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^*.$$

我沒有最後的內容 $(\ boldsymbol {\ operatorname {int}} K)^ * = K ^ * $ 。為什麼這是有效的平等?我的想法是,如果 $ K $ 的邊界點具有 $ y ^ \ top x <0 $ 這與作為開放集的 $ \ boldsymbol {\ operatorname {int}} K $ 矛盾,但是我無法對此進行形式化。

2

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^*$.


1

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