¿Cómo comprobar si un poliedro convexo está contenido en otro poliedro convexo?

Question

Supongamos que tenemos dos poliedros convexos

$$P_1=\{x\in \mathbb{R}^n \mid A_1 x \geq b_1 \}$$

$$P_2=\{x\in \mathbb{R}^n \mid A_2 x \geq b_2 \}$$

¿Hay alguna manera de comprobar si $P_1 \subseteq P_2$ ? Esperaba que esto se pudiera hacer resolviendo algún programa lineal. ¿Es esto posible?

Answer 1

Pues bien, esta es una forma de hacerlo. Deja que $A_{i2}$ y $b_{i2}$ denotan el $i$ La fila de $A_2$ y $i$ elemento de $b_2$ respectivamente. Entonces resolvemos $m$ programas lineales: $$\begin{array}{ll} \text{minimize} & A_{i2}^T x - b_{i2} \\ \text{subject to} & A_1 x \geq b_1 \end{array} \qquad i=1,2,\dots, m$$ Si alguno de ellos tiene un objetivo negativo, incluyendo posiblemente $-\infty$ entonces $P_1\not\subseteq P_2$ . No es barato, lo reconozco, pero funciona.

Answer 2

Una forma no tan elegante sería determinar los vértices de $P_1$ y las introducimos en las restricciones de $P_2$ si cada vértice satisface la $P_2$ restricciones, entonces por convexidad, también lo hace todo el poliedro.

Como ha señalado @D.W., este enfoque suele ser muy lento, ya que el número de vértices aumenta rápidamente con el número de aristas. El enfoque de Michael Grant, como se ha indicado anteriormente y se ha aceptado, tiene un tiempo de ejecución más rápido.

Answer 3

Esto equivale a la viabilidad de las siguientes restricciones lineales: $$ \Lambda A_2 = A_1, \Lambda b_2 \ge b_1, $$ donde $\Lambda$ es una matriz con entradas no negativas. La prueba se desprende del dual de programas lineales que mencionó Michael.