Bukti singkat dan apik dari teorema dualitas yang kuat untuk pemrograman linier

Pertimbangkan program linier

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

Teorema dualitas yang lemah menyatakan bahwa jika $\vec{x}$ dan $\vec{y}$ memenuhi kendala maka $\vec{c}^T\vec{x} \leq \vec{y}^T\vec{b}$ . Ini memiliki bukti pendek dan apik menggunakan aljabar linier: $\vec{c}^T\vec{x} \leq \vec{y}^T A \vec{x} \leq \vec{y}^T\vec{b}$ .

Teorema dualitas yang kuat menyatakan bahwa jika $\vec{x}$ adalah solusi optimal untuk primal maka ada $\vec{y}$ yang merupakan solusi untuk dual dan $\vec{c}^T\vec{x} = \vec{y}^T\vec{b}$ .

Apakah ada bukti yang sama pendek dan apik untuk teorema dualitas yang kuat?

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

Bab 4 dari kursus online MIT web.mit.edu/15.053/www oleh Bradley, Hax, dan Magnanti memberikan bukti yang cukup singkat di sepanjang baris ini. Apakah ini yang Anda cari?

cody

@cody, well, sepertinya pada dasarnya sama dengan yang ada di CLRS. Ini bisa baik-baik saja jika Anda bisa mengekspresikannya dengan cara aljabar linier yang apik (yaitu tanpa jumlah)

Kaveh

Sepertinya apa yang saya inginkan mungkin tidak mungkin. Farkas menggunakan kedekatan ruang yang berarti mungkin tidak ada bukti aljabar linier murni.

Kaveh

Mencoba menemukan sesuatu yang tidak terlalu merepotkan diri sendiri, untuk ditunjukkan kepada murid-murid saya (sehingga mereka tidak harus hanya mengambil dualitas yang kuat pada iman), dan sebagian besar dari apa yang saya temui lebih dalam kategori terlalu rumit. Baru saja menemukan argumen dalam catatan dari kelas Dan Spielman, yang cukup singkat dan tampaknya sederhana. Tidak yakin apakah menyembunyikan beberapa kompleksitas, atau apakah ada sesuatu yang hilang? (Belum memeriksanya dengan cukup teliti untuk diceritakan.) Cs.yale.edu/homes/spielman/BAP/lect12.pdf

Magnus Lie Hetland

Ah, saya kira titik sentral adalah interpretasi geometris dalam kuliah sebelumnya, yang membawa kita kembali ke keluarga Simplex of proofs: cs.yale.edu/homes/spielman/BAP/lect11/lect11.pdf

Magnus Lie Hetland

Jawaban:

Mungkin tidak. Berikut adalah argumen konseptual berdasarkan

Farkas Lemma : Persis salah satu dari alternatif berikut memiliki solusi:

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

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

Sekarang mari menjadi nilai objektif optimal dari primal. Biarkan menjadi arbitrer. Biarkan menjadi dengan tambahan sebagai baris terakhir. Biarkan menjadi dengan tambahan sebagai nilai terakhir. $\delta$ $\epsilon > 0$ $A'$ $A$ $-c^T$ $b'$ $b$ $-\delta - \epsilon$

Sistem tidak memiliki solusi. Oleh Farkas, ada sedemikian rupa sehingga: $A'x'\le b'$ $y' = (y,\alpha)$

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

Perhatikan bahwa jika kita berada dalam alternatif lain dari Farkas. Karena itu . $\epsilon = 0$ $\alpha > 0$

Skala sehingga . layak ganda. Dualitas yang lemah menyiratkan . $y'$ $\alpha = 1$ $y$ $\delta \le y^Tb < \delta + \epsilon$

Louis
sumber

Saya pikir ini adalah bukti dalam catatan kuliah Jeff Erickson . Saya mencari sesuatu yang menghindari hal-hal epsilon (seperti aljabar linier murni).

Kaveh

Apa yang dimiliki JeffE sedikit berbeda, dan lebih menjelaskan geometri. Bagaimanapun, Anda tidak akan menemukan apa yang Anda inginkan, dalam arti bahwa wilayah yang layak adalah polyhedron, bukan ruang linear, jadi pada akhirnya sesuatu akan perlu memanfaatkannya. (Di sini, ia bersembunyi di Farkas. Buku Gärtner dan Matoušek adalah referensi yang sangat bagus untuk barang-barang ini. Saya cukup yakin buktinya ada di sana.)

Louis