La suma de dos poliedros es un poliedro

Question

Estoy revisando para un examen parcial la próxima semana en un curso de optimización. Actualmente, estoy teniendo muchos problemas con un problema de repaso. El problema es el siguiente:

Dejemos que $P$ y $Q$ sean poliedros en $\mathbb{R}^n$ . Sea $P+Q = \{x + y | x \in P\mathrm{\ and\ }y \in Q\}$ .

(a) Demuestre que $P+Q$ es un poliedro

(b) Demuestre que todo punto extremo de $P+Q$ es la suma de un punto extremo de $P$ y un punto extremo de $Q$ .

En primer lugar, sé que esta pregunta se ha formulado aquí antes, pero, debido a la falta de información de la OP, fue bastante sin respuesta.

Mi intento ha sido el siguiente: Mi profesor dice $P$ es un poliedro si $P$ puede escribirse de la forma $P = \{ x \in \mathbb{R}^n | a_ix \geq b_i,\mathrm{\ for\ } i = 1,...,m\}$ de manera equivalente, si $A$ es la matriz con vectores de fila $a_i$ tenemos $P = \{x \in \mathbb{R}^n | Ax \geq b\}$ . Por tanto, un poliedro es la intersección de un número finito de medios espacios. Sin embargo, después de esto, estoy completamente perdido.

Tengo eso $z = x+y$ pero no puede empezar a mostrar cómo o por qué la suma de cualquier $x$ de $P$ y $y$ de $Q$ debe estar en un poliedro. Intenté demostrar que $z$ satisfecho $(a_i+h_i)z \geq b_i + g_i$ , $a_i$ y $h_i$ son las restricciones que $x$ y $y$ satisfacer respectivamente, pero no creo que sea cierto. Cualquier consejo sobre cómo podría abordar este problema / lo que está mal con mi enfoque sería muy apreciado.

Answer 1

a)

Dejemos que $P=\{x|Ax\ge a\}, Q=\{y|By\ge b\}$ .

Ahora defina $M=\{(x,y,z)|Ax\ge a, By \ge b, z=x+y\}$ .

$P+Q$ es la proyección de $M$ en el $z$ coordenadas, por lo tanto un poliedro.

b)

Queremos demostrar que $x$ debe ser un punto extremo en $P$ , si $z=x+y$ es un punto extremo en $P+Q$

Primero vamos a suponer que $x$ no es un punto extremo en $P$ es decir, hay $x_1,x_2\in P\backslash\{x\}$ y $0<\lambda<1$ s.t. $$\lambda x_1 + (1-\lambda) x_2 = x$$

Desde $x_1, x_2\in P$ También $z_1:=x_1+y, z_2:=x_2+y\in P+Q$ (así es como $P+Q$ se define).

Como habrás adivinado, $\lambda z_1 + (1-\lambda) z_2 = z$ (es fácil comprobarlo, basta con sustituir el $z_1, z_2$ con su definición, ampliar y simplificar).

Pero espera, hemos representado $z$ como una combinación lineal de elementos de $P+Q$
_{(para ser formalmente correcto: $0<\lambda<1,\;z_1,z_2\in (P+Q)\backslash{z},\;\lambda z_1+(1-\lambda)z_2 = z$ )}
Por lo tanto, $z$ no puede ser un punto extremo en $P+Q$ .

Así que demostramos que si $x$ no es un punto extremo en $P$ entonces $z=x+y$ no puede ser un punto extremo en $P+Q$ . Aplica la contraposición y ya está: Si $z=x+y$ es un punto extremo en $P+Q$ entonces $x$ es un punto extremo en $P$ .

Tenga en cuenta que $x, P$ y $y, Q$ son intercambiables entre sí.