¿Cuáles son los puntos extremos de este politopo?

Question

Dejemos que $n, k$ sean enteros positivos con $n\geq k$ .

Dejemos que $P_{n,k}$ sea el conjunto de vectores $x$ en $[0,1]^n$ para lo cual

$$ \sum_{i=1}^n x_i = k $$

$P_{n,k}$ está definido por ecuaciones lineales, por lo que es un politopo. ¿Cuáles son sus vértices (puntos extremos)?

Mi opinión es que las esquinas son el " $k$ -vectores "binarios" - los vectores con exactamente $k$ y $n-k$ ceros. Para demostrar esto, basta con probar (creo) que todo vector en $P_{n,k}$ es una combinación convexa de $k$ -vectores binarios. ¿Es esto correcto?

Nota: cuando $k=1$ , $P_{n,1}$ es sólo el simplex estándar en $\mathbb{R}^n$ . ¿Tiene un nombre cuando $k > 1$ ?

Answer 1

Demostramos que cada $x$ en $P_{n,k}$ -- es decir, con $x_i\in[0,1]$ y $x\cdot \vec{1}=k$ -- está en el casco convexo de los vectores enteros en $P_{n,k}$ por inducción en el número de componentes no enteros de $x$ (por supuesto, todos los componentes enteros tienen valores $0$ o $1$ ).

Si todos los $x_i$ son enteros hemos terminado. Ahora supongamos que algún componente de $x$ no es un número entero. Entonces, como la suma de ellos es entera, hay al menos dos componentes no enteros, $x_i$ y $x_j$ . En primer lugar, disminuyamos $x_i$ y aumentar $x_j$ hasta que uno de ellos se convierta en un número entero. Llama al vector resultante $x_l$ . Entonces aumentemos $x_i$ y disminuir $x_j$ hasta que uno de ellos se convierta en un número entero. Llama al vector resultante $x_u$ . Entonces $x$ es una combinación convexa de $x_l$ y $x_u$ (Prueba: Denotando por $d$ el vector con $1$ en $i$ coordenadas y $-1$ en $j$ la coordenada, $x_u=x+t_ud$ y $x_l=x-dt_l$ para algún positivo $t_u, t_l$ así que $x$ está en el segmento entre $x_u$ y $x_l$ como se quiera). Por supuesto, ambos $x_l$ y $x_u$ están en $P_{n,k}$ .

Ahora por hipótesis de inducción, $x_l$ y $x_u$ son ambas combinaciones convexas de puntos enteros en $P_{n,k}$ y, por lo tanto, también lo es $x$ .

Answer 2

Para encontrar sus esquinas, dejemos $\mathbf{x} = (x_i)_{i=1}^n \in P_{n,k}$ . Sea el vector elemental $\mathbf{e}_i \in \mathbb{R}^n$ sea un vector cuyo $i$ -el componente número uno es $1$ y $0$ en otro lugar.

Es fácil ver que si existe $i$ tal que $x_i \in (0,1)$ entonces $\mathbf{x}$ no es una esquina, ya que también tenemos otro índice $i' \ne i$ tal que $x_{i'} \in (0,1)$ . (En caso contrario, si $i$ es el único índice no entero, la suma de los componentes $\sum_i x_i \notin \mathbb{Z}$ , contradiciendo $\sum_i x_i = k \in \mathbb{Z}$ .) Queda por construir el intervalo que contiene $\mathbf{x}$ . Elija un tamaño lo suficientemente pequeño $\epsilon > 0$ tal que $\mathbf{x}$ es el punto medio del intervalo $[\mathbf{x} - \epsilon \mathbf{e}_i + \epsilon \mathbf{e}_{i'}, \mathbf{x} + \epsilon \mathbf{e}_i - \epsilon \mathbf{e}_{i'}] \subseteq P_{n,k}$ . Eso es posible ya que $\mathbf{x}$ tiene un número finito de componentes.

Como resultado, podemos restringir los posibles candidatos a $\{0,1\}^n$ . La restricción de igualdad $\sum_i x_i = k$ nos dice todo, para que la prueba esté terminada.

Nota: Si $x_i = 1$ entonces el $i$ -a componente de $\mathbf{x} + \epsilon \mathbf{e}_i - \epsilon \mathbf{e}_{i'}$ sería $x_i + \epsilon > 1$ , contradiciendo nuestra elección de $\mathbf{x} \in [0,1]^n$ .

Answer 3

De las notas del curso Curso de optimización combinatoria de Alexander Schrijver (= Lex Schrijver) encontramos

Teorema 2.2. Dejemos que $P = \{ x \space | \space Ax \le b \}$ sea un poliedro en $\mathbb{R}^{n}$ y que $z \in P$ . Entonces $z$ es un vértice de $P$ si y sólo si $\text{rank}(A_{z}) = n$ .

Donde también se explica la terminología sobre un vértice y lo que $A_{z}$ significa: $A_z$ es la submatriz de $A$ que consiste en esas filas $a_i$ de $A$ para lo cual $a_i z=b_i$ .

Así que la pregunta da este poliedro

$\begin{equation*} Ax = \begin{bmatrix} 1 & 1 & \cdots & 1 \\ -1 & -1 & \cdots & -1 \\ 1 & & & \\ & 1 & & \\ & & \ddots & \\ & & & 1 \\ -1 & & & \\ & -1 & & \\ & & \ddots & \\ & & & -1 \\ \end{bmatrix} x \le \begin{bmatrix} k \\ -k\\ 1 \\ 1\\ \vdots \\ 1 \\ 0 \\ 0 \\ \vdots \\ 0 \\ \end{bmatrix} = b. \end{equation*}$

No es difícil ver que un vértice $z$ con $k$ y $n - k$ los ceros dan lugar a una submatriz $A_{z}$ que tiene rango $n$ por lo que esos puntos son vértices. Es obvio que $a_{1}z = k = b_{1}$ y $a_{2}z = -k = b_{2}$ porque $z$ tiene $k$ los. Así que se mantienen esas filas. Ahora, un $z_{i}$ es igual a $1$ o $0$ . Así que mira la columna $i$ de $A$ . Si $z_{i} = 1$ se mantiene la fila con $1$ en la diagonal, en caso contrario, si $z_{i} = 0$ se mantiene la fila con el $-1$ en la diagonal porque $-1 \cdot 0 = 0 = b_{q}$ . Así que terminará con una matriz $A_{z}$ con $a_{1}$ y $a_{2}$ en la parte superior y una diagonal con $\pm 1$ abajo. Obviamente $\text{rank}(A_{z}) = n$ , usted tiene $n$ pivotes después de todo. Así que concluimos $z$ es un vértice.

Cualquier otro $z$ en el poliedro debe tener un $z_{i}$ con $0 < z_{i} < 1$ por lo que también implica que hay un $z_{j}$ con $i \ne j$ con $0 < z_{j} < 1$ porque $z_{1} + \dots + z_{n} = k$ después de todo. De nuevo $a_{1}z = k = b_{1}$ y $a_{2}z = -k = b_{2}$ . Sin embargo, en la columna $i$ de $A$ te multiplicarás con $z_{i} \ne 0, 1$ y, por lo tanto, se elimina la fila de la matriz $A$ con $1$ en la diagonal pero también la fila con $-1$ en la diagonal, porque en esas filas debe ser igual a $1$ o $0$ son los valores en $b$ en las posiciones correspondientes. Esto se aplica a la columna $j$ también (nota $j \ne i$ ). Así que desde ambas diagonales (la de $1$ y el de $-1$ ') mantendrá como máximo $n - 2$ filas con un $\pm 1$ . Sin embargo, las dos primeras filas siguen estando ahí, pero sólo pueden proporcionarle como máximo 1 pivote, así que $\text{rank}(A_{z}) \le n - 1$ por lo que esos $z$ no son vértices.

Es importante entender en la columna $i$ de $A$ puedes elegir como máximo una fila de $A$ correspondiente al $b_{q}$ donde $b_{q} = 1$ o $b_{q} = 0$ . Prueba con $n = 4$ y $k = 2$ por ejemplo, si necesita una ayuda extra para entenderlo. Los ejemplos concretos son buenos para eso.