Apa kelebihan / kekurangan metode titik interior dibandingkan metode simpleks untuk optimasi linier?

Seperti yang saya pahami, karena solusi untuk program linier selalu terjadi pada titik set yang layak polyhedral (jika ada solusi dan nilai fungsi objektif yang optimal dibatasi dari bawah, dengan asumsi masalah minimisasi), bagaimana bisa pencarian melalui interior wilayah yang layak menjadi lebih baik? Apakah konvergen lebih cepat? Dalam keadaan apa akan menguntungkan untuk menggunakan metode simpleks daripada metode titik interior? Apakah yang satu lebih mudah diimplementasikan dalam kode daripada yang lain?

convex-optimization linear-programming Paul
sumber

Salah satu pernyataan Anda salah. Solusi untuk masalah optimisasi cembung TIDAK selalu terjadi pada batas. Ambil, misalnya, , di mana solusi optimal terjadi pada

, yang ada di bagian dalam wilayah yang layak. Selain itu, di luar konteks pemrograman linier, metode simpleks umumnya mengacu pada metode simpleks Nelder-Mead, yang bahkan mungkin tidak konvergen ke solusi optimal dalam dimensi lebih besar dari 1. Metode ini tidak disarankan untuk pemrograman cembung. Harap edit pertanyaan Anda untuk kejelasan dan kebenaran.

min_{x \in [- 1, 1]} x^{2}

$\min_{x \in [-1, 1]} x^{2}$

x = 0

$x = 0$

Geoff Oxberry

Apakah akan lebih tepat untuk mengatakan "optimasi linier" daripada "optimasi cembung"?

Paul

Ya, maka pernyataan Anda benar. Terima kasih telah mengedit pertanyaan Anda.

Geoff Oxberry

Masalah dengan metode simpleks adalah tidak dapat digeneralisasi untuk masalah nonlinier, yaitu mayoritas masalah dunia nyata.

Jawaban:

Berdasarkan pengalaman pribadi, saya akan mengatakan bahwa metode simpleks sedikit lebih mudah untuk memahami bagaimana menerapkan daripada metode titik interior, berdasarkan pengalaman pribadi dari penerapan kedua primal simpleks dan metode titik interior dasar di MATLAB sebagai bagian dari mengambil kelas pemrograman linier . Hambatan utama dalam primal simplex adalah memastikan bahwa Anda menerapkan Fase I dan Fase II dengan benar, dan juga bahwa Anda menerapkan aturan anticycling dengan benar. Hambatan utama dalam menerapkan metode titik interior untuk pemrograman linier cenderung lebih tentang menerapkan metode iteratif dengan benar, dan meningkatkan parameter penghalang yang sesuai.

Anda dapat menemukan diskusi yang lebih lengkap tentang pro dan kontra dari setiap algoritma dalam buku teks tentang pemrograman linier, seperti Pengantar Pengoptimalan Linier oleh Bertsimas dan Tsitsiklis. ( Penafian: Saya belajar pemrograman linear dari buku teks ini, dan mengambil pemrograman linear di MIT dari istri Bertsimas.) Berikut adalah beberapa dasar-dasarnya:

Pro simpleks:

Mengingat variabel keputusan, biasanya konvergen dalam operasi dengan pivot. $n$ $O(n)$ $O(n)$
Mengambil keuntungan dari geometri masalah: mengunjungi simpul set yang layak dan memeriksa setiap simpul yang dikunjungi untuk optimalitas. (Dalam simpleks primal, pengurangan biaya dapat digunakan untuk pemeriksaan ini.)
Bagus untuk masalah kecil.

Kontra simpleks:

Diberikan variabel keputusan, Anda selalu dapat menemukan contoh masalah di mana algoritma tersebut membutuhkan operasi dan pivot untuk sampai pada solusi. $n$ $O(2^{n})$
Tidak terlalu bagus untuk masalah besar, karena operasi pivot menjadi mahal. Algoritma pemotongan-pesawat atau algoritma pembuatan kolom yang tertunda seperti Dantzig-Wolfe terkadang dapat mengompensasi kekurangan ini.

Kelebihan metode titik interior:

Memiliki kompleksitas waktu asimptotik polinomial , di mana adalah jumlah bit input ke algoritma. $O(n^{3.5}L^2\log{L}\log\log{L})$ $L$
Lebih baik untuk masalah besar, jarang karena aljabar linier yang dibutuhkan untuk algoritma lebih cepat.

Kontra dari metode titik interior:

Secara intuitif tidak memuaskan karena Anda benar, metode ini tidak mengunjungi simpul. Mereka berkeliaran di wilayah interior, mencari solusi ketika berhasil.
Untuk masalah kecil, simpleks mungkin akan lebih cepat. (Anda dapat membuat kasus patologis, seperti kubus Klee-Minty.)

Geoff Oxberry
sumber

Ringkasan yang bagus. Klee-Minty sebenarnya tampaknya dirancang untuk mengacaukan metode LP simpleks ...

@ JM Ya, itulah intinya - ini adalah konstruksi eksplisit untuk menunjukkan bahwa metode simpleks tidak polinomial (walaupun ada varian yang membuat metode titik interior menangis juga).

Christian Clason

Terima kasih atas posting informatif ini. Saya bertanya-tanya berapa banyak variabel yang membuat masalah besar? Puluhan? Ratusan? Ribuan?

KjMag

The Klee-Minty Cube berjalan di <0,1 detik di opensource pemecah GLPK 4,65 simpleks. (Nilai dalam dan menyebabkan banyak pemecah masalah bertingkah pada D = 100, tetapi itu berbeda.) Apakah ada masalah sama sekali di mana metode simpleks berjalan lambat, katakan jarang dengan <1M nonzeros?

5^{D}

$5^D$

A

$A$

x^{*}

$x^*$

denis

Jawabannya mudah. Keduanya (metode titik interior dan simpleks) adalah bidang yang matang dari sudut pandang algoritmik. Keduanya bekerja sangat baik dalam praktik. Reputasi baik IPM (metode titik interior) adalah karena kompleksitas polinomialnya dalam kasus terburuk. Itu tidak berlaku untuk simpleks yang memiliki kompleksitas kombinatorial. Namun demikian, program linear kombinatorial hampir tidak pernah terjadi dalam praktiknya. Untuk masalah skala yang sangat besar, IP tampaknya sedikit lebih cepat, tetapi tidak diperlukan aturannya. Menurut pendapat saya IP bisa mudah dipahami dan diterapkan, tetapi yang pasti, orang lain bisa tidak setuju, dan itu tidak masalah. Sekarang, di LP, jika solusinya unik, sudah pasti ada di titik, (baik IP dan Simplex juga di sini). Solusinya juga bisa di muka polihedron atau di tepi dalam hal ini, vertex yang berdekatan adalah (atau simpul) juga solusi (sekali lagi, baik IP dan simplex melakukannya dengan baik). Jadi mereka hampir sama.

Carlos Ramirez
sumber

Saya menyadari contoh yang saya berikan bukanlah program linier; jika Anda melihat riwayat revisi, versi sebelumnya dari pertanyaan ini diminta untuk membandingkan metode simpleks dan metode titik interior untuk masalah optimisasi cembung. Saya memberikan contoh tandingan untuk membenarkan suntingan yang saya buat, dan untuk mendorong poster asli untuk memperbaiki pertanyaannya, yang dia lakukan.

Geoff Oxberry