Demostración del teorema de Helly

Question

El problema es demostrar el teorema de Helly para el caso, cuando los cuerpos convexos son politopos, utilizando la dualidad de programación lineal.

Teorema de Helly

Dejemos que $B_{1},...,B_{m}$ sea una colección de cuerpos convexos en $\mathbb{R}^{d}$ con $m>d$ . Si cada $d+1$ de estos cuerpos convexos tienen un punto en común, entonces todos $m$ de estos cuerpos convexos tienen un punto en común.

Ideas para la solución

Por definición, los politopos son la intersección de los medios espacios, por lo que la intersección de los politopos es la intersección de los medios espacios, por lo que podemos definir las desigualdades $Ax<b$ . Así obtenemos un problema de programación lineal.

Para demostrarlo, podemos ver un problema equivalente, según Teorema de Helly , $Ax<b$ (intersección de medios espacios) no tiene solución, cuando cualquier $n+1$ Las desigualdades seleccionadas no tienen solución.

Debemos plantear el problema de LP dual, que debe ser factible y sin límites. El siguiente paso es demostrar que $n + 1 $ variables duales no nulas suficientes para una solución no limitada.

Preguntas

Desgraciadamente, no consigo averiguar qué representará exactamente el problema dual. ¿Y qué función objetivo se debe utilizar? En contradicción con este problema, otro uso de la dualidad, al demostrar teorema minimax , fue muy claro. Tenemos dos problemas de LP, primal y dual (minimizar la pérdida y maximizar el pago), donde las funciones objetivo son la pérdida y el pago.

---

Elaboremos un poco más

Es un problema de LP primario

$max \space 0$

$Ax<b$

Es Dual

$min \space b^Ty$

$A^Ty=0$

$y \geq 0$

Así que ahora, el problema es demostrar que el problema dual de LP es ilimitado usando $n+1$ variables duales no nulas.

Pero las restricciones en el problema dual es el Sistemas homogéneos . Lo que sabemos sobre el sistema homogéneo,

1) si $u$ y $v$ son dos vectores que representan soluciones de un sistema homogéneo, entonces la suma de vectores $u + v$ es también una solución al sistema.

2) Si $u$ es un vector que representa una solución de un sistema homogéneo, y $r$ es un escalar cualquiera, entonces $ru$ es también una solución al sistema.

3) El conjunto de soluciones de un sistema homogéneo es el mismo que el espacio nulo de la matriz A correspondiente.

Así que puede estar usando $n+1$ solución factible podemos demostrar que hay infinitas soluciones básicas factibles, por lo que el problema puede ser ilimitado. Estoy seguro de que esto no tiene sentido. Pero no tengo una explicación mejor.

La segunda idea, en realidad por el teorema de la dualidad fuerte, si el problema primario es inviable que el problema dual es ilimitado, pero en este caso, ¿cómo puedo aplicar $n+1$ ¿Soluciones no nulas?

Answer 1

Probaremos la afirmación equivalente que menciona el OP: Si $m$ espacios intermedios en $\mathbb{R}^d$ , $m > d$ no tienen un punto en común, entonces existe algún $d+1$ de ellos que tampoco tienen un punto en común.

Si el $m$ semiespacios definidos por $Ax \leq b$ no tienen un punto en común, entonces eso significa que el siguiente programa lineal no tiene solución:

$\begin{align} \max \text{ } &0 \\ \text{s.t. } &Ax \leq b. \end{align}$

Por dualidad fuerte, su problema dual es inviable o ilimitado:

$\begin{align} \min &b^T y \\ \text{s.t. } &A^T y =0, \\ &y \geq 0. \end{align}$

Desde $y =0$ es factible para el dual, sin embargo, el dual debe ser ilimitado.

Con respecto al método simplex, un problema no acotado significa que existe alguna solución básica factible con una variable de entrada pero sin variable de salida. Supongamos, sin pérdida de generalidad, que $y_1, y_2, \ldots, y_d$ son las variables básicas para esta solución básica factible. (Hay $d$ de estos porque el dual tiene $d$ limitaciones). Supongamos, de nuevo sin pérdida de generalidad, que $y_{d+1}$ es la variable entrante para la que no existe una variable saliente. Al aumentar el valor de $y_{d+1}$ suficiente podemos obtener una solución $y'$ tal que

1. $y'$ es factible; es decir, $A^T y' = 0$ y $y' \geq 0$ ;
2. $b^T y' < 0$ ;
3. $y'_{d+2} = y'_{d+3} = \cdots = y'_m = 0$ . (Esto se debe a que estas variables siguen siendo no básicas como $y_{d+1}$ se incrementa).

Ahora, dejemos que $A^T_D$ , $y_D$ y $b_D$ denota la restricción de $A^T$ , $y'$ y $b$ respectivamente, a las variables $y_1, y_2, \ldots, y_{d+1}$ . Debido a la propiedad (3) de $y'$ tenemos $A^T_D y_D = 0$ y $b^T_D y_D < 0$ . Por supuesto, $y_D \geq 0$ también.

Por último, consideremos la intersección de $d+1$ semiespacios definidos por $A_D x \leq b_D$ . Si existe un $x$ en esta intersección, entonces

$\begin{align} & x^T A^T_D \leq b^T_D \\ & \Rightarrow x^T A^T_D y_D \leq b^T_D y_D \\ & \Rightarrow 0 \leq b^T y_D, \end{align}$

que es una contradicción. Por lo tanto, la intersección de $d+1$ semiespacios definidos por $A_D x \leq b_D$ está vacía, por lo que hemos encontrado un conjunto de $d+1$ de la $m$ semiespacios que no tienen un punto en común.