Intuicyjny / nieformalny dowód na LP Duality?

Jaki byłby dobry nieformalny / intuicyjny dowód na „trafienie w sedno” na temat dualności LP? Jak najlepiej wykazać, że zminimalizowana funkcja celu jest rzeczywiście minimalna, z intuicyjnym sposobem rozumienia granicy?

Sposób, w jaki mnie uczono, doprowadził do tego, że DUŻO ludzi, które znam, podziela jedno zrozumienie: jestem pewien, że dla każdego odpowiedniego problemu minimalizacji istnieje równoważny problem maksymalizacji, który można uzyskać poprzez odwrócenie ograniczeń nierówności. Kropka. Ten „wniosek” dualności jest tym, co wydaje się trzymać, ale nie „dlaczego tak jest” (tj. W jaki sposób / dlaczego wiąże się optymalne rozwiązanie).

Czy istnieje sposób na grę z nierównościami, aby po prostu „pokazać” dolną / górną granicę optimum, która może być motywacją do udowodnienia?

Przejrzałem książkę Chvatala, a także kilka innych, ale nie znalazłem nic, co mogłoby być zrozumiane przez absolutne nooby dla LP. Najbliższa mi była książka Vazirani na temat algorytmów, w której mówi on o „pomnożeniu nierówności przez niektóre magiczne liczby, które pokazują granicę” - nie jestem pewien, jak odtworzyć efekt dla dowolnego LP.

linear-programming primal-dual

— Doktorat
źródło

W tej odpowiedzi na matematykę omówię krok po kroku, skąd pochodzi dwoistość - i dlaczego - dla problemu, który ma większość różnych możliwości, które mogą wyniknąć z LP. Może to może pomóc?

— Mike Spivey

Nie jestem pewien, dlaczego uważasz, że argument Vazirani nie działa w przypadku ogólnego LP. Osobiście najbardziej podoba mi się to wyjaśnienie.

— Suresh Venkat

Pytasz o słabą dualność czy silną dualność?

— Tsuyoshi Ito

Możesz uzyskać geometryczną intuicję, wizualizując (powiedzmy w 2d), co to znaczy wziąć liniową kombinację wiązań. Na przykład, wyciągnąć ograniczenia

x \leq 1

$x \le 1$ i

y \leq 1

$y \le 1$ w płaszczyźnie. Kombinacje liniowe tych ograniczeń daje

a x + b y \leq a + b

$ax + by \le a + b$ dla każdego

a, b \geq 0

$a,b \ge 0$ . Narysuj to, aby to zobaczyć. Zasadniczo liniowa kombinacja wiązań daje podpierające półprzestrzenie wielościanów. Zapytaj teraz, dlaczego jedna z tych wspierających półprzestrzeni sama w sobie zawsze wystarcza, aby ograniczyć koszty? Jeśli to widzisz, to silna dualność.

— Neal Young

@MikeSpivey - Chciałbym, żeby twój komentarz był odpowiedzią :)

— PhD

Odpowiedzi:

Na życzenie OP, oto odpowiedź matematyczna, do której odsyłam w powyższym komentarzu.

Może warto omówić, skąd bierze się dualność, na przykładowym problemie. To potrwa chwilę, ale mam nadzieję, że dualność nie będzie wydawać się tak tajemnicza, kiedy skończymy.

Załóżmy, że mamy pierwotny problem w następujący sposób.

P r i m a l = {\begin{matrix} max 5 x_{1} - 6 x_{2} \\ s . t . 2 x_{1} - x_{2} = 1 \\ x_{1} + 3 x_{2} \leq 9 \\ x_{1} \geq 0 \end{matrix}}

$Primal =\begin{Bmatrix} \max \ \ \ \ 5x_1 - 6x_2 \\ \ \ \ s.t. \ \ \ \ 2x_1 -x_2 = 1\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 +3x_2 \leq9\\ \ \ \ \ x_1 \geq 0\\ \end{Bmatrix}$

Załóżmy teraz, że chcemy wykorzystać ograniczenia pierwotne jako sposób na znalezienie górnej granicy optymalnej wartości pierwotnej. Jeśli pomnożymy pierwsze ograniczenie przez

, drugie ograniczenie przez

i dodamy je razem, otrzymamy

dla lewej strony i

po prawej stronie. Ponieważ pierwsze ograniczenie jest równością, a drugie nierównością, oznacza to

9

$9$

1

$1$

9 (2 x_{1} - x_{2}) + 1 (x_{1} + 3 x_{2})

$9(2x_1 - x_2) + 1(x_1 +3 x_2)$

9 (1) + 1 (9)

$9(1) + 1(9)$

Ale ponieważ

, to jest również prawdą, że

, a więc

Zatem ,

jest związany z górnym na wartość optymalną do pierwotnego problemu.

19 x_{1} - 6 x_{2} \leq 18.

$19x_1 - 6x_2 \leq 18.$

x_{1} \geq 0

$x_1 \geq 0$

5 x_{1} \leq 19 x_{1}

$5x_1 \leq 19x_1$

5 x_{1} - 6 x_{2)} \leq 19 x_{1} - 6 x_{2)} \leq 18

$5x_1 - 6x_2 \leq 19x_1 - 6x_2 \leq 18.$

18

$18$

Z pewnością możemy zrobić to lepiej. Zamiast zgadywać i jako mnożniki, pozwólmy im być zmiennymi. Dlatego szukamy mnożników i aby wymusić $9$ $1$ $y_1$ $y_2$

5 x_{1} - 6 x_{2} \leq y_{1} (2 x_{1} - x_{2}) + y_{2} (x_{1} + 3 x_{2}) \leq y_{1} (1) + y_{2} (9) .

$5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9).$

Teraz, aby utrzymać tę parę nierówności, co musi być prawdą o i ? Weźmy dwie nierówności pojedynczo. $y_1$ $y_2$

Pierwszy nierówność : $5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2)$

$x_1$ $x_2$ $x_1$ $5$ $5$ $x_1 \geq 0$ $5$ $x_1$ $2y_1 + y_2 \geq 5$

$x_2$ $x_2$ $-6$ $x_2$ $-6$ $x_2$ $-6$ $x_2$ $x_2$ . $-y_1 + 3y_2 = -6$

Druga nierówność :

y_{1} (2 x_{1} - x_{2}) + y_{2} (x_{1} + 3 x_{2}) \leq y_{1} (1) + y_{2} (9)

$y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9)$

$y_1$ $y_2$ $y_1$ $y_1$ $y_1$ $y_2$ $y_2$ $y_2 \geq 0$

$y_1 + 9y_2$

$y_1$ $y_2$

\begin{aligned} Zminimalizować y_{1} + 9 y_{2)} \\ z zastrzeżeniem 2) y_{1} + y_{2)} & \geq 5 \\ - y_{1} + 3) y_{2)} & = - 6 \\ y_{2)} & \geq 0. \end{aligned}

$\begin{align*} \text{Minimize }\:\:\:\:\: y_1 + 9y_2& \\ \text{subject to }\:\:\:\:\: 2y_1 + y_2& \geq 5 \\ -y_1 + 3y_2& = -6\\ y_2 & \geq 0. \end{align*}$

I to jest podwójne.

Prawdopodobnie warto podsumować implikacje tego argumentu dla wszystkich możliwych form pierwotnych i podwójnych. Poniższa tabela pochodzi z p. 214 Wstępu do badań operacyjnych , 8. edycja, Hillier i Lieberman. Odnoszą się do tego jako do metody SOB, gdzie SOB oznacza Sensible, Odd lub Bizarre, w zależności od prawdopodobieństwa znalezienia tego konkretnego ograniczenia lub ograniczenia zmiennej w problemie maksymalizacji lub minimalizacji.

             Primal Problem                           Dual Problem
             (or Dual Problem)                        (or Primal Problem)

             Maximization                             Minimization

Sensible     <= constraint            paired with     nonnegative variable
Odd          =  constraint            paired with     unconstrained variable
Bizarre      >= constraint            paired with     nonpositive variable

Sensible     nonnegative variable     paired with     >= constraint
Odd          unconstrained variable   paired with     = constraint
Bizarre      nonpositive variable     paired with     <= constraint

— Mike Spivey
źródło

$x$ $x = B$ $x$ $x \leq C$ $C$ $B \leq \min C$ $B$ $B = \min C$ $B$ $B$

$f$ $f$ $S,O$ $f(S) \geq (1-1/e) f(O)$ $f$ $f$ $f(O) = 1$ $f(S)$ $\min f(S) = 1-1/e$ $1-1/e$ $f(S) \geq 1-1/e$

To pozostawia otwarte pytanie, dlaczego tak naprawdę utrzymuje się silna dualność. Istnieją dwa dowody na to, że dotyczy programowania liniowego, jeden dotyczy algorytmu simpleks, drugi lemat Farkasa. Lemat Farkasa jest prawdopodobnie „poprawnym” sposobem na zrozumienie sytuacji, sprowadzając wszystko do intuicyjnego faktu geometrycznego. Przyznaję jednak, że ta intuicja przechodzi mi przez głowę.

W bardziej ogólnych sytuacjach (powiedzmy programowanie półfinałowe), musisz użyć bardziej ogólnych warunków Karush-Kuhn-Tucker (forma mnożników Lagrange'a), aby uzyskać dualność i warunki silnego dwoistości. Jest to traktowane w tekstach o optymalizacji nieliniowej lub wypukłej.

— Yuval Filmus
źródło