Mengapa metode titik interior sulit untuk memulainya?

10

Saya sering menemukan pepatah umum bahwa metode titik interior sulit untuk memulai. Apakah ada penjelasan intuitif di balik saran ini? Apakah ada situasi di mana seseorang dapat mengharapkan manfaat dari pemanasan dimulai dengan metode titik interior? Adakah yang bisa merekomendasikan beberapa referensi bermanfaat tentang topik ini?

optimization constrained-optimization Christopher Johnson
sumber

Jawaban:

11

Metode titik interior bekerja dengan mengikuti jalur pusat ke solusi optimal. Ketika Anda mengubah fungsi tujuan, solusi optimal dari versi sebelumnya dari masalah jauh dari jalur pusat untuk masalah baru, sehingga diperlukan beberapa iterasi untuk kembali ke jalur pusat dan selanjutnya harus kembali ke pusat yang cukup baik. larutan. Maka Anda harus bekerja Anda menyusuri jalan menuju solusi optimal baru. Anda mungkin juga memulai metode titik interior dari titik arbitrer.

Sebagai perbandingan, metode simpleks (primal atau dual) bergerak dari vertex ke vertex dari set yang layak. Dalam kasus tipikal, perubahan yang cukup kecil dalam tujuan akan menghasilkan solusi optimal baru yang hanya berjarak beberapa pivot simpleks.

... ditambahkan ke penjelasan intuitif di atas untuk memberikan detail lebih lanjut ...

Dalam praktik komputasi, pengalaman sama sekali belum menunjukkan manfaat substansial apa pun untuk menghangatkan metode titik interior primal-dual awal. Ini bukan fitur kode yang banyak digunakan seperti CPLEX dan Gurobi (perusahaan yang memproduksi paket-paket ini pasti akan menambahkan fitur seperti itu jika layak sementara), dan ada relatif sedikit makalah yang membahas strategi untuk memulai metode titik interior yang hangat. .

Dua referensi yang akan saya rekomendasikan adalah:

EA Yildirim dan S. Wright. Strategi Mulai-Hangat dalam Metode Titik-Interior untuk Pemrograman Linear. SIAM Journal on Optimization 12: 782-810, 2002. Makalah ini memberikan beberapa batasan teoretis yang bagus tentang beberapa strategi awal yang hangat. Lihat http://pages.cs.wisc.edu/~swright/papers/YilW02a.pdf

Sebuah makalah selanjutnya yang ditulis bersama oleh Yildirim memberikan beberapa hasil komputasi, tetapi penulis mengakui bahwa hanya memulai dingin sering lebih cepat dalam tes mereka daripada memulai hangat:

E. John dan EA Yildirim. Implementasi strategi mulai-hangat dalam metode titik-interior untuk pemrograman linier dalam dimensi tetap. Optimalisasi dan Aplikasi Komputasi. 41: 151-183, 2008. Lihat http://link.springer.com/article/10.1007/s10589-007-9096-y

Brian Borchers
sumber
Saya harus mengatakan bahwa saya merasa penjelasan Anda sedikit kurang. Untuk masalah yang sedikit tidak tepat, menemukan titik yang layak sudah merupakan masalah dengan sendirinya dan sebagian besar metode menggunakan metode "Tahap I" untuk menemukan titik layak pertama ini. Masih belum jelas bagi saya mengapa Anda tidak dapat menggunakan titik yang layak untuk setidaknya melewati fase itu, jika tidak benar-benar memastikan keberhasilan metode ini.
olamundo
Sebenarnya, sebagian besar implementasi metode titik interior primal-dual menggunakan titik awal yang tidak layak (sehubungan dengan kendala kesetaraan) dan bekerja secara simultan pada kelayakan dan optimalitas. Tidak ada fase terpisah I.
Brian Borchers