Separación de poliedros disjuntos con dualidad LP

Question

Esta es la pregunta 4.35 de Introducción a la optimización lineal de Bertsimas y Tsitsiklis.

El problema

Consideremos dos poliedros no vacíos $P=\{\mathbf{x}\in\mathbb{R}^n\ |\ \mathbf{Ax}\leq\mathbf{b}\}$ y $Q=\{\mathbf{x}\in\mathbb{R}^n\ |\ \mathbf{Dx}\leq\mathbf{d}\}$ .

(a) Diseñe un problema de programación lineal tal que: si $P\cap Q\neq\varnothing$ devuelve un punto en $P\cap Q$ ; si $P\cap Q=\varnothing$ el problema de programación lineal es inviable.

(b) Supongamos que $P\cap Q$ está vacía. Utiliza el dual del problema que has construido en la parte (a) para demostrar que existe un vector $\mathbf{c}$ tal que $\mathbf{c}^\text{T}\mathbf{x}<\mathbf{c}^\text{T}\mathbf{y}$ para todos $\mathbf{x}\in P$ y $\mathbf{y}\in Q$ .

Intento de solución

Creo que tengo una respuesta para la parte (a): $$ \begin{array}{rl} \text{max}\quad&\mathbf{0}^\text{T}\mathbf{x} \\ \text{s.t.}\quad&\mathbf{Ax}\leq\mathbf{b} \\ & \mathbf{Dx}\leq\mathbf{d} \end{array} $$

Esto parece cumplir los requisitos de la parte (a). Estoy atascado en la parte (b). El dual del programa lineal anterior es $$ \begin{array}{rl}\text{min}\quad&\mathbf{p}_1^\text{T}\mathbf{b}+\mathbf{p}_2^\text{T}\mathbf{d}\\\text{s.t.}\quad&\mathbf{p}_1^\text{T}\mathbf{A}+\mathbf{p}_2^\text{T}\mathbf{D}=\mathbf{0}^\text{T}\\ & \mathbf{p}_1,\mathbf{p}_2\geq\mathbf{0} \end{array} $$ Si suponemos que el primal es inviable (es decir $P\cap Q=\varnothing$ ), entonces el dual es inviable o no tiene límites. Dado que $\mathbf{p}_1=\mathbf{0}$ , $\mathbf{p}_2=\mathbf{0}$ es factible para el dual, debe ser ilimitado. Creo que esto podría ser un hecho útil, pero no puedo ver exactamente cómo.

Geométricamente, esta cuestión es muy sencilla. Pero me cuesta encontrar el álgebra que demuestre la existencia de este $\mathbf{c}$ .

Pregunta similar

La pregunta encontrada aquí es similar, pero no me interesa calcular el hiperplano de separación, sólo demostrar su existencia.

Answer 1

(a) El programa lineal

\begin{array}{rl} \max &\mathbf{0}^\text{T}\mathbf{x} \\ \text{s.t.}&\mathbf{Ax}\leq\mathbf{b} \tag{P}\label{P}\\ & \mathbf{Dx}\leq\mathbf{d} \end{array}

sugerido por el OP responde al problema.

(b) Ya que $P \cap Q = \varnothing$ cada uno de estos dos puntos satisface exactamente una de las dos restricciones en \eqref{P} (de la definición de $P$ y $Q$ ).

La deducción de la OP es correcta:

El dual para \eqref{P} es \begin{array}{rl} \min & \mathbf{p}_1^\text{T}\mathbf{b}+\mathbf{p}_2^\text{T}\mathbf{d} \\ \text{s.t.} & \mathbf{p}_1^\text{T}\mathbf{A}+\mathbf{p}_2^\text{T}\mathbf{D}=\mathbf{0}^\text{T} \tag{D} \label{D} \\ & \mathbf{p}_1,\mathbf{p}_2\geq\mathbf{0} \end{array} La inviabilidad de \eqref{P} y la viabilidad de \eqref{D} (con $\mathbf{p}_1 = {\bf 0}, \mathbf{p}_2 = {\bf 0}$ ) implica que \eqref{D} no tiene límites.

De la no limitación de \eqref{D}, deducimos que para cada $z \in \Bbb R$ existe $\mathbf{p}_1,\mathbf{p}_2\geq\mathbf{0}$ tal que $\mathbf{p}_1^\text{T}\mathbf{b}+\mathbf{p}_2^\text{T}\mathbf{d} \le z$ . En particular, fijamos $\epsilon > 0$ y tomar $z = -\epsilon$ para que $$\mathbf{p}_1^\text{T}\mathbf{b}+\mathbf{p}_2^\text{T}\mathbf{d} < 0 \tag{*} \label{*}.$$

Para todos ${\bf x} \in P$ y ${\bf y} \in Q$ tenemos (a partir de la definición de $P$ y $Q$ )

\begin{align} \mathbf{Ax} &\leq \mathbf{b} \tag{1}\label{1} \\ \mathbf{Dy} &\leq \mathbf{d} \tag{2}\label{2} \end{align}

Multiplicar $\mathbf{p}_1^\text{T}$ y $\mathbf{p}_2^\text{T}$ en ambos lados de \eqref{1} y \eqref{2} respectivamente. (Podemos hacerlo ya que $\mathbf{p}_1 \ge {\bf 0}, \mathbf{p}_2 \ge {\bf 0}$ .)

\begin{align} \mathbf{p}_1^\text{T}\mathbf{Ax} &\leq \mathbf{p}_1^\text{T}\mathbf{b} \tag{3}\label{3} \\ \mathbf{p}_2^\text{T}\mathbf{Dy} &\leq \mathbf{p}_2^\text{T}\mathbf{d} \tag{4}\label{4} \end{align}

Sustituya la restricción en \eqref {D} en \eqref {4}.

$$(-\mathbf{p}_1^\text{T}\mathbf{A}){\bf y} \leq \mathbf{p}_2^\text{T}\mathbf{d} \tag{4'}\label{4'}$$

Añadir \eqref {3} y \eqref {4'}.

$$\mathbf{p}_1^\text{T}\mathbf{A} ({\bf x} - {\bf y}) \le \mathbf{p}_1^\text{T}\mathbf{b}+\mathbf{p}_2^\text{T}\mathbf{d} \stackrel{\eqref{*}}< 0 \tag{$ \N - La estrella $} \label{fin}$$

Es evidente a partir de \eqref{fin} que ${\bf c} = (\mathbf{p}_1^\text{T}\mathbf{A})^\text{T} = \mathbf{A}^\text{T} \mathbf{p}_1$ satisface $$\mathbf{c}^\text{T}\mathbf{x}<\mathbf{c}^\text{T}\mathbf{y} \quad \forall \mathbf{x} \in P, \forall \mathbf{y} \in Q.$$