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?

— 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

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