Krótki i sprytny dowód silnego twierdzenia o dualności dla programowania liniowego

Rozważ programy liniowe

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

Twierdzenie o słabym dualności mówi, że jeśli i spełniają ograniczenia, to . Ma krótki i szybki dowód za pomocą algebry liniowej: . $\vec{x}$ $\vec{y}$ $\vec{c}^T\vec{x} \leq \vec{y}^T\vec{b}$ $\vec{c}^T\vec{x} \leq \vec{y}^T A \vec{x} \leq \vec{y}^T\vec{b}$

Twierdzenie o silnym dualności mówi, że jeśli jest optymalnym rozwiązaniem dla pierwotności, to istnieje który jest rozwiązaniem dla dualnego i . $\vec{x}$ $\vec{y}$ $\vec{c}^T\vec{x} = \vec{y}^T\vec{b}$

Czy istnieje podobnie krótki i sprytny dowód na mocne twierdzenie o dualności?

algorithms reference-request linear-programming linear-algebra duality Kaveh
źródło

Rozdział 4 kursu internetowego MIT web.mit.edu/15.053/www autorstwa Bradleya, Haxa i Magnanti daje dość krótki dowód na to. Czy tego szukasz?

cody

@cody, cóż, wydaje się zasadniczo taki sam jak ten w CLRS. Może być dobrze, jeśli możesz wyrazić to w zręczny sposób algebry liniowej (tj. Bez sum).

Kaveh,

Wygląda na to, że to, czego chciałem, prawdopodobnie nie jest możliwe. Farkas używa zamkniętej przestrzeni, co oznacza, że prawdopodobnie nie ma czystego dowodu algebry liniowej.

Kaveh

Próbuję znaleźć coś niezbyt uciążliwego, pokazać moim uczniom (aby nie musieli po prostu mocno wierzyć w wiarę), a większość tego, co spotkałem, jest bardziej w zbyt uciążliwej kategorii. Właśnie znalazłem argument w notatkach klasy Dana Spielmana, który jest dość krótki i na pozór prosty. Nie jesteś pewien, czy ukrywa to złożoność, czy też czegoś brakuje? (Jeszcze nie zbadałem go wystarczająco dokładnie, aby powiedzieć.) Cs.yale.edu/homes/spielman/BAP/lect12.pdf

Magnus Lie Hetland

Ach, chyba centralnym punktem jest interpretacja geometryczna z poprzedniego wykładu, która przenosi nas z powrotem do rodziny dowodów Simplex: cs.yale.edu/homes/spielman/BAP/lect11/lect11.pdf

Magnus Lie Hetland

Odpowiedzi:

Prawdopodobnie nie. Oto argument koncepcyjny oparty na

Farkas Lemma : Dokładnie jedna z następujących alternatyw ma rozwiązanie:

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

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

Teraz niech będzie optymalną wartością obiektywną pierwotności. Niech będzie arbitralny. Niech będzie z dodatkowym jako ostatnim wierszem. Niech będzie z dodatkową jako ostatnią wartością. $\delta$ $\epsilon > 0$ $A'$ $A$ $-c^T$ $b'$ $b$ $-\delta - \epsilon$

System nie ma rozwiązania. Według Farkasa istnieje takie, że: $A'x'\le b'$ $y' = (y,\alpha)$

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

Zauważ, że jeśli jesteśmy inną alternatywą dla Farkas. Dlatego . $\epsilon = 0$ $\alpha > 0$

Skaluj tak aby . jest podwójnie wykonalne. Słaba dualność oznacza . $y'$ $\alpha = 1$ $y$ $\delta \le y^Tb < \delta + \epsilon$

Louis
źródło

Myślę, że jest to dowód w notatkach wykładowych Jeffa Ericksona . Szukam czegoś, co pozwala uniknąć elementów epsilon (jak czysta algebra liniowa).

Kaveh

To, co ma JeffE, jest nieco inne i bardziej wyjaśnia geometrię. W każdym razie nie znajdziesz tego, czego chcesz, w tym sensie, że wykonalnym regionem jest wielościan, a nie przestrzeń liniowa, więc coś w końcu będzie musiało z tego skorzystać. (Tutaj ukrywa się w Farkas. Książka Gärtnera i Matouška jest naprawdę dobrym odniesieniem do tych rzeczy. Jestem prawie pewien, że ten dowód jest.)

Louis