Boyd y Vandenberghe, pregunta 2.31(d). Atascado en el simple problema interior de un cono doble.

Question

En Boyd & Vandenberghe "Optimización Convexa", pregunta 2.31(d) pide a demostrar que el interior de la doble cono $K^*$ es igual a

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

Recordemos que el doble cono de cono K es el conjunto:

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

He pasado un trozo sólido de tiempo tratando de demostrar esta simple y aparentemente evidente declaración sobre el interior de la doble cono, pero mantener pegado en el problema de la delimitación de la interna del producto de x con un perturbado versión de z (detalles a continuación). Frustrante, la prueba en el libro la clave de respuestas (disponible en línea) toma como dado este hecho que de que estoy atascado en demostrar.

Mi trabajo en la comprobación de la declaración (1) es la siguiente. Espero que alguien me puede mostrar la pieza de matemática de la tecnología, me estoy perdiendo. Gracias!

---

Pregunta 2.31(d):

Deje $K$ ser un cono convexo y $K^* = \{ y \mid y^\top x \ge 0 $ todos los $ x \in K \}$ ser su doble cono.

Deje $S = \{ z \mid z^\top x > 0 $ todos los $ x \in K \}.$ Muestran que $S = \text{int } K^*.$

Ciertamente, $S \subseteq K^*.$ Ahora considere un punto arbitrario $z_0 \in S$. Para todos los $x \in K$ tenemos $z_0^\top x > 0$. Está claro que tenemos que encontrar una $\epsilon$ tal que para todos los $z' \in D(z_0, \epsilon)$,

$~~~~ z'^\top x > 0 $ todos los $ x \in K.$

Por desgracia, no sé cómo mostrar $z'^\top x > 0$ $z' \in D(z_0, \epsilon)$ al $\epsilon$ elegido es lo suficientemente pequeño.

Sé que podemos escribir $z'$ $z_0 + \gamma u$ donde$\|u\| = 1$$\gamma \in (0,\epsilon)$. Y yo sé que

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

donde $z_0^\top x > 0$ $\gamma \|x\| \ge 0.$

Sin embargo, no sé cómo mostrar la pieza fundamental, que

$~~~~ z_0^\top x - \gamma \|x\| > 0$

al $\epsilon$ elegido es lo suficientemente pequeña, ya $x$ puede abarcar $K$ y, por tanto, $\|x\|$ puede ser arbitrariamente grande.

Frustrante, la solución de B&V simplemente da por sentado que para suficientemente pequeño $\epsilon$,

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

He mirado en línea para algunos matriz de la teoría de la perturbación de los resultados de aplicar, pero nada de lo que yo he encontrado ha sido útil.

Cualquier ayuda es muy apreciada,

Ted

Answer 1

Bueno, la crítica de la pieza que me faltaba es que para cualquier $z$, $z^\top x > 0 \iff z^\top x / \|x\| > 0.$

Así que vamos a $x_0 = \text{arg inf } \{ z^\top x \mid x \in \text{cl}(K) \cap \{0\}, \|x\|=1 \}$ y deje $c_{x_0} = z^\top x_0 > 0$. Sabemos $x_0$ existe porque el conjunto de $\text{cl}(K)\cap \{x \mid \|x\| = 1 \}$ es cerrado y acotado.

Ahora vamos a $\varepsilon = c_{x_0} / 2$, de modo que para cualquier $z' = z + \gamma u$ donde$\|u\|=1$$\gamma \in (0,\varepsilon)$, tenemos

$$z'^\top x_0 \ge c_{x_0} - \gamma > c_{x_0} / 2 > 0.$$

Por otra parte, para cualquier otro $x \in \text{cl}(K)\cap \{x \mid \|x\| = 1 \}$ sabemos

$$z'^\top x \ge z'^\top x_0 > 0.$$

Por lo tanto, para cualquier $x \in \text{cl}(K) \backslash \{0\}$ hemos

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

lo que demuestra $z'^\top x > 0$ siempre $z' \in D(z,\varepsilon)$.

La otra pieza de la prueba, que es mostrar que $z^\top x = 0$ $x \in \text{cl}(K) \backslash \{0\}$ sólo al $z$ está en el límite de $K^*$. Esto no es muy difícil.

Answer 2

La pregunta tiene un error adicional: $K$ debe suponerse que se cerrará. Por ejemplo, tomar $K$ ser el orthant positivo junto con $0$, es decir, $K={x\in\mathbb{R}^{n}:x{i}>0,i=1,\ldots n} \cup {0}$. Entonces $K^{\ast}=\mathbb{R}{+}^{n}={x\in \mathbb{R}^{n}:x_{i}\geq0,i=1,\ldots n}$. Cumple con cada elemento $z\in K^{\ast}\backslash {0}$ $z^{T}x>0$ % todo $x\in K\backslash {0}$, incluso aquellos en el límite de $K^{\ast}$.