4 votos

Demostrar que un conjunto es el casco convexo de otro conjunto

Define dos conjuntos:

  • $A = \{x \in \{0,1\}^n : \lVert x \rVert_1 \leq k\}$ es un conjunto finito de vectores binarios;
  • $B = \{x \in [0,1]^n : \lVert x \rVert_1 \leq k\}$ es un conjunto infinito de vectores de valor real, cuyos elementos están comprendidos entre $0$ y $1$ ;

donde $0 \leq k \leq n$ , $k$ es un número entero y $\lVert x \rVert_1$ denota el $l_1$ norma: $\lVert x \rVert_1 = \sum_{i=1}^{n} \lvert x_i \rvert$ .

Creo que $B$ es el casco convexo de $A$ ( $conv(A)$ ), pero no puede demostrarlo. Es fácil demostrar $conv(A) \subseteq B$ . Estoy atascado en la dirección inversa. Estoy pensando en utilizar la prueba de inducción: suponer que se cumple para $0 \leq k < n$ demuestre que también se cumple para $k+1$ pero no lo he conseguido.

0voto

dubek Puntos 2815

Creo que probablemente hay una variedad de pruebas con longitudes dependiendo de la cantidad de teoría poliédrica que desea invocar. He aquí un método: demostrar que todos los puntos extremos de $B$ están en $A$ . Esto es suficiente por la compacidad de $B$ .

Sea $x$ sea un punto extremo de $B$ . El conjunto $B$ se define por $2n + 1$ desigualdades lineales: $0\leq x_i\leq 1$ y $\sum x_i \leq k$ . En un punto extremo $n$ de estas restricciones deben ser estrictas (mantenerse con igualdad). Para cada $x_i$ como máximo una de las restricciones $0\leq x_i$ o $x_i\leq 1$ puede ser ajustado.

Supongamos que $x\not\in A$ . Hay algunos $j$ sin una restricción estricta: $x_j\in (0,1)$ . Dado que, la única manera de tener $n$ desigualdades estrechas en $x$ es tener $\sum x_i = k$ y también tienen cada $x_i$ con $i\neq j$ satisfacen alguna restricción de límites. Pero entonces $x_j = k - \sum_{i\neq j} x_i$ es un número entero, una contradicción.

0voto

timmow Puntos 1625

$B = B_1 \cup B_2$

donde

$$B_1 = \{x \in [0,1]^n : \lVert x \rVert_1 = k\}$$

y

$$B_2 = \{x \in [0,1]^n : \lVert x \rVert_1 < k\}$$

Sea $x \in B$

Caso 1: $x \in B_1$ escribamos x en su representación cartesiana ( $(e_i)i$ es la base trivial del espacio ortonormal $\mathbb{R}^n$ y $(x_i)i$ los cordianatos de x en esta base)

$x=\sum_{k=1}^{n}{x_i.ei}$

$x=\sum_{k=1}^{n}{\frac{x_i}{k}*k.ei}$

tenemos todos los vectores $k.e_i \in A$

y tenemos $\sum_{k=1}^{n}\frac{x_i}{k}=1$ y todos $\frac{x_i}{k} \geq 0$

así que $x \in conv(A)$

$$B_1 \subset conv(A)$$

Cas 2: $x \in B_2$

supongamos que $x\neq O$

si podemos encontrar y tal que $x=\lambda.y+(1-\lambda).O = \lambda.y$ y $y \in B_1$ y $\lambda \in [0,1]$ . entonces podemos concluir que $x \in conv(A)$

que $y$ es $y=\frac{k}{\lVert x \rVert_1}x$ y $\lambda = \frac{\lVert x \rVert_1}{k}$ $$B_2 \subset conv(A)$$

entonces $$B \subset conv(A)$$

veranear

  1. B es convexo (es la intersección de la Bola (O,k) y el Ortante positivo, ambos conjuntos convexos)
  2. $conv(A)$ es el convexo más pequeño que contiene a A
  3. $A \subset B$
  4. $B \subset conv(A)$

podemos concluir que $$B = conv(A)$$

0voto

Leon Katsnelson Puntos 274

Es cierto que $\mathbb{co} A = B$, pero la prueba es un poco tedioso.

Desde $A \subset B$, está claro que $\mathbb{co} A \subset B$. La otra dirección, se requiere un poco más de trabajo:

Tanto en $A$ $B$ están cerrados acotado establece, por lo tanto compacto. $B$ es convexa. El convex hull $\mathbb{co} A$ es cerrado y compacto (sigue de la compacidad y el teorema de Carathéodory).

Deje $E$ el conjunto de puntos extremos de $B$. La idea básica es mostrar que $E \subset A$. Desde el Krein-Milman teorema nos dice que $B = \overline{\mathbb{co}} E$, a continuación, siga ese $B \subset \mathbb{co} A$.

Para caracterizar los puntos extremos, necesito un poco de notación y un lema.

Deje $C = \{ x \in \mathbb{R}^n | \; g_i (x) \leq 0, \; \forall i \in I \}$, donde cada una de las $g_i$ tiene la forma $g_i(x) = \langle \gamma_i, x \rangle - \beta_i$. (Tenga en cuenta que $B$ tiene esta forma). Definir el 'índice activo set' $I_{x_0} = \{ i \in I | g_i(x_0) = 0 \}$.

Lema: $x_0$ es un punto extremo de $C$ fib $x_0 \in C$$\mathbb{sp} \{ \gamma_i \}_{i \in I_{x_0}} = \mathbb{R}^n$.

Prueba: ($\implies$): Supongamos $x_0$ es un punto extremo de $C$, pero $\mathbb{sp} \{ \gamma_i \}_{i \in I_{x_0}} \neq \mathbb{R}^n$. A continuación, elija un valor distinto de cero $h \in \mathbb{sp} \{ \gamma_i \}_{i \in I_{x_0}}^{\bot}$. Además tenga en cuenta que si $ i \notin I_{x_0}$, entonces existe una vecindad $U$ $x_0$ tal que $i \notin I_x$, forall $x \in U$. Ahora considere los puntos de $x_0 + \lambda h$, y observar que para $\lambda$ lo suficientemente pequeño, $x_0 \pm\lambda h \in C$ (ya que todas las restricciones son satisfechas). Podemos escribir $x_0 = \frac{1}{2} ( (x_0+\lambda h) + (x_0-\lambda h))$, lo que contradice el hecho de que $x_0$ es extrema.

($\impliedby$): Ahora supongamos $x_0 \in C$$\mathbb{sp} \{ \gamma_i \}_{i \in I_{x_0}} = \mathbb{R}^n$. Supongamos $x_0 = \lambda x + (1-\lambda) y$,$x,y \in C$, e $\lambda \in (0,1)$. Deje $i \in I_{x_0}$,$g_i(x_0) = \lambda g_i(x) + (1-\lambda) g_i(y) = 0$. De ello se desprende que $g_i(x) = g_i(y) = 0$, de la cual tenemos $\langle \gamma_i, x_0 \rangle = \langle \gamma_i, x \rangle = \langle \gamma_i, y \rangle$, para todos los $i \in I_{x_0}$. Sin embargo, esto implica que $x_0-x$ $x_0-y$ mentira en el complemento de $\mathbb{sp} \{ \gamma_i \}_{i \in I_{x_0}}$, $\{ 0 \}$ por supuesto. Por lo tanto $x = y = x_0$. De ello se desprende que $x_0$ es extrema.

Ahora, de vuelta al set $B$. Deje $x$ ser un punto extremo de $B$. $B$ se define por $2n+1$ limitaciones, sin embargo, de las $2n$ restricciones de $x_i \in [0,1]$, en la mayoría de las $n$ puede estar activo. Por lo tanto, en la mayoría de los $n+1$ restricciones pueden ser activos (y cualquier $n$ de estos son linealmente independientes).

Hay dos posibilidades: (1) $x_1+...+x_n = k$. En este caso, $n-1$ de las otras restricciones deben ser activo (es decir, $x_i$ es $0$ o $1$ $n-1$ índices de $i$). Desde $k$ es un número entero, entonces se sigue que el resto de los $x_i$ debe también ser $0$ o $1$. Por lo tanto $x = \sum_{j \in J} e_j$, donde $|J| = k$. (2) $x_1+...+x_n < k$. En este caso todos los $x_i$ debe ser $0$ o $1$ (en la mayoría de las $k-1$$1$, por supuesto). Esto le da a $x = \sum_{j \in J} e_j$ donde $|J| < k$.

Esto caracteriza a los puntos extremos de $B$ como tener la forma $x = \sum_{j \in J} e_j$ donde $|J| \leq k$, y una sencilla observación tenga en cuenta que todos esos $x$ satisfacer $x \in A$. Por lo tanto, tenemos el resultado deseado.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X