Bukti intuitif / informal untuk LP Duality?

Apa yang akan menjadi bukti informal / intuitif yang baik untuk 'mencapai titik asal' tentang dualitas LP? Bagaimana cara terbaik untuk menunjukkan bahwa fungsi objektif yang diminimalkan memang minimum dengan cara intuitif memahami batasan?

Cara saya diajari Dualitas hanya mengarah pada satu pemahaman yang saya yakini dimiliki oleh BANYAK orang yang saya kenal: Untuk setiap masalah minimisasi yang bersesuaian, ada masalah maksimalisasi setara yang dapat diturunkan dengan membalikkan kendala ketimpangan. Titik. "Kesimpulan" dualitas ini adalah apa yang tampaknya melekat tetapi tidak "mengapa demikian" (yaitu bagaimana / mengapa ada solusi yang optimal).

Apakah ada cara bermain dengan ketidaksetaraan hanya untuk 'menunjukkan' batas bawah / atas pada optimum yang bisa menjadi motivasi untuk pembuktian?

Saya telah membaca buku Chvatal dan juga beberapa buku lainnya, tetapi tidak menemukan apa pun yang dapat dipahami oleh noobs mutlak untuk LP. Yang paling dekat yang saya dapatkan adalah dari buku Vazirani tentang algoritma, di mana ia berbicara tentang 'mengalikan ketidaksetaraan dengan beberapa angka ajaib yang menunjukkan batasan' - Saya tidak yakin bagaimana mereproduksi efek untuk LP yang sewenang-wenang.

linear-programming primal-dual PhD
sumber

Dalam jawaban math.SE ini saya melihat contoh langkah-demi-langkah dari mana dual berasal - dan mengapa - untuk masalah yang memiliki sebagian besar kemungkinan berbeda yang dapat muncul dengan LP. Mungkin itu bisa membantu?

Mike Spivey

Tidak yakin mengapa Anda berpikir argumen Vazirani tidak berfungsi untuk LP umum. Secara pribadi, saya suka penjelasan itu yang terbaik dari semuanya.

Suresh Venkat

Apakah Anda bertanya tentang dualitas yang lemah atau dualitas yang kuat?

Tsuyoshi Ito

Anda bisa mendapatkan intuisi geometris dengan memvisualisasikan (dalam 2d, katakanlah) apa artinya mengambil kombinasi linear dari kendala. Misalnya, gambar kendala dan di pesawat. Kombinasi linear dari batasan ini memberi Anda untuk setiap . Gambarlah ini untuk melihatnya. Umumnya, kombinasi linear dari kendala memberi Anda setengah ruang pendukung dari polyhedra. Sekarang tanyakan, mengapa salah satu dari setengah ruang pendukung ini selalu cukup, dengan sendirinya, untuk memberi batasan pada biaya? Jika Anda melihatnya, itu dualitas yang kuat.

x \leq 1

$x \le 1$

y \leq 1

$y \le 1$

a x + b y \leq a + b

$ax + by \le a + b$

a, b \geq 0

$a,b \ge 0$

Neal Young

@MikeSpivey - Saya harap komentar Anda adalah jawaban :)

PhD

Jawaban:

Sesuai keinginan OP, inilah jawaban math.SE yang saya tautkan dalam komentar saya di atas.

Mungkin ada baiknya untuk membahas dari mana dual berasal dari contoh masalah. Ini akan memakan waktu, tetapi mudah-mudahan dual tidak akan tampak begitu misterius ketika kita selesai.

Misalkan dengan memiliki masalah mendasar sebagai berikut.

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

Sekarang, anggaplah kita ingin menggunakan batasan primal sebagai cara untuk menemukan batas atas pada nilai optimal primal. Jika kita mengalikan kendala pertama dengan , kendala kedua dengan , dan menambahkannya bersama-sama, kita mendapatkan untuk sisi kiri dan untuk sisi kanan. Karena kendala pertama adalah persamaan dan yang kedua adalah ketidaksetaraan, ini menyiratkan Tetapi karena , juga benar bahwa , dan demikian juga Oleh karena itu, adalah batas atas pada nilai optimal dari masalah primal.

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)$

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$

Tentunya kita bisa melakukan lebih baik dari itu. Daripada hanya menebak dan sebagai pengganda, mari kita biarkan mereka menjadi variabel. Karenanya kami sedang mencari pengganda dan untuk memaksa $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).$

Sekarang, agar pasangan ketidaksetaraan ini bisa bertahan, apa yang benar tentang dan ? Mari kita ambil dua ketidaksetaraan satu per satu. $y_1$ $y_2$

Ketidaksetaraan pertama : $5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2)$

Kita harus melacak koefisien variabel dan secara terpisah. Pertama, kita perlu total koefisien di sisi kanan paling tidak . Mendapatkan tepat akan bagus, tetapi karena , apa pun yang lebih besar dari juga akan memuaskan ketidaksetaraan untuk . Secara matematis, ini berarti kita membutuhkan . $x_1$ $x_2$ $x_1$ $5$ $5$ $x_1 \geq 0$ $5$ $x_1$ $2y_1 + y_2 \geq 5$

Di sisi lain, untuk memastikan ketidaksetaraan untuk variabel kita membutuhkan total koefisien di sisi kanan menjadi . Karena bisa positif, kita tidak bisa lebih rendah dari , dan karena bisa negatif, kita tidak bisa lebih tinggi dari (karena nilai negatif untuk akan membalik arah ketidaksetaraan). Jadi untuk ketidaksetaraan pertama yang berfungsi untuk variabel , kita harus memiliki . $x_2$ $x_2$ $-6$ $x_2$ $-6$ $x_2$ $-6$ $x_2$ $x_2$ $-y_1 + 3y_2 = -6$

Ketidaksetaraan kedua :

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)$

Di sini kita harus melacak dan variabel secara terpisah. The variabel berasal dari kendala pertama, yang merupakan kendala kesetaraan. Tidak masalah jika positif atau negatif, batasan kesetaraan tetap berlaku. Dengan demikian, tidak dibatasi masuk. Namun, variabel berasal dari kendala kedua, yang merupakan kurang dari atau sama dengan kendala. Jika kita mengalikan kendala kedua dengan angka negatif yang akan membalik arahnya dan mengubahnya menjadi kendala yang lebih besar atau sama. Untuk tetap dengan tujuan kami melampaui batas tujuan utama, kita tidak bisa membiarkan itu terjadi. Jadi $y_1$ $y_2$ $y_1$ $y_1$ $y_1$ $y_2$ $y_2$ variabel tidak boleh negatif. Jadi kita harus memiliki . $y_2 \geq 0$

Akhirnya, kami ingin membuat sisi kanan ketimpangan kedua sekecil mungkin, karena kami ingin batas atas seketat mungkin pada tujuan utama. Jadi kami ingin meminimalkan . $y_1 + 9y_2$

semua pembatasan ini pada dan bersama-sama kami menemukan bahwa masalah menggunakan kendala primal untuk menemukan batas atas terbaik pada tujuan primal optimal mencakup penyelesaian program linear berikut: $y_1$ $y_2$

\begin{aligned} Minimize y_{1} + 9 y_{2} \\ subject to 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*}$

Dan itu dual.

Mungkin perlu meringkas implikasi argumen ini untuk semua bentuk yang mungkin dari yang primer dan ganda. Tabel berikut ini diambil dari hal. 214 dari Pengantar Riset Operasi , edisi ke-8, oleh Hillier dan Lieberman. Mereka menyebut ini sebagai metode SOB, di mana SOB singkatan Sensible, Odd, atau Aneh, tergantung pada seberapa besar kemungkinan seseorang akan menemukan kendala tertentu atau batasan variabel dalam masalah maksimalisasi atau minimisasi.

             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
sumber

Menguraikan jawaban Mike dan komentar Vazirani, Anda mendapatkan dua dengan mempertimbangkan bentuk umum dari bukti optimalitas untuk solusi untuk masalah asli. Misalkan Anda memiliki masalah maksimalisasi yang diberikan beberapa ketidaksetaraan linear, dan tanpa kehilangan generalitas, misalkan Anda mencoba untuk memaksimalkan variabel . Diberikan solusi di mana , bagaimana kita tahu bahwa itu optimal? Salah satu caranya adalah mencoba untuk terikat pada dengan mengambil kombinasi linear dari ketidaksetaraan linear. Beberapa kombinasi linear memberikan batas-batas bentuk , dan Anda mencoba untuk mendapatkan yang terbaik (minimal) mungkin. Dualitas yang lemah menyatakan bahwa $x$ $x = B$ $x$ $x \leq C$ $C$ $B \leq \min C$ , yang jelas menurut definisi. Kuat negara dualitas bahwa ketika terbatas, maka . Ini berarti bahwa jika maksimum adalah maka ada "alasan" bahwa Anda tidak dapat melampaui , yang berfungsi ganda sebagai bukti optimalitas. $B$ $B = \min C$ $B$ $B$

Sudut pandang ini terkadang sangat membantu. Biarkan menjadi fungsi set ( mengambil set dan menampilkan bilangan real), dan menjadi dua set. Misalkan Anda mencoba menurunkan ketimpangan dari sekelompok ketidaksetaraan mengenai fungsi (itu contoh nyata). Anda menulis program linear di mana nilai-nilai adalah variabel, adalah kendala, dan tujuannya adalah untuk meminimalkan . Solusi untuk program ini adalah (anggaplah adalah yang terbaik), dan solusi untuk dual memberi Anda bukti $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$ .

Ini membuka pertanyaan mengapa dualitas yang kuat benar-benar berlaku. Ada dua bukti fakta ini untuk pemrograman linier, satu melibatkan algoritma simpleks, lemma Farkas lainnya. Lemma Farkas mungkin adalah cara yang "benar" untuk memahami situasi, mereduksi segalanya menjadi fakta geometris yang intuitif. Namun, saya akui bahwa intuisi ini melampaui kepala saya.

Dalam situasi yang lebih umum (katakanlah pemrograman semidefinite), Anda perlu menggunakan kondisi Karush-Kuhn-Tucker yang lebih umum (suatu bentuk pengganda Lagrange) untuk mendapatkan dual dan kondisi untuk dualitas yang kuat. Ini diperlakukan dalam teks pada optimasi non-linear atau cembung.

Yuval Filmus
sumber