PL: Poliedros, Vértices y Conos

¿Qué es un poliedro?

Un poliedro es el conjunto de soluciones factibles que resulta de intersectar un número finito de semiespacios definidos por restricciones lineales. En 2D, cada restricción es una recta que corta el plano; al juntarlas se forma la región factible.

Politopo

Un politopo es un poliedro acotado: toda su región factible cabe dentro de una bola de radio finito. Todo politopo es un poliedro, pero no todo poliedro es un politopo (puede ser no acotado).

Forma estándar y existencia de vértices

Cuando el poliedro se escribe en forma estándar, si es no vacío entonces siempre tiene al menos un vértice. Esto es clave: garantiza que el método Simplex tenga un punto de partida.

Dos definiciones equivalentes de vértice

1. Definición geométrica

Un punto $v\in P$ es vértice (o punto extremo) si no se puede escribir como punto medio de otros dos puntos factibles distintos. Es una "esquina" del poliedro.

2. Definición algebraica

Un punto $v\in P\subseteq {\mathbb{R}}^n$ es vértice si en él se activan (se cumplen con igualdad) al menos $n$ restricciones linealmente independientes. Por eso un poliedro en ${\mathbb{R}}^n$ necesita al menos $n$ restricciones LI para tener vértices.

¿Cuántos vértices puede tener?

Con $m$ restricciones en ${\mathbb{R}}^n$, el número de vértices está acotado por las formas de elegir $n$ restricciones activas de entre $m$:

Ejemplo (Ayudantía 7)

Considera el poliedro $|x_1|+|x_2|+|x_3|\le 1$. Cada valor absoluto se abre en dos casos, generando $2^3=8$ desigualdades lineales:

En ${\mathbb{R}}^3$ un vértice necesita 3 restricciones LI activas. Resolviendo, los vértices son los 6 puntos:

El cono: un poliedro con b = 0

Un cono poliedral es un poliedro donde el lado derecho es cero. Geométricamente representa las direcciones en que el poliedro se puede extender.

Propiedades

• El origen siempre pertenece: $0\in C$, porque $A\cdot 0=0\le 0$.
• Es cerrado bajo escalamiento no negativo: si $x\in C$, entonces $\lambda x\in C$ para todo $\lambda \ge 0$.
• Cono trivial: $C=\{0\}$ (solo el origen). Cono regular: existe algún $x\ne 0$ en $C$.

¿Por qué importa?

El cono de recesión indica si el poliedro es acotado. Si el cono es regular (hay una dirección no nula dentro), el poliedro es no acotado: puedes avanzar infinitamente sin salir de $P$. Si el cono es trivial, $P$ es acotado (un politopo).

Representar cualquier punto factible

Politopo: combinación convexa de vértices

Todo punto de un politopo se puede escribir como una mezcla ponderada de sus vértices, con pesos no negativos que suman 1. Los ${\lambda }_i$ se interpretan como "qué tan cerca" está el punto de cada vértice.

Poliedro general: descomposición de Minkowski-Weyl

Un poliedro (posiblemente no acotado) se descompone en una parte acotada (el politopo de sus vértices) más una parte infinita (su cono de recesión). Todo punto se escribe como $x=x^{\prime }+h$, con $x^{\prime }$ combinación convexa de vértices y $h$ un rayo del cono.

¿Dónde está el óptimo?

Teorema. Si el poliedro $P$ posee vértices, entonces el problema $\min c^{T}x$ sobre $P$ o bien es no acotado, o bien alcanza su valor óptimo en un vértice de $P$.

Consecuencia práctica: para optimizar sobre un politopo basta evaluar la función objetivo en cada vértice y quedarse con el mejor.

Ejemplo (Ayudantía 7)

Sobre el poliedro $|x_1|+|x_2|+|x_3|\le 1$ (vértices $(\pm 1,0,0),(0,\pm 1,0),(0,0,\pm 1)$), maximizamos $f(x)=2x_1-3x_2+x_3$ evaluando en cada vértice:

El máximo se alcanza en $x^{\ast }=(0,-1,0)$ con $z^{\ast }=3$.

Detectar no acotamiento sin resolver todo

Un problema de minimización es no acotado si existe una dirección $y$ en la que puedes moverte infinitamente sin violar restricciones ($Ay=0$) y que además disminuye el objetivo ($c^{T}y<0$).

Regla rápida en forma estándar: si al buscar variable entrante una columna $A_B^{-1}{A}_j$ es completamente $\le 0$, esa variable puede crecer sin límite y el problema es no acotado.