Prova curta e precisa do forte teorema da dualidade para programação linear

Considere os programas lineares

\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}$

O teorema da dualidade fraca afirma que se $\vec{x}$ e $\vec{y}$ satisfazem as restrições, então $\vec{c}^T\vec{x} \leq \vec{y}^T\vec{b}$ . Ele possui uma prova curta e lisa usando álgebra linear: $\vec{c}^T\vec{x} \leq \vec{y}^T A \vec{x} \leq \vec{y}^T\vec{b}$ .

O forte teorema da dualidade afirma que se o $\vec{x}$ é uma solução ideal para o primal, então existe $\vec{y}$ que é uma solução para o dual e $\vec{c}^T\vec{x} = \vec{y}^T\vec{b}$ .

Existe uma prova semelhante e curta para o forte teorema da dualidade?

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

O capítulo 4 do curso on-line do MIT web.mit.edu/15.053/www de Bradley, Hax e Magnanti fornece uma prova razoavelmente curta nesse sentido. É isso que você está procurando?

Cody

@ Cody, bem, parece essencialmente o mesmo que o do CLRS. Pode ser bom se você puder expressá-lo de uma maneira lisa e álgebra linear (ou seja, sem somas).

Kaveh

Parece que o que eu queria provavelmente não é possível. O Farkas usa o fechamento do espaço, o que significa que provavelmente não há prova pura de álgebra linear.

Kaveh

Tentando encontrar algo não muito pesado para mostrar aos meus alunos (para que eles não precisem apenas ter uma forte dualidade de fé), e a maior parte do que eu me deparei é mais na categoria muito complicada. Acabei de encontrar um argumento nas notas de uma classe de Dan Spielman, que é bastante curta e aparentemente simples. Não tem certeza se está escondendo alguma complexidade ou se falta alguma coisa? (Ainda não examinou exaustivamente o suficiente para dizer, ainda.) Cs.yale.edu/homes/spielman/BAP/lect12.pdf

Magnus Lie Hetland

Ah, acho que um ponto central é a interpretação geométrica da palestra anterior, que nos leva de volta à família de provas Simplex: cs.yale.edu/homes/spielman/BAP/lect11/lect11.pdf

Magnus Lie Hetland

Respostas:

Provavelmente não. Aqui está um argumento conceitual baseado em

Lema de Farkas : Exatamente uma das seguintes alternativas tem uma solução:

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

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

Agora seja o valor objetivo ideal do primal. Seja arbitrário. Seja com adicional como a última linha. Vamos para ser com um adicional como o último valor. $\delta$ $\epsilon > 0$ $A'$ $A$ $-c^T$ $b'$ $b$ $-\delta - \epsilon$

O sistema não tem solução. Por Farkas, existe um tal que: $A'x'\le b'$ $y' = (y,\alpha)$

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

Note que se , estamos na outra alternativa de Farkas. Portanto, . $\epsilon = 0$ $\alpha > 0$

Escale para que . é dual viável. A dualidade fraca implica . $y'$ $\alpha = 1$ $y$ $\delta \le y^Tb < \delta + \epsilon$

Louis
fonte

Acho que essa é a prova nas anotações da aula de Jeff Erickson . Estou procurando algo que evite o material epsilon (como álgebra linear pura).

Kaveh #

O que JeffE tem é um pouco diferente e explica mais a geometria. De qualquer forma, você não encontrará o que deseja, no sentido de que a região viável é um poliedro, não um espaço linear; portanto, algo eventualmente precisará fazer uso disso. (Aqui, é esconderijo no Farkas Gärtner e livro de Matousek é realmente uma boa referência para essas coisas eu tenho certeza que esta prova está lá...)

Louis