Prueba breve y resbaladiza del fuerte teorema de la dualidad para la programación lineal.

Considere los programas lineales.

\begin{array}{ccc} P r i m a l : & A \vec{x} \leq \vec{b} & max {\vec{c}}^{T} \vec{x} \end{array}

$\begin{array}{|ccc|} \hline Primal: & A\vec{x} \leq \vec{b} \hspace{.5cm} & \max \vec{c}^T\vec{x} \\ \hline \end{array}$

\begin{array}{ccc} D u a l : & \vec{c} \leq {\vec{y}}^{T} A & min {\vec{y}}^{T} \vec{b} \end{array}

$\begin{array}{|ccc|} \hline Dual: & \vec{c} \leq \vec{y}^TA \hspace{.5cm} & \min \vec{y}^T\vec{b} \\ \hline \end{array}$

El teorema de la dualidad débil establece que si $\vec{x}$ y $\vec{y}$ satisfacen las restricciones, entonces $\vec{c}^T\vec{x} \leq \vec{y}^T\vec{b}$ . Tiene una prueba corta y pulida usando álgebra lineal: $\vec{c}^T\vec{x} \leq \vec{y}^T A \vec{x} \leq \vec{y}^T\vec{b}$ .

El fuerte teorema de la dualidad establece que si $\vec{x}$ es una solución óptima para el primario, entonces hay $\vec{y}$ que es una solución para el dual y $\vec{c}^T\vec{x} = \vec{y}^T\vec{b}$ .

¿Existe una prueba igualmente corta y resbaladiza para el fuerte teorema de la dualidad?

algorithms reference-request linear-programming linear-algebra duality Kaveh
fuente

El Capítulo 4 del curso en línea del MIT web.mit.edu/15.053/www de Bradley, Hax y Magnanti ofrece una prueba razonablemente breve en este sentido. ¿Es esto lo que estás buscando?

cody

@cody, bueno, parece esencialmente el mismo que el de CLRS. Puede estar bien si puede expresarlo de una manera hábil algebra lineal (es decir, sin sumas).

Kaveh

Parece que lo que quería probablemente no sea posible. El Farkas utiliza la cercanía del espacio, lo que significa que probablemente no exista una prueba de álgebra lineal pura.

Kaveh

Tratando de encontrar algo que no sea demasiado engorroso para mostrarles a mis alumnos (para que no tengan que tomar una fuerte dualidad en la fe), y la mayoría de lo que he encontrado está más en la categoría de demasiado engorroso. Acabo de encontrar un argumento en las notas de una clase de Dan Spielman, que es bastante breve y aparentemente simple. ¿No está seguro si está ocultando cierta complejidad o si falta algo? (Todavía no lo he examinado a fondo lo suficiente como para contarlo). Cs.yale.edu/homes/spielman/BAP/lect12.pdf

Magnus Lie Hetland

Ah, supongo que un punto central es la interpretación geométrica en la conferencia anterior, que nos lleva de vuelta a la familia de pruebas Simplex: cs.yale.edu/homes/spielman/BAP/lect11/lect11.pdf

Magnus Lie Hetland

Respuestas:

Probablemente no. Aquí hay un argumento conceptual basado en

Farkas Lemma : Exactamente una de las siguientes alternativas tiene una solución:

$Ax \le b$ y $x \ge 0$

$y^TA\ge 0$ e $y^Tb < 0$

Ahora dejemos que sea el valor objetivo óptimo de lo primario. Deje que sea arbitrario. Deje que sea con un adicional como la última fila. Deje que sea con un adicional como último valor. $\delta$ $\epsilon > 0$ $A'$ $A$ $-c^T$ $b'$ $b$ $-\delta - \epsilon$

El sistema no tiene solución. Por Farkas, hay un tal que: $A'x'\le b'$ $y' = (y,\alpha)$

$y^TA\ge \alpha c$ y . $y^Tb < \alpha (\delta + \epsilon)$

Tenga en cuenta que si estamos en la otra alternativa de Farkas. Por lo tanto . $\epsilon = 0$ $\alpha > 0$

Escala para que . es doble factible. La dualidad débil implica . $y'$ $\alpha = 1$ $y$ $\delta \le y^Tb < \delta + \epsilon$

Louis
fuente

Creo que esta es la prueba en las notas de conferencia de Jeff Erickson . Estoy buscando algo que evite las cosas épsilon (como álgebra lineal pura).

Kaveh

Lo que JeffE tiene es un poco diferente, y explica más la geometría. De todos modos, no vas a encontrar lo que buscas, en el sentido de que la región factible es un poliedro, no un espacio lineal, por lo que algo necesitará hacer uso de eso. (Aquí se esconde en Farkas. El libro de Gärtner y Matoušek es una muy buena referencia para estas cosas. Estoy bastante seguro de que esta prueba está ahí).

Louis